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 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 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 proof is verified against the bmt root.
2. The shards from the valid chunks are used to reconstruct the original k data shards.
3. To ensure consistency, the recovered data shards are re-encoded, and a new bmt root is generated. 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.
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> 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>

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

type ReShard = Chunk<H>

A shard shared with other participants, to aid them in reconstruction.

type CheckedShard = Chunk<H>

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

type CheckingData = ()

Data which can assist in checking shards.

type Error = Error

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

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

fn reshard( _config: &Config, commitment: &Self::Commitment, index: u16, shard: Self::Shard, ) -> Result<(Self::CheckingData, Self::CheckedShard, Self::ReShard), Self::Error>

Take your own shard, check it, and produce a Scheme::ReShard to forward to others.

fn check( _config: &Config, commitment: &Self::Commitment, _checking_data: &Self::CheckingData, index: u16, reshard: Self::ReShard, ) -> Result<Self::CheckedShard, Self::Error>

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

fn decode( config: &Config, commitment: &Self::Commitment, _checking_data: Self::CheckingData, shards: &[Self::CheckedShard], ) -> Result<Vec<u8>, Self::Error>

Decode the data from shards received from other participants.

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