Author: Zsolt Felfoldi (zsfelfoldi@ethereum.org)
Transaction pools currently order transactions based on a single metric (gasPrice), fetching the highest elements when constructing a new block and discarding the lowest elements when the pool is full. With EIP-1559 transaction ordering becomes more difficult because the effective miner reward (MIN(tx.tip, tx.feeCap-headBlock.baseFee)) depends on the latest block's base fee. A new EIP-1559 compatible pool design suggested by this proposal and implemented in this pull request orders transactions primarily based on feeCap in the eviction queue while the current efferctive reward is used for block construction. This is a good first approach because inclusion chance correlates with feeCap on the low end. The only potential danger is that feeCap might be meaningless when much higher than baseFee+tip, and still, the pool always prefers to keep the transactions with the highest feeCap. If there are many transactions with high feeCap but minimal tip then it's possible that the pool evicts the transactions that are most preferable for inclusion (higher tip, sufficient but not excessive feeCap).
Whether this scenario is possible depends on the capacity of the pool and the severity of congestions. It is generally expected that EIP-1559 will reduce congestions by making the block size flexible. It's hard to tell though how much the demand will fluctuate but hopefully a big enough pool will not have any serious issues. What might be worth considering though is that some users will probably prefer not specifying a high feeCap but do multi-step bidding. Revealing and irrevokably offering the highest fee you are willing to pay in a single step is probably a good option for many users but is not an economically optimal strategy. When there are enough transactions to fill up the next block then the baseFee is expected to rise quickly. In this case, for those who can raise their bids in multiple steps the optimal strategy is not to offer a high feeCap with a barely enough tip but to offer a higher effective reward in order to get into an earlier block with lower baseFee. Since the bids can be raised later, these bidding nodes also have no reason to specify a feeCap higher than baseFee+tip. This strategy can get the transaction included earlier, at a potentially lower price (while the naive "floaters" will be pushed to the top of the price peaks). Therefore we should expect some users to follow this strategy.
Eventually some bidders might even offer a tip comparable to the expected rise in baseFee. This is fine because it's still the baseFee that dominates the price balancing process while the extra tip just smooths out rough bumps. The problem is that for those who prefer to not offer a high feeCap it's hard to determine when this strategy might lead them to being evicted from the majority of miner pools. It's a bad tradeoff between following an economically optimal strategy and risking unpredictable pool behavior. Also offering a high feeCap while competing with the tip is possible but since it exposes the sender to a greater risk of overpayment, it also incentivizes to fight for early inclusion even harder. With enough competing parties this could end up in a trap situation similar to a "dollar auction" where each bidder pays their last bid but only the highest bidder takes the prize (in this case the prize being the earlier inclusion with lower baseFee).
In a good economic incentive system the "selfish" (economically optimal) behavior should be a Schelling point for all participants. EIP-1559 can have a nice equilibrium but I believe over the long term it would be preferable to have a transaction pool design with guaranteed nice behavior for both the "urgent" strategy (high reward right now) and the "floating" strategy (low tip, high fee cap).
Instead of indexing the entire pool of transactions with a min queue based on feeCap for eviction and optionally with a max queue based on effective reward for inclusion candidates, the proposed design uses two queues connected in series. The first queue, the "urgency queue" is based on effective reward and its size is limited to a certain percentage of the entire pool size limit. The size limit of the urgency queue should be enough to fill at least the next block to 2*gasTarget even if each transaction uses minimal gas. Just like with the current design, a max queue is needed only for miners while a min queue (also based on effective reward) will evict transactions from the urgency queue. Evicted items don't get discarded yet though, instead they are inserted into the "floating queue" which is a min queue based on feeCap. When the total size of the two queues exceed the pool size limit then the items with the lowest feeCap are evicted from the floating queue and discarded. New or updated transactions are first inserted into the urgency queue if they can pay the minimum reward at the moment, otherwise they are added to the floating queue. When a new block is received or created and the baseFee is changed, the effective reward for every transaction is recalculated and the queues are constructed again.
If there are not enough transactions with a sufficient effective miner reward to fill up the urgency queue then it is possible to allow more transactions in the floating queue. An alternative (simpler) approach is used in the current implementation: the urgency queue does comparisons based on the effective reward formula MIN(tx.tip, tx.feeCap-headBlock.baseFee) regardless of whether this value goes into the negative region. This means that the currently insufficiently priced transactions will be effectively sorted by fee cap even if they make it into the urgency queue because of the lack of sufficiently priced ones. The rest (that have even smaller fee cap) can go to the floating queue. This ensures that even in the case of a high base fee peak, the entire capacity of the pool can be utilized for future candidates includable with a lower base fee, without complicating the implementation.
The basic issue is that there are two potentially important factors that are impossible to directly compare against each other. When the effective miner reward is high enough then the feeCap is not relevant. If it's not high enough to get the transaction included soon then the current effective reward becomes meaningless (because baseFee will rise) and then feeCap becomes more relevant. The proposed design addresses this problem by not trying to compare these two factors against each other but giving a chance to stay in the pool based on either factor and only evicting those transactions that are not likely to be included based on either metric.
The performance and complexity of this design is expected to be similar to the current one. Though there are more queues now, each transaction is placed only in one of them. Floating transactions are only indexed once while urgent ones are indexed either once or twice (depending on whether the node is mining or not). After each new block a re-queueing happens which for some transactions means adding to one queue, then popping it and adding it to another queue. They cannot oscillate back and forth between the two queues, items in the floating queue are only promoted to the urgency queue by explicit re-queueing. Two queue operations per transaction per block is probably negligible CPU load.
The proposed dual queue design can be considered a middle ground between "evict lowest fee cap" strategy (which is ideal if all transactions are "floaters" with identical minimum tips) and the "evict lowest effective reward based on current base fee" strategy (which is ideal if all transactions are "urgent" and offering high tips). The only possible disadvantage compared to either of these strategies is that given the total capacity of the pool, each queue has half the capacity compared to a single-queue design. Therefore it performs well with a a balanced mix of urgents and floaters but might theoretically perform worse with only floaters or only urgents.
This does not mean though that the pool can handle half as many transactions in these extreme cases. With all urgents it will basically perform equally well because sorting them by fee cap basically gives the same result (the effective reward is limited by fee cap anyway). The difference is that adding a few high fee cap floaters to the pool might push out some transactions that could theoretically pay more if they would fit into the next block. This is usually an improvement though because those urgents that do not fit in the urgent queue will definitely not go into the next block (because the urgent queue can always fill up the next block and probably a few more), therefore the base fee will be significantly higher by the time it would have its chance, making the current effective reward a less and less relevant sorting parameter. The newly added high fee cap floaters will probably be more relevant inclusion candidates in the second queue. Therefore the dual queue design performs equally well for all urgents compared to the pure effective reward sorting, and probably starts performs better as the mix starts deviating from that extreme.
With the other extreme (all minimum tip floaters) the dual queue design also performs similarly well compared to the pure fee cap ordering. If tips are exactly equal then the behaviour will be the exact same because the urgency queue will also sort by fee cap as a second ordering condition. As soon as there are some (even if very small) deviations in the tips, the urgency queue will prefer the higher tips. In this case the dual queue setup might theoretically perform somewhat worse because after filling up the next block from the urgency queue, the remaining transactions in that queue might turn out to be useless for the near future, having just barely enough fee cap for the next block they did not fit into. We can say that in this worst case the effective capacity of the pool is the size of the floating queue plus one block filled up to 2*gasTarget. This is worse than the single fee cap queue (though better than half of that). I do not expect this scenario to arise because if there are too many high paying transactions and it's already hard to get into the pool then competing with high fee cap floaters is not a rational strategy. In these cases it is always better to offer a higher tip that eventually makes up for the difference caused by the base fee rise, making the rest of the urgency queue relevant. Also, if it turns out that for some reason most of the senders still use minimum tip floaters to fill up the pool in congestions then we can tune the ratio of the capacities of the two queues, making the urgency queue smaller in order to reduce the total capacity loss. I highly doubt that this would be ever necessary though.
The proposed dual queue design is implemented in this pull request.