zkvm: mempool

[oleganza]

This is a follow-up to #398, describing the design of a DoS-resistant mempool.

Overview

Memory pool is a data structure maintained by each peer for managing unconfirmed transactions. It decides which transactions to accept from other peers and relay further.

Generally, transactions are sorted by feerate: the amount of fees paid per byte. Nodes choose some reasonable limits for their mempool sizes. As mempool becomes full, lowest-paying transactions are evicted from it. When a new block is created, it takes the highest-paying transactions. When nodes see a new block, they clear their mempools, removing confirmed transactions.

What if transaction does not pay high enough fee? At best it’s not going to be relayed anywhere.
At worst, it’s going to be relayed and dropped by some nodes, and relayed again by others, etc.

This situation poses two problems:

1. Denial of service risk: low-fee transactions that barely make it to the mempool can get re-relayed many times over, consuming bandwidth of the network, while the same fee is amortized over all the relay cycles, lowering the cost of attack.
2. Stuck transactions: as nodes reject double-spend attempts, user may have to wait indefinitely until his low-fee transaction is either completely forgotten or finally published in a block.

There are two ways to address stuck transactions:

1. Replace the transaction with another one, spending the same outputs, but with a higher fee. This is known as replace-by-fee (RBF). This method has a practical downside to the user: one need to re-communicate blinding factors with the recipient when making an alternative tx. So in this implementation we do not support RBF at all.
2. Create a chained transaction that pays a higher fee to cover for itself and for the parent. This is known as child pays for parent (CPFP). This is implemented here.

The DoS risk is primarily limited by requiring transactions pay not only for themselves, but also for
the cost of relaying the transactions that are being evicted. The evicted transaction is now unlikely to be confirmed, so the cost of relaying it must be covered by some other transaction.

There is an additional problem, though. After the mempool is partially cleared by a newly published block, the previously evicted transaction may come back and will be relayed once again.
At first glance, it is not a problem because someone's transaction that cause the eviction has already paid for the first relay. However, for the creator of the transaction potentially unlimited number of relays comes at a constant (low) cost. This means, the network may have to relay twice as much traffic due to such bouncing transactions, and the actual users of the network may need to pay twice as much.

To address this issue, we need to efficiently remember the evicted transaction. Then, to accept it again, we require it to have the effective feerate = minimum feerate + flat feerate. If the transaction pays by itself, it is fine to accept it again. The only transaction likely to return again and again is the one paying a very low fee, so the bump by flat feerate would force it to be paid via CPFP (parked and wait for a higher-paying child).

Specification

Mempool consists of two parts: main pool and peer pools.

Peer pool

Peer pool uses FIFO order and generally accepts low number of transactions (<100). This provides a sufficient window for relaying chains of CPFP transactions, without requiring a separate "package relay" mode.

When a valid transaction cannot be accepted to the main pool due to insufficient fee, it is parked in a peer pool. When a mempool is cleared by a newly published block, or a node receives a higher-paying child, parked transactions are moved into the main pool.

Parked transactions are not relayed to other peers. When the oldest parked transaction is evicted, it is simply dropped. When peer disconnects, all parked transactions are forgotten.

Main pool

Main pool sorts transactions by effective feerate.

When the main pool is full, the incoming transaction must pay for itself and for the evicted transaction (since the evicted one was already relayed, but now is unlikely to pay for this relay).

Filters for evicted transactions

To mitigate bandwidth exhaustion by zombie transactions (that get evicted and return several times), we remember both evicted transaction IDs and the outputs IDs that they spend in a bloom filter. The filter is reset every 24 hours to keep the rate of false positives negligible.

When a new transaction arrives

1. It is validated statelessly per ZkVM rules. The peer may be deprioritized or banned if it relays invalid transaction.
2. Timestamp is checked w.r.t. to the last block timestamp. Transactions must use generous time bounds to account for clock differences. This simplifies validation logic, as we don't need to allow windowing or check for self-consistency of unconfirmed tx chains.
3. If the tx can be applied to the peerpool, it is parked there. Effective feerates are recalculated for all ancestors. If any tx now has a sufficient effective feerate to enter the mempool, it is moved there. Children are tested and included recursively. If any tx fails to apply to main pool (double spend), it and its children are evicted from peer pool.
4. If the tx can be applied to the main pool, it is applied there. Peer pools are not updated at this point and may contain double-spends, but those have no effect because they are filtered out when a new tx enters peerpool.
5. If the mempool is not full, it must pay the minimum flat feerate (configured by the peer).
6. If the mempool is full, it must pay for the evicted tx: min_feerate * (evicted_tx_size + new_tx_size).
7. If the tx.maxtime is less than mempool time +24h, an additional flat feerate is required on top of the above. This is because such transaction is more likely to expire and become invalid (unlike unbounded ones), while the network has spent bandwidth on relaying it.
8. If the tx ID is found in a bloom filter: it is treated as resurrected, and must pay the fee as calculated above, but increased by flat feerate. If it does not pay sufficiently, it is parked in the peerpool until CPFP happens, or the filter is reset.
9. If the tx spends an output marked in the bloom filter, but its ID is not found: it is rejected as double-spend (we don't support replace-by-fee). If a regular transaction triggers false positive in the filter (<1% risk), it is not accepted or relayed by this node, but other >99% nodes may relay it, since all nodes initialize their filters with random seeds.

When a new block arrives

1. The new Utreexo state and timestamp are assigned to the mempool.
2. All transactions are re-applied to the state, starting with the highest-paying txs (unconfirmed parents are re-applied recursively).
3. Peerpool transactions are processed later, when new txs are parked there. See above.

Notes

The above design contains several design decisions worth pointing out:

1. Transactions are always valid at all levels. Orphan txs are not allowed and must be sorted out at a transport level. In the future, if we use UDP, we may implement a separate buffer in peer pools for that purpose.
2. Double spends are not allowed at any level. This is, obviously, a hard rule for the blockchain, but it also means the replace-by-fee (RBF) is not allowed in mempools. The rationale is that child-pays-for-parent (CPFP) needs to be supported anyway, and replacing confidential transactions requires update of all blinding factors, which normally means another round of communication between the wallets. Also, handling fees when RBF happens across eviction and preventing subtle DoS scenarios is trickier than simply disallow RBF. Do not consider this design choice as an endorsement of 0-confirmation transactions; those do not become more secure because this policy is strictly focused on protecting the node itself and does not offer any security to other nodes.
3. Single-mode relay with peerpools. Transactions are assumed to be simply relayed in topological order, one by one. There is no separate "package relay" for CPFP. Txs with insufficient fees are parked in a per-peer buffer until a higher-paying child arrives.
4. Discounted child feerate. To simplify a NP-complete task of calculating an optimal subset of tx graph, effective feerate of a parent is computed by simply combining feerates of children. In case a child has several parents, we prevent overcounting by splitting its feerate among all parents. For the most cases it does not treat txs unfairly, but allows adding up feerates in a straightforward manner.