Discussions in Eth R&D Discord: Discord
TL;DL
- The idea of an EIP-1559 transaction pool for fast sorting.
- Computational complexity
- Add a transaction in $O(\log n)$
- Sort transactions when basefee changes in $O(k \log n)$
- Pop the most profitable transaction in $O(\log n)$
- Produce a block in $O(m \log n)$
- $n$: The number of transactions in a txpool
- $k$: The number of transactions where the miner bribe varies with basefee
- $m$: The number of transactions in a block
- Implementation: GitHub - minaminao/eip1559txpool