rsmt2d

package module
v0.14.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 16, 2024 License: Apache-2.0 Imports: 11 Imported by: 49

README

rsmt2d

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

Tests Codecov GoDoc

Example

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
    }

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

Contributing

  1. Install Go 1.21+
  2. Install golangci-lint
Helpful Commands
# Run unit tests
go test ./...

# Run benchmarks
go test -benchmem -bench=.

# Run linter
golangci-lint run

Audits

Informal Systems audited rsmt2d v0.9.0 in Q2 of 2023. See informal-systems.pdf.

Documentation

Overview

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

Index

Constants

View Source 
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 shares less than or equal to 256. The Leopard
	// codec uses 16-bit leopard for shares greater than 256.
	Leopard = "Leopard"
)

Variables

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

ErrUnevenChunks is thrown when non-nil shares are not all of equal size. Note: chunks is synonymous with shares.

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

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

Functions

This section is empty.

Types

type Axis added in v0.5.0 

type Axis int

Axis represents which of a row or col. 

const (
	Row Axis = iota
	Col
)

func (Axis) String added in v0.6.0 

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 + parity data.
	Decode(data [][]byte) ([][]byte, error)
	// MaxChunks returns the max number of chunks this codec supports in a 2D
	// original data square. Chunk is a synonym of share.
	MaxChunks() int
	// Name returns the name of the codec.
	Name() string
	// ValidateChunkSize returns an error if this codec does not support
	// chunkSize. Returns nil if chunkSize is supported. Chunk is a synonym of
	// share.
	ValidateChunkSize(chunkSize int) error
}

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 added in v0.5.0 

type ErrByzantineData struct {
	// Axis describes if this ErrByzantineData is for a row or column.
	Axis Axis
	// Index is the row or column index.
	Index uint
	// Shares contain the shares in the row or column that the client can
	// determine proofs for (either through sampling or using shares decoded
	// from the extended data square). In other words, it contains shares whose
	// individual inclusion is guaranteed to be provable by the full node (i.e.
	// shares usable in a bad encoding fraud proof). Missing shares are nil.
	Shares [][]byte
}

ErrByzantineData is returned when a repaired row or column does not match the expected row or column Merkle root. It is also returned when the parity data from a row or a column is not equal to the encoded original data.

func (*ErrByzantineData) Error added in v0.5.0 

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 shares of original data.

func ImportExtendedDataSquare 

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

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

func NewExtendedDataSquare added in v0.10.0 

func NewExtendedDataSquare(codec Codec, treeCreatorFn TreeConstructorFn, edsWidth uint, shareSize uint) (*ExtendedDataSquare, error)

NewExtendedDataSquare returns a new extended data square with a width of edsWidth. All shares are initialized to nil so that the returned extended data square can be populated via subsequent SetCell invocations.

func (*ExtendedDataSquare) Col 

func (eds *ExtendedDataSquare) Col(colIdx 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, error)

ColRoots returns the Merkle roots of all the columns in the square. Returns an error if the EDS is incomplete (i.e. some shares are nil).

func (*ExtendedDataSquare) Equals added in v0.11.0 

func (eds *ExtendedDataSquare) Equals(other *ExtendedDataSquare) bool

Equals returns true if other is equal to eds.

func (*ExtendedDataSquare) Flattened added in v0.7.0 

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

Flattened returns the extended data square as a flattened slice of bytes.

func (*ExtendedDataSquare) FlattenedODS added in v0.11.0 

func (eds *ExtendedDataSquare) FlattenedODS() (flattened [][]byte)

FlattenedODS returns the original data square as a flattened slice of bytes.

func (ExtendedDataSquare) GetCell added in v0.6.0 

func (ds ExtendedDataSquare) GetCell(rowIdx uint, colIdx uint) []byte

GetCell returns a copy of a specific cell.

func (*ExtendedDataSquare) MarshalJSON added in v0.8.0 

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

func (*ExtendedDataSquare) Repair added in v0.5.0 

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

Repair attempts to repair an incomplete extended data square (EDS). The parameters rowRoots and colRoots are the expected Merkle roots for each row and column. rowRoots and colRoots are used to verify that a repaired row or column is correct. Prior to the repair process, if a row or column is already complete but the Merkle root for the row or column doesn't match the expected root, an error is returned. Missing shares in the EDS 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) Roots added in v0.12.0 

func (eds *ExtendedDataSquare) Roots() (roots [][]byte, err error)

Roots returns a byte slice with this eds's RowRoots and ColRoots concatenated.

func (*ExtendedDataSquare) Row 

func (eds *ExtendedDataSquare) Row(rowIdx 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, error)

RowRoots returns the Merkle roots of all the rows in the square. Returns an error if the EDS is incomplete (i.e. some shares are nil).

func (ExtendedDataSquare) SetCell added in v0.6.0 

func (ds ExtendedDataSquare) SetCell(rowIdx uint, colIdx uint, newShare []byte) error

SetCell sets a specific cell. The cell to set must be `nil`. Returns an error if the cell to set is not `nil` or newShare is not the correct size.

func (*ExtendedDataSquare) UnmarshalJSON added in v0.8.0 

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

func (*ExtendedDataSquare) Width 

func (eds *ExtendedDataSquare) Width() uint

Width returns the width of the square.

type LeoRSCodec added in v0.10.0 

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

func NewLeoRSCodec added in v0.7.0 

func NewLeoRSCodec() *LeoRSCodec

func (*LeoRSCodec) Decode added in v0.10.0 

func (l *LeoRSCodec) Decode(data [][]byte) ([][]byte, error)

func (*LeoRSCodec) Encode added in v0.10.0 

func (l *LeoRSCodec) Encode(data [][]byte) ([][]byte, error)

func (*LeoRSCodec) MaxChunks added in v0.10.0 

func (l *LeoRSCodec) MaxChunks() int

MaxChunks returns the max number of shares this codec supports in a 2D original data square.

func (*LeoRSCodec) Name added in v0.10.0 

func (l *LeoRSCodec) Name() string

func (*LeoRSCodec) ValidateChunkSize added in v0.11.0 

func (l *LeoRSCodec) ValidateChunkSize(shareSize int) error

ValidateChunkSize returns an error if this codec does not support shareSize. Returns nil if shareSize is supported.

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, _ 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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.