square

README

go-square

go-square is a Go module that provides data structures and utilities for interacting with data squares in the Celestia network. The data square is a special form of block serialization in the Celestia blockchain designed for sampling. This repo deals with the original data square which is distinct from the extended data square. Operations on the extended data square are handled by rsmt2d.

Package	Description
inclusion	Package inclusion contains functions to generate the blob share commitment from a given blob.
proto	Package contains proto definitions and go generated code
share	Package share contains encoding and decoding logic from blobs to shares.
square	Package square implements the logic to construct the original data square based on a list of transactions.
tx	Package tx contains BlobTx and IndexWrapper types

Installation

To use go-square as a dependency in your Go project, you can use go get:

go get github.com/celestiaorg/go-square/v3

Branches and Releasing

This repo has one long living development branch main, for changes targeting the next major version as well as long living branches for each prior major version i.e. v1.x, v2.x. Non breaking changes may be backported to these branches. This repo follows semver versioning.

Contributing

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

This repo attempts to conform to conventional commits so PR titles should ideally start with fix:, feat:, build:, chore:, ci:, docs:, style:, refactor:, perf:, or test: because this helps with semantic versioning and changelog generation. It is especially important to include an ! (e.g. feat!:) if the PR includes a breaking change.

Tools

1. Install Go 1.23.6
2. Install golangci-lint
3. Fork this repo
4. Make your changes
5. Submit a pull request

Helpful Commands

# Display all available make commands
make help

# Run tests
make test

# Run linter
make lint

# Perform benchmarking
make benchmark

Documentation

Overview

Package square implements the logic to construct the original data square based on a list of transactions.

Index

• func BlobShareRange(txs [][]byte, txIndex, blobIndex, maxSquareSize, subtreeRootThreshold int) (share.Range, error)
• func IsPowerOfTwo[I constraints.Integer](input I) bool
• func RoundUpPowerOfTwo[I constraints.Integer](input I) I
• func Size(length int) int
• func TxShareRange(txs [][]byte, txIndex, maxSquareSize, subtreeRootThreshold int) (share.Range, error)
• type Builder
  • func NewBuilder(maxSquareSize int, subtreeRootThreshold int, txs ...[]byte) (*Builder, error)
  • func (b *Builder) AppendBlobTx(blobTx *tx.BlobTx) bool
  • func (b *Builder) AppendTx(tx []byte) bool
  • func (b *Builder) BlobShareLength(pfbIndex, blobIndex int) (int, error)
  • func (b *Builder) CurrentSize() int
  • func (b *Builder) Export() (Square, error)
  • func (b *Builder) FindBlobStartingIndex(pfbIndex, blobIndex int) (int, error)
  • func (b *Builder) FindTxShareRange(txIndex int) (share.Range, error)
  • func (b *Builder) GetWrappedPFB(txIndex int) (*v2.IndexWrapper, error)
  • func (b *Builder) IsEmpty() bool
  • func (b *Builder) NumPFBs() int
  • func (b *Builder) NumTxs() int
  • func (b *Builder) RevertLastBlobTx() error
  • func (b *Builder) RevertLastTx() error
  • func (b *Builder) SubtreeRootThreshold() int
• type Element
• type PFBDecoder
• type Square
  • func Build(txs [][]byte, maxSquareSize, subtreeRootThreshold int) (Square, [][]byte, error)
  • func Construct(txs [][]byte, maxSquareSize, subtreeRootThreshold int) (Square, error)
  • func EmptySquare() Square
  • func WriteSquare(txWriter, pfbWriter *share.CompactShareSplitter, ...) (Square, error)
  • func (s Square) Equals(other Square) bool
  • func (s Square) Hash() [32]byte
  • func (s Square) IsEmpty() bool
  • func (s Square) Size() int
  • func (s Square) ToBytes() []byte
  • func (s Square) WrappedPFBs() ([][]byte, error)

Functions

func BlobShareRange

func BlobShareRange(txs [][]byte, txIndex, blobIndex, maxSquareSize, subtreeRootThreshold int) (share.Range, error)

BlobShareRange returns the range of share indexes that the blob, identified by txIndex and blobIndex, occupies. The range is end exclusive.

func IsPowerOfTwo

func IsPowerOfTwo[I constraints.Integer](input I) bool

IsPowerOfTwo returns true if input is a power of two.

func RoundUpPowerOfTwo

func RoundUpPowerOfTwo[I constraints.Integer](input I) I

RoundUpPowerOfTwo returns the next power of two greater than or equal to input.

func Size

func Size(length int) int

Size returns the size of the row or column in shares of a square. This function is currently a wrapper around the da packages equivalent function to avoid breaking the api. In future versions there will not be a copy of this code here.

func TxShareRange

func TxShareRange(txs [][]byte, txIndex, maxSquareSize, subtreeRootThreshold int) (share.Range, error)

TxShareRange returns the range of share indexes that the tx, specified by txIndex, occupies. The range is end exclusive.

Types

type Builder

type Builder struct {

	// here we keep track of the pending data to go in a square
	Txs   [][]byte
	Pfbs  []*v2.IndexWrapper
	Blobs []*Element

	// for compact shares we use a counter to track the amount of shares needed
	TxCounter  *share.CompactShareCounter
	PfbCounter *share.CompactShareCounter
	// contains filtered or unexported fields
}

func NewBuilder

func NewBuilder(maxSquareSize int, subtreeRootThreshold int, txs ...[]byte) (*Builder, error)

func (*Builder) AppendBlobTx

func (b *Builder) AppendBlobTx(blobTx *tx.BlobTx) bool

AppendBlobTx attempts to allocate the blob transaction to the square. It returns false if there is not enough space in the square to fit the transaction.

func (*Builder) AppendTx

func (b *Builder) AppendTx(tx []byte) bool

AppendTx attempts to allocate the transaction to the square. It returns false if there is not enough space in the square to fit the transaction.

func (*Builder) BlobShareLength

func (b *Builder) BlobShareLength(pfbIndex, blobIndex int) (int, error)

BlobShareLength returns the amount of shares a blob takes up in the square. It takes the index of the pfb in the tx set and the index of the blob within the PFB. TODO: we could look in to creating a map to avoid O(n) lookup when we expect large numbers of blobs

func (*Builder) CurrentSize

func (b *Builder) CurrentSize() int

func (*Builder) Export

func (b *Builder) Export() (Square, error)

Export constructs the square.

func (*Builder) FindBlobStartingIndex

func (b *Builder) FindBlobStartingIndex(pfbIndex, blobIndex int) (int, error)

FindBlobStartingIndex returns the starting share index of the blob in the square. It takes the index of the pfb in the tx set and the index of the blob within the PFB.

func (*Builder) FindTxShareRange

func (b *Builder) FindTxShareRange(txIndex int) (share.Range, error)

FindTxShareRange returns the range of shares occupied by the tx at txIndex. The indexes are both inclusive.

func (*Builder) GetWrappedPFB

func (b *Builder) GetWrappedPFB(txIndex int) (*v2.IndexWrapper, error)

func (*Builder) IsEmpty

func (b *Builder) IsEmpty() bool

func (*Builder) NumPFBs

func (b *Builder) NumPFBs() int

func (*Builder) NumTxs

func (b *Builder) NumTxs() int

func (*Builder) RevertLastBlobTx

func (b *Builder) RevertLastBlobTx() error

RevertLastBlobTx reverts the last blob transaction that was appended to the builder. It returns an error if there are no blob transactions to revert or if this method has been called consecutively without adding a tx in between calls.

func (*Builder) RevertLastTx

func (b *Builder) RevertLastTx() error

RevertLastTx reverts the last transaction that was appended to the builder. It returns an error if there are no transactions to revert or if this method has been called consecutively without adding a tx in between calls.

func (*Builder) SubtreeRootThreshold

func (b *Builder) SubtreeRootThreshold() int

type Element

type Element struct {
	Blob       *share.Blob
	PfbIndex   int
	BlobIndex  int
	NumShares  int
	MaxPadding int
}

type PFBDecoder

type PFBDecoder func(txBytes []byte) ([]uint32, error)

type Square

type Square []share.Share

Square is a 2D square of shares with symmetrical sides that are always a power of 2.

func Build

func Build(txs [][]byte, maxSquareSize, subtreeRootThreshold int) (Square, [][]byte, error)

Build takes an arbitrary long list of (prioritized) transactions and builds a square that is never greater than maxSquareSize. It also returns the ordered list of transactions that are present in the square and which have all PFBs trailing regular transactions. Note, this function does not check the underlying validity of the transactions. Errors should not occur and would reflect a violation in an invariant.

func Construct

func Construct(txs [][]byte, maxSquareSize, subtreeRootThreshold int) (Square, error)

Construct takes the exact list of ordered transactions and constructs a square, validating that

• all blobTxs are ordered after non-blob transactions
• the transactions don't collectively exceed the maxSquareSize.

Note that this function does not check the underlying validity of the transactions.

func EmptySquare

func EmptySquare() Square

EmptySquare returns a 1x1 square with a single tail padding share

func WriteSquare

func WriteSquare(
	txWriter, pfbWriter *share.CompactShareSplitter,
	blobWriter *share.SparseShareSplitter,
	nonReservedStart, squareSize int,
) (Square, error)

func (Square) Equals

func (s Square) Equals(other Square) bool

Equals returns true if two squares are equal

func (Square) Hash

func (s Square) Hash() [32]byte

Hash returns a hash based on the shares in the square.

func (Square) IsEmpty

func (s Square) IsEmpty() bool

func (Square) Size

func (s Square) Size() int

Size returns the size of the sides of a square

func (Square) ToBytes

func (s Square) ToBytes() []byte

ToBytes returns all the shares in the square flattened into a single byte slice.

func (Square) WrappedPFBs

func (s Square) WrappedPFBs() ([][]byte, error)

WrappedPFBs returns the wrapped PFBs in a square