$$ \newcommand \TP {\mathrm{TxPool}} \newcommand \Tx {\mathrm{Tx}} \newcommand \LastValid {\mathrm{LastValid}} \newcommand \BlockEval {\mathrm{BlockEvaluator}} $$

Transaction Pool

The Transaction Pool \( \TP \) is a Ledger component that maintains a queue of transactions received by the node.

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

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

• The remembered queue \( \TP_{rq} \),

• The pending queue \( \TP_{pq} \).

The pending queue \( \TP_{pq} \) is the main structure used to supply transactions to the active pending \( \BlockEval \), which evaluates transactions for the next block.

⚙️ IMPLEMENTATION

Pending block evaluator reference implementation.

⚙️ IMPLEMENTATION

Here we provide some implementation details about the remembered queue \( \TP_{rq} \) and the pending queue \( \TP_{pq} \) structures used in the \( \TP \).

Whenever a new block is confirmed and committed to the Ledger, the node triggers OnNewBlock.

This function may rebuild the pending \( \BlockEval \) (except for a future round’s pending \( \BlockEval \)). As part of this process, the pending queue \( \TP_{pq} \) is synchronized with the remembered queue \( \TP_{rq} \) by replacing its contents entirely.

In contrast, when the Remember function is called, the verified transaction group is first appended to the remembered queue \( \TP_{rq} \). Then the entire \( \TP_{rq} \) is appended to \( \TP_{pq} \) 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 \( \TP_{pq} \) is updated from \( \TP_{rq} \).

If flush=true, \( \TP_{pq} \) is completely overwritten; if flush=false, \( \TP_{rq} \) is appended.

In summary:

• OnNewBlock → calls rememberCommit(true) → replaces \( \TP_{pq} \) with \( \TP_{rq} \).

• Remember → appends to \( \TP_{rq} \), then calls rememberCommit(false) → appends \( \TP_{rq} \) to \( \TP_{pq} \).

Temporary queue divergence is expected and resolved at the next block confirmation.

Given a properly signed and well-formed transaction group \( gtx \in \TP_{pq} \), we say that \( gtx \) is remembered when it is pushed into \( \TP_{rq} \) if:

• Its aggregated fee is sufficiently high,

• Its state changes are consistent with the prior transactions in \( \TP_{rq} \).

Note that a single transaction can be viewed as a group \( gtx \) containing only one transaction.

\( \TP_{rq} \) 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 \( \mathcal{O}(1) \) lookup of any enqueued transaction by its ID.

Additionally, \( \TP_{pq} \) 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 \( \TP_{rq} \) to be pruned as soon as a new block is committed, even while the next block is being assembled concurrently.

Transaction Pool Functions

The following is a list of abstracted minimal functionalities that the \( \TP \) should provide.

Prioritization

An algorithm that decides which transactions should be retained and which ones should be dropped, especially important when the \( \TP \) 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.

Update

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 > \Tx_{\LastValid}\).

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

Ingestion

This component handles the ingestion of new transaction groups (\( gtx \)) that are to be remembered (enqueued to \( \TP_{rq} \)). Before enqueuing, it verifies that each transaction group is internally valid and consistent in the context of transactions already present in \( \TP_{rq} \). 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.

BlockAssembly

This process builds a new block’s payset (the body with block’s transactions) by selecting valid transaction groups \( gtx \) dequeued from the \( \TP \), 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.