shares

package
v0.13.3 Latest Latest
Warning

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

 Go to latest Published: May 24, 2023 License: Apache-2.0 Imports: 14 Imported by: 4

Documentation

Overview

Package shares provides primitives for splitting block data into shares and parsing shares back into block data.

Compact vs. Sparse

There are two types of shares:

  1. Compact
  2. Sparse

Compact shares can contain data from one or more unit (transactions or intermediate state roots). Sparse shares can contain data from zero or one blob. Compact shares and sparse shares are encoded differently. The motivation behind the distinction is that transactions and intermediate state roots are expected to have small lengths so they are encoded in compact shares to minimize the number of shares needed to store them. On the other hand, blobs are expected to be larger and have the desideratum that clients should be able to create proofs of blob inclusion. This desiradum is infeasible if client A's blob is encoded into a share with another client B's blob that is unknown to A. It follows that client A's blob is encoded into a share such that the contents can be determined by client A without any additional information. See message layout rational or adr-006-non-interactive-defaults for more details.

Universal Prefix

Both types of shares have a universal prefix. The first 8 bytes of a share contain the namespace.ID. The next byte is an InfoByte that contains the share version and a sequence start indicator. If the sequence start indicator is `1` (i.e. this is the first share of a sequence) then the next 4 bytes contain a big endian uint32 of the sequence length.

For the first share of a sequence: 

| universal prefix                           | data                      |
| namespace_id | info_byte | sequence_length | sequence_data             |
| 8 bytes      | 1 byte    | 4 bytes         | remaining bytes of share  |

For continuation share of a sequence: 

| universal prefix         | data                      |
| namespace_id | info_byte | sequence_data             |
| 8 bytes      | 1 byte    | remaining bytes of share  |

The remaining bytes depend on the share type.

Compact Share Schema

The four bytes after the universal prefix are reserved for the location in the share of the first unit of data that starts in this share.

For the first compact share: 

| universal prefix                           | reserved bytes         | data                                                |
| namespace_id | info_byte | sequence_length | location_of_first_unit | transactions or intermediate state roots            |
| 8 bytes      | 1 byte    | 4 bytes         | 4 bytes                | remaining bytes of share                            |

For continuation compact share: 

| universal prefix         | reserved bytes         | data                                                |
| namespace_id | info_byte | location_of_first_unit | transactions or intermediate state roots            |
| 8 bytes      | 1 byte    | 4 bytes                | remaining bytes of share                            |

Notes

  • All shares in a reserved namespace belong to one sequence.
  • Each unit (transaction or intermediate state root) in data is prefixed with a varint of the length of the unit.

Sparse Share Schema

The remaining bytes contain blob data.

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrIncorrectNumberOfIndexes = errors.New(
		"number of indexes is not identical to the number of blobs",
	)
	ErrUnexpectedFirstBlobShareIndex = errors.New(
		"the first blob started at an unexpected index",
	)
)

Functions

func BlobSharesUsedNonInteractiveDefaults added in v0.12.0 

func BlobSharesUsedNonInteractiveDefaults(cursor, squareSize int, blobShareLens ...int) (sharesUsed int, indexes []uint32)

BlobSharesUsedNonInteractiveDefaults returns the number of shares used by a given set of blobs share lengths. It follows the non-interactive default rules and returns the share indexes for each blob.

func BlobsFromProto added in v0.12.0 

func BlobsFromProto(blobs []core.Blob) ([]coretypes.Blob, error)

func CompactSharesNeeded added in v0.12.0 

func CompactSharesNeeded(sequenceLen int) (sharesNeeded int)

CompactSharesNeeded returns the number of compact shares needed to store a sequence of length sequenceLen. The parameter sequenceLen is the number of bytes of transactions or intermediate state roots in a sequence.

func DelimLen 

func DelimLen(size uint64) int

DelimLen calculates the length of the delimiter for a given unit size

func ExtractShareIndexes 

func ExtractShareIndexes(txs coretypes.Txs) []uint32

ExtractShareIndexes iterates over the transactions and extracts the share indexes from wrapped transactions. It returns nil if the transactions are from an old block that did not have share indexes in the wrapped txs.

func FitsInSquare 

func FitsInSquare(cursor, squareSize int, blobShareLens ...int) (bool, int)

FitsInSquare uses the non interactive default rules to see if blobs of some lengths will fit in a square of squareSize starting at share index cursor. Returns whether the blobs fit in the square and the number of shares used by blobs. See non-interactive default rules https://github.com/celestiaorg/celestia-specs/blob/master/src/rationale/message_block_layout.md#non-interactive-default-rules https://github.com/celestiaorg/celestia-app/blob/1b80b94a62c8c292f569e2fc576e26299985681a/docs/architecture/adr-009-non-interactive-default-rules-for-reduced-padding.md

func IsPowerOfTwo added in v0.9.0 

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

IsPowerOfTwo returns true if input is a power of two.

func MarshalDelimitedBlob added in v0.12.0 

func MarshalDelimitedBlob(blob coretypes.Blob) []byte

MarshalDelimitedBlob marshals the raw share data (excluding the namespace) of this blob and prefixes it with the length of the blob.

func MarshalDelimitedTx 

func MarshalDelimitedTx(tx coretypes.Tx) ([]byte, error)

MarshalDelimitedTx prefixes a transaction with the length of the transaction encoded as a varint.

func MinSquareSize added in v0.12.0 

func MinSquareSize(shareCount int) int

MinSquareSize returns the minimum square size that can contain shareCount number of shares.

func NewReservedBytes added in v0.8.0 

func NewReservedBytes(byteIndex uint32) ([]byte, error)

NewReservedBytes returns a byte slice of length appconsts.CompactShareReservedBytes that contains the byteIndex of the first unit that starts in a compact share.

func NextMultipleOfBlobMinSquareSize added in v0.12.0 

func NextMultipleOfBlobMinSquareSize(cursor, blobLen, squareSize int) (index int, fitsInRow bool)

NextMultipleOfBlobMinSquareSize determines the next index in a square that is a multiple of the blob's minimum square size. This function returns false if the entire the blob cannot fit on the given row. Assumes that all args are non negative, and that squareSize is a power of two. https://github.com/celestiaorg/celestia-specs/blob/master/src/rationale/message_block_layout.md#non-interactive-default-rules https://github.com/celestiaorg/celestia-app/blob/1b80b94a62c8c292f569e2fc576e26299985681a/docs/architecture/adr-009-non-interactive-default-rules-for-reduced-padding.md

func ParseBlobs added in v0.12.0 

func ParseBlobs(shares [][]byte) ([]coretypes.Blob, error)

ParseBlobs collects all blobs from the shares provided

func ParseDelimiter 

func ParseDelimiter(input []byte) (inputWithoutLenDelimiter []byte, unitLen uint64, err error)

ParseDelimiter attempts to parse a varint length delimiter from the input provided. It returns the input without the len delimiter bytes, the length parsed from the varint optionally an error. Unit length delimiters are used in compact shares where units (i.e. a transaction) are prefixed with a length delimiter that is encoded as a varint. Input should not contain the namespace ID or info byte of a share.

func ParseReservedBytes added in v0.8.0 

func ParseReservedBytes(reservedBytes []byte) (uint32, error)

ParseReservedBytes parses a byte slice of length appconsts.CompactShareReservedBytes into a byteIndex.

func ParseTxs 

func ParseTxs(shares [][]byte) (coretypes.Txs, error)

ParseTxs collects all of the transactions from the shares provided

func RoundDownPowerOfTwo added in v0.9.0 

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

RoundDownPowerOfTwo returns the next power of two less than or equal to input.

func RoundUpPowerOfTwo added in v0.9.0 

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

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

func RoundUpPowerOfTwoStrict added in v0.9.0 

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

RoundUpPowerOfTwo returns the next power of two that is strictly greater than input.

func SparseSharesNeeded added in v0.12.0 

func SparseSharesNeeded(sequenceLen uint32) (sharesNeeded int)

SparseSharesNeeded returns the number of shares needed to store a sequence of length sequenceLen.

func SplitTxs 

func SplitTxs(txs coretypes.Txs) (txShares []Share, pfbShares []Share, shareRanges map[coretypes.TxKey]ShareRange)

func ToBytes 

func ToBytes(shares []Share) (bytes [][]byte)

func TxsFromBytes 

func TxsFromBytes(txs [][]byte) coretypes.Txs

func TxsToBytes 

func TxsToBytes(txs coretypes.Txs) [][]byte

Types

type CompactShareSplitter 

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

CompactShareSplitter will write raw data compactly across a progressively increasing set of shares. It is used to lazily split block data such as transactions or intermediate state roots into shares.

func NewCompactShareSplitter 

func NewCompactShareSplitter(ns namespace.ID, shareVersion uint8) *CompactShareSplitter

NewCompactShareSplitter returns a CompactShareSplitter using the provided namespace and shareVersion.

func (*CompactShareSplitter) Count 

func (css *CompactShareSplitter) Count() (shareCount int)

Count returns the number of shares that would be made if `Export` was invoked on this compact share splitter.

func (*CompactShareSplitter) Export 

func (css *CompactShareSplitter) Export(shareRangeOffset int) ([]Share, map[coretypes.TxKey]ShareRange)

Export finalizes and returns the underlying compact shares and a map of shareRanges. All share ranges in the map of shareRanges will be offset (i.e. incremented) by the shareRangeOffset provided. shareRangeOffset should be 0 for the first compact share sequence in the data square (transactions) but should be some non-zero number for subsequent compact share sequences (e.g. pfb txs).

func (*CompactShareSplitter) WriteTx 

func (css *CompactShareSplitter) WriteTx(tx coretypes.Tx)

WriteTx adds the delimited data for the provided tx to the underlying compact share splitter.

type InfoByte 

type InfoByte byte

InfoByte is a byte with the following structure: the first 7 bits are reserved for version information in big endian form (initially `0000000`). The last bit is a "sequence start indicator", that is `1` if this is the first share of a sequence and `0` if this is a continuation share.

func NewInfoByte 

func NewInfoByte(version uint8, isSequenceStart bool) (InfoByte, error)

func ParseInfoByte 

func ParseInfoByte(i byte) (InfoByte, error)

func (InfoByte) IsSequenceStart added in v0.8.0 

func (i InfoByte) IsSequenceStart() bool

IsSequenceStart returns whether this share is the start of a sequence.

func (InfoByte) Version 

func (i InfoByte) Version() uint8

Version returns the version encoded in this InfoByte. Version is expected to be between 0 and appconsts.MaxShareVersion (inclusive).

type Share 

type Share []byte

Share contains the raw share data (including namespace ID).

func AppendToShares 

func AppendToShares(shares []Share, nid namespace.ID, rawData []byte, shareVersion uint8) []Share

AppendToShares appends raw data as shares. Used for blobs.

func FromBytes 

func FromBytes(bytes [][]byte) (shares []Share)

func NamespacePaddingShare added in v0.12.0 

func NamespacePaddingShare(ns namespace.ID) Share

NamespacePaddingShare returns a share that acts as padding. Namespace padding shares follow a blob so that the next blob may start at an index that conforms to non-interactive default rules. The ns parameter provided should be the namespace of the blob that precedes this padding in the data square.

func NamespacePaddingShares added in v0.12.0 

func NamespacePaddingShares(ns namespace.ID, n int) []Share

NamespacePaddingShares returns n namespace padding shares.

func NewShare 

func NewShare(data []byte) (Share, error)

func ReservedPaddingShare added in v0.12.0 

func ReservedPaddingShare() Share

ReservedPaddingShare returns a share that acts as padding. Reserved padding shares follow all significant shares in the reserved namespace so that the first blob can start at an index that conforms to non-interactive default rules.

func ReservedPaddingShares added in v0.12.0 

func ReservedPaddingShares(n int) []Share

ReservedPaddingShare returns n reserved padding shares.

func Split 

func Split(data coretypes.Data, useShareIndexes bool) ([]Share, error)

Split converts block data into encoded shares, optionally using share indexes that are encoded as wrapped transactions. Most use cases out of this package should use these share indexes and therefore set useShareIndexes to true.

func SplitBlobs added in v0.12.0 

func SplitBlobs(cursor int, indexes []uint32, blobs []coretypes.Blob, useShareIndexes bool) ([]Share, error)

func TailPaddingShare added in v0.12.0 

func TailPaddingShare() Share

TailPaddingShare is a share that is used to pad a data square to the desired square size. Tail padding shares follow the last blob share in the data square.

func TailPaddingShares 

func TailPaddingShares(n int) []Share

TailPaddingShares returns n tail padding shares.

func (Share) InfoByte 

func (s Share) InfoByte() (InfoByte, error)

func (Share) IsCompactShare added in v0.12.0 

func (s Share) IsCompactShare() bool

IsCompactShare returns true if this is a compact share.

func (Share) IsPadding added in v0.12.0 

func (s Share) IsPadding() (bool, error)

IsPadding returns whether this share is padding or not.

func (Share) IsSequenceStart added in v0.12.0 

func (s Share) IsSequenceStart() (bool, error)

IsSequenceStart returns true if this is the first share in a sequence.

func (Share) NamespaceID 

func (s Share) NamespaceID() namespace.ID

func (Share) RawData added in v0.11.1 

func (s Share) RawData() (rawData []byte, err error)

RawData returns the raw share data. The raw share data does not contain the namespace ID, info byte, sequence length, or reserved bytes.

func (Share) SequenceLen added in v0.11.1 

func (s Share) SequenceLen() (sequenceLen uint32, err error)

SequenceLen returns the sequence length of this share and optionally an error. It returns 0, nil if this is a continuation share (i.e. doesn't contain a sequence length).

func (Share) ToBytes added in v0.12.0 

func (s Share) ToBytes() []byte

func (Share) Version added in v0.12.0 

func (s Share) Version() (uint8, error)

type ShareRange added in v0.12.0 

type ShareRange struct {
	// Start is the index of the first share occupied by this range.
	Start int
	// End is the index of the last share occupied by this range.
	End int
}

type ShareSequence 

type ShareSequence struct {
	NamespaceID namespace.ID
	Shares      []Share
}

ShareSequence represents a contiguous sequence of shares that are part of the same namespace and blob. For compact shares, one share sequence exists per reserved namespace. For sparse shares, one share sequence exists per blob.

func ParseShares 

func ParseShares(rawShares [][]byte) ([]ShareSequence, error)

func (ShareSequence) RawData added in v0.12.0 

func (s ShareSequence) RawData() (data []byte, err error)

RawData returns the raw share data of this share sequence. The raw data does not contain the namespace ID, info byte, sequence length, or reserved bytes.

func (ShareSequence) SequenceLen added in v0.12.0 

func (s ShareSequence) SequenceLen() (uint32, error)

type SparseShareSplitter 

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

SparseShareSplitter lazily splits blobs into shares that will eventually be included in a data square. It also has methods to help progressively count how many shares the blobs written take up.

func NewSparseShareSplitter 

func NewSparseShareSplitter() *SparseShareSplitter

func (*SparseShareSplitter) Count 

func (sss *SparseShareSplitter) Count() int

Count returns the current number of shares that will be made if exporting.

func (*SparseShareSplitter) Export 

func (sss *SparseShareSplitter) Export() []Share

Export finalizes and returns the underlying shares.

func (*SparseShareSplitter) RemoveBlob added in v0.12.0 

func (sss *SparseShareSplitter) RemoveBlob(i int) (int, error)

RemoveBlob will remove a blob from the underlying blob state. If there is namespaced padding after the blob, then that is also removed.

func (*SparseShareSplitter) Write 

func (sss *SparseShareSplitter) Write(blob coretypes.Blob) error

Write writes the provided blob to this sparse share splitter. It returns an error or nil if no error is encountered.

func (*SparseShareSplitter) WriteNamespacedPaddedShares 

func (sss *SparseShareSplitter) WriteNamespacedPaddedShares(count int)

WriteNamespacedPaddedShares adds empty shares using the namespace of the last written share. This is useful to follow the message layout rules. It assumes that at least one share has already been written, if not it panics.

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.