Struct ReedSolomon 

pub struct ReedSolomon<H> { /* private fields */ }

A SIMD-optimized Reed-Solomon coder that emits chunks that can be proven against a bmt.

Behavior

The encoder takes input data, splits it into k data shards, and generates m recovery shards using Reed-Solomon encoding. All n = k + m shards are then used to build a bmt, producing a single root hash. Each shard is packaged as a chunk containing the shard data, its index, and a Merkle multi-proof against the bmt root.

Encoding

              +--------------------------------------+
              |         Original Data (Bytes)        |
              +--------------------------------------+
                                 |
                                 v
              +--------------------------------------+
              | [Length Prefix | Original Data...]   |
              +--------------------------------------+
                                 |
                                 v
             +----------+ +----------+    +-----------+
             |  Shard 0 | |  Shard 1 | .. | Shard k-1 |  (Data Shards)
             +----------+ +----------+    +-----------+
                    |            |             |
                    |            |             |
                    +------------+-------------+
                                 |
                                 v
                       +------------------+
                       | Reed-Solomon     |
                       | Encoder (k, m)   |
                       +------------------+
                                 |
                                 v
             +----------+ +----------+    +-----------+
             |  Shard k | | Shard k+1| .. | Shard n-1 |  (Recovery Shards)
             +----------+ +----------+    +-----------+

Merkle Tree Construction

All n shards (data and recovery) are hashed and used as leaves to build a bmt.

Shards:    [Shard 0, Shard 1, ..., Shard n-1]
            |        |              |
            v        v              v
Hashes:    [H(S_0), H(S_1), ..., H(S_n-1)]
            \       / \       /
             \     /   \     /
              +---+     +---+
                |         |
                \         /
                 \       /
                  +-----+
                     |
                     v
               +----------+
               |   Root   |
               +----------+

The final output is the bmt root and a set of n chunks.

(Root, [Chunk 0, Chunk 1, ..., Chunk n-1])

Each chunk contains:

• shard: The shard data (original or recovery).
• index: The shard’s original index (0 to n-1).
• proof: A Merkle multi-proof of the shard’s inclusion in the bmt.

Decoding and Verification

The decoder requires any k chunks to reconstruct the original data.

1. Each chunk’s Merkle multi-proof is verified against the bmt root.
2. Exactly k shards are fed to the Reed-Solomon decoder (any surplus chunks are redundant), which reconstructs the full codeword: the missing data shards and the missing recovery shards both come out of the same decode. When all k data shards are already present there is nothing to decode, so the recovery shards are re-encoded instead.
3. To ensure consistency, a new bmt root is generated over the full reconstructed codeword. This new root MUST match the original bmt root. This prevents attacks where an adversary provides a valid set of chunks that decode to different data, and binds any surplus chunks (which are rebuilt from the reconstruction, not trusted).
4. If the roots match, the original data is extracted from the reconstructed data shards.

Trait Implementations

impl<H: Clone> Clone for ReedSolomon<H>

fn clone(&self) -> ReedSolomon<H>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<H: Copy> Copy for ReedSolomon<H>

impl<H> Debug for ReedSolomon<H>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<H: Hasher> Scheme for ReedSolomon<H>

type Commitment = <H as Hasher>::Digest

A commitment attesting to the shards of data.

type Shard = Chunk<<H as Hasher>::Digest>

A shard of data, to be received by a participant.

type CheckedShard = CheckedChunk<<H as Hasher>::Digest>

A shard that has been checked for inclusion in the commitment.

type Error = Error

The type of errors that can occur during encoding, checking, and decoding.

fn encode( config: &Config, data: impl Buf, strategy: &impl Strategy, ) -> Result<(Self::Commitment, Vec<Self::Shard>), Self::Error>

Encode a piece of data, returning a commitment, along with shards, and proofs.

fn check( config: &Config, commitment: &Self::Commitment, index: u16, shard: &Self::Shard, ) -> Result<Self::CheckedShard, Self::Error>

Check the integrity of a shard, producing a checked shard.

fn decode<'a>( config: &Config, commitment: &Self::Commitment, shards: impl Iterator<Item = &'a Self::CheckedShard>, strategy: &impl Strategy, ) -> Result<Vec<u8>, Self::Error>

Decode the data from shards received from other participants.