Constellation Erasure

A Rust implementation of Constellation-inspired Reed-Solomon erasure coding with randomized fuzzing, boundary recovery proofs, and a parameterized encoder foundation.

---

Overview

This project explores the Reed-Solomon Forward Error Correction (FEC) pipeline used in Solana's broadcast stage and extends it toward the Constellation paper's PSlice/PShred architecture.

Current focus:

Payload
    ↓
Data Shards
    ↓
Parity Shards
    ↓
Reed-Solomon Encoding
    ↓
Random Packet Loss
    ↓
Reconstruction
    ↓
Original Data Recovery

---

Motivation

Solana's broadcast stage converts entries into shreds and groups them into FEC sets. Reed-Solomon coding allows the network to tolerate packet loss without retransmission.

This project aims to:

• Understand Agave's shredder.rs
• Explore Reed-Solomon FEC
• Verify correctness through round-trip testing
• Build a Constellation-inspired encoder
• Eventually implement PSlices, PShreds, Merkle proofs, and benchmarks

---

Current Features

Reed-Solomon Encoder

Supports configurable:

data_shards
parity_shards

Example:

EncoderConfig {
    data_shards: 64,
    parity_shards: 192,
}

Result:

256 total shards
64 data shards
192 coding shards

---

Random Payload Generation

Each data shard contains random bytes:

rng.fill(&mut shard[..]);

This exercises actual GF(2⁸) arithmetic instead of simple repetitive data.

---

Encoding

Creates:

64 Data Shards
+
192 Parity Shards
↓
256 Total Shards

using:

rs.encode(&mut shards)

---

Reconstruction

Uses:

rs.reconstruct_data(&mut shards)

to recover missing data shards.

---

Correctness Testing

Positive Boundary Test

Lose exactly parity shards:

64 data
192 parity

Lose 192 shards
↓
64 remain
↓
Recovery succeeds

Verifies:

recover_after_192_losses()

---

Negative Boundary Test

Lose one shard beyond tolerance:

Lose 193 shards
↓
63 remain
↓
Recovery fails

Verifies:

fail_after_193_losses()

---

Random Loss Fuzzing

Loss positions are randomized:

indices.shuffle(&mut rand::rng());

This simulates arbitrary packet loss patterns.

Each test iteration:

Encode
↓
Lose random shards
↓
Recover
↓
Verify original data

Runs multiple iterations to ensure correctness.

---

Round-Trip Verification

Correctness property:

Random Payload
↓
Encode
↓
Random Loss
↓
Decode
↓
Recovered Data == Original Data

This follows the assignment recommendation:

Running the encoder output back through the decoder and verifying the original data is recovered is the only meaningful test of RS correctness.

---

Project Structure

src/
│
├── encoder.rs
│     EncoderConfig
│     create_encoder()
│     create_encoded_shards()
│
├── tests.rs
│     Positive boundary tests
│     Negative boundary tests
│     Randomized loss testing
│
└── main.rs

---

Current Progress

Agave Understanding

• Broadcast stage
• Data shreds
• Coding shreds
• FEC sets
• ReedSolomonCache
• shredder.rs

---

Reed-Solomon Correctness

• Encoder
• Reconstruction
• Boundary proofs
• Random loss fuzzing
• Random payload generation
• Parameterized encoder

---

Progress Map

Agave understanding
[X] RS correctness
[X] Boundary proofs
[X] Random loss fuzzing
[X] Random payloads
[X] Parameterized encoder
[ ] PSlices
[ ] PShreds
[ ] FECSet abstraction
[ ] Merkle layer
[ ] Criterion benchmarks
[ ] tc netem simulation

---

Roadmap

PSlices

Transaction List T
        ↓
     PSlices

PShreds

PSlices
    ↓
PShreds

FEC Sets

Data PShreds
+
Coding PShreds
↓
FEC Set

Merkle Proofs

Payload
↓
Merkle Tree
↓
Merkle Root
↓
PShreds + Proofs

Benchmarks

Inspired by Agave benchmark structure.

Network Loss Simulation

Using:

tc netem

to simulate attester loss scenarios.

---

References

• Solana Agave shredder.rs
• Reed-Solomon Erasure Crate
• Constellation Whitepaper
• Solana Broadcast Stage
• Turbine Block Propagation