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

The Transaction Tail TxTailTxTail is a data structure responsible for deduplication and recent history lookups. It can be considered a rolling window of recent transactions and block headers observed in a reduced history of rounds, optimized for lookup and retrieval.

Important

IMPLEMENTATION:

Transaction tail reference implementation.

It provides the following fields:

• recentLeaseMap

A mapping of round -> (TXLease -> round) that saves the transaction Lease by observation round, and the mapping uses TXLease as keys to store the Lease expiring round.

• blockHeaderData

Contains recent block header data. The expected availability range is [Latest - MaxTxnLife, Latest], allowing MaxTxnLife + 1 rounds of lookback ( 10011001 with current parameters).

• lastValidMap

A mapping of round -> (txid -> uint16) that enables the lookup of all transactions expiring in a given round. For each round, the inner map stores txids mapped to 16-bit unsigned integers representing the difference between the transaction’s lastValid field and the round it was confirmed (lastValid > confirmationRound for all confirmed transactions).

• lowWaterMark

An unsigned 64-bit integer representing a round number such that for any transactions where the lastValid field is lastValid < lowWaterMark, the node can quickly assert that it is not present in the TxTailTxTail.

A duplication check is the core functionality of TxTailTxTail.

Algorithm1: Check DuplicateAlgorithm 1: Check Duplicate

1: functionCheckDuplicate(Txr,FirstValid,LastValid,TxID,TxLease)2: ifLastValid<TxTail.LowWaterMarkthen3: returnTxID is not in TxTail4: endif5: ifTxLease≠∅then6: FirstChecked←FirstValid7: LastChecked←LastValid8: forr∈[FirstChecked,LastChecked]do9: ifTxLease∈RecentLeaseMap(Txr).Lease∧r≤TxLease.Expirationthen10:returnLease is a duplicate11:endif12:endfor13:endif14:ifTxID∈TxTail.LastValidMap(LastValid).TxIDthen15:returnTxID is a duplicate transaction16:endif17:return18: endfunction1: function CheckDuplicate(Txr,FirstValid,LastValid,TxID,TxLease)2: if LastValid<TxTail.LowWaterMark then3: return TxID is not in TxTail4: end if5: if TxLease≠∅ then6: FirstChecked←FirstValid7: LastChecked←LastValid8: for r∈[FirstChecked,LastChecked] do9: if TxLease∈RecentLeaseMap(Txr).Lease∧r≤TxLease.Expiration then10:return Lease is a duplicate11:end if12:end for13:end if14:if TxID∈TxTail.LastValidMap(LastValid).TxID then15:return TxID is a duplicate transaction16:end if17:return18: end function

The algorithm receives four fields of a transaction:

• The transaction round TxrTxr,

• The transaction validity round fields FirstValidFirstValid and LastValidLastValid,

• The transaction identifier TxIDTxID,

• The transaction lease TxLeaseTxLease (if set).

An early check is performed, where the LowWaterMarkLowWaterMark field is used to quickly discard transactions too far back in history and already purged from the TxTailTxTail.

In case a TxLeaseTxLease is set, the RecentLeaseMapRecentLeaseMap field is used to deduplicate by LeaseLease.

After checking for the LeaseLease, the LastValidMapLastValidMap is used and the transaction is deduplicated through a lookup of TxIDTxID by its LastValidLastValid round.

If the transaction is not found on the TxTailTxTail, the node can assume it is not a duplicate, otherwise the validity interval would be too far back in the past for the transaction to be confirmed anyway.