Group shreds into FEC sets

Use the explicit set key

Group by (slot, fec_set_index). The FEC-set index is a common-header field and normally equals the first data-shred index in that erasure set. Do not compute a group as index / 32. Current production commonly targets 32 data and 32 coding shreds, but final sets can be shorter and construction can change.

One owner should mutate a set. Hash the key to a worker or protect it with a narrow lock. Do not let multiple threads independently start recovery for the same set.

Accept data before configuration

Data shreds do not carry num_data_shreds or num_coding_shreds. Coding shreds do. A data member can therefore arrive before the set's k and m are known. Store verified data by global data index under the set key, with a strict count and time bound. When the first coding member arrives, validate all retained data against its declared range.

For a data index i, local erasure position is i - fec_set_index. Use checked subtraction. Once k is known, require the local position to be less than k.

For a coding member, require position < m and map it to k + position. Derive the set's first coding index as coding_index - position using checked subtraction. Every coding member in the set must derive the same value.

Enforce one configuration

The first authenticated coding member can propose set configuration. Subsequent members must match k, m, first coding index, version, proof form, Merkle root, chained root when present, and leader signature. Set protocol limits before allocating k + m slots. Use the limits from the pinned Agave release.

This standalone model shows the actual position rules:

use std::collections::BTreeMap;

#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Config { k: u16, m: u16, first_code: u32 }

#[derive(Default)]
struct FecSet {
    start: u32,
    config: Option<Config>,
    shards: BTreeMap<usize, Vec<u8>>,
}

impl FecSet {
    fn insert_data(&mut self, index: u32, bytes: Vec<u8>) -> Result<(), &'static str> {
        let local = index.checked_sub(self.start).ok_or("data index before set")? as usize;
        if self.config.is_some_and(|c| local >= usize::from(c.k)) {
            return Err("data index outside configured set");
        }
        if self.shards.insert(local, bytes).is_some() { return Err("duplicate shard position"); }
        Ok(())
    }

    fn insert_code(&mut self, index: u32, position: u16, k: u16, m: u16,
                   bytes: Vec<u8>) -> Result<(), &'static str> {
        if k == 0 || m == 0 { return Err("zero erasure count"); }
        if position >= m { return Err("coding position outside set"); }
        let first_code = index.checked_sub(u32::from(position)).ok_or("bad coding index")?;
        let config = Config { k, m, first_code };
        if self.config.is_some_and(|old| old == config) == false && self.config.is_some() {
            return Err("conflicting erasure config");
        }
        if self.config.is_none() && self.shards.keys().any(|&p| p >= usize::from(k)) {
            return Err("invalid retained data position");
        }
        self.config = Some(config);
        let local = usize::from(k) + usize::from(position);
        if self.shards.insert(local, bytes).is_some() { return Err("duplicate shard position"); }
        Ok(())
    }

    fn recoverable(&self) -> bool {
        self.config.is_some_and(|c| self.shards.len() >= usize::from(c.k))
    }
}

fn main() {
    let mut set = FecSet { start: 64, ..FecSet::default() };
    set.insert_data(64, Vec::from([1])).unwrap();
    set.insert_code(100, 4, 32, 32, Vec::from([2])).unwrap();
    if set.recoverable() { std::process::exit(1); }
}

The retained-data validation expression in a production implementation should iterate stored data identities, not infer type from a shared shard map. Keep data and coding records tagged until local positions have been validated. The sample focuses on checked index arithmetic and configuration equality.

Count unique authenticated shards

Recovery becomes possible when at least k unique compatible erasure positions are present. Duplicate packets do not add capacity. Conflicting content at one position does not add capacity either and should quarantine the conflict.

If all local data positions 0..k are present, emit the set without recovery. If at least k total positions are present but a data position is absent, start recovery once. If fewer than k remain at expiry, record an unrecoverable set.

Do not require all k + m members. Coding shreds exist so completion can occur before all packets arrive. Late members after emission are duplicates or diagnostic evidence and should not reopen a completed set.

Link adjacent sets carefully

Chained Merkle roots bind an FEC set to a preceding root. Validate the chain when the preceding set is known. UDP reordering means the later set may arrive first, so keep a bounded pending chain check. A chain failure is different from insufficient Reed-Solomon shards.

Data reassembly crosses FEC-set boundaries. Completion is defined by consecutive data indices and DATA_COMPLETE_SHRED, not by finishing one FEC set. Send recovered or complete data members into a per-slot ordering stage.

Evict bounded state

Expire by monotonic age and slot horizon. Also enforce maximum active sets and total retained bytes. Prefer removing the oldest whole incomplete set. Export accepted unique members, data-complete bypass, recovery-ready sets, conflicts, duplicate positions, expired sets, and bytes evicted.

Test data-first arrival, code-first arrival, reverse order, duplicate positions, conflicting k or m, coding position equal to m, underflowing first coding index, short final sets, and more than one active set for one slot.

Store the first and most recent arrival time on every set so expiry and recovery latency remain measurable.