This sounds great and is a good starting point for formalizing a threat model for the MEVA. There are a few things that seem like major challenges for this system:
- Added latency between transaction selection and sequencing
- Constructing a Bayes-optimal auction for the sequencing auction that is efficiently computable
- Inflation / dilution / burning mechanics of the underlying system
- This doesn’t address all sources of MEV, so there is non-zero deadweight loss for the tax
Let’s analyze these independently.
Latency
It seems unavoidable that this mechanism adds in some latency between transaction selection and transaction sequencing. The simplest high-level view of the mempool is as a standard priority queue (implemented as a heap) whose keys are (gas price, nonce) [0]. This means that when a block is emitted from an honest and rational (profit-maximizing in-protocol only) miner, they simply pop the maximum number of transactions that fit into a block and pack a block [1]. This combines selection and sequencing in a single operation (with runtime O(n \log T) where n is the number of transactions in the mempool and n is the number withdrawn for a block) and doesn’t incur the latency of having two agents — the transaction selector and the transaction sequence — having to coordinate.
What are options for dealing with this latency? In particular, how do we minimize the rounds of communication between the transaction selector and the sequencer? I have a couple ideas:
- Mild Idea: Run the sequencer auctions ahead of the block production time (e.g. auction for block h takes place in a smart contract executed at block h-1) so that the winning sequencers are ready to receive transaction sets ahead of time. The sequencer might need to stake a small amount of collateral, to ensure that they are online to sequence when it is their turn
- Crazy idea: Have a distributed priority queue such that each potential sequencer participates in with some stake (e.g. they lock up some assets at block height h to commit to a sequence at height h+1). Each insertion or deletion into this priority queue costs a fee and the final ordering cost is the aggregation of these fees. This way, sequencer can spend the entire time between a block at height h and a block at height h+1 attempting to sequence transactions, such that once the transaction selector sends the approved transactions, the elements that aren’t in the queue are removed and the transactor who wins (either by auction or via the most fees, this might be a way of obviating the auction dynamics) chooses the final ordering of the transactions that were selected that weren’t in the distributed priority queue. This optimization doesn’t improve the worst case run time, but it does improve the average case run time. There is some potential for griefing attacks, but they are bounded by how unbalanced the heap implementation can get
Optimizing the Auction
The field of combinatorial auctions has been well-studied by game theorists such as Noam Nisan and Tim Roughgarden for an extended period of time. Most combinatorial auctions, such as the spectrum auction, involve selling unordered sets, so these techniques (see Chapter 11 of Nisan, Roughgarden, and Tardos) should make it relative easy for the transaction selection auction. I wouldn’t try to reinvent the wheel here, if I were you.
On the other hand, auction dynamics for the sequencing side of things is much harder to discern. In a famous paper, Betting on Permutations illustrates a Condorcet-like impossibility result — it is NP-hard to compute an optimal betting / auction strategy when bidding on permutations. One of the reasons for this is that the original first-price auction for gas prices, in isolation of previous blocks and mempools, is not a Bayes-optimal auction, whereas this auction is. The reason for this is that bidders have to condition their expected utility computations on the transactions they have received. How do we analyze such an auction in a way that is comparable to how the current gas auctions works? We’ll try to walk through the basic mathematical elements that each agent has to choose and then provide some tried and trued techniques for doing primitive mechanism design here.
In order to do this, we first have to define fairness. Note that we consider an auction to be \epsilon-fair if the probability distribution over auction outcomes returns no particular ordering with probability \epsilon more than the uniform distribution (e.g. all orderings are basically equally likely). Why is this a good definition fair? It serves as way of saying that no particular transaction ordering is favored by much under all possible instantiations of the auction with different participants.
Next, we need to look at what it means for an individual participant or agent to pick a certain ordering. Let’s suppose that the transaction selector has sent n transactions, T_1, \ldots, T_n \in \mathcal{T} and that the transaction sequencer has a utility function U : \mathcal{T}^n \rightarrow \mathbb{R}. We will represent the possible transaction orderings (e.g. linear orderings such as T_1 < T_3 < T_2) via permutations on n letters. In order to figure out our bidding strategy, we first have to compute a) which permutations are most important to evaluate (there are n! of them, so we need to be efficient) and b) how to value a given permutation. The first is specified by computing a subjective probability, \mu_{n}(\sigma) = \mathsf{Pr}[\sigma(T_1, \ldots, T_n) | n, T_1, \ldots, T_n] for each element \sigma \in S_n, where S_n is the symmetric group on n letters. The second component is specified by an expected utility,
\mathsf{E}[U | T_1, \ldots, T_n] = \frac{1}{n!} \sum_{\sigma \in S_n} U(\sigma(T_1, \ldots, T_n))\mathsf{Pr}[\sigma(T_1, \ldots, T_n) | n, T_1, \ldots, T_n]
Finally note that in this notation, we define a \epsilon-fair auction as one that returns a transaction ordering \sigma(T_1, \ldots, T_n) with probability distribution p where d_{TV}(p, \mathsf{Unif}([n])) < \epsilon.
Each rational participant in the auction will have a utility function U and subjective probabilities \mu_n that will guide how their strategies evolve in this auction. If we believe that rational, honest players are participating in the sequencer protocol, then we rely on this expectation being positive (altruists are those who continue playing when this is non-positive). Moreover, there isn’t a unique archetype of a rational, honest player here (unlike in consensus) — for instance, we have two simple strategies that meet the stated goals of being rational, non-malicious, and able to always submit a bid:
- Maximum a posteriori optimizer — select the ordering \sigma^* \in S_n such that \sigma^* \in \text{arg}\max_{\sigma \in S_n} \mathsf{Pr}[\sigma(T_1, \ldots, T_n) | n, T_1, \ldots, T_n]
- Empirical expected utility maximizer — Take k samples \sigma_1, \ldots, \sigma_k \sim \mathsf{Pr}[\sigma(T_1, \ldots, T_n) | n, T_1, \ldots, T_n] and choose the ordering \sigma^* = \text{arg}\max_{i \in [k]} U(\sigma_i(T_1, \ldots, T_n)
These are only two of the rational, honest strategies available here as agents can localize their bets (e.g. convolve their subjective probability with the indicator function 1_{A}) to any subset A \subset S_n. This vastly expanded space of rational, honest strategies makes traditional algorithmic game theory tools somewhat meaningless for analyzing such an auction. What can we do?
We can take a page out of the online advertising auction design playbook and try to model the sequencing auction by segmenting the the participants into two categories:
- “Passive” honest, rational agents who participate regardless and have a static strategy and a single, common utility function U
- “Active” aggressive strategies that have dynamic strategies such that the probability measure \mu_n changes from block to block.
Once we do this, we can take techniques like those used in the above Milgrom paper to create auctions that have a social welfare function [2] V(\gamma) = \gamma V_{\text{passive}} + V_{\text{active}} whose revenue sharing and reserve pricing can be optimized based on the desired goals of the sequencing auction. I strongly suspect this will be important in ensuring that spamming and spoofing these auctions is expensive for those who are trying to encourage participation in certain transaction orderings.
Note that methodologies for auctions, akin to the Milgrom paper, are inclusive of collusion — the authors do not assume independence of the bids that participants that are “active”. The parameter \gamma (as well as other parameters, such as reserve sizes) control how much correlation/bribery is needed to change an auction from the default.
This is all of the background needed to try to construct a k th price auction with reserve amounts that is \epsilon-fair. Good luck!
Impact on Inflation
If the fees from this auction are paid back to the network we have three options:
- Pro-rata redistribution: This is basically stake-weighted redistribution of the auction revenue
- Burned: We burn the revenue from the auction
- Concentrated redistribution: Only redistributing to certain participants (e.g. validators, top-k validators)
The third option is likely the most unfair and has perverse incentives to bribe validators for certain orderings. The second option has implications for inflation: If the MEV auction clearing prices are increasing faster than the block reward is increasing (e.g. subsidy inflation), then the ‘real’ inflation of the system will actually be lower than expected. The first option will cause a tax liability for holders and/or encourages the highest stake participants to try to cause the clearing price to increase. These trade-offs are really worth considering!
Other Sources of MEV
The simplest form of MEV that isn’t discussed is transaction elision — e.g. a validator not repeatedly adding a transaction to the transaction set. Under the assumption of 50% honest, rational agents, one can show that a transaction that enters the mempool at block h will eventually get into the chain at block h+k (there is a Kiayias paper for this that is escaping me). The probability that this happens decays exponentially in k (the exponential base is a function of the percentage of rational honest agents), but it does have a burn in time (e.g. linear for 0 \leq k \leq k', exponential for k \geq k').
Thanks to Brock Elmore, Peteris Erins, and Lev Livnev for useful discussion on these points
[0] In the current implementation of the Geth mempool, the file core/tx_pool.go contains the logic for the pool (including the priority queue). The choice of keys and comparison is actually done in a different translation unit, miner/worker.go
[1] Note that Bitcoin’s mempool logic is significantly more complex and sophisticated. The child-pays-for-parent tree allows for UTXOs to be spent over multiple blocks and lets scripts trigger future payments. See Alex Morcos excellent fee guide and Jeremy Rubin’s OP_CTV. It should be noted that this complexity in the mempool is partially due to the inflexibility of Bitcoin script, which forces multiblock payments to be mediated at the mempool (instead of in a contract). But it has the side-effect of making fee sniping a lot more difficult in Bitcoin.
[2] Recall that in Algorithmic Game Theory, the social welfare function represents the ‘macroeconomic’ observable that we are trying to optimize for our mechanism. In auctions with independent bidding and no repeated rounds or reserves, this simply is the sum of the quasilinear utilities of the participants. When there is collusion / correlation, this gets significantly more complciated