# EIP-1559 Transaction Sorting: Part 2

Follow-up to [this overview](https://hackmd.io/@adietrichs/1559-transaction-sorting) 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](https://github.com/ethereum/pm/issues/234). ~~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](https://hackmd.io/@VVsmryteTEWuiOBecRGFhw/Hy0ZyFn3w) 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?