Module reed_solomon

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.

Example

use commonware_coding::reed_solomon::{encode, decode};
use commonware_cryptography::Sha256;

// Generate data to encode
let data = b"Hello, world! This is a test of Reed-Solomon encoding.";

// Configure the encoder to generate 7 total chunks, with a minimum of 4 required for decoding
let total = 7u16;
let min = 4u16;

// Encode the data
let (root, chunks) = encode::<Sha256>(total, min, data.to_vec()).unwrap();

// Pick a few chunks to recover from (a mix of original and recovery shards)
let some_chunks = vec![
    chunks[0].clone(), // original
    chunks[2].clone(), // original
    chunks[5].clone(), // recovery
    chunks[6].clone(), // recovery
];

// Decode the data from the subset of chunks
let decoded_data = decode::<Sha256>(total, min, &root, some_chunks).unwrap();

// Verify that the decoded data matches the original data
assert_eq!(decoded_data, data);

Structs

Chunk

Data that has been encoded using a Reed-Solomon coder and inserted into a bmt.

Enums

Error

Errors that can occur when interacting with the Reed-Solomon coder.

Functions

decode

Decode data from a set of Chunks.

encode

Encode data using a Reed-Solomon coder and insert it into a bmt.