rsmt2d

package module
v0.0.0-...-c1d6ecc Latest Latest
Warning

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

 Go to latest Published: Apr 16, 2026 License: Apache-2.0 Imports: 11 Imported by: 0

README

rsmt2d

Repo này là một bản chỉnh sửa của rsmt2d của Celestia, tập trung vào 3 phần:

  • package gốc rsmt2d: mở rộng ODS -> EDS bằng 2D erasure coding và tính Merkle roots cho từng hàng/cột
  • package rlnc: thử nghiệm Random Linear Network Coding trên GF(2^8) với hệ số ngẫu nhiên thật sự
  • package cda: mô phỏng pipeline publisher -> storage node -> receiver và tích hợp KZG bằng gnark-crypto

Cấu trúc chính

  • extendeddatasquare.go, extendeddatacrossword.go, datasquare.go, tree.go: logic EDS, repair và Merkle commitments
  • leopard*.go: codec Reed-Solomon dùng cho flow EDS chuẩn
  • rlnc/: codec RLNC, Gaussian elimination, recode và test riêng
  • cda/: publisher, store, receiver, KZG provider và test pipeline

Trạng thái hiện tại

  • rsmt2d gốc vẫn dùng flow EDS chuẩn với codec Leopard
  • rlnc hiện encode từng PieceData{Data, Coeffs}, decode từ []PieceData, và hỗ trợ Recode/RecodeWithBeta
  • hệ số RLNC được sinh bằng crypto/rand, không còn là ma trận xác định theo SHA256
  • cda đã có unit test cho pipeline và test với GnarkKZG thật

Lưu ý quan trọng

RLNC hiện tổ hợp dữ liệu trên GF(2^8), trong khi KZG của gnark-crypto làm việc trên trường BLS12-381. Vì vậy:

  • recovery của RLNC hoạt động bình thường
  • combine/verify của KZG hoạt động bình thường nếu dữ liệu được tổ hợp trong cùng trường của KZG
  • verify trực tiếp một stored RLNC piece bằng KZG hiện chưa tương thích hoàn toàn về mặt đại số Đã chuyển trường số RLNC sang Fr tương thích với KZG

Chạy dự án

Yêu cầu: Go 1.24+

make build
make test
make bench
make lint

Hoặc:

go test ./...

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 

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 BufferedTreeConstructor 

type BufferedTreeConstructor interface {
	NewConstructor(squareSize uint) TreeConstructorFn
	TreeCount() int
}

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 

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 

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 ComputeExtendedDataSquareWithBuffer 

func ComputeExtendedDataSquareWithBuffer(
	data [][]byte,
	codec Codec,
	treeCreator BufferedTreeConstructor,
) (*ExtendedDataSquare, error)

ComputeExtendedDataSquareWithBuffer computes the extended data square for some shares of original data, it limits parallel operations and uses buffered nmts to avoid allocations when computing root.

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 

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) BuildKateCommitmentProof 

func (eds *ExtendedDataSquare) BuildKateCommitmentProof(colIdx uint) (*KateMerkleProof, error)

BuildKateCommitmentProof builds an inclusion proof for the column commitment at colIdx.

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 

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

Equals returns true if other is equal to eds.

func (*ExtendedDataSquare) Flattened 

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

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

func (*ExtendedDataSquare) FlattenedODS 

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

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

func (ExtendedDataSquare) GetCell 

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

GetCell returns a copy of a specific cell.

func (*ExtendedDataSquare) KZGColumnMerkleRoot 

func (eds *ExtendedDataSquare) KZGColumnMerkleRoot(columnCommitments [][]byte) ([]byte, error)

KZGColumnMerkleRoot computes the Merkle root of all column KZG commitments.

func (*ExtendedDataSquare) KateCols 

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

KateCols returns the KZG commitments of all columns in the square.

func (*ExtendedDataSquare) KatePieceCommitments 

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

KatePieceCommitments returns N*k commitments for piece-columns.

func (*ExtendedDataSquare) KateRoot 

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

KateRoot computes the Merkle root over per-column KZG commitments.

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). 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 

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 

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) SetKateColumnCommitmentFn 

func (eds *ExtendedDataSquare) SetKateColumnCommitmentFn(fn KateColumnCommitmentFn)

SetKateColumnCommitmentFn sets a custom per-column commitment function.

func (*ExtendedDataSquare) SetKateColumnCommitments 

func (eds *ExtendedDataSquare) SetKateColumnCommitments(columnCommitments [][]byte) error

SetKateColumnCommitments stores N commitments for EDS columns.

func (*ExtendedDataSquare) SetKatePieceCommitments 

func (eds *ExtendedDataSquare) SetKatePieceCommitments(pieceCommitments [][]byte)

SetKatePieceCommitments stores N*k commitments for piece-columns.

func (*ExtendedDataSquare) SetKateRootFromColumnCommitments 

func (eds *ExtendedDataSquare) SetKateRootFromColumnCommitments(columnCommitments [][]byte) ([]byte, error)

SetKateRootFromColumnCommitments validates commitments and computes aggregate root.

func (*ExtendedDataSquare) UnmarshalJSON 

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

func (*ExtendedDataSquare) VerifyKateCommitmentProof 

func (eds *ExtendedDataSquare) VerifyKateCommitmentProof(proof *KateMerkleProof, root []byte) bool

VerifyKateCommitmentProof verifies a Kate commitment inclusion proof against a root. If root is nil, this function uses the EDS current KateRoot.

func (*ExtendedDataSquare) Width 

func (eds *ExtendedDataSquare) Width() uint

Width returns the width of the square.

type KateColumnCommitmentFn 

type KateColumnCommitmentFn func(col [][]byte, colIdx uint) ([]byte, error)

KateColumnCommitmentFn computes the commitment for one data square column.

type KateMerkleProof 

type KateMerkleProof struct {
	ProofSet   [][]byte
	ProofIndex uint64
	NumLeaves  uint64
}

KateMerkleProof proves a column commitment belongs to the Kate commitment tree.

type LeoRSCodec 

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

func NewLeoRSCodec 

func NewLeoRSCodec() *LeoRSCodec

func (*LeoRSCodec) Decode 

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

func (*LeoRSCodec) Encode 

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

func (*LeoRSCodec) MaxChunks 

func (l *LeoRSCodec) MaxChunks() int

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

func (*LeoRSCodec) Name 

func (l *LeoRSCodec) Name() string

func (*LeoRSCodec) ValidateChunkSize 

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

Directories

Path Synopsis

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.