ADR 118: Mempool QoS

Changelog

2024-04-12: Initial notes (@hvanz)
2024-04-12: Comments on the notes (@sergio-mena)
2024-04-17: Discussions (@sergio-mena @hvanz)
2024-04-18: Preliminary structure (@hvanz)
2024-05-01: Add Context and Properties (@hvanz)
2024-05-21: Add more Properties + priority mempool (@sergio-mena)
2024-06-13: Technical design (@hvanz)
2024-07-02: Updates based on reviewer's comments (@hvanz, @sergio-mena)
2024-07-09: Updates based on reviewer's comments (@hvanz)
2024-09-13: Added pre-confirmations section (@sergio-mena)
2024-09-27: Allow lanes to have same priority + lane capacities (@hvanz)

Status

Accepted. Tracking issue: [#2803][tracking-issue].

Context

In the current implementation, the only property that the mempool tries to enforce when processing and disseminating transactions is maintaining the order in which transactions arrive to the nodes, that is, a FIFO ordering. However, ensuring a strict transmission order over the network proves challenging due to inherent characteristics of the underlying communication protocols that causes message delays and potential reordering. Consequently, while many Tendermint Core and CometBFT applications have always assumed this ordering always holds, the FIFO-ness of transactions is not guaranteed and is offered only as a best effort.

Beyond the apparent FIFO sequencing, transactions in the mempool are treated equally, meaning that they are not discriminated as to which are disseminated first or which transactions the mempool offers to the proposer when creating the next block. In practice, however, not all transactions have the same importance for the application logic, especially when it comes to latency requirements. Depending on the application, we may think of countless categories of transactions based on their importance and requirements, spanning from IBC messages to transactions for exchanges, for smart contract execution, for smart contract deployment, grouped by SDK modules, and so on. Even transactions prioritized by economic incentives could be given a preferential treatment. Or big transactions, regardless of their nature, could be categorized as low priority, to mitigate potential attacks on the mempool.

The goal of this document is thus to propose a mechanism enabling the mempool to prioritize transactions by classes, for processing and dissemination, directly impacting block creation and transaction latency. In IP networking terminology, this is known as Quality of Service (QoS). By providing certain QoS guarantees, developers will be able to more easily estimate when transactions will be disseminated and reaped from the mempool to be included in a block.

In practical terms, we envision an implementation of the transaction class abstraction as mempool lanes. The application will be allowed to split the mempool transaction space into a hierarchy of lanes, with each lane operating as an independent mempool. At the same time, all of them need to be coordinated to ensure the delivery of the desired levels of QoS.

Note that improving the dissemination protocol to reduce bandwidth and/or latency is a separate concern and falls outside the scope of this proposal. Likewise, graceful degradation under high load is an orthogonal problem to transaction classification, although the latter may help improve the former.

Properties

Before jumping into the design of the proposal, we define more formally the properties supported by the current implementation of the mempool. Then we state what properties the new mempool should offer to guarantee the desired QoS. The following definitions are common to all properties.

When attempting to add an incoming transaction to the mempool, the node first checks that it is not already in the cache before checking its validity with the application.

:memo: Definition: We say that a node receives a transaction tx for the first time when the node receives tx and tx is not in the cache.

By this definition, it is possible that a node receives a transaction "for the first time", then gets the transaction evicted from the cache, and at a later time receives it "for the first time" again. The cache implements a Least-Recently Used (LRU) policy for removing entries when the cache is full.

:memo: Definition: Given any two different transactions tx1 and tx2, in a given node, we say that:

tx1 is validated before tx2, when tx1 and tx2 are received for the first time, and tx1 is validated against the application (via CheckTx) before tx2,
tx1 is rechecked before tx2, when tx1 and tx2 are in the mempool and tx1 is re-validated (rechecked via CheckTx) before tx2,
tx1 is reaped before tx2, when tx1 is reaped from the mempool to be included in a block proposal before tx2,
tx1 is disseminated before tx2, when tx1 is sent to a given peer before tx2.

In 2, both transactions are rechecked at the same height, because both are in the mempool.

In 4, note that in the current implementation there is one dissemination routine per peer, so it could happen that tx2 is sent to a peer before tx1 is sent to a different peer. Hence the importance of expression "to a given peer" in that definition.

Current mempool

As stated above, the current mempool offers a best-effort FIFO ordering of transactions. We state this property as follows.

:parking: Property FIFO ordering of transactions: We say that the mempool makes a best effort in maintaining the FIFO ordering of transactions when transactions are validated, rechecked, reaped, and disseminated in the same order in which the mempool has received them.

More formally, given any two different transactions tx1 and tx2, if a node's mempool receives tx1 before receiving tx2, then tx1 will be validated, rechecked, reaped, and disseminated before tx2 (as defined above).

Note that a node's mempool can receive a transaction either from a broadcast_tx_* RPC endpoint or from a peer.

This property guarantees the FIFO ordering at any given node, but it cannot be generalised to all the nodes in the network because the property does not hold at the network level. Hence, FIFO ordering on the whole system is best effort.

Mempool with QoS

The main goal of QoS is to guarantee that certain transactions have lower latency than others. Before stating this property, we need to make some definitions.

:memo: Definition: a transaction class is a disjoint set of transactions having some common characteristics as defined by the application.

A transaction may only have one class. If it is not assigned any specific class, it will be assigned a default class, which is a special class always present in any set of classes. This is analogous to the native VLAN for untagged traffic in an 802.1Q network. Because no transaction can belong to two or more classes, transaction classes form disjoint sets, that is, the intersection between any two classes is empty. Also, all transactions in the mempool are the union of the transactions in all classes.

:memo: Definition: Each class has a priority and two classes cannot have the same priority. Therefore all classes can be ordered by priority.

When a transaction is received for the first time and validated via CheckTx, the application MAY return the class that it assigns to the transaction. If it actually returns a class, the mempool MUST use it to prioritize the transaction. When transactions are rechecked, applications MAY return a class, but the mempool will discard it.

Given these definitions, we want the proposed QoS mechanism to offer the following property:

Basic properties

:parking: Property Priorities between classes: Transactions belonging to a certain class will be reaped and disseminated before transactions belonging to another class with lower priority.

Formally, given two transaction classes c1 and c2, with c1 having more priority than c2, if the application assigns the classes c1 and c2 respectively to transactions tx1 and tx2, then tx1 will be reaped and disseminated before tx2.

More importantly, as a direct consequence of this property, tx1 will be disseminated faster and it will be included in a block before tx2. Thus, tx1 will have a lower latency than tx2. Currently, it is not possible to guarantee this kind of property.

:memo: Definition: The latency of a transaction is the difference between the time at which a user or client submits the transaction for the first time to any node in the network, and the timestamp of the block in which the transaction finally was included.

We want also to keep the FIFO ordering within each class (for the time being):

:parking: Property FIFO ordering per class: For transactions within the same class, the mempool will maintain a FIFO order within the class when transactions are validated, rechecked, reaped, and disseminated.

Given any two different transactions tx1 and tx2 belonging to the same class, if the mempool receives tx1 before receiving tx2, then:

tx1 will be validated and recheck against the application (via CheckTx) before tx2, and
tx1 will be reaped and disseminated before tx2.

As a consequence, given that classes of transactions have a sequential ordering, and that classes do not have elements in common, we can state the following property:

:parking: Property Partial ordering of all transactions: The set of all the transactions in the mempool, regardless of their classes, will have a partial order.

This means that some pairs of transactions are comparable and, thus, have an order, while others not.

Network-wide consistency

The properties presented so far may be interpreted as per-node properties. However, we need to define some network-wide properties in order for a mempool QoS implementation to be useful and predictable for the whole appchain network. These properties are expressed in terms of consistency of the information, configuration and behaviour across nodes in the network.

:parking: Property Consistent transaction classes: For any transaction tx, and any two correct nodes $p$ and $q$ that receive tx for the first time, $p$ and $q$ MUST have the same set of transaction classes and their relative priority and configuration.

The property is only required to hold for on-the-fly transactions: if a node receives a (late) transaction that has already been decided, this property does not enforce anything. The same goes for duplicate transactions. Notice that, if this property does not hold, it is not possible to guarantee any property across the network, such as transaction latency as defined above.

:parking: Property Consistent transaction classification: For any transaction tx and any two correct nodes $p$ and $q$ that receive tx for the first time, $p$'s application MUST classify tx into the same transaction class as $q$'s application.

This property only makes sense when the previous property ("Consistent transaction classes") defined above holds. Even if we ensure consistent transaction classes, if this property does not hold, a given transaction may not receive the same classification across the network and it will thus be impossible to reason about any network-wide guarantees we want to provide that transaction with.

Additionally, it is important to note that these two properties also constrain the way transaction classes and transaction classification logic can evolve in an existing implementation. If either transaction classes or classification logic are not modified in a coordinated manner in a working system, there will be at least a period where these two properties may not hold for all transactions.

Alternative Approaches

CometBFT Priority Mempool

CometBFT used to have a v1 mempool, specified in Tendermint Core [ADR067][adr067] and deprecated as of v0.37.x, which supported per-transaction priority assignment. The key point of the priority mempool's design was that CheckTxResponse was extended with a few fields, one of which being an int64 that the application could use to provide a priority to the transaction being checked.

This design can be seen as partially addressing the specification of a Mempool with QoS presented in the previous section. Every possible value of the int64 priority field returned by the application can be understood as a different traffic class. Let us examine whether the properties specified above are fulfilled by the priority mempool design as described in [ADR067][adr067]:

Partial ordering of all transactions is maintained because the design still keeps a FIFO queue for gossiping transactions. Also, transactions are reaped according to non-decreasing priority first, and then in FIFO order for transactions with equal priority (see this ReapMaxBytesMaxGas's [docstring][reapmaxbytesmaxgas]).
Since the priority mempool uses FIFO for transactions of equal priority, it also fulfills the "FIFO ordering per class" property. The problem here is that, since every value of the priority int64 field is considered a different transaction class, there are virtually unlimited traffic classes. So it is too easy for an application to end up using hundreds, if not thousands of transactions classes at a given time. In this situation, "FIFO ordering per class", while fulfilled, becomes a corner case and thus does not add much value.
The consistent transaction classes property is trivially fulfilled, as the set of transaction classes never changes: it is the set of all possible values of an int64.
Finally, the priority mempool design does not make any provisions on how the application is to evolve its prioritization (i.e., transaction classification) logic. Therefore, the design does not guarantee the fulfillment of the consistent transaction classification property.

The main hindrance for the wide adoption of the priority mempool was the dramatic reduction of the observable FIFO guarantees for transactions (as explained in point 2 above) with respect to the v0 mempool.

Besides, the lack of provisions for evolving the prioritization logic (point 4 above) could have also got in the way of adoption.

Solana

Introduction to Gulf Stream and Comparison with CometBFT's Mempool

A core part of Solana's design is [Gulf Stream][gulf-stream], which is marketed as a "mempool-less" way of processing in-flight transactions. Similarly of a CometBFT- based chain, the sequence of leaders (nodes that produce blocks) is known in advance. However, unlike CometBFT, Solana keeps the same leader for a whole epoch, whole typical length is approx. 2 days (what if the leader fails in the middle of an epoch?). According to the Gulf Stream design, rather than maintaining a mempool at all nodes to ensure transactions will reach any leader/validator, transactions are directly sent to the current leader and the next, according to the sequence of leaders calculated locally (known as leader schedule). As a result, Gulf Stream does not use gossip-based primitives to disseminate transactions, but UDP packets sent directly to the current (and next) leader's IP address. One of the main points of adopting gossip protocols by Tendermint Core and CometBFT (coming from Bitcoin and Ethereum) is censorship resistance. It is not clear how Gulf Stream deals with an adversary controlling a part of the network that stands on the way of those UDP packets containing submitted transactions.

Transaction Priority Design

In Solana, transaction priority is controlled by fees: they introduce the concept of [priority fees][solana-prio-fees]. The priority fee is an optional configuration parameter when submitting a transaction, which allows the submitter to increase the likelihood of their transaction making it to a block. The priority fee is provided in terms of price per Unit of Computation (UC), priced in [micro-lamports per CU][prio-fee-price]. A UC is the equivalent of Cosmos's gas, and so, the priority fee is analogous (in concept) to the Cosmos SDK's --gas-prices [flag][sdk-gas-prices]. The main difference if that the SDK (currently) uses --gas-prices to set up a per-node threshold of acceptability in gas prices, whereas Solana uses the (default or user-configured) priority fee as the transaction's actual priority.

This is very similar to the way CometBFT's priority mempool in v0.37.x was supposed to be used by applications, but in a monolithic manner: there is no "priority" abstraction in Solana as there is nothing similar to ABCI. In short, the fees are the priority. Thus, if we were to check the properties specified above, with the caveat that Solana does not have a built-in mempool, we would reach the same conclusions as with the CometBFT's v0.37.x priority mempool. Namely, a degradation in observable FIFO guarantees (affecting applications that depend on it for performance), and a lack a provisions of evolving priority classification in a consistent manner. The latter may appear less important as transactions are directly sent to the current leader, but it is not clear how retried transactions in periods of high load can be receive a consistent priority treatment.

Ethereum Pre-confirmations

Brief Explanation

Ethereum pre-confirmations are a mechanism designed to reduce transaction latency. Justin Drake's [proposal][based-preconfs] for based pre-confirmations has gained attention in recent months in the Ethereum research community, though similar ideas date back to Bitcoin's [Oconfs][Oconfs].

Pre-confirmations occur in the context of fast games, techniques applied between consecutive Layer-1 blocks to improve certain performance guarantees and help manage MEV (Maximal Extractable Value).

The process is straightforward. A user submits a transaction and requests a preconfer (a validator) to guarantee specific handling of that transaction, typically for a fee, called tip. In exchange, the preconfer signs a promise — most often guaranteeing transaction inclusion in the next block. The preconfer can only claim the tip if the promise is fulfilled, and validators opting in to become preconfers accept new slashing conditions related to liveness (failure to propose a block) and safety (failure to meet the promise).

This design enables various implementations of pre-confirmations, and it's still early to determine which form will dominate in Ethereum.

Comparison to Mempool QoS

Unlike Mempool QoS — the design described below — which prioritizes transactions based on network resource availability, pre-confirmations focus on individual user guarantees about transaction treatment and certainty of inclusion. While the connection to MEV is not fully understood yet, pre-confirmations may provide some mitigation against MEV-related risks.

Pre-confirmations can also coexist with Mempool QoS in CometBFT-based blockchains. For instance, particular Mempool QoS configurations, such as a starving, FIFO, high-priority lane, could be part of an implementation of pre-confirmations in a CometBFT-based chain.

Skip's Block-SDK Lanes

As of version v0.47.x, the Cosmos SDK offers application developers the possibility to use an [Application-Side Mempool][sdk-app-mempool]. It is a mempool structure maintained by the SDK application and populated with valid transactions received via CheckTx. An application maintaining such a mempool is free to define the way transactions are ordered, reaped for a block, aggregated, removed, etc. Typically, upon PrepareProposal, the SDK application disregards the transactions proposed by CometBFT, and rather proposes transactions reaped from its own mempool, and according to its mempool's rules.

Excerpt (19996 of 44958 characters). Read the whole page on CometBFT ADRs and RFCs ↗

← Back to Documentation