shares

package
v0.10.0 Latest Latest
Warning

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

 Go to latest Published: Nov 23, 2022 License: Apache-2.0 Imports: 13 Imported by: 3

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, intermediate state roots, evidence). Sparse shares can contain data from zero or one message. Compact shares and sparse shares are encoded differently. The motivation behind the distinction is that transactions, intermediate state roots, and evidence 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, messages are expected to be larger and have the desideratum that clients should be able to create proofs of message inclusion. This desiradum is infeasible if client A's message is encoded into a share with another client B's message that is unknown to A. It follows that client A's message 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 1-10 bytes contain a varint of the uint64 sequence length.

For the first share of a sequence: 

| universal prefix                           | data                      |
| namespace_id | info_byte | sequence_length | sequence_data             |
| 8 bytes      | 1 byte    | 1-10 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 first byte after the universal prefix is a reserved byte that indicates the location in the share of the first unit of data that starts in this share.

For the first compact share in a reserved namespace: 

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

For continuation compact share in a reserved namespace: 

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

Notes

  • All shares in a reserved namespace belong to one sequence.
  • Each unit (transaction, intermediate state root, evidence) in data is prefixed with a varint of the length of the unit.
  • Although the sequence_length varint can technically be 1-10 bytes to store the maximum possible uint64, in-practice it is hard-coded to 4 bytes to contain the maximum possible sequence_length (based on share size and maximum square size).

Sparse Share Schema

The remaining bytes contain message data.

Index

Constants

This section is empty.

Variables

View Source 
var (
	ErrIncorrectNumberOfIndexes = errors.New(
		"number of malleated transactions is not identical to the number of wrapped transactions",
	)
	ErrUnexpectedFirstMessageShareIndex = errors.New(
		"the first message started at an unexpected index",
	)
)

Functions

func DelimLen 

func DelimLen(size uint64) int

DelimLen calculates the length of the delimiter for a given message 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, msgShareLens ...int) (bool, int)

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

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 MarshalDelimitedMessage 

func MarshalDelimitedMessage(msg coretypes.Message) ([]byte, error)

MarshalDelimitedMessage marshals the raw share data (excluding the namespace) of this message and prefixes it with the length of the message encoded as a varint.

func MarshalDelimitedTx 

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

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

func Merge 

func Merge(eds *rsmt2d.ExtendedDataSquare) (coretypes.Data, error)

Merge extracts block data from an extended data square.

func MessageShareCountsFromMessages 

func MessageShareCountsFromMessages(msgs []*core.Message) []int

func MessagesFromProto 

func MessagesFromProto(msgs []*core.Message) []coretypes.Message

func MessagesToProto 

func MessagesToProto(msgs []coretypes.Message) []*core.Message

func MsgSharesUsed 

func MsgSharesUsed(msgSize int) int

MsgSharesUsed calculates the minimum number of shares a message will take up. It accounts for the necessary delimiter and potential padding.

func MsgSharesUsedNonInteractiveDefaults 

func MsgSharesUsedNonInteractiveDefaults(cursor, squareSize int, msgShareLens ...int) (int, []uint32)

MsgSharesUsedNonInteractiveDefaults calculates the number of shares used by a given set of messages share lengths. It follows the non-interactive default rules and returns the share indexes for each message.

func NewReservedBytes added in v0.8.0 

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

NewReservedBytes returns a byte slice of length appconsts.CompactShareReservedBytes that contains a varint of the byteIndex of the first unit that starts in a compact share. If no unit starts in the compact share, ReservedBytes is [0, 0].

func NextAlignedPowerOfTwo 

func NextAlignedPowerOfTwo(cursor, msgLen, squareSize int) (int, bool)

NextAlignedPowerOfTwo calculates the next index in a row that is an aligned power of two and returns false if the entire the msg cannot fit on the given row at the next aligned power of two. An aligned power of two means that the largest power of two that fits entirely in the msg or the square size. pls see specs for further details. Assumes that cursor < squareSize, 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

func ParseDelimiter 

func ParseDelimiter(input []byte) (inputWithoutLengthDelimiter []byte, dataLength uint64, err error)

ParseDelimiter finds and returns the length delimiter of the share provided while also removing the delimiter bytes from the input. ParseDelimiter applies to both compact and sparse shares. Input should not contain the namespace ID or info byte of a share.

func ParseEvd 

func ParseEvd(shares [][]byte) (coretypes.EvidenceData, error)

ParseEvd collects all evidence from the shares provided.

func ParseMsgs 

func ParseMsgs(shares [][]byte) (coretypes.Messages, error)

ParseMsgs collects all messages from the shares provided

func ParseReservedBytes added in v0.8.0 

func ParseReservedBytes(reservedBytes []byte) (uint64, 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 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, intermediate state roots, and evidence into shares.

func NewCompactShareSplitter 

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

NewCompactShareSplitter returns a CompactShareSplitter using the provided namespace.

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() []Share

Export finalizes and returns the underlying compact shares.

func (*CompactShareSplitter) WriteBytes 

func (css *CompactShareSplitter) WriteBytes(rawData []byte)

WriteBytes adds the delimited data to the underlying compact shares.

func (*CompactShareSplitter) WriteEvidence 

func (css *CompactShareSplitter) WriteEvidence(evd coretypes.Evidence) error

func (*CompactShareSplitter) WriteTx 

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

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

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) []Share

AppendToShares appends raw data as shares. Used for messages.

func FromBytes 

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

func NewShare 

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

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 SplitEvidence 

func SplitEvidence(evd coretypes.EvidenceList) ([]Share, error)

func SplitMessages 

func SplitMessages(cursor int, indexes []uint32, msgs []coretypes.Message, useShareIndexes bool) ([]Share, error)

func SplitTxs 

func SplitTxs(txs coretypes.Txs) []Share

func TailPaddingShares 

func TailPaddingShares(n int) []Share

TailPaddingShares creates n tail padding shares.

func (Share) InfoByte 

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

func (Share) NamespaceID 

func (s Share) NamespaceID() namespace.ID

func (Share) SequenceLength added in v0.8.0 

func (s Share) SequenceLength() (uint64, error)

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 message. For compact shares, one share sequence exists per reserved namespace. For sparse shares, one share sequence exists per message.

func ParseShares 

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

type SparseShareSplitter 

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

SparseShareSplitter lazily splits messages into shares that will eventually be included in a data square. It also has methods to help progressively count how many shares the messages 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) RemoveMessage 

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

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

func (*SparseShareSplitter) Write 

func (sss *SparseShareSplitter) Write(msg coretypes.Message)

Write adds the delimited data to the underlying messages shares.

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.