EIP-1559 Transaction Pool for Fast Sorting

Discussions in Eth R&D Discord: https://discord.com/channels/595666850260713488/749160974506000444/790156754347753472

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: https://github.com/minaminao/eip1559txpool