Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

• Auto
• Light
• Dark

Algorand Specifications

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

The transaction sequence of block rr is denoted TxSeqrTxSeqr.

Each valid block contains a transaction commitment TxCommitrTxCommitr which is a Merkle Tree Commitment to this sequence.

The leaves in the Merkle Tree are hashed as:

Hash(TL,TxID,Hash(STIB))Hash(TL,TxID,Hash(STIB))

Where:

• HashHash is the cryptographic SHA-512-256 hash function;

• The TxIDTxID is the 32-byte transaction identifier;

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

Signed transactions in a block STIBSTIB are encoded in a slightly different way than standalone transactions TxTx, for efficiency:

If a standalone transaction TxTx contains a GenesisIDGenesisID value, then:

• The transaction’s GenesisIDGenesisID MUST match the block’s GenesisIDGenesisID;

• The transaction’s GenesisIDGenesisID value MUST be omitted from the STIBSTIB transaction’s msgpack encoding in the block;

• The STIBSTIB transaction’s msgpack encoding in the block MUST indicate the GenesisIDGenesisID value was omitted by including a key hgi with the boolean value True.

Since transactions MUST include a GenesisHashGenesisHash value, the GenesisHashGenesisHash value of each transaction in a block MUST match the block’s GenesisHashGenesisHash, and the GenesisHashGenesisHash value is omitted from the STIBSTIB transaction as encoded in a block.

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

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

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

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:

SHA256(TL,SHA256(TxID),SHA256(STIB))SHA256(TL,SHA256(TxID),SHA256(STIB))

and

SHA512(TL,SHA512(TxID),SHA512(STIB))SHA512(TL,SHA512(TxID),SHA512(STIB))

Where:

• SHA256SHA256 is the cryptographic SHA-256 hash function;

• SHA256(TxID)=SHA256(TX||Tx)SHA256(TxID)=SHA256(TX||Tx)

• SHA256(STIB)=SHA256(STIB||Sig(Tx)||ApplyData)SHA256(STIB)=SHA256(STIB||Sig(Tx)||ApplyData)

• SHA512SHA512 is the cryptographic SHA-512 hash function;

• SHA512(TxID)=SHA512(TX||Tx)SHA512(TxID)=SHA512(TX||Tx)

• SHA512(STIB)=SHA512(STIB||Sig(Tx)||ApplyData)SHA512(STIB)=SHA512(STIB||Sig(Tx)||ApplyData)

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

A valid transaction sequence TxSeqTxSeq 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 TxSeqrTxSeqr to refer unambiguously to the set in this block).

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

All transactions have a size in bytes. The size of the transaction TxTx is denoted |Tx||Tx|.

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

∑Tx∈TxSeqr|Tx|≤Bmax∑Tx∈TxSeqr|Tx|≤Bmax

The transaction tail TxTailTxTail for a given round rr is a set produced from the union of the transaction identifiers TxIDTxID of each transaction in the last TxTailmaxTxTailmax transaction sets and is used to detect duplicate transactions.

In other words,

TxTailr=⋃r−TxTailmax≤s≤r−1Hash(Tx)|Tx∈TxSeqs.TxTailr=⋃r−TxTailmax≤s≤r−1Hash(Tx)|Tx∈TxSeqs.

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

TxTailr+1=TxTailr∖Hash(Tx)|Tx∈TxSeqr−Tmax∪Hash(Tx)|Tx∈TxSeqr.TxTailr+1=TxTailr∖Hash(Tx)|Tx∈TxSeqr−Tmax∪Hash(Tx)|Tx∈TxSeqr.

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