Proposal For A New Mempool Design

The proposed solution involves maintaining a total ordering of the mempool's transactions, which would be used to implement symmetrically opposite mining and eviction algorithms.

Proposal For A New Mempool Design
  • "The current mempool is primarily designed around maintaining two different sort orders, where for each transaction we keep track of its position in an ancestor-feerate-sort and in a descendant-feerate-sort. We then use those two cached sort orders in order to implement eviction and mining."
  • "Those algorithms are deficient in several ways. In particular, the eviction algorithm (which removes the transaction with lowest descendant feerate, along with its descendants) does not guarantee that the first transaction evicted would be the last transaction mined, and there exist situations where we could evict a transaction that would otherwise actually be mined in the next block."
  • "Furthermore, the mining algorithm is more complex than the ancestor feerate sort we maintain, and it is insufficient to merely do lookups into our ancestor feerate index to determine which of two transactions will be mined from the mempool first."
  • "This lack of a total ordering on mempool transactions makes RBF calculations difficult to align with miner incentives, and creates distortions where we sometimes can replace transactions via RBF that would actually be better for a miner than the replacement."
  • "To solve all these problems, we propose maintaining a total ordering on mempool transactions, which we use to implement a mining and eviction algorithm that are symmetrically opposite and provide better RBF rules for determining when to allow a replacement to occur."

GitHub Repo
PDF Document