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.

Decoding is all-or-nothing per commitment. A successful decode proves that the committed codeword is the canonical encoding of the returned data under this Config, so every set of at least k shards checked against that commitment decodes to the same data. A commitment that is not the canonical encoding of any payload fails for every such set.

Supported Configurations

With k = minimum_shards and m = extra_shards, the total k + m must fit in a u16, and larger totals return Error::TooManyTotalShards. The coder works over GF(2^16) and also requires min(k, m).next_power_of_two() + max(k, m) to be at most 65536. Totals that fit but fail this condition return Error::ReedSolomon carrying UnsupportedShardCount.

The canonical shard width is the payload length plus its four-byte prefix, divided by k and rounded up to an even number of bytes. Encoding returns Error::InvalidDataLength when the payload length or that width exceeds u32::MAX (with k of one, the five largest payload lengths) or when k + m shards of that width exceed MAX_ALLOCATION_BYTES.

Resource Usage

Encoding and decoding hold all k + m shards of the codeword in memory, along with the Merkle tree over those shards and a bounded per-thread coding workspace. At the canonical width, the codeword is about (k + m) / k times the payload. Encoding also returns a Merkle proof for every shard.

Decoding reconstructs the m shards beyond the k it decodes from and rebuilds the commitment over all of them, so even the minimum k shards cost the full codeword. With k of one and m of 65,534, decoding a single shard reconstructs and hashes 65,534 shards of its width.

Callers that accept a Config or shards from an untrusted source must bound the shard counts and the maximum payload length before encoding or decoding. Reading a Scheme::Shard takes the same maximum and rejects any shard wider than the canonical width of a maximum-length payload.

Trait Implementations

impl<H> Clone for ReedSolomon<H>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<H> 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>

fn max_shard_size(config: &Config, data: usize) -> usize

Returns an upper bound on the encoded size of any chunk Scheme::encode produces under config from at most data bytes.

Panics

Panics if config cannot encode data bytes: its total exceeds u16::MAX shards, the backend does not support its shard counts, data or the shard width exceeds u32::MAX, or the codeword exceeds MAX_ALLOCATION_BYTES.

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>

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, strategy: &impl Strategy, ) -> Result<Self::CheckedShard, Self::Error>

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

fn check_many( config: &Config, commitment: &Self::Commitment, shards: &[(u16, &Self::Shard)], strategy: &impl Strategy, ) -> Vec<Result<Self::CheckedShard, Self::Error>>

Check the integrity of multiple shards.

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.