Recover missing shreds with Reed-Solomon

Know the threshold

An FEC set has k data shards and m coding shards. Reed-Solomon reconstruction succeeds when any k valid shard positions are available, assuming their byte slices are equal length and belong to one encoding. It can tolerate at most m missing positions out of k + m.

Do not infer k and m from a typical 32 by 32 set. Read them from a sanitized coding header. Require coding members to agree. Count unique local positions, not UDP packets.

Skip recovery when every data position is present. The purpose is to rebuild missing data, not to wait for or regenerate all parity.

Extract the correct erasure slices

Solana does not apply Reed-Solomon to the complete UDP datagram byte-for-byte. Data and coding shreds have different header lengths, and coding headers are outside the encoded slice. The variant implementation selects equal-length erasure regions. For data, that region includes enough header and payload bytes to reconstruct the missing data shred. For coding, it selects the parity region.

Those range calculations are variant-dependent and internal to current Agave shred code. Their standalone byte ranges are not currently specified by the product wire contract. Use a thin adapter copied from or exposed by the exact pinned Agave release. Do not invent a universal start or end offset.

The mathematical core with reed-solomon-erasure = "6" is:

use reed_solomon_erasure::galois_8::ReedSolomon;

fn reconstruct(
    k: usize,
    m: usize,
    mut shards: Vec<Option<Vec<u8>>>,
) -> Result<Vec<Option<Vec<u8>>>, String> {
    if (shards.len() == k + m) == false { return Err("wrong shard vector length".into()); }
    let sizes: Vec<usize> = shards.iter().flatten().map(Vec::len).collect();
    let Some(&size) = sizes.first() else { return Err("no shards present".into()); };
    if sizes.iter().any(|&n| (n == size) == false) { return Err("shard lengths differ".into()); }
    if shards.iter().filter(|s| s.is_some()).count() < k {
        return Err("not enough unique shards".into());
    }
    let rs = ReedSolomon::new(k, m).map_err(|e| e.to_string())?;
    rs.reconstruct(&mut shards).map_err(|e| e.to_string())?;
    Ok(shards)
}

fn main() {
    let rs = ReedSolomon::new(2, 1).unwrap();
    let mut full = Vec::from([Vec::from([1, 2]), Vec::from([3, 4]), Vec::from([0, 0])]);
    rs.encode(&mut full).unwrap();
    let input = Vec::from([Some(full[0].clone()), None, Some(full[2].clone())]);
    let out = reconstruct(2, 1, input).unwrap();
    if (out[1].as_deref() == Some(full[1].as_slice())) == false { std::process::exit(1); }
}

This code demonstrates the actual library contract. In the receiver, shards[0..k] are data erasure slices and shards[k..k+m] are coding erasure slices. Missing positions are None.

Rebuild typed shreds

Reconstruction produces erasure bytes, not a fully trusted Shred. For each missing data position, create the variant-correct stub or packet envelope used by the pinned Agave implementation, copy reconstructed bytes into its erasure region, deserialize its common and data headers, and sanitize it. Require reconstructed slot, data index, version, and FEC-set index to equal the expected values.

Rebuild Merkle leaves for all k + m positions and compute the tree. The root must equal the root authenticated by the leader signature on received members. Generate the missing proof if later code expects a complete typed shred. A root mismatch invalidates the set.

Current Agave's recovery implementation performs these steps together: it sorts by erasure position, makes stubs, reconstructs equal slices through a cached Reed-Solomon instance, deserializes recovered data headers, sanitizes recovered members, rebuilds the Merkle tree, compares the root, and installs proofs. Prefer that implementation or a reviewed extraction of it.

Avoid premature recovery

At the instant the kth unique member arrives, recovery is possible. Running immediately minimizes latency but may spend CPU reconstructing a data shard that arrives microseconds later. A tiny grace interval can reduce recovery work but adds delay to every lossy set.

Choose from the consumer objective. A low-latency system usually starts as soon as recoverable. Cache or pool Reed-Solomon matrices by (k, m). Do not allocate a new codec for every set.

Only one worker should recover a key. Mark the set recovering before starting CPU work. Late members can be recorded but must not start a second reconstruction.

Handle failure precisely

Distinguish too few shards, different lengths, invalid position, conflicting configuration, reconstruction error, recovered-header error, and Merkle-root mismatch. The first can result from packet loss. The others indicate malformed or mixed state, a parser mismatch, or corrupted input.

Expire incomplete sets after a measured deadline. Record present data and coding counts, missing data positions, age, and receiver loss deltas. Do not keep waiting without a bound because UDP provides no retransmission from this service.

Test every missing-position pattern up to m on fixed valid fixtures. Test more than m losses, duplicate positions, one corrupted parity byte, mixed roots, wrong proof size, short final sets, and data arriving while recovery runs.

Keep received and reconstructed status per position until the completed data members enter ordering. This makes recovery metrics exact and prevents a late network copy from being counted as a second recovered result. Release parity buffers immediately after the set is authenticated and emitted, unless a bounded diagnostic policy retains their digests.