$$ \newcommand \Tx {\mathrm{Tx}} \newcommand \TxID {\Tx\mathrm{ID}} \newcommand \TxSeq {\Tx\mathrm{Seq}} \newcommand \TxCommit {\Tx\mathrm{Commit}} \newcommand \TxTail {\Tx\mathrm{Tail}} \newcommand \Hash {\mathrm{Hash}} \newcommand \SHATFS {\mathrm{SHA256}} \newcommand \SHAFOT {\mathrm{SHA512}} \newcommand \Sig {\mathrm{Sig}} \newcommand \STIB {\mathrm{STIB}} \newcommand \Genesis {\mathrm{Genesis}} \newcommand \GenesisID {\Genesis{\mathrm{ID}}} \newcommand \GenesisHash {\Genesis\Hash} \newcommand \ApplyData {\mathrm{ApplyData}} \newcommand {\abs}[1] {\lvert #1 \rvert} \newcommand \MaxTxnBytesPerBlock {B_{\max}} \newcommand \MaxTxTail {\mathrm{TxTail}_{\max}} $$

Transaction Sequences, Sets, and Tails

Transaction Sequence

Each block contains a transaction sequence, an ordered sequence of transactions in that block.

The transaction sequence of block \( r \) is denoted \( \TxSeq_r \).

Each valid block contains a transaction commitment \( \TxCommit_r \) which is a Merkle Tree Commitment to this sequence.

The leaves in the Merkle Tree are hashed as:

$$ \Hash(\texttt{TL}, \TxID, \Hash(\STIB)) $$

Where:

• \( \Hash \) is the cryptographic SHA-512-256 hash function;

• The \( \TxID \) is the 32-byte transaction identifier;

• The \( \Hash(\STIB) \) is a 32-byte hash of the signed transaction and ApplyData for the transaction, hashed with the domain-separation prefix STIB (signed transaction in block).

Signed transactions in a block \( \STIB \) are encoded in a slightly different way than standalone transactions \( \Tx \), for efficiency:

If a standalone transaction \( \Tx \) contains a \( \GenesisID \) value, then:

• The transaction’s \( \GenesisID \) MUST match the block’s \( \GenesisID \);

• The transaction’s \( \GenesisID \) value MUST be omitted from the \( \STIB \) transaction’s msgpack encoding in the block;

• The \( \STIB \) transaction’s msgpack encoding in the block MUST indicate the \( \GenesisID \) value was omitted by including a key hgi with the boolean value True.

Since transactions MUST include a \( \GenesisHash \) value, the \( \GenesisHash \) value of each transaction in a block MUST match the block’s \( \GenesisHash \), and the \( \GenesisHash \) value is omitted from the \( \STIB \) transaction as encoded in a block.

• Signed transactions in a block are also augmented with the \( \ApplyData \) that reflect how that transaction was applied to the Account State.

The transaction commitment (\( \TxCommit \)) for a block covers the transaction encodings with the changes described above.

Individual transaction signatures cover the original encoding of transactions as standalone transactions (\( \Tx \)).

In addition to the transaction commitment, each block contains SHA-256 and SHA-512 transaction commitments. They allow a verifier not supporting SHA-512/256 function to verify proof of membership for transactions.

To construct these commitments, we use a Vector Commitment.

The leaves in the Vector Commitment tree are hashed respectively as:

$$ \SHATFS(\texttt{TL}, \SHATFS(\TxID), \SHATFS(\STIB)) $$

and

$$ \SHAFOT(\texttt{TL}, \SHAFOT(\TxID), \SHAFOT(\STIB)) $$

Where:

• \( \SHATFS \) is the cryptographic SHA-256 hash function;

• \( \SHATFS(\TxID) = \SHATFS(\texttt{TX} || \Tx) \)

• \( \SHATFS(\STIB) = \SHATFS(\texttt{STIB} || \Sig(\Tx) || \ApplyData) \)

• \( \SHAFOT \) is the cryptographic SHA-512 hash function;

• \( \SHAFOT(\TxID) = \SHAFOT(\texttt{TX} || \Tx) \)

• \( \SHAFOT(\STIB) = \SHAFOT(\texttt{STIB} || \Sig(\Tx) || \ApplyData) \)

These Vector Commitments use SHA-256 and SHA-512 for internal nodes as well.

A valid transaction sequence \( \TxSeq \) contains no duplicates: each transaction in the transaction sequence MUST appear exactly once.

We can call the set of these transactions the transaction set (for convenience, we may also write \( \TxSeq_r \) to refer unambiguously to the set in this block).

For a block to be valid, its transaction sequence \( \TxSeq_r \) MUST be valid (i.e., no duplicate transactions may appear there).

All transactions have a size in bytes. The size of the transaction \( \Tx \) is denoted \( \abs{\Tx} \).

For a block to be valid, the sum of the sizes of each transaction in a transaction sequence MUST NOT exceed \( \MaxTxnBytesPerBlock \); in other words:

$$ \sum_{\Tx \in \TxSeq_r} \abs{\Tx} \leq \MaxTxnBytesPerBlock $$

Transaction Tails

The transaction tail \( \TxTail \) for a given round \( r \) is a set produced from the union of the transaction identifiers \( \TxID \) of each transaction in the last \( \MaxTxTail \) transaction sets and is used to detect duplicate transactions.

In other words,

$$ \TxTail_r = \bigcup_{r-\MaxTxTail \leq s \leq r-1} {\Hash(\Tx) | \Tx \in \TxSeq_s}. $$

As a result, the transaction tail for round \( r+1 \) is computed as follows:

$$ \TxTail_{r+1} = \TxTail_r \setminus {\Hash(\Tx) | \Tx \in \TxSeq_{r-T_{\max}}} \cup {\Hash(\Tx) | \Tx \in \TxSeq_r}. $$

The transaction tail is part of the Ledger state but is distinct from the account state and is not committed to in the block.