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 Pool TxPoolTxPool is a Ledger component that maintains a queue of transactions received by the node.

This section presents an implementor-oriented definition of TxPoolTxPool and is based on the reference implementation to clarify how it is constructed and operated by a node.

The TxPoolTxPool implementation makes use of two distinct queues to aid the processes of pruning already observed transactions and block commitment:

• The remembered queue TxPoolrqTxPoolrq,
• The pending queue TxPoolpqTxPoolpq.

The pending queue TxPoolpqTxPoolpq is the main structure used to supply transactions to the active pending BlockEvaluatorBlockEvaluator, which evaluates transactions for the next block.

Important IMPLEMENTATION: Pending block evaluator reference implementation.

Important IMPLEMENTATION: Here we provide some implementation details about the remembered queue TxPoolrqTxPoolrq and the pending queue TxPoolpqTxPoolpq structures used in the TxPoolTxPool. Whenever a new block is confirmed and committed to the Ledger, the node triggers OnNewBlock. This function may rebuild the pending BlockEvaluatorBlockEvaluator (except for a future round’s pending BlockEvaluatorBlockEvaluator). As part of this process, the pending queue TxPoolpqTxPoolpq is synchronized with the remembered queue TxPoolrqTxPoolrq by replacing its contents entirely. In contrast, when the Remember function is called, the verified transaction group is first appended to the remembered queue TxPoolrqTxPoolrq. Then the entire TxPoolrqTxPoolrq is appended to TxPoolpqTxPoolpq rather than replacing it. This causes the two queues to diverge temporarily until the next OnNewBlock call resyncs them. Example of Remember function used by the txnHandler to enqueue a verified transaction group in the reference implementation. For more detail, see the rememberCommit(bool flush) function, which controls how TxPoolpqTxPoolpq is updated from TxPoolrqTxPoolrq. If flush=true, TxPoolpqTxPoolpq is completely overwritten; if flush=false, TxPoolrqTxPoolrq is appended. In summary:

• OnNewBlock → calls rememberCommit(true) → replaces TxPoolpqTxPoolpq with TxPoolrqTxPoolrq.
• Remember → appends to TxPoolrqTxPoolrq, then calls rememberCommit(false) → appends TxPoolrqTxPoolrq to TxPoolpqTxPoolpq.

Temporary queue divergence is expected and resolved at the next block confirmation. Given a properly signed and well-formed transaction group gtx∈TxPoolpqgtx∈TxPoolpq, we say that gtxgtx is remembered when it is pushed into TxPoolrqTxPoolrq if:

• Its aggregated fee is sufficiently high,
• Its state changes are consistent with the prior transactions in TxPoolrqTxPoolrq. Note that a single transaction can be viewed as a group gtxgtx containing only one transaction. TxPoolrqTxPoolrq is structured as a two-dimensional array. Each element in this array holds a list of well-formed, signed transactions. To improve efficiency, the node also uses a key-value mapping where the keys are transaction IDs and the values are the corresponding signed transactions. This map duplicates the data in the queue, which adds a small computational cost when updating the queue (for insertions and deletions), but it enables fast, constant-time O(1)O(1) lookup of any enqueued transaction by its ID. Additionally, TxPoolpqTxPoolpq serves as another layer of optimization. It stores transaction groups that are prepared in advance for the next block assembly process. In a multithreaded system with strict timing constraints, this setup allows TxPoolrqTxPoolrq to be pruned as soon as a new block is committed, even while the next block is being assembled concurrently.

The following is a list of abstracted minimal functionalities that the TxPoolTxPool should provide.

An algorithm that decides which transactions should be retained and which ones should be dropped, especially important when the TxPoolTxPool becomes congested (i.e., when transactions are arriving faster than they can be processed, de-enqueued in a block, or observed in a committed block and pruned). A simple approach could be a _“first-come, first-served” policy. However, the go-algorand reference implementation uses a more selective method: a threshold-based fee prioritization algorithm, which prioritizes transactions paying higher fees.

This process is triggered when a new block is observed as committed. At this point, transactions are pruned if they meet either of the following conditions:

• They have already been included in a committed block (as determined by the OnNewBlock function), or
• Their LastValid field has expired. Specifically, if the current round r>TxLastValidr>TxLastValid.

In addition to pruning outdated or committed transactions, this step also updates the internal variables used for the prioritization.

This component handles the ingestion of new transaction groups (gtxgtx) that are to be remembered (enqueued to TxPoolrqTxPoolrq). Before enqueuing, it verifies that each transaction group is internally valid and consistent in the context of transactions already present in TxPoolrqTxPoolrq. Once transactions pass these checks, they are forwarded to any active Block Evaluator, so they can be considered for inclusion in blocks currently being assembled.

This process builds a new block’s payset (the body with block’s transactions) by selecting valid transaction groups gtxgtx dequeued from the TxPoolTxPool, all within a deadline. A (pending) Block Evaluator is responsible for processing the transactions, while the BlockAssembly function coordinates with it. The assembly process halts as soon as the time constraints are reached.