rsmt2d

README

rsmt2d

Go implementation of two dimensional Reed-Solomon Merkle tree data availability scheme.

Example

package main

import (
    "bytes"

    "github.com/celestiaorg/rsmt2d"
)

func main() {
    // Size of each share, in bytes
    bufferSize := 64
    // Init new codec
    codec := rsmt2d.NewLeoRSFF8Codec()

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

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

    // Save all shares in flattened form.
    flattened := make([][]byte, 0, eds.Width()*eds.Width())
    for i := uint(0); i < eds.Width(); i++ {
        flattened = append(flattened, eds.Row(i)...)
    }

    // 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(
        eds.RowRoots(),
        eds.ColRoots(),
    )
    if err != nil {
        // err contains information to construct a fraud proof
        // See extendeddatacrossword_test.go
    }
}

Building From Source

Run benchmarks

go test -benchmem -bench=.

Documentation

Overview

Package rsmt2d implements the two dimensional Reed-Solomon merkle tree data availability scheme.

Index

• Constants
• Variables
• func NewLeoRSCodec() *leoRSCodec
• type Axis
  • func (a Axis) String() string
• type Codec
• type DefaultTree
  • func (d *DefaultTree) Push(data []byte) error
  • func (d *DefaultTree) Root() ([]byte, error)
• type ErrByzantineData
  • func (e *ErrByzantineData) Error() string
• type ExtendedDataSquare
  • func ComputeExtendedDataSquare(data [][]byte, codec Codec, treeCreatorFn TreeConstructorFn) (*ExtendedDataSquare, error)
  • func ImportExtendedDataSquare(data [][]byte, codec Codec, treeCreatorFn TreeConstructorFn) (*ExtendedDataSquare, error)
  • func (eds *ExtendedDataSquare) Col(y uint) [][]byte
  • func (eds *ExtendedDataSquare) ColRoots() [][]byte
  • func (ds ExtendedDataSquare) Flattened() [][]byte
  • func (ds ExtendedDataSquare) GetCell(x uint, y uint) []byte
  • func (eds *ExtendedDataSquare) MarshalJSON() ([]byte, error)
  • func (eds *ExtendedDataSquare) Repair(rowRoots [][]byte, colRoots [][]byte) error
  • func (eds *ExtendedDataSquare) Row(x uint) [][]byte
  • func (eds *ExtendedDataSquare) RowRoots() [][]byte
  • func (ds ExtendedDataSquare) SetCell(x uint, y uint, newChunk []byte)
  • func (eds *ExtendedDataSquare) UnmarshalJSON(b []byte) error
  • func (eds *ExtendedDataSquare) Width() uint
• type SquareIndex
• type Tree
  • func NewDefaultTree(axis Axis, index uint) Tree
• type TreeConstructorFn

Constants

const (
	// Leopard is a codec that was originally implemented in the C++ library
	// https://github.com/catid/leopard. rsmt2d uses a Go port of the C++
	// library in https://github.com/klauspost/reedsolomon. The Leopard codec
	// uses 8-bit leopard for shards less than or equal to 256. The Leopard
	// codec uses 16-bit leopard for shards greater than 256.
	Leopard = "Leopard"
)

Variables

var ErrUnevenChunks = errors.New("non-nil chunks not all of equal size")

ErrUnevenChunks is thrown when non-nil chunks are not all of equal size.

var ErrUnrepairableDataSquare = errors.New("failed to solve data square")

ErrUnrepairableDataSquare is thrown when there is insufficient chunks to repair the square.

Functions

func NewLeoRSCodec

func NewLeoRSCodec() *leoRSCodec

Types

type Axis

type Axis int

Axis represents which of a row or col.

const (
	Row Axis = iota
	Col
)

func (Axis) String

func (a Axis) String() string

type Codec

type Codec interface {
	// Encode encodes original data, automatically extracting share size.
	// There must be no missing shares. Only returns parity shares.
	Encode(data [][]byte) ([][]byte, error)
	// Decode decodes sparse original + parity data, automatically extracting share size.
	// Missing shares must be nil. Returns original shares only.
	Decode(data [][]byte) ([][]byte, error)
	// contains filtered or unexported methods
}

type DefaultTree

type DefaultTree struct {
	*merkletree.Tree
	// contains filtered or unexported fields
}

func (*DefaultTree) Push

func (d *DefaultTree) Push(data []byte) error

func (*DefaultTree) Root

func (d *DefaultTree) Root() ([]byte, error)

type ErrByzantineData

type ErrByzantineData struct {
	Axis   Axis     // Axis of the data.
	Index  uint     // Row/Col index.
	Shares [][]byte // Pre-repaired shares. Missing shares are nil.
}

ErrByzantineData is thrown when a repaired row or column does not match the expected row or column Merkle root.

func (*ErrByzantineData) Error

func (e *ErrByzantineData) Error() string

type ExtendedDataSquare

type ExtendedDataSquare struct {
	// contains filtered or unexported fields
}

ExtendedDataSquare represents an extended piece of data.

func ComputeExtendedDataSquare

func ComputeExtendedDataSquare(
	data [][]byte,
	codec Codec,
	treeCreatorFn TreeConstructorFn,
) (*ExtendedDataSquare, error)

ComputeExtendedDataSquare computes the extended data square for some chunks of data.

func ImportExtendedDataSquare

func ImportExtendedDataSquare(
	data [][]byte,
	codec Codec,
	treeCreatorFn TreeConstructorFn,
) (*ExtendedDataSquare, error)

ImportExtendedDataSquare imports an extended data square, represented as flattened chunks of data.

func (*ExtendedDataSquare) Col

func (eds *ExtendedDataSquare) Col(y uint) [][]byte

Col returns a column slice. This slice is a copy of the internal column slice.

func (*ExtendedDataSquare) ColRoots

func (eds *ExtendedDataSquare) ColRoots() [][]byte

ColRoots returns the Merkle roots of all the columns in the square.

func (ExtendedDataSquare) Flattened

func (ds ExtendedDataSquare) Flattened() [][]byte

Flattened returns the concatenated rows of the data square.

func (ExtendedDataSquare) GetCell

func (ds ExtendedDataSquare) GetCell(x uint, y uint) []byte

GetCell returns a copy of a specific cell.

func (*ExtendedDataSquare) MarshalJSON

func (eds *ExtendedDataSquare) MarshalJSON() ([]byte, error)

func (*ExtendedDataSquare) Repair

func (eds *ExtendedDataSquare) Repair(
	rowRoots [][]byte,
	colRoots [][]byte,
) error

Repair attempts to repair an incomplete extended data square (EDS), comparing repaired rows and columns against expected Merkle roots.

Input

Missing shares must be nil.

Output

The EDS is modified in-place. If repairing is successful, the EDS will be complete. If repairing is unsuccessful, the EDS will be the most-repaired prior to the Byzantine row or column being repaired, and the Byzantine row or column prior to repair is returned in the error with missing shares as nil.

func (*ExtendedDataSquare) Row

func (eds *ExtendedDataSquare) Row(x uint) [][]byte

Row returns a row slice. This slice is a copy of the internal row slice.

func (*ExtendedDataSquare) RowRoots

func (eds *ExtendedDataSquare) RowRoots() [][]byte

RowRoots returns the Merkle roots of all the rows in the square.

func (ExtendedDataSquare) SetCell

func (ds ExtendedDataSquare) SetCell(x uint, y uint, newChunk []byte)

SetCell sets a specific cell. Cell to set must be `nil`. Panics if attempting to set a cell that is not `nil`.

func (*ExtendedDataSquare) UnmarshalJSON

func (eds *ExtendedDataSquare) UnmarshalJSON(b []byte) error

func (*ExtendedDataSquare) Width

func (eds *ExtendedDataSquare) Width() uint

Width returns the width of the square.

type SquareIndex

type SquareIndex struct {
	Axis, Cell uint
}

SquareIndex contains all information needed to identify the cell that is being pushed

type Tree

type Tree interface {
	Push(data []byte) error
	Root() ([]byte, error)
}

Tree wraps Merkle tree implementations to work with rsmt2d

func NewDefaultTree

func NewDefaultTree(axis Axis, index uint) Tree

type TreeConstructorFn

type TreeConstructorFn = func(axis Axis, index uint) Tree

TreeConstructorFn creates a fresh Tree instance to be used as the Merkle tree inside of rsmt2d.