EIP-1559 Transaction Sorting: Part 2

Follow-up to this overview from late last year. This document outlines my current thinking on the topic of mempool transaction sorting under EIP-1559 and is meant to serve as preparation for the 9th implementers' call. A fleshed-out writeup with these thoughts and the results of the call discussion will follow soon (targeting next week). Plan (for now) is to update this document instead, to keep the relevant information in one place.

tl;dr What initially looked mostly like a move from an one-dimensional to a two-dimensional sorting problem now seems to more generally be a challenge of adapting the current transaction handling implementations to the subtle changes of 1559. Simple "good enough" adaptations seem sufficient for now, with clear directions for further improvements.

General Observations

• Under 1559, the network is expected to be in (or close to) a short-run steady state most of the time, where the base_fee oscillates around an equilibrium base fee.
• Blocks on average have 1x the target size, with some larger and smaller blocks.
• That means miners on average only have one block's worth of includable transactions (usually ~100-200) when creating their blocks (as they would otherwise create larger blocks).
• Thus, the vast majority of transactions in mempool will be non-includable, i.e. with tx.fee_cap_per_gas < latest_block.base_fee.
• During demand spikes, there can be a large backlog of includable transactions for a limited amount of time

Mining

• Miners (at least in geth) currently re-build a max-heap of all pending mempool transactions every 1-3 seconds and re-build an entirely new block to switch to for mining.
• Theoretically, they could just keep doing that under 1559.
• However, ideally the mempool is able to only provide currently includable transactions.
• To find transactions that switched between includable and non-includable, the mempool needs to maintain a max-heap of non-includable and a min-heap of includable transactions.
• In addition, the miner should ideally also be adjusted to operate in "append-only" mode while the new block is not full (and append new transactions immediately), as opposed to fully re-creating the block every 1-3 seconds.
• For demand spikes, the sorting of includable transactions could also be made more efficient. @minaminao gave a detailed overview and initial implementation of the most efficient approach (together with an initial implementation).
• Preliminary recommendations:
  • immediate implementation of includable / non-includable mempool distinction
  • immediate implementation of append-only mining
  • naive sorting of includable transactions first, optimizations for demand spikes later

Eviction

• Currently non-includable transactions will generally be included as soon as base fee drops sufficiently low.
• That means that, even with a high max_miner_bribe_per_gas, they have a low expected effective miner bribe.
• If the mempool additionally enforces some minimum miner bribe (or, more precisely, a MIN_MAX_MINER_BRIBE_PER_GAS), all non-includable transactions will have a limited range of expected effective miner bribes.
• Empirically estimating the expected value for miners is complex, as it has to take into account both the expected effective miner bribe and the chance of (eventual) inclusion.
• However, due to the limited range, simple eviction decisions based solely on fee_cap_per_gas is less inaccurate than initially thought.
• Sorting the bottom of the mempool by fee_cap_per_gas can be done re-using the existing min-heap based implementation logic.
• The exact degree to which this differs from an ideal solution depends on multiple factors around expected 1559 behavior:
  • How much base fee volatility is to be expected outside of demand spikes?
  • How frequently will there be demand spikes and of which magnitudes?
  • What is the expected user behavior with regards to sending non-includable transactions?
  • …
• Preliminary recommendation: simple fee_cap_per_gas evictions first, optimizations later

Further Questions

• More explicit optimizations in mempool around queued / pending / includable?
• Adjustments to the base fee algorithm to reduce volatility?
• How to deal with block time variability in Eth1?
• Which aspects will change in Eth2?
• Unrelated side question that came up: Are 1559-transactions valid if the sender account would be unable to pay the full fee_cap_per_gas, but able to pay at the current base fee level?