Celestia App Specifications

• Specification
  • Data Structures
  • Consensus
  • Block Proposer
  • Networking
• Rationale
  • Message Layout

Specification

• Data Structures
• Consensus
• Block Proposer
• Networking

Data Structures

Data Structures Overview

Type Aliases

Blockchain Data Structures

Block

Blocks are the top-level data structure of the Celestia blockchain.

Header

Block header, which is fully downloaded by both full clients and light clients.

The size of the original data square, availableDataOriginalSquareSize, isn't explicitly declared in the block header. Instead, it is implicitly computed as the smallest power of 2 whose square is at least availableDataOriginalSharesUsed (in other words, the smallest power of 4 that is at least availableDataOriginalSharesUsed).

The header hash is the hash of the serialized header.

AvailableDataHeader

The number of row/column roots of the original data shares in square layout for this block. The availableDataRoot of the header is computed using the compact row and column roots as described here.

The number of row and column roots is each availableDataOriginalSquareSize * 2, and must be a power of 2. Note that the minimum availableDataOriginalSquareSize is 1 (not 0), therefore the number of row and column roots are each at least 2.

Implementations can prune rows containing only tail padding as they are implicitly available.

AvailableData

Data that is erasure-coded for data availability checks.

Commit

Timestamp

Timestamp is a type alias.

Celestia uses google.protobuf.Timestamp to represent time.

HashDigest

HashDigest is a type alias.

Output of the hashing function. Exactly 256 bits (32 bytes) long.

TransactionFee

Abstraction over transaction fees.

Address

Address is a type alias.

Addresses are the hash digest of the public key.

Addresses have a length of 32 bytes.

CommitSig

enum CommitFlag : uint8_t {
    CommitFlagAbsent = 1,
    CommitFlagCommit = 2,
    CommitFlagNil = 3,
};

Signature

Output of the signing process.

ConsensusVersion

Serialization

Objects that are committed to or signed over require a canonical serialization. This is done using a deterministic (and thus, bijective) variant of protobuf defined here.

Note: there are two requirements for a serialization scheme, should this need to be changed:

1. Must be bijective.
2. Serialization must include the length of dynamic structures (e.g. arrays with variable length).

Hashing

All protocol-level hashing is done using SHA-2-256 as defined in FIPS 180-4. SHA-2-256 outputs a digest that is 256 bits (i.e. 32 bytes) long.

Libraries implementing SHA-2-256 are available in Go (https://pkg.go.dev/crypto/sha256) and Rust (https://docs.rs/sha2).

Unless otherwise indicated explicitly, objects are first serialized before being hashed.

Public-Key Cryptography

Consensus-critical data is authenticated using ECDSA, with the curve secp256k1. A highly-optimized library is available in C (https://github.com/bitcoin-core/secp256k1), with wrappers in Go (https://pkg.go.dev/github.com/ethereum/go-ethereum/crypto/secp256k1) and Rust (https://docs.rs/crate/secp256k1).

Public keys are encoded in uncompressed form, as the concatenation of the x and y values. No prefix is needed to distinguish between encoding schemes as this is the only encoding supported.

Deterministic signatures (RFC-6979) should be used when signing, but this is not enforced at the protocol level as it cannot be.

Signatures are represented as the r and s (each 32 bytes), and v (1-bit) values of the signature. r and s take on their usual meaning (see: SEC 1, 4.1.3 Signing Operation), while v is used for recovering the public key from a signature more quickly (see: SEC 1, 4.1.6 Public Key Recovery Operation). Only low-s values in signatures are valid (i.e. s <= secp256k1.n//2); s can be replaced with -s mod secp256k1.n during the signing process if it is high. Given this, the first bit of s will always be 0, and can be used to store the 1-bit v value.

v represents the parity of the Y component of the point, 0 for even and 1 for odd. The X component of the point is assumed to always be low, since the possibility of it being high is negligible.

Putting it all together, the encoding for signatures is:

|    32 bytes   ||           32 bytes           |
[256-bit r value][1-bit v value][255-bit s value]

This encoding scheme is derived from EIP 2098: Compact Signature Representation.

Merkle Trees

Merkle trees are used to authenticate various pieces of data across the Celestia stack, including transactions, messages, the validator set, etc. This section provides an overview of the different tree types used, and specifies how to construct them.

Binary Merkle Tree

Binary Merkle trees are constructed in the same fashion as described in Certificate Transparency (RFC-6962), except for using a different hashing function. Leaves are hashed once to get leaf node values and internal node values are the hash of the concatenation of their children (either leaf nodes or other internal nodes).

Nodes contain a single field:

The base case (an empty tree) is defined as the hash of the empty string:

node.v = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

For leaf node node of leaf data d:

node.v = h(0x00, serialize(d))

For internal node node with children l and r:

node.v = h(0x01, l.v, r.v)

Note that rather than duplicating the last node if there are an odd number of nodes (the Bitcoin design), trees are allowed to be imbalanced. In other words, the height of each leaf may be different. For an example, see Section 2.1.3 of Certificate Transparency (RFC-6962).

Leaves and internal nodes are hashed differently: the one-byte 0x00 is prepended for leaf nodes while 0x01 is prepended for internal nodes. This avoids a second-preimage attack where internal nodes are presented as leaves trees with leaves at different heights.

BinaryMerkleTreeInclusionProof

A proof for a leaf in a binary Merkle tree, as per Section 2.1.1 of Certificate Transparency (RFC-6962).

Namespace Merkle Tree

Shares in Celestia are associated with a provided namespace ID. The Namespace Merkle Tree (NMT) is a variation of the Merkle Interval Tree, which is itself an extension of the Merkle Sum Tree. It allows for compact proofs around the inclusion or exclusion of shares with particular namespace IDs.

Nodes contain three fields:

The base case (an empty tree) is defined as:

node.n_min = 0x0000000000000000
node.n_max = 0x0000000000000000
node.v = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

For leaf node node of share data d:

node.n_min = d.namespaceID
node.n_max = d.namespaceID
node.v = h(0x00, d.namespaceID, d.rawData)

The namespaceID message field here is the namespace ID of the leaf, which is a NAMESPACE_ID_BYTES-long byte array.

Leaves in an NMT must be lexicographically sorted by namespace ID in ascending order.

For internal node node with children l and r:

node.n_min = min(l.n_min, r.n_min)
if l.n_min == PARITY_SHARE_NAMESPACE_ID
  node.n_max = PARITY_SHARE_NAMESPACE_ID
else if r.n_min == PARITY_SHARE_NAMESPACE_ID
  node.n_max = l.n_max
else
  node.n_max = max(l.n_max, r.n_max)
node.v = h(0x01, l.n_min, l.n_max, l.v, r.n_min, r.n_max, r.v)

Note that the above snippet leverages the property that leaves are sorted by namespace ID: if l.n_min is PARITY_SHARE_NAMESPACE_ID, so must {l,r}.n_max. By construction, either both the min and max namespace IDs of a node will be PARITY_SHARE_NAMESPACE_ID, or neither will: if r.n_min is PARITY_SHARE_NAMESPACE_ID, so must r.n_max.

For some intuition: the min and max namespace IDs for subtree roots with at least one non-parity leaf (which includes the root of an NMT, as the right half of an NMT as used in Celestia will be parity shares) ignore the namespace ID for the parity leaves. Subtree roots with only parity leaves have their min and max namespace ID set to PARITY_SHARE_NAMESPACE_ID. This allows for shorter proofs into the tree than if the namespace ID of parity shares was not ignored (which would cause the max namespace ID of the root to always be PARITY_SHARE_NAMESPACE_ID).

A compact commitment can be computed by taking the hash of the serialized root node.

NamespaceMerkleTreeInclusionProof

When verifying an NMT proof, the root hash is checked by reconstructing the root node root_node with the computed root_node.v (computed as with a plain Merkle proof) and the provided rootNamespaceIDMin and rootNamespaceIDMax as the root_node.n_min and root_node.n_max, respectively.

Sparse Merkle Tree

Sparse Merkle Trees (SMTs) are sparse, i.e. they contain mostly empty leaves. They can be used as key-value stores for arbitrary data, as each leaf is keyed by its index in the tree. Storage efficiency is achieved through clever use of implicit defaults, avoiding the need to store empty leaves.

Additional rules are added on top of plain binary Merkle trees:

1. Default values are given to leaf nodes with empty leaves.
2. While the above rule is sufficient to pre-compute the values of intermediate nodes that are roots of empty subtrees, a further simplification is to extend this default value to all nodes that are roots of empty subtrees. The 32-byte zero, i.e. 0x0000000000000000000000000000000000000000000000000000000000000000, is used as the default value. This rule takes precedence over the above one.
3. The number of hashing operations can be reduced to be logarithmic in the number of non-empty leaves on average, assuming a uniform distribution of non-empty leaf keys. An internal node that is the root of a subtree that contains exactly one non-empty leaf is replaced by that leaf's leaf node.

Nodes contain a single field:

In the base case, where a sparse Merkle tree has height = 0, the root of a tree is defined as the hash of the empty string:

node.v = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

When a sparse Merkle tree has a height of 0, it can have no leaves, and, therefore, no default value children. The root is then calculated as the hash of the empty string, similar to that of an empty binary Merkle tree.

For a tree with height > 0, the root of an empty tree is defined as the default value:

node.v = 0x0000000000000000000000000000000000000000000000000000000000000000

Note that this is in contrast to the base case of the sparse and binary Merkle trees, where the root is the hash of the empty string. When a sparse Merkle tree has a height greater than 0, a new tree instance is composed of default value leaves. Nodes containing only default value children have the default value as well. Applying these rules recursively percolates the default value up to the tree's root.

For leaf node node of leaf data d with key k:

node.v = h(0x00, k, h(serialize(d)))

The key of leaf nodes must be prepended, since the index of a leaf node that is not at maximum depth cannot be determined without this information. Leaf values are hashed so that they do not need to be included in full in non-membership proofs.

For internal node node with children l and r:

node.v = h(0x01, l.v, r.v)

SparseMerkleTreeInclusionProof

SMTs can further be extended with compact proofs. Merkle proofs are composed, among other things, of a list of sibling node values. We note that, since nodes that are roots of empty subtrees have known values (the default value), these values do not need to be provided explicitly; it is sufficient to simply identify which siblings in the Merkle branch are roots of empty subtrees, which can be done with one bit per sibling.

For a Merkle branch of height h, an h-bit value is appended to the proof. The lowest bit corresponds to the sibling of the leaf node, and each higher bit corresponds to the next parent. A value of 1 indicates that the next value in the list of values provided explicitly in the proof should be used, and a value of 0 indicates that the default value should be used.

A proof into an SMT is structured as:

The includedSiblings is ordered by most-significant-byte first, with each byte ordered by most-significant-bit first. The lowest bit corresponds to the leaf node level.

Erasure Coding

In order to enable trust-minimized light clients (i.e. light clients that do not rely on an honest majority of validating state assumption), it is critical that light clients can determine whether the data in each block is available or not, without downloading the whole block itself. The technique used here was formally described in the paper Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities.

The remainder of the subsections below specify the 2D Reed-Solomon erasure coding scheme used, along with the format of shares and how available data is arranged into shares.

Reed-Solomon Erasure Coding

Note that while data is laid out in a two-dimensional square, rows and columns are erasure coded using a standard one-dimensional encoding.

Reed-Solomon erasure coding is used as the underlying coding scheme. The parameters are:

• 16-bit Galois field
• availableDataOriginalSquareSize original pieces (maximum of AVAILABLE_DATA_ORIGINAL_SQUARE_MAX)
• availableDataOriginalSquareSize parity pieces (maximum of AVAILABLE_DATA_ORIGINAL_SQUARE_MAX) (i.e availableDataOriginalSquareSize * 2 total pieces), for an erasure efficiency of 50%. In other words, any 50% of the pieces from the availableDataOriginalSquareSize * 2 total pieces are enough to recover the original data.
• SHARE_SIZE bytes per piece

Note that availableDataOriginalSquareSize may vary each block, and is decided by the block proposer of that block. Leopard-RS is a C library that implements the above scheme with quasilinear runtime.

2D Reed-Solomon Encoding Scheme

The 2-dimensional data layout is described in this section. The roots of NMTs for each row and column across four quadrants of data in a 2k * 2k matrix of shares, Q0 to Q3 (shown below), must be computed. In other words, 2k row roots and 2k column roots must be computed. The row and column roots are stored in the availableDataCommitments of the AvailableDataHeader.

The data of Q0 is the original data, and the remaining quadrants are parity data. Setting k = availableDataOriginalSquareSize, the original data first must be split into shares and arranged into a k * k matrix. Then the parity data can be computed.

Where A -> B indicates that B is computed using erasure coding from A:

• Q0 -> Q1 for each row in Q0 and Q1
• Q0 -> Q2 for each column in Q0 and Q2
• Q2 -> Q3 for each row in Q2 and Q3

Note that the parity data in Q3 will be identical if it is vertically extended from Q1 or horizontally extended from Q2.

As an example, the parity data in the second column of Q2 (in striped purple) is computed by extending the original data in the second column of Q0 (in solid blue).

Now that all four quadrants of the 2k * 2k matrix are filled, the row and column roots can be computed. To do so, each row/column is used as the leaves of a NMT, for which the compact root is computed (i.e. an extra hash operation over the NMT root is used to produce a single HashDigest). In this example, the fourth row root value is computed as the NMT root of the fourth row of Q0 and the fourth row of Q1 as leaves.

Finally, the availableDataRoot of the block Header is computed as the Merkle root of the binary Merkle tree with the row and column roots as leaves, in that order.

Share

A share is a fixed-size data chunk associated with a namespace ID, whose data will be erasure-coded and committed to in Namespace Merkle trees.

A sequence is a contiguous set of shares that contain semantically relevant data. A sequence should be parsed together because data may be split across share boundaries. One sequence exists per reserved namespace and per message.

• The first NAMESPACE_ID_BYTES of a share's raw data rawData is the namespace ID of that share, namespaceID.
• The next SHARE_INFO_BYTES bytes are for share information with the following structure:
  • The first 7 bits represent the share version in big endian form (initially, this will be 0000000 for version 0);
  • The last bit is a sequence start indicator, that is 1 if the share is at the start of a sequence or 0 if it is a continuation share.

The remainder of a share's raw data rawData is interpreted differently depending on the namespace ID.

Compact Share

For shares with a reserved namespace ID through NAMESPACE_ID_MAX_RESERVED:

Note The first NAMESPACE_ID_BYTES of a share's raw data rawData is the namespace ID of that share, namespaceID. The next SHARE_INFO_BYTES bytes are for share information.

• If this is the first share of a sequence, the next SEQUENCE_BYTES contain a big endian uint32 that represents the length of the sequence that follows in bytes.
• The next SHARE_RESERVED_BYTES bytes are the starting byte of the length of the canonically serialized first request that starts in the share, or 0 if there is none, as an unsigned varint.
• The remaining SHARE_SIZE-NAMESPACE_ID_BYTES-SHARE_INFO_BYTES - SEQUENCE_BYTES bytes (only if this is the first share of a sequence) - SHARE_RESERVED_BYTES bytes are transactions, intermediate state roots, or PayForBlob transaction data. Each transaction, intermediate state root, or PayForBlob transaction is prefixed with a varint of the length of that unit.
• If there is insufficient transaction, intermediate state root, or PayForBlob transaction data to fill the share, the remaining bytes are filled with 0.

First share in a sequence:

where reserved bytes would be 17 as a binary big endian uint32 ([0b00000000, 0b00000000, 0b00000000, 0b00010001]).

Continuation share in a sequence:

where reserved bytes would be 80 as a binary big endian uint32 ([0b00000000, 0b00000000, 0b00000000, 0b01010000]).

Sparse Share

For shares with a namespace ID above NAMESPACE_ID_MAX_RESERVED but below PARITY_SHARE_NAMESPACE_ID:

Note The first NAMESPACE_ID_BYTES of a share's raw data rawData is the namespace ID of that share, namespaceID. The next SHARE_INFO_BYTES bytes are for share information.

• If this is the first share of a sequence, the next SEQUENCE_BYTES contain a big endian uint32 that represents the length of the sequence that follows in bytes.
• The remaining SHARE_SIZE-NAMESPACE_ID_BYTES-SHARE_INFO_BYTES - SEQUENCE_BYTES bytes (only if this is the first share of a sequence) bytes are message data. Message data are opaque bytes of data that are included in the block but do not impact the state. In other words, the remaining bytes have no special meaning and are simply used to store data.
• If there is insufficient message data to fill the share, the remaining bytes are filled with 0.

First share in a sequence:

Continuation share in a sequence:

Parity Share

For shares with a namespace ID equal to PARITY_SHARE_NAMESPACE_ID (i.e. parity shares):

• Bytes carry no special meaning.

Namespace Padding Share

A namespace padding share acts as padding between blobs so that the subsequent blob may begin at an index that conforms to the non-interactive default rules. A namespace padding share contains the namespace ID of the blob that precedes it in the data square so that the data square can retain the property that all shares are ordered by namespace.

The first NAMESPACE_ID_BYTES of a share's raw data rawData is the namespace ID of the blob that precedes this padding share. The next SHARE_INFO_BYTES bytes are for share information. The sequence start indicator is always 1. The version bits are filled with the share version. The sequence length is zeroed out. The remaining SHARE_SIZE-NAMESPACE_ID_BYTES-SHARE_INFO_BYTES - SEQUENCE_BYTES bytes are filled with 0.

Reserved Padding Share

Reserved padding shares are placed after the last reserved namespace share in the data square so that the first blob can start at an index that conforms to non-interactive default rules. Clients can safely ignore the contents of these shares because they don't contain any significant data.

For shares with a namespace ID equal to RESERVED_PADDING_NAMESPACE_ID (i.e. reserved padding shares):

The first NAMESPACE_ID_BYTES of a share's raw data rawData is the namespace ID of that share, namespaceID. The next SHARE_INFO_BYTES bytes are for share information. The sequence start indicator is always 1. The version bits are filled with the share version. The sequence length is zeroed out. The remaining SHARE_SIZE-NAMESPACE_ID_BYTES-SHARE_INFO_BYTES - SEQUENCE_BYTES bytes are filled with 0.

Tail Padding Share

Tail padding shares are placed after the last blob in the data square so that the number of shares in the data square is a perfect square. Clients can safely ignore the contents of these shares because they don't contain any significant data.

For shares with a namespace ID equal to TAIL_PADDING_NAMESPACE_ID (i.e. tail padding shares):

The first NAMESPACE_ID_BYTES of a share's raw data rawData is the namespace ID of that share, namespaceID. The next SHARE_INFO_BYTES bytes are for share information. The sequence start indicator is always 1. The version bits are filled with the share version. The sequence length is zeroed out. The remaining SHARE_SIZE-NAMESPACE_ID_BYTES-SHARE_INFO_BYTES - SEQUENCE_BYTES bytes are filled with 0.

Arranging Available Data Into Shares

The previous sections described how some original data, arranged into a k * k matrix, can be extended into a 2k * 2k matrix and committed to with NMT roots. This section specifies how available data (which includes transactions, intermediate state roots, PayForBlob transactions, and messages) is arranged into the matrix in the first place.

Then,

1. For each of transactionData, intermediateStateRootData, PayForBlob transactions, serialize:
   1. For each request in the list:
      1. Serialize the request (individually).
      2. Compute the length of each serialized request, serialize the length, and pre-pend the serialized request with its serialized length.
   2. Split up the length/request pairs into SHARE_SIZE-NAMESPACE_ID_BYTES-SHARE_RESERVED_BYTES-byte chunks.
   3. Create a share out of each chunk. This data has a reserved namespace ID, so the first NAMESPACE_ID_BYTES+SHARE_RESERVED_BYTES bytes for these shares must be set specially.
2. Concatenate the lists of shares in the order: transactions, intermediate state roots, PayForBlob transactions.

Note that by construction, each share only has a single namespace, and that the list of concatenated shares is lexicographically ordered by namespace ID.

These shares are arranged in the first quadrant (Q0) of the availableDataOriginalSquareSize*2 * availableDataOriginalSquareSize*2 available data matrix in row-major order. In the example below, each reserved data element takes up exactly one share.

Each message in the list messageData:

1. Serialize the message (individually).
2. Compute the length of each serialized message, serialize the length, and pre-pend the serialized message with its serialized length.
3. Split up the length/message pairs into SHARE_SIZE-NAMESPACE_ID_BYTES-byte chunks.
4. Create a share out of each chunk. The first NAMESPACE_ID_BYTES bytes for these shares is set to the namespace ID.

For each message, it is placed in the available data matrix, with row-major order, as follows:

1. Place the first share of the message at the next unused location in the matrix, then place the remaining shares in the following locations.

Transactions must commit to a Merkle root of a list of hashes that are each guaranteed (assuming the block is valid) to be subtree roots in one or more of the row NMTs. For additional info, see the rationale document for this section.

However, with only the rule above, interaction between the block producer and transaction sender may be required to compute a commitment to the message the transaction sender can sign over. To remove interaction, messages can optionally be laid out using a non-interactive default:

1. Place the first share of the message at the next unused location in the matrix whose column is aligned with the largest power of 2 that is not larger than the message length or availableDataOriginalSquareSize, then place the remaining shares in the following locations unless there are insufficient unused locations in the row.
2. If there are insufficient unused locations in the row, place the first share of the message at the first column of the next row. Then place the remaining shares in the following locations. By construction, any message whose length is greater than availableDataOriginalSquareSize will be placed in this way.

In the example below, two messages (of lengths 2 and 1, respectively) are placed using the aforementioned default non-interactive rules.

The non-interactive default rules may introduce empty shares that do not belong to any message (in the example above, the top-right share is empty). These are zeroes with namespace ID equal to the either TAIL_TRANSACTION_PADDING_NAMESPACE_ID if between a request with a reserved namespace ID and a message, or the namespace ID of the previous message if succeeded by a message. See the rationale doc for more info.

Available Data

TransactionData

WrappedTransaction

Wrapped transactions include additional metadata by the block proposer that is committed to in the available data matrix.

Transaction

SignedTransactionData

enum TransactionType : uint8_t {
    Transfer = 1,
    MsgPayForData = 2,
    CreateValidator = 3,
    BeginUnbondingValidator = 4,
    UnbondValidator = 5,
    CreateDelegation = 6,
    BeginUnbondingDelegation = 7,
    UnbondDelegation = 8,
    Burn = 9,
    RedelegateCommission = 10,
    RedelegateReward = 11,
};

Signed transaction data comes in a number of types:

1. Transfer
2. MsgPayForData
3. CreateValidator
4. BeginUnbondingValidator
5. UnbondValidator
6. CreateDelegation
7. BeginUnbondingDelegation
8. UnbondDelegation
9. Burn
10. RedelegateCommission
11. RedelegateReward

Common fields are denoted here to avoid repeating descriptions:

SignedTransactionDataTransfer

Transfers amount coins to to.

SignedTransactionDataMsgPayForData

Pays for the inclusion of a message in the same block.

The commitment to message shares messageShareCommitment is a Merkle root of message share roots. Each message share root is a subtree root in a row NMT. For rationale, see rationale doc.

SignedTransactionDataCreateValidator

Create a new Validator at this address.

SignedTransactionDataBeginUnbondingValidator

Begin unbonding the Validator at this address.

SignedTransactionDataUnbondValidator

Finish unbonding the Validator at this address.

SignedTransactionDataCreateDelegation

Create a new Delegation of amount coins worth of voting power for validator with address to.

SignedTransactionDataBeginUnbondingDelegation

Begin unbonding the Delegation at this address.

SignedTransactionDataUnbondDelegation

Finish unbonding the Delegation at this address.

SignedTransactionDataBurn

SignedTransactionRedelegateCommission

Assigns validator's pending commission to a delegation.

SignedTransactionRedelegateReward

Adds delegation's pending rewards to voting power.

PayForBlobData

IntermediateStateRootData

WrappedIntermediateStateRoot

IntermediateStateRoot

MessageData

Message

State

The state of the Celestia chain is intentionally restricted to containing only account balances and the validator set metadata. One unified Sparse Merkle Tree is maintained for the entire chain state, the state tree. The root of this tree is committed to in the block header.

The state tree is separated into 2**(8*STATE_SUBTREE_RESERVED_BYTES) subtrees, each of which can be used to store a different component of the state. This is done by slicing off the highest STATE_SUBTREE_RESERVED_BYTES bytes from the key and replacing them with the appropriate reserved state subtree ID. Reducing the key size within subtrees also reduces the collision resistance of keys by 8*STATE_SUBTREE_RESERVED_BYTES bits, but this is not an issue due the number of bits removed being small.

A number of subtrees are maintained:

1. Accounts
2. Active validator set
3. Inactive validator set
4. Delegation set
5. Message shares paid for

StateElement

Data structure for state elements is given below:

Account

enum AccountStatus : uint8_t {
    None = 1,
    DelegationBonded = 2,
    DelegationUnbonding = 3,
    ValidatorQueued = 4,
    ValidatorBonded = 5,
    ValidatorUnbonding = 6,
    ValidatorUnbonded = 7,
};

The status of an account indicates weather it is a validator (AccountStatus.Validator*), delegating to a validator (AccountStatus.Delegation*), or neither (AccountStatus.None). Being a validator and delegating are mutually exclusive, and only a single validator can be delegated to.

Delegations have two statuses:

1. DelegationBonded: This delegation is enabled for a Queued or Bonded validator. Delegations to a Queued validator can be withdrawn immediately, while delegations for a Bonded validator must be unbonded first.
2. DelegationUnbonding: This delegation is unbonding. It will remain in this status for at least UNBONDING_DURATION blocks, and while unbonding may still be slashed. Once the unbonding duration has expired, the delegation can be withdrawn.

Validators have four statuses:

1. ValidatorQueued: This validator has entered the queue to become an active validator. Once the next validator set transition occurs, if this validator has sufficient voting power (including its own stake and stake delegated to it) to be in the top MAX_VALIDATORS validators by voting power, it will become an active, i.e. ValidatorBonded validator. Until bonded, this validator can immediately exit the queue.
2. ValidatorBonded: This validator is active and bonded. It can propose new blocks and vote on proposed blocks. Once bonded, an active validator must go through an unbonding process until its stake can be freed.
3. ValidatorUnbonding: This validator is in the process of unbonding, which can be voluntary (the validator decided to stop being an active validator) or forced (the validator committed a slashable offence and was kicked from the active validator set). Validators will remain in this status for at least UNBONDING_DURATION blocks, and while unbonding may still be slashed.
4. ValidatorUnbonded: This validator has completed its unbonding and has withdrawn its stake. The validator object will remain in this status until delegatedCount reaches zero, at which point it is destroyed.

In the accounts subtree, accounts (i.e. leaves) are keyed by the hash of their address. The first byte is then replaced with ACCOUNTS_SUBTREE_ID.

Delegation

Delegation objects represent a delegation.

In the delegation subtree, delegations are keyed by the hash of their address. The first byte is then replaced with DELEGATIONS_SUBTREE_ID.

Validator

Validator objects represent all the information needed to be keep track of a validator.

In the validators subtrees, validators are keyed by the hash of their address. The first byte is then replaced with ACTIVE_VALIDATORS_SUBTREE_ID for the active validator set or INACTIVE_VALIDATORS_SUBTREE_ID for the inactive validator set. Active validators are bonded, (i.e. ValidatorBonded), while inactive validators are not bonded (i.e. ValidatorUnbonded). By construction, the validators subtrees will be a subset of a mirror of the accounts subtree.

The validator queue (i.e. validators with status ValidatorQueued) is a subset of the inactive validator set. This queue is represented as a linked list, with each validator pointing to the next validator in the queue, and the head of the linked list stored in ValidatorQueueHead.

ActiveValidatorCount

Since the active validator set is stored in a Sparse Merkle Tree, there is no compact way of proving that the number of active validators exceeds MAX_VALIDATORS without keeping track of the number of active validators. The active validator count is stored in the active validators subtree, and is keyed with 0 (i.e. 0x0000000000000000000000000000000000000000000000000000000000000000), with the first byte replaced with ACTIVE_VALIDATORS_SUBTREE_ID.

ActiveVotingPower

Since the active validator set is stored in a Sparse Merkle Tree, there is no compact way of proving the active voting power. The active voting power is stored in the active validators subtree, and is keyed with 1 (i.e. 0x0000000000000000000000000000000000000000000000000000000000000001), with the first byte replaced with ACTIVE_VALIDATORS_SUBTREE_ID.

ProposerBlockReward

The current block reward for the proposer is kept track of here. This is keyed with 2 (i.e. 0x0000000000000000000000000000000000000000000000000000000000000002), with the first byte replaced with ACTIVE_VALIDATORS_SUBTREE_ID.

ProposerInitialVotingPower

The proposer's voting power at the beginning of the block is kept track of here. This is keyed with 3 (i.e. 0x0000000000000000000000000000000000000000000000000000000000000003), with the first byte replaced with ACTIVE_VALIDATORS_SUBTREE_ID.

ValidatorQueueHead

The head of the queue for validators that are waiting to become active validators is stored in the inactive validators subtree, and is keyed with 0 (i.e. 0x0000000000000000000000000000000000000000000000000000000000000000), with the first byte replaced with INACTIVE_VALIDATORS_SUBTREE_ID.

If the queue is empty, head is set to the default value (i.e. the hash of the leaf is the default value for a Sparse Merkle Tree).

PeriodEntry

Decimal

Represents a (potentially) non-integer number.

MessagePaid

MessagePaidHead

The head of the list of paid message shares is stored in the message share paid subtree, and is keyed with 0 (i.e. 0x0000000000000000000000000000000000000000000000000000000000000000), with the first byte replaced with MESSAGE_PAID_SUBTREE_ID.

If the paid list is empty, head is set to the default value (i.e. the hash of the leaf is the default value for a Sparse Merkle Tree).

Consensus Parameters

Various consensus parameters are committed to in the block header, such as limits and constants.

In order to compute the consensusHash field in the block header, the above list of parameters is hashed.

Consensus Rules

System Parameters

Units

Constants

Reserved Namespace IDs

Reserved State Subtree IDs

Rewards and Penalties

Leader Selection

TODO

Fork Choice

The Tendermint consensus protocol is fork-free by construction under an honest majority of stake assumption.

If a block has a valid commit, it is part of the canonical chain. If equivocation evidence is detected for more than 1/3 of voting power, the node must halt.

Block Validity

The validity of a newly-seen block, block, is determined by two components, detailed in subsequent sections:

1. Block structure: whether the block header is valid, and data in a block is arranged into a valid and matching data root (i.e. syntax).
2. State transition: whether the application of transactions in the block produces a matching and valid state root (i.e. semantics).

Pseudocode in this section is not in any specific language and should be interpreted as being in a neutral and sane language.

Block Structure

Before executing state transitions, the structure of the block must be verified.

The following block fields are acquired from the network and parsed (i.e. deserialized). If they cannot be parsed, the block is ignored but is not explicitly considered invalid by consensus rules. Further implications of ignoring a block are found in the networking spec.

1. block.header
2. block.availableDataHeader
3. block.lastCommit

If the above fields are parsed successfully, the available data block.availableData is acquired in erasure-coded form as a list of share rows, then parsed. If it cannot be parsed, the block is ignored but not explicitly invalid, as above.

block.header

The block header block.header (header for short) is the first thing that is downloaded from the new block, and commits to everything inside the block in some way. For previous block prev (if prev is not known, then the block is ignored), and previous block header prev.header, the following checks must be true:

availableDataOriginalSquareSize is computed as described here.

1. header.height == prev.header.height + 1.
2. header.timestamp > prev.header.timestamp.
3. header.lastHeaderHash == the header hash of prev.
4. header.lastCommitHash == the hash of lastCommit.
5. header.consensusHash == the value computed here.
6. header.stateCommitment == the root of the state, computed with the application of all state transitions in this block.
7. availableDataOriginalSquareSize <= AVAILABLE_DATA_ORIGINAL_SQUARE_MAX.
8. header.availableDataRoot == the Merkle root of the tree with the row and column roots of block.availableDataHeader as leaves.
9. header.proposerAddress == the leader for header.height.

block.availableDataHeader

The available data header block.availableDataHeader (availableDataHeader for short) is then processed. This commits to the available data, which is only downloaded after the consensus commit is processed. The following checks must be true:

1. Length of availableDataHeader.rowRoots == availableDataOriginalSquareSize * 2.
2. Length of availableDataHeader.colRoots == availableDataOriginalSquareSize * 2.
3. The length of each element in availableDataHeader.rowRoots and availableDataHeader.colRoots must be 32.

block.lastCommit

The last commit block.lastCommit (lastCommit for short) is processed next. This is the Tendermint commit (i.e. polka of votes) for the previous block. For previous block prev and previous block header prev.header, the following checks must be true:

1. lastCommit.height == prev.header.height.
2. lastCommit.round >= 1.
3. lastCommit.headerHash == the header hash of prev.
4. Length of lastCommit.signatures <= MAX_VALIDATORS.
5. Each of lastCommit.signatures must be a valid CommitSig
6. The sum of the votes for prev in lastCommit must be at least 2/3 (rounded up) of the voting power of prev's next validator set.

block.availableData

The block's available data (analogous to transactions in contemporary blockchain designs) block.availableData (availableData for short) is finally processed. The list of share rows is parsed into the actual data structures using the reverse of the process to encode available data into shares; if parsing fails here, the block is invalid.

Once parsed, the following checks must be true:

1. The commitments of the erasure-coded extended availableData must match those in header.availableDataHeader. Implicitly, this means that both rows and columns must be ordered lexicographically by namespace ID since they are committed to in a Namespace Merkle Tree.
2. Length of availableData.intermediateStateRootData == length of availableData.transactionData + length of availableData.payForBlobData + 2. (Two additional state transitions are the begin and end block implicit transitions.)

State Transitions

Once the basic structure of the block has been validated, state transitions must be applied to compute the new state and state root.

For this section, the variable state represents the state tree, with state.accounts[k], state.inactiveValidatorSet[k], state.activeValidatorSet[k], and state.delegationSet[k] being shorthand for the leaf in the state tree in the accounts, inactive validator set, active validator set, and delegation set subtrees with pre-hashed key k. E.g. state.accounts[a] is shorthand for state[(ACCOUNTS_SUBTREE_ID << 8*(32-STATE_SUBTREE_RESERVED_BYTES)) | ((-1 >> 8*STATE_SUBTREE_RESERVED_BYTES) & hash(a))].

State transitions are applied in the following order:

1. Begin block.
2. Transactions.
3. End block.

block.availableData.transactionData

Transactions are applied to the state. Note that transactions mutate the state (essentially, the validator set and minimal balances), while messages do not.

block.availableData.transactionData is simply a list of WrappedTransactions. For each wrapped transaction in this list, wrappedTransaction, with index i (starting from 0), the following checks must be true:

1. wrappedTransaction.index == i.

For wrappedTransaction's transaction transaction, the following checks must be true:

1. transaction.signature must be a valid signature over transaction.signedTransactionData.

Finally, each wrappedTransaction is processed depending on its transaction type. These are specified in the next subsections, where tx is short for transaction.signedTransactionData, and sender is the recovered signing address. We will define a few helper functions:

tipCost(y, z) = y * z
totalCost(x, y, z) = x + tipCost(y, z)

where x above is the amount of coins sent by the transaction authorizer, y above is the tip rate set in the transaction, and z above is the measure of the block space used by the transaction (i.e. size in bytes).

Four additional helper functions are defined to manage the validator queue:

1. findFromQueue(power), which returns the address of the last validator in the validator queue with voting power greater than or equal to power, or 0 if the queue is empty or no validators in the queue have at least power voting power.
2. parentFromQueue(address), which returns the address of the parent in the validator queue of the validator with address address, or 0 if address is not in the queue or is the head of the queue.
3. validatorQueueInsert, defined as

function validatorQueueInsert(validator)
    # Insert the new validator into the linked list
    parent = findFromQueue(validator.votingPower)
    if parent != 0
        if state.accounts[parent].status == AccountStatus.ValidatorBonded
            validator.next = state.activeValidatorSet[parent].next
            state.activeValidatorSet[parent].next = sender
        else
            validator.next = state.inactiveValidatorSet[parent].next
            state.inactiveValidatorSet[parent].next = sender
    else
        validator.next = state.validatorQueueHead
        state.validatorQueueHead = sender

4. validatorQueueRemove, defined as

function validatorQueueRemove(validator, sender)
    # Remove existing validator from the linked list
    parent = parentFromQueue(sender)
    if parent != 0
        if state.accounts[parent].status == AccountStatus.ValidatorBonded
            state.activeValidatorSet[parent].next = validator.next
            validator.next = 0
        else
            state.inactiveValidatorSet[parent].next = validator.next
            validator.next = 0
    else
        state.validatorQueueHead = validator.next
        validator.next = 0

Note that light clients cannot perform a linear search through a linked list, and are instead provided logarithmic proofs (e.g. in the case of parentFromQueue, a proof to the parent is provided, which should have address as its next validator).

In addition, three helper functions to manage the message paid list:

1. findFromMessagePaidList(start), which returns the transaction ID of the last transaction in the message paid list with finish greater than start, or 0 if the list is empty or no transactions in the list have at least start finish.
2. parentFromMessagePaidList(txid), which returns the transaction ID of the parent in the message paid list of the transaction with ID txid, or 0 if txid is not in the list or is the head of the list.
3. messagePaidListInsert, defined as

function messagePaidListInsert(tx, txid)
    # Insert the new transaction into the linked list
    parent = findFromMessagePaidList(tx.messageStartIndex)
    state.messagesPaid[txid].start = tx.messageStartIndex
    numShares = ceil(tx.messageSize / SHARE_SIZE)
    state.messagesPaid[txid].finish = tx.messageStartIndex + numShares - 1
    if parent != 0
        state.messagesPaid[txid].next = state.messagesPaid[parent].next
        state.messagesPaid[parent].next = txid
    else
        state.messagesPaid[txid].next = state.messagePaidHead
        state.messagePaidHead = txid

We define a helper function to compute F1 entries:

function compute_new_entry(reward, power)
    if power == 0
        return 0
    return reward // power

After applying a transaction, the new state state root is computed.

SignedTransactionDataTransfer

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.Transfer.
2. totalCost(tx.amount, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.

Apply the following to the state:

state.accounts[sender].nonce += 1

state.accounts[sender].balance -= totalCost(tx.amount, tx.fee.tipRate, bytesPaid)
state.accounts[tx.to].balance += tx.amount

state.activeValidatorSet.proposerBlockReward += tipCost(bytesPaid)

SignedTransactionDataMsgPayForData

bytesPaid = len(tx) + tx.messageSize
currentStartFinish = state.messagesPaid[findFromMessagePaidList(tx.messageStartIndex)]
parentStartFinish = state.messagesPaid[parentFromMessagePaidList(findFromMessagePaidList(tx.messageStartIndex))]

The following checks must be true:

1. tx.type == TransactionType.MsgPayForData.
2. totalCost(0, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. The ceil(tx.messageSize / SHARE_SIZE) shares starting at index tx.messageStartIndex must:
   1. Have namespace ID tx.messageNamespaceID.
5. tx.messageShareCommitment == computed as described here.
6. parentStartFinish.finish < tx.messageStartIndex.
7. currentStartFinish.start == 0 or currentStartFinish.start > tx.messageStartIndex + ceil(tx.messageSize / SHARE_SIZE).

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(tx.amount, tx.fee.tipRate, bytesPaid)

messagePaidListInsert(tx, id(tx))

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionDataCreateValidator

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.CreateValidator.
2. totalCost(0, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. tx.commissionRate.denominator > 0.
5. tx.commissionRate.numerator <= tx.commissionRate.denominator.
6. state.accounts[sender].status == AccountStatus.None.

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(0, tx.fee.tipRate, bytesPaid)
state.accounts[sender].status = AccountStatus.ValidatorQueued

validator = new Validator
validator.commissionRate = tx.commissionRate
validator.delegatedCount = 0
validator.votingPower = 0
validator.pendingRewards = 0
validator.latestEntry = PeriodEntry(0)
validator.unbondingHeight = 0
validator.isSlashed = false

validatorQueueInsert(validator)

state.inactiveValidatorSet[sender] = validator

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionDataBeginUnbondingValidator

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.BeginUnbondingValidator.
2. totalCost(0, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. state.accounts[sender].status == AccountStatus.ValidatorQueued or state.accounts[sender].status == AccountStatus.ValidatorBonded.

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(0, tx.fee.tipRate, bytesPaid)
state.accounts[sender].status = ValidatorStatus.Unbonding

if state.accounts[sender].status == AccountStatus.ValidatorQueued
    validator = state.inactiveValidatorSet[sender]
else if state.accounts[sender].status == AccountStatus.ValidatorBonded
    validator = state.activeValidatorSet[sender]
    delete state.activeValidatorSet[sender]

validator.unbondingHeight = block.height + 1
validator.latestEntry += compute_new_entry(validator.pendingRewards, validator.votingPower)
validator.pendingRewards = 0

validatorQueueRemove(validator, sender)

state.inactiveValidatorSet[sender] = validator

state.activeValidatorSet.activeVotingPower -= validator.votingPower

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionDataUnbondValidator

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.UnbondValidator.
2. totalCost(0, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. state.accounts[sender].status == AccountStatus.ValidatorUnbonding.
5. state.inactiveValidatorSet[sender].unbondingHeight + UNBONDING_DURATION < block.height.

Apply the following to the state:

validator = state.inactiveValidatorSet[sender]

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(0, tx.fee.tipRate, bytesPaid)
state.accounts[sender].status = AccountStatus.ValidatorUnbonded

state.accounts[sender].balance += validator.commissionRewards

state.inactiveValidatorSet[sender] = validator

if validator.delegatedCount == 0
    state.accounts[sender].status = AccountStatus.None
    delete state.inactiveValidatorSet[sender]

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionDataCreateDelegation

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.CreateDelegation.
2. totalCost(tx.amount, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. state.accounts[tx.to].status == AccountStatus.ValidatorQueued or state.accounts[tx.to].status == AccountStatus.ValidatorBonded.
4. tx.nonce == state.accounts[sender].nonce + 1.
5. state.accounts[sender].status == AccountStatus.None.

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(tx.amount, tx.fee.tipRate, bytesPaid)
state.accounts[sender].status = AccountStatus.DelegationBonded

if state.accounts[tx.to].status == AccountStatus.ValidatorQueued
    validator = state.inactiveValidatorSet[tx.to]
else if state.accounts[tx.to].status == AccountStatus.ValidatorBonded
    validator = state.activeValidatorSet[tx.to]

delegation = new Delegation
delegation.status = DelegationStatus.Bonded
delegation.validator = tx.to
delegation.stakedBalance = tx.amount
delegation.beginEntry = validator.latestEntry
delegation.endEntry = PeriodEntry(0)
delegation.unbondingHeight = 0

validator.latestEntry += compute_new_entry(validator.pendingRewards, validator.votingPower)
validator.pendingRewards = 0
validator.delegatedCount += 1
validator.votingPower += tx.amount

# Update the validator in the linked list by first removing then inserting
validatorQueueRemove(validator, delegation.validator)
validatorQueueInsert(validator)

state.delegationSet[sender] = delegation

if state.accounts[tx.to].status == AccountStatus.ValidatorQueued
    state.inactiveValidatorSet[tx.to] = validator
else if state.accounts[tx.to].status == AccountStatus.ValidatorBonded
    state.activeValidatorSet[tx.to] = validator
    state.activeValidatorSet.activeVotingPower += tx.amount

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionDataBeginUnbondingDelegation

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.BeginUnbondingDelegation.
2. totalCost(0, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. state.accounts[sender].status == AccountStatus.DelegationBonded.

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(0, tx.fee.tipRate, bytesPaid)
state.accounts[sender].status = AccountStatus.DelegationUnbonding

delegation = state.delegationSet[sender]

if state.accounts[delegation.validator].status == AccountStatus.ValidatorQueued ||
      state.accounts[delegation.validator].status == AccountStatus.ValidatorUnbonding ||
      state.accounts[delegation.validator].status == AccountStatus.ValidatorUnbonded
    validator = state.inactiveValidatorSet[delegation.validator]
else if state.accounts[delegation.validator].status == AccountStatus.ValidatorBonded
    validator = state.activeValidatorSet[delegation.validator]

delegation.status = DelegationStatus.Unbonding
delegation.endEntry = validator.latestEntry
delegation.unbondingHeight = block.height + 1

validator.latestEntry += compute_new_entry(validator.pendingRewards, validator.votingPower)
validator.pendingRewards = 0
validator.delegatedCount -= 1
validator.votingPower -= delegation.stakedBalance

# Update the validator in the linked list by first removing then inserting
# Only do this if the validator is actually in the queue (i.e. bonded or queued)
if state.accounts[delegation.validator].status == AccountStatus.ValidatorBonded ||
      state.accounts[delegation.validator].status == AccountStatus.ValidatorQueued
    validatorQueueRemove(validator, delegation.validator)
    validatorQueueInsert(validator)

state.delegationSet[sender] = delegation

if state.accounts[delegation.validator].status == AccountStatus.ValidatorQueued ||
      state.accounts[delegation.validator].status == AccountStatus.ValidatorUnbonding ||
      state.accounts[delegation.validator].status == AccountStatus.ValidatorUnbonded
    state.inactiveValidatorSet[delegation.validator] = validator
else if state.accounts[delegation.validator].status == AccountStatus.ValidatorBonded
    state.activeValidatorSet[delegation.validator] = validator
    state.activeValidatorSet.activeVotingPower -= delegation.stakedBalance

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionDataUnbondDelegation

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.UnbondDelegation.
2. totalCost(0, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. state.accounts[sender].status == AccountStatus.DelegationUnbonding.
5. state.delegationSet[sender].unbondingHeight + UNBONDING_DURATION < block.height.

Apply the following to the state:

delegation = state.accounts[sender].delegationInfo

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(0, tx.fee.tipRate, bytesPaid)
state.accounts[sender].status = None

# Return the delegated stake
state.accounts[sender].balance += delegation.stakedBalance
# Also disperse rewards (commission has already been levied)
state.accounts[sender].balance += delegation.stakedBalance * (delegation.endEntry - delegation.beginEntry)

if state.accounts[delegation.validator].status == AccountStatus.ValidatorQueued ||
      state.accounts[delegation.validator].status == AccountStatus.ValidatorUnbonding
      state.accounts[delegation.validator].status == AccountStatus.ValidatorUnbonded
    validator = state.inactiveValidatorSet[delegation.validator]
else if state.accounts[delegation.validator].status == AccountStatus.ValidatorBonded
    validator = state.activeValidatorSet[delegation.validator]

if validator.delegatedCount == 0 &&
      state.accounts[delegation.validator].status == AccountStatus.ValidatorUnbonded
    state.accounts[delegation.validator].status = AccountStatus.None
    delete state.inactiveValidatorSet[delegation.validator]

delete state.accounts[sender].delegationInfo

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionDataBurn

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.Burn.
2. totalCost(tx.amount, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(tx.amount, tx.fee.tipRate, bytesPaid)

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionRedelegateCommission

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.RedelegateCommission.
2. totalCost(0, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. state.accounts[tx.to].status == AccountStatus.DelegationBonded.
5. state.accounts[sender].status == AccountStatus.ValidatorBonded.

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(0, tx.fee.tipRate, bytesPaid)

delegation = state.delegationSet[tx.to]
validator = state.activeValidatorSet[delegation.validator]

# Force-redelegate pending rewards for delegation
pendingRewards = delegation.stakedBalance * (validator.latestEntry - delegation.beginEntry)
delegation.stakedBalance += pendingRewards
delegation.beginEntry = validator.latestEntry

validator.latestEntry += compute_new_entry(validator.pendingRewards, validator.votingPower)
validator.pendingRewards = 0

# Assign pending commission rewards to delegation
commissionRewards = validator.commissionRewards
delegation.stakedBalance += commissionRewards
validator.commissionRewards = 0

# Update voting power
validator.votingPower += pendingRewards + commissionRewards
state.activeValidatorSet.activeVotingPower += pendingRewards + commissionRewards

state.delegationSet[tx.to] = delegation
state.activeValidatorSet[delegation.validator] = validator

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

SignedTransactionRedelegateReward

bytesPaid = len(tx)

The following checks must be true:

1. tx.type == TransactionType.RedelegateReward.
2. totalCost(0, tx.fee.tipRate, bytesPaid) <= state.accounts[sender].balance.
3. tx.nonce == state.accounts[sender].nonce + 1.
4. state.accounts[sender].status == AccountStatus.DelegationBonded.
5. state.accounts[state.delegationSet[sender].validator].status == AccountStatus.ValidatorBonded.

Apply the following to the state:

state.accounts[sender].nonce += 1
state.accounts[sender].balance -= totalCost(0, tx.fee.tipRate, bytesPaid)

delegation = state.delegationSet[sender]
validator = state.activeValidatorSet[delegation.validator]

# Redelegate pending rewards for delegation
pendingRewards = delegation.stakedBalance * (validator.latestEntry - delegation.beginEntry)
delegation.stakedBalance += pendingRewards
delegation.beginEntry = validator.latestEntry

validator.latestEntry += compute_new_entry(validator.pendingRewards, validator.votingPower)
validator.pendingRewards = 0

# Update voting power
validator.votingPower += pendingRewards
state.activeValidatorSet.activeVotingPower += pendingRewards

state.delegationSet[sender] = delegation
state.activeValidatorSet[delegation.validator] = validator

state.activeValidatorSet.proposerBlockReward += tipCost(tx.fee.tipRate, bytesPaid)

Begin Block

At the beginning of the block, rewards are distributed to the block proposer.

Apply the following to the state:

proposer = state.activeValidatorSet[block.header.proposerAddress]

# Compute block subsidy and save to state for use in end block.
rewardFactor = (TARGET_ANNUAL_ISSUANCE * BLOCK_TIME) / (SECONDS_PER_YEAR * sqrt(GENESIS_COIN_COUNT))
blockReward = rewardFactor * sqrt(state.activeValidatorSet.activeVotingPower)
state.activeValidatorSet.proposerBlockReward = blockReward

# Save proposer's initial voting power to state for use in end block.
state.activeValidatorSet.proposerInitialVotingPower = proposer.votingPower

state.activeValidatorSet[block.header.proposerAddress] = proposer

End Block

Apply the following to the state:

account = state.accounts[block.header.proposerAddress]

if account.status == AccountStatus.ValidatorUnbonding
      account.status == AccountStatus.ValidatorUnbonded
    proposer = state.inactiveValidatorSet[block.header.proposerAddress]
else if account.status == AccountStatus.ValidatorBonded
    proposer = state.activeValidatorSet[block.header.proposerAddress]

# Flush the outstanding pending rewards.
proposer.latestEntry += compute_new_entry(proposer.pendingRewards, proposer.votingPower)
proposer.pendingRewards = 0

blockReward = state.activeValidatorSet.proposerBlockReward
commissionReward = proposer.commissionRate.numerator * blockReward // proposer.commissionRate.denominator
proposer.commissionRewards += commissionReward
proposer.pendingRewards += blockReward - commissionReward

# Even though the voting power hasn't changed yet, we consider this a period change.
proposer.latestEntry += compute_new_entry(proposer.pendingRewards, state.activeValidatorSet.proposerInitialVotingPower)
proposer.pendingRewards = 0

if account.status == AccountStatus.ValidatorUnbonding
      account.status == AccountStatus.ValidatorUnbonded
    state.inactiveValidatorSet[block.header.proposerAddress] = proposer
else if account.status == AccountStatus.ValidatorBonded
    state.activeValidatorSet[block.header.proposerAddress] = proposer

At the end of a block, the top MAX_VALIDATORS validators by voting power with voting power greater than zero are or become active (bonded). For newly-bonded validators, the entire validator object is moved to the active validators subtree and their status is changed to bonded. For previously-bonded validators that are no longer in the top MAX_VALIDATORS validators begin unbonding.

Bonding validators is simply setting their status to AccountStatus.ValidatorBonded. The logic for validator unbonding is found here, minus transaction sender updates (nonce, balance, and fee).

Finally, the state subtree with ID MESSAGE_PAID_SUBTREE_ID is deleted.

This end block implicit state transition is a single state transition, and only has a single intermediate state root associated with it.

Honest Block Proposer

This document describes the tasks of an honest block proposer to assemble a new block. Performing these actions is not enforced by the consensus rules, so long as a valid block is produced.

Deciding on a Block Size

Before arranging available data into shares, the size of the original data's square must be determined.

There are two restrictions on the original data's square size:

1. It must be at most AVAILABLE_DATA_ORIGINAL_SQUARE_MAX.
2. It must be a power of 2.

With these restrictions in mind, the block proposer performs the following actions:

1. Collect as many transactions and messages from the mempool as possible, such that the total number of shares is at most AVAILABLE_DATA_ORIGINAL_SQUARE_MAX.
2. Compute the smallest square size that is a power of 2 that can fit the number of shares.
3. Attempt to lay out the collected transactions and messages in the current square.
   1. If the square is too small to fit all transactions and messages (which may happen due to needing to insert padding between messages) and the square size is smaller than AVAILABLE_DATA_ORIGINAL_SQUARE_MAX, double the size of the square and repeat the above step.

Note: the maximum padding shares between messages should be at most twice the number of message shares. Doubling the square size (i.e. quadrupling the number of shares in the square) should thus only have to happen at most once.

Laying out Transactions and Messages

Networking

Wire Format

AvailableData

AvailableDataRow

ConsensusProposal

Defined as ConsensusProposal:

message ConsensusProposal {
  SignedMsgType type = 1;
  int32 round = 2;
  int32 pol_round = 3;
  // 32-byte hash
  // Proposed block header
  Header header = 4;
  AvailableDataHeader da_header = 5;
  // 64-byte signature
  bytes proposer_signature = 6;
}

When receiving a new block proposal proposal from the network, the following steps are performed in order. Must indicates that peers must be blacklisted (to prevent DoS attacks) and should indicates that the network message can simply be ignored.

1. proposal.type must be a SignedMsgType.
2. proposal.round is processed identically to Tendermint.
3. proposal.pol_round is processed identically to Tendermint.
4. proposal.header must be well-formed.
5. proposal.header.version.block must be VERSION_BLOCK.
6. proposal.header.version.app must be VERSION_APP.
7. proposal.header.height should be previous known height + 1.
8. proposal.header.chain_id must be CHAIN_ID.
9. proposal.header.time is processed identically to Tendermint.
10. proposal.header.last_header_hash must be previous block's header hash.
11. proposal.header.last_commit_hash must be the previous block's commit hash.
12. proposal.header.consensus_hash must be the hash of consensus parameters.
13. proposal.header.state_commitment must be the state root after applying the previous block's transactions.
14. proposal.header.available_data_original_shares_used must be at most AVAILABLE_DATA_ORIGINAL_SQUARE_MAX ** 2.
15. proposal.header.available_data_root must be the root of proposal.da_header.
16. proposal.header.proposer_address must be the correct leader.
17. proposal.da_header must be well-formed.
18. The number of elements in proposal.da_header.row_roots and proposal.da_header.row_roots must be equal.
19. The number of elements in proposal.da_header.row_roots must be the same as computed here.
20. proposal.proposer_signature must be a valid digital signature over the header hash of proposal.header that recovers to proposal.header.proposer_address.
21. For full nodes, proposal.da_header must be the result of computing the roots of the shares (received separately).
22. For light nodes, proposal.da_header should be sampled from for availability.

MsgWirePayForData

Defined as MsgWirePayForData:

message MsgWirePayForData {
  TransactionFee fee = 1;
  uint64 nonce = 2;
  // 8-byte namespace ID
  bytes message_namespace_id = 3;
  uint64 message_size = 4;
  bytes message = 5;
  repeated MessageCommitmentAndSignature message_commitment_and_signature = 6;
}

Accepting a MsgWirePayForData into the mempool requires different logic than other transactions in Celestia, since it leverages the paradigm of block proposers being able to malleate transaction data. Unlike SignedTransactionDataMsgPayForData (the canonical data type that is included in blocks and committed to with a data root in the block header), each MsgWirePayForData (the over-the-wire representation of the same) has potentially multiple signatures.

Transaction senders who want to pay for a message will create a SignedTransactionDataMsgPayForData object, stx, filling in the stx.messageShareCommitment field based on the non-interactive default rules for k = AVAILABLE_DATA_ORIGINAL_SQUARE_MAX, then signing it to get a transaction tx. This process is repeated with successively smaller ks, decreasing by powers of 2 until k * k <= stx.messageSize. At that point, there would be insufficient shares to include both the message and transaction. Using the rest of the signed transaction data along with the pairs of (tx.signedTransactionData.messageShareCommitment, tx.signature), a MsgWirePayForData object is constructed.

Receiving a MsgWirePayForData object from the network follows the reverse process: for each message_commitment_and_signature, verify using the non-interactive default rules that the signature is valid.

Invalid Erasure Coding

If a malicious block producer incorrectly computes the 2D Reed-Solomon code for a block's data, a fraud proof for this can be presented. We assume that the light clients have the AvailableDataHeader and the Header for each block. Hence, given a ShareProof, they can verify if the rowRoot or colRoot specified by isCol and position commits to the corresponding Share. Similarly, given the height of a block, they can access all elements within the AvailableDataHeader and the Header of the block.

ShareProof

BadEncodingFraudProof

Defined as BadEncodingFraudProof:

// https://github.com/celestiaorg/celestia-specs/blob/master/specs/networking.md#badencodingfraudproof
message BadEncodingFraudProof {
  // height of the block with the offending row or column
  int64 height = 1;
  // the available shares in the offending row or column and their Merkle proofs
  // array of ShareProofs
  repeated ShareProof shareProofs = 2;
  // a Boolean indicating if it is an offending row or column; false if it is a row
  bool isCol = 3;
  // the index of the offending row or column in the square
  uint64 position = 4;
}

Invalid State Update

If a malicious block producer incorrectly computes the state, a fraud proof for this can be presented. We assume that the light clients have the AvailableDataHeader and the Header for each block. Hence, given a ShareProof, they can verify if the rowRoot or colRoot specified by isCol and position commits to the corresponding Share. Similarly, given the height of a block, they can access all elements within the AvailableDataHeader and the Header of the block.

StateFraudProof

Defined as StateFraudProof:

// https://github.com/celestiaorg/celestia-specs/blob/master/specs/networking.md#statefraudproof
message StateFraudProof {
  // height of the block with the intermediate state roots 
  // Subtracting one from height gives the height of the block with the transactions.
  int64 height = 1;
  // shares containing the transactions and their Merkle proofs
  // isCol within the ShareProof must be false.
  // array of ShareProofs
  repeated ShareProof transactionShareProofs = 2;
  // shares containing the intermediate state roots and their Merkle proofs
  // isCol within the ShareProof must be false.
  // array of ShareProofs
  repeated ShareProof isrShareProofs = 3;
  // index for connecting the WrappedIntermediateStateRoot and WrappedTransaction after shares are parsed
  uint64 index = 4;
  // state elements that were changed by the transactions
  // array of StateElements
  repeated StateElement intermediateStateElements = 5;
  // sparse Merkle tree inclusion proofs for the state elements
  // array of SparseMerkleTreeInclusionProofs
  repeated SparseMerkleTreeInclusionProof stateInclusionProofs = 6;
}

Rationale

• Message Layout

Message Layout

Preamble

Celestia uses a data availability scheme that allows nodes to determine whether a block's data was published without downloading the whole block. The core of this scheme is arranging data in a two-dimensional matrix then applying erasure coding to each row and column. This document describes the rationale for how data—transactions, messages, and other data—is actually arranged. Familiarity with the originally proposed data layout format is assumed.

Message Layout Rationale

Block data consists of:

1. Cosmos SDK module transactions (e.g. MsgSend). These modify the Celestia chain's state.
2. Celestia-specific transactions (e.g. PayForBlobs). These modify the Celestia chain's state.
3. Intermediate state roots: required for fraud proofs of the aforementioned transactions.
4. Messages: binary blobs which do not modify the Celestia state, but which are intended for a Celestia application identified with a provided namespace ID.

We want to arrange this data into a k * k matrix of fixed-sized shares, which will later be committed to in Namespace Merkle Trees (NMTs).

The simplest way we can imagine arranging block data is to simply serialize it all in no particular order, split it into fixed-sized shares, then arrange those shares into the k * k matrix in row-major order. However, this naive scheme can be improved in a number of ways, described below.

First, we impose some ground rules:

1. Data must be ordered by namespace ID. This makes queries into a NMT commitment of that data more efficient.
2. Since non-message data are not naturally intended for particular namespaces, we assign reserved namespaces for them. A range of namespaces is reserved for this purpose, starting from the lowest possible namespace ID.
3. By construction, the above two rules mean that non-message data always precedes message data in the row-major matrix, even when considering single rows or columns.
4. Data with different namespaces must not be in the same share. This might cause a small amount of wasted block space, but makes the NMT easier to reason about in general since leaves are guaranteed to belong to a single namespace.

Transactions can pay fees for a message to be included in the same block as the transaction itself. However, we do not want serialized transactions to include the entire message they pay for (which is the case in other blockchains with native execution, e.g. calldata in Ethereum transactions or OP_RETURN data in Bitcoin transactions), otherwise every node that validates the sanctity of the Celestia coin would need to download all message data. Transactions must therefore only include a commitment to (i.e. some hash of) the message they pay fees for. If implemented naively (e.g. with a simple hash of the message, or a simple binary Merkle tree root of the message), this can lead to a data availability problem, as there are no guarantees that the data behind these commitments is actually part of the block data.

To that end, we impose some additional rules onto messages only: messages must be placed is a way such that both the transaction sender and the block producer can be held accountable—a necessary property for e.g. fee burning. Accountable in this context means that

1. The transaction sender must pay sufficient fees for message inclusion.
2. The block proposer cannot claim that a message was included when it was not (which implies that a transaction and the message it pays for must be included in the same block).

Specifically, messages must begin at a new share, unlike non-message data which can span multiple shares. We note a nice property from this rule: if the transaction sender knows 1) k, the size of the matrix, 2) the starting location of their message in a row, and 3) the length of the message (they know this since they are sending the message), then they can actually compute a sequence of roots to subtrees in the row NMTs. More importantly, anyone can compute this, and can compute the simple Merkle root of these subtree roots.

This, however, requires the block producer to interact with the transaction sender to provide them the starting location of their message. This can be done selectively, but is not ideal as a default for e.g. end-user wallets.

Non-Interactive Default Rules

As a non-consensus-critical default, we can impose one additional rule on message placement to make the possible starting locations of messages sufficiently predictable and constrained such that users can deterministically compute subtree roots without interaction:

Messages start at an index that is a multiple of the message minimum square size. The message minimum square size is the smallest square that can contain the message in isolation (i.e. a square with only this message and no other transactions or messages).

In the constraint mentioned above, the number of rows/columns in the minimum square size should be a power of 2. With the above constraint, we can compute subtree roots deterministically. In order to compute the subtree roots, split the message into chunks that are of maximum size: message minimum square size. As an example, a message of length 11 has a minimum square size of 4 because 11 is not greater than 4 * 4 = 16 total shares. Split the message into chunks of length 4, 4, 2, 1. The resulting slices are the leaves of subtrees whose roots can be computed. These subtree roots will be present as internal nodes in the NMT of some row(s).

This is similar to Merkle Mountain Ranges, though with the largest subtree bounded by the message minimum square size rather than being unbounded.

The last piece of the puzzle is determining which row the message is placed at (or, more specifically, the starting location). This is needed to keep the block producer accountable. To this end, the block producer simply augments each fee-paying transaction with some metadata: the starting location of the message the transaction pays for.

Caveats

The message placement rules described above conflict with the first rule that shares must be ordered by namespace ID, as shares between two messages that are not placed adjacent to each other do not have a natural namespace they belong to. This is resolved by requiring that such shares have a value of zero and a namespace ID equal to the preceding message's. Since their value is known, they can be omitted from NMT proofs of all shares of a given namespace ID.