rsmt2d: 2D Reed-Solomon Merkle Tree

rsmt2d is a Go implementation of a two-dimensional Reed-Solomon Merkle tree data availability scheme. It allows for computing parity shares for a data square, extracting row and column roots for verification, and repairing missing data shares using those roots.

To use the library, you typically follow this lifecycle:

1. Initialize a codec using rsmt2d.NewLeoRSCodec().
2. Compute an Extended Data Square using rsmt2d.ComputeExtendedDataSquare from a 2D slice of bytes.
3. Extract RowRoots() and ColRoots() for use in verification or repair.
4. If data is lost, use rsmt2d.ImportExtendedDataSquare to re-import the (potentially incomplete) flattened data.
5. Call Repair(rowRoots, colRoots) to reconstruct the missing shares.

package main

import (
    "bytes"

    "github.com/celestiaorg/rsmt2d"
)

func main() {
    // shareSize is the size of each share (in bytes).
    shareSize := 512
    // Init new codec
    codec := rsmt2d.NewLeoRSCodec()

    ones := bytes.Repeat([]byte{1}, shareSize)
    twos := bytes.Repeat([]byte{2}, shareSize)
    threes := bytes.Repeat([]byte{3}, shareSize)
    fours := bytes.Repeat([]byte{4}, shareSize)

    // Compute parity shares
    eds, err := rsmt2d.ComputeExtendedDataSquare(
        [][]byte{
            ones, twos,
            threes, fours,
        },
        codec,
        rsmt2d.NewDefaultTree,
    )
    if err != nil {
        // ComputeExtendedDataSquare failed
    }

    rowRoots, err := eds.RowRoots()
    if err != nil {
    // RowRoots failed
    }
    colRoots, err := eds.ColRoots()
    if err != nil {
    // ColRoots failed
    }

    flattened := eds.Flattened()

    // Delete some shares, just enough so that repairing is possible.
    flattened[0], flattened[2], flattened[3] = nil, nil, nil
    flattened[4], flattened[5], flattened[6], flattened[7] = nil, nil, nil, nil
    flattened[8], flattened[9], flattened[10] = nil, nil, nil
    flattened[12], flattened[13] = nil, nil

    // Re-import the data square.
    eds, err = rsmt2d.ImportExtendedDataSquare(flattened, codec, rsmt2d.NewDefaultTree)
    if err != nil {
        // ImportExtendedDataSquare failed
    }

    // Repair square.
    err = eds.Repair(
        rowRoots,
        colRoots,
    )
    if err != nil {
        // err contains information to construct a fraud proof
    }
}

The LeoRSCodec implements the Codec interface using the Leopard Galois Field. It is designed for 2D data squares where the number of parity shares equals the number of data shares (a 2:1 ratio).

Encoding

Encode(data [][]byte) takes a slice of data chunks and returns the generated parity shares. The input data must be a 2D square of chunks.

Decoding

Decode(data [][]byte) reconstructs missing shares. Important: The method performs in-place reconstruction. It fills nil entries in the provided data slice. If you need to preserve the original slice (with its nil values), you must copy the slice before calling Decode.

Constraints

• Chunk Size: The shareSize must be a multiple of 64 bytes. Use ValidateChunkSize(shareSize int) to check compatibility.
• Max Chunks: The maximum number of shares supported in a 2D original data square is $32768 imes 32768$.

codec := rsmt2d.NewLeoRSCodec()

// Encoding
data := [][]byte{...}
parity, err := codec.Encode(data)

// Decoding (In-place)
// data must contain nil for missing shares
err := codec.Decode(data)

The Codec interface defines the required behavior for 2D Reed-Solomon implementations in rsmt2d. It handles the transformation between original data and parity shares.

Key methods:

• Encode(data [][]byte) ([][]byte, error): Encodes original data into parity shares. It automatically extracts share size from the input. Note that there must be no missing shares for encoding, and it only returns the parity shares.
• Decode(data [][]byte) ([][]byte, error): Decodes sparse data (original data + parity shares). Missing shares must be provided as nil. It returns the full set of original and parity data.
• MaxChunks() int: Returns the maximum number of chunks (shares) supported by the codec in a 2D original data square.
• ValidateChunkSize(chunkSize int) error: Validates if the codec supports a specific chunkSize. Returns nil if supported, or an error otherwise.
• Name() string: Returns the identifier for the codec.

// Example usage pattern for a Codec implementation
var codec rsmt2d.Codec

// Encoding original data to get parity shares
parity, err := codec.Encode(originalData)
if err != nil {
    // handle error
}

// Decoding data where some shares might be missing (nil)
// data contains original + parity, with missing shares as nil
fullData, err := codec.Decode(data)
if err != nil {
    // handle error
}