## 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](https://github.com/algorand/go-algorand/blob/55011f93fddb181c643f8e3f3d3391b62832e7cd/ledger/txtail.go#L46).

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 `txid`s 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.