rsmt2d

README

rsmt2d

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

Experimental software. Use at your own risk!

Usage

Run benchmarks

go test -tags leopard -benchmem -bench=.

Documentation

Overview

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

Index

• Constants
• Variables
• func NewRSGF8Codec() *rsGF8Codec
• type Codec
  • func NewLeoRSFF16Codec() Codec
  • func NewLeoRSFF8Codec() Codec
• type DefaultTree
  • func (d *DefaultTree) Prove(idx int) (merkleRoot []byte, proofSet [][]byte, proofIndex uint64, numLeaves uint64)
  • func (d *DefaultTree) Push(data []byte, _idx SquareIndex)
  • func (d *DefaultTree) Root() []byte
• type ErrByzantineColumn
  • func (e *ErrByzantineColumn) Error() string
• type ErrByzantineRow
  • func (e *ErrByzantineRow) 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 RepairExtendedDataSquare(rowRoots [][]byte, columnRoots [][]byte, data [][]byte, codec Codec, ...) (*ExtendedDataSquare, error)
  • func (ds ExtendedDataSquare) Cell(x uint, y uint) []byte
  • func (ds ExtendedDataSquare) ColRoot(y uint) []byte
  • func (ds ExtendedDataSquare) Column(y uint) [][]byte
  • func (ds ExtendedDataSquare) ColumnRoots() [][]byte
  • func (ds ExtendedDataSquare) Row(x uint) [][]byte
  • func (ds ExtendedDataSquare) RowRoot(x uint) []byte
  • func (ds ExtendedDataSquare) RowRoots() [][]byte
  • func (ds ExtendedDataSquare) Width() uint
• type SquareIndex
• type Tree
  • func NewDefaultTree() Tree
• type TreeConstructorFn

Constants

const (
	LeopardFF16 = "LeopardFF16"
	LeopardFF8  = "LeopardFF8"
	RSGF8       = "RSFG8"
)

Variables

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

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

Functions

func NewRSGF8Codec

func NewRSGF8Codec() *rsGF8Codec

NewRSGF8Codec issues a new cached RSGF8Codec

Types

type Codec

type Codec interface {
	Encode(data [][]byte) ([][]byte, error)
	Decode(data [][]byte) ([][]byte, error)
	// contains filtered or unexported methods
}

func NewLeoRSFF16Codec

func NewLeoRSFF16Codec() Codec

func NewLeoRSFF8Codec

func NewLeoRSFF8Codec() Codec

type DefaultTree

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

func (*DefaultTree) Prove

func (d *DefaultTree) Prove(idx int) (merkleRoot []byte, proofSet [][]byte, proofIndex uint64, numLeaves uint64)

func (*DefaultTree) Push

func (d *DefaultTree) Push(data []byte, _idx SquareIndex)

func (*DefaultTree) Root

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

type ErrByzantineColumn

type ErrByzantineColumn struct {
	ColumnNumber uint     // Column index
	Shares       [][]byte // Pre-repaired column shares
}

ErrByzantineColumn is thrown when there is a repaired column does not match the expected column Merkle root.

func (*ErrByzantineColumn) Error

func (e *ErrByzantineColumn) Error() string

type ErrByzantineRow

type ErrByzantineRow struct {
	RowNumber uint     // Row index
	Shares    [][]byte // Pre-repaired row shares
}

ErrByzantineRow is thrown when there is a repaired row does not match the expected row Merkle root.

func (*ErrByzantineRow) Error

func (e *ErrByzantineRow) 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 RepairExtendedDataSquare

func RepairExtendedDataSquare(
	rowRoots [][]byte,
	columnRoots [][]byte,
	data [][]byte,
	codec Codec,
	treeCreatorFn TreeConstructorFn,
) (*ExtendedDataSquare, error)

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

Input

Missing data chunks should be represented as 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) Cell

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

Cell returns a single chunk at a specific cell.

func (ExtendedDataSquare) ColRoot

func (ds ExtendedDataSquare) ColRoot(y uint) []byte

ColRoot calculates and returns the root of the selected row. Note: unlike the ColRoots method, ColRoot does not use the built in cache

func (ExtendedDataSquare) Column

func (ds ExtendedDataSquare) Column(y uint) [][]byte

Column returns the data in a column.

func (ExtendedDataSquare) ColumnRoots

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

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

func (ExtendedDataSquare) Row

func (ds ExtendedDataSquare) Row(x uint) [][]byte

Row returns the data in a row.

func (ExtendedDataSquare) RowRoot

func (ds ExtendedDataSquare) RowRoot(x uint) []byte

RowRoot calculates and returns the root of the selected row. Note: unlike the RowRoots method, RowRoot uses the built-in cache when available.

func (ExtendedDataSquare) RowRoots

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

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

func (ExtendedDataSquare) Width

func (ds 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, idx SquareIndex)
	// TODO(ismail): is this general enough?
	Prove(idx int) (merkleRoot []byte, proofSet [][]byte, proofIndex uint64, numLeaves uint64)
	Root() []byte
}

Tree wraps merkle tree implementations to work with rsmt2d

func NewDefaultTree

func NewDefaultTree() Tree

type TreeConstructorFn

type TreeConstructorFn = func() Tree

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