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

Mempool

Warning

This blueprint is a work in progress. See also Resources

In Cardano, for blocks to have useful data, they have to contain transactions, which are codifications of operations on the Ledger state that only some authorized actors can enact. Notice that such transactions are what makes up the contents of the block. In one way, one could see the ledger as being able to validate transactions, and by implication full blocks as those are mainly collections of transactions.

Notice that WHAT constitutes a transaction is defined by the Ledger layer and it depends on the current era on the Ledger State that the transaction is being validated against.

Tip

The Ledger layer provides mechanisms to translate transactions from older eras to more recent ones. In the reference Haskell node, the original transaction is the one that will be forwarded to other peers, i.e. the “translated” version of the transaction is not sent over the network, but this is not a requirement.

Transactions are pending on some Ledger State if they have not been included in any block since Genesis up until such Ledger State. Transactions are valid on some Ledger State if they can be applied to such Ledger State through the Ledger rules. Notice we can create a new Ledger State by applying a single transaction to an existing Ledger State.

Once a transaction has been included in a block, it is not a pending transaction anymore in that fork of the chain, in fact from that point onwards it will be an invalid transaction, as in Cardano every transaction consumes at least one UTxO, in this case consumed by the instance of the transaction that was included in a block.

Note

Notice a transaction can be invalid in a fork but valid or pending in a different fork.

Purpose of the Mempool component

The Mempool serves two very different purposes:

  • Provide a sequence of pending (and therefore valid) transactions to include in the next block being forged.

  • Serve transactions that were pending (and therefore valid) on top of some recent Chain Selection to which we will refer as mempool anchor (or anchor). Having transactions to serve means it also needs to validate incoming transactions.

Note

Notice that a transaction might be considered valid in one peer, but invalid in another peer which uses a different anchor ledger state.

Even in the case both peers have the same anchor, the existence in the mempool (or lack thereof) of some other specific transaction that creates (or consumes) the inputs for this one could lead to different verdicts on each peer. (This would not be the case if we validate transactions independently, but that was discarded)

While only nodes that forge new blocks will use these transactions to create blocks, non-block-producing nodes are still expected to diffuse transactions to their peers. All participating nodes must be able to receive, validate, and distribute transactions.

Tip

When a node is shut down, the implementation can choose what to do with the pending transactions. The reference Haskell implementation discards them. However, it is conceivable for a node to store on disk the pending transactions from its mempool.

Mempool size

In order to prevent overusing resources, the Ledger places a limit on the number of pending transactions it accepts on a single block, which should be enforced by the mempool. Once this limit is reached, requests to add new transactions will be rejected. This back-pressure mechanism is critically important in periods of intense traffic to preserve the overall throughput of the network.

This limit is not defined as a raw number of transactions but as a cap on various metrics, currently 4 metrics:

  • transaction size in bytes
  • CPU execution units
  • memory execution units
  • reference scripts size

Protocol requirements and guarantees

The TxSubmission2 miniprotocol is the one used to diffuse the pending transactions through the network.

To be able to diffuse transactions through TxSubmission2 and to fulfill the requirements of the Consensus layer, any mempool implementation has the following requirements:

  • Acquiring a snapshot of valid transactions for a newly forged block should be as fast as possible, as it will delay all other steps in the diffusion of such a block. This is required by the Consensus layer for forging blocks promptly.
  • Cursor-like access to transactions which are pending (and therefore valid) with regards to a mempool anchor. This is required by the TxSubmission2 protocol as it uses a ticketing counter to index transmitted transactions. If transaction X depends on transaction Y, then Y must have a lower ticket counter than X (i.e. Y must come before X in the transmitted sequence). See below for a discussion on this.
  • Eventual re-validation on a new selected chain: it is useless to keep transactions that are no longer valid in the mempool but a node does not need to eagerly evict transactions. This is an inherent requirement of the mempool itself.

In particular, there are two important facts that derive from these requirements:

  • The transactions served by a peer were valid (and therefore pending) in some recent Ledger State the peer synced their mempool with. They might not be valid on the local node’s Ledger State or even on the current selected tip of the peer.

  • The node can ingest transactions (and then serve them) as long as they are valid (and therefore pending) in some recent Ledger State, which means the node does not need to ensure a transaction is valid on the current selected tip.

Fairness

Warning

TODO: describe fairness and what should mempools do in this regard.

Improvements

The reference Haskell node does not do these optimizations but they were discussed hence we record them for the future:

DAG-based mempool

We require that:

if transaction X depends on Y, then Y must have a lower ticket counter than transaction X.

The reference Haskell node achieves this by storing the transactions in the mempool as a sequence that is always applied in order. As it doesn’t analyze dependency among transactions, when a transaction is invalidated, it needs to re-validate the transactions that come after it in the sequence, as they might now become invalid too.

Amaru team suggested that a DAG-based mempool would allow the mempool to right away discard a branch of the DAG without having to revalidate unrelated transactions.

Resources