constellation-encoder

A Reed-Solomon erasure encoder re-parameterised from Agave's shred sizing to Constellation's, built on the same reed-solomon-erasure crate Agave uses (reed_solomon_erasure::galois_8::ReedSolomon).

Background (from the Agave source)

• ledger/src/shred.rs: a FEC set is 32 data + 32 coding shreds (DATA_SHREDS_PER_FEC_BLOCK == CODING_SHREDS_PER_FEC_BLOCK == 32). That is 1x redundancy, so any 32 of the 64 shreds rebuild the set.
• ledger/src/shredder.rs: ReedSolomonCache keeps one galois_8::ReedSolomon per (data, parity) pair and reuses it, because constructing a ReedSolomon builds Galois-field tables and is expensive.

Constellation re-parameterises this. With q attesters a pslice is erasure coded into q pshreds at 4x redundancy, so q/4 pshreds are enough to rebuild the pslice (whitepaper: "shredded across all q attesters with 4x redundancy, i.e., q/4 of the pshreds are sufficient"). For q = 256 that is a (256, 64) code: 64 data shards, 192 parity.

	data	parity	total	redundancy	need to recover
Agave FEC set	32	32	64	1x	any 32
Constellation (q=256)	64	192	256	4x	any 64

Layout

• src/lib.rs: ErasureParams, a small ReedSolomonCache, and Encoder with encode (pslice into pshreds) and decode (pshreds back to pslice). Also the wire framing used by the netem harness.
• src/main.rs: in-process round trip, drops the maximum recoverable number of pshreds and reconstructs.
• src/bin/send.rs, src/bin/recv.rs: UDP sender and receiver for the tc netem test.
• tests/roundtrip.rs: round-trip correctness, including the failure boundary.
• benches/erasure.rs: criterion benchmark extending PR #5695's sweep.

Run

cargo run --release                 # in-process round trip demo
cargo test --release                # correctness (use --release, debug math is slow)
cargo bench                         # encode and recover timings

tc netem test (Linux)

This applies real packet loss on an interface with tc netem, instead of dropping shreds in-process. It needs Linux with NET_ADMIN, so it was run in a Docker container on the container's loopback. The sender paces the burst (100us between datagrams) so the receiver's socket buffer does not overflow and add loss of its own at 0%.

Reproduce from the project directory:

docker run --rm --cap-add=NET_ADMIN \
  -v "$PWD":/work:ro -w /work -e CARGO_TARGET_DIR=/tmp/t rust:1-slim-bookworm bash -c '
    apt-get update -qq && apt-get install -y -qq build-essential iproute2
    cargo build --release
    B=/tmp/t/release
    for L in 0 50 70 75 80 85; do
      tc qdisc add dev lo root netem loss ${L}%
      "$B/recv" 127.0.0.1:9000 & sleep 0.4
      "$B/send" 127.0.0.1:9000
      wait
      tc qdisc del dev lo root
    done
  '

Constellation needs any 64 of 256 pshreds (25%), so it reconstructs while at least 64 survive and fails once fewer do. Measured:

netem loss	pshreds received	reconstruct
0%	256 / 256	OK
50%	128 / 256	OK
70%	73 / 256	OK
75%	62 / 256	failed
80%	46 / 256	failed
85%	34 / 256	failed

The crossover lands on the q/4 = 64 threshold: 70% loss leaves 73 survivors and recovers, 75% leaves 62 and fails. So the 4x redundancy tolerates close to 75% attester loss, which is what the paper's "q/4 of the pshreds are sufficient" predicts.

Benchmark notes

benches/erasure.rs follows PR #5695's bench_recover_shreds structure (a sweep over how many shreds are lost, reusing a cache) and adds the (data, parity) ratio as a new axis so 32:32 and 64:192 can be compared directly. It measures the raw galois_8 encode and reconstruct, which is narrower than the PR's shred::recover: there is no Merkle proof or signing here, only the field math.