What happens when your order hits the Ethereum mempool?

If you are reading this, you may well have some idea. The short answer is that it waits around for a bit before (hopefully) being included into a block, removed from the mempool, and executed, resulting in a state update.

You may also know that other message can end up making it into a block before yours, even if they arrived later. If you sent your message to the public mempool, other entities may even spy it and react, so that messages are deliberately inserted ahead of or behind yours, for example, to extract value by manipulating prices on an AMM DEX.

Now you’re a protocol designer who wants to protect his users from the worst symptoms of extractable value. Is your design really as “MEV-proof” as your marketers claimed? What can you prove about it? What guarantees can you give your users, given that your protocol will be executing in diverse market conditions?

That’s the subject of my paper Adversarial blockchain queues and trading on a CFMM DEX, which the mathematically inclined will want to dive straight into. In this blog post, I’ll walk you through some of the theoretical concepts discussed in the paper and connect it to applications in designing and evaluating MEV-aware protocols.1

Blockchain queues in theory

Naturally, to answer the questions posed in the introduction we need a model. The part of mathematics that deals with situations where things arrive somewhere, wait around for a bit, and are eventually processed, whereupon they disappear from the system, is called queueing theory. It has its roots in Agner Krarup Erlang’s work for the Copenhagen Telephone Company and flourished in the 50s and 60s where it was central to the engineering of ARPANET and later the Internet. Classical queueing theory gives us methods to compute quantities such as the distribution of queue (a.k.a. mempool) size in equilibrium.

The Ethereum mempool is essentially a weird type of queue. It’s weird because its architects don’t specify the queue discipline, that is, the algorithm by which messages are selected from the mempool for inclusion into blocks and the way the messages within a block are ordered.

While there are some properties of queues that don’t really depend on the discipline — for example the dynamics of queue size — “client-side” quantities that impact the experience of a user submitting a particular message — such as execution price on a CFMM — most certainly do.2

In this post, we’ll talk specifically about the following question:

Given realistic constraints, what can we say about the number of blocks a message must wait until it is executed? What about its position in the block into which it is eventually included?

In particular, we study:

In given market conditions, how much does the execution price of an order on a CFMM deviate from the price the trader sees when he creates the order?

Which assumptions on queue discipline are realistic?

So queue discipline is a direct cofactor of user experience. It’s no surprise then that some authors are inventing weird queues to try and improve the situation.

The nature of permissionless blockchain networks places some limits on the extent to which the system architect can impose a discipline. Namely, although one could feasibly add conditions about ordering into Ethereum’s validation rules, there are difficulties with adding rules about inclusion, because enforcing a rule like “you must include a transaction like $X$ if you see it” would require visibility into the block producer’s private view of the mempool. Anyway, Ethereum protocol in its current form scarcely places any restrictions at all on discipline, even for ordering.

Given that block producers don’t have to follow any laws, the next best assumption is that they follow the law of the jungle — that is, they do whatever is best for their operators. This kind of self-interested (or as economists call it, rational) behaviour in networking isn’t unique to blockchain: selfish ISP routing is a well-documented phenomenon,3 and frontrunning trades by abusing remote communications networks has been reported as far as 75 years before Erlang. However, unlike previous iterations of network architecture, blockchain applications tend to put rational behaviour at the core of their design.

Rationality gives us another way to influence queue discipline: manipulate incentives to achieve a desired outcome. The challenge here is to understand the incentives of block producers well enough to prove properties about the resulting decision problem, a task that can prove surprisingly intractable. (Enforcing an ordering rule is secretly an instance of incentive design: if blocks don’t follow the rules, clients don’t accept it and the token on that block producer’s fork is worthless!)

Two limits of queue design

Protocol designers are constantly evolving new ways to influence blockmaking. But let’s start from the beginning, and isolate two simplified and extreme scenarios:

  1. The block producer can only see the priority fee of a message at the time of block construction. He cannot deduce any information at all about the transaction payload. He may insert his own messages, but does so in a manner completely independent from the stream of incoming transactions, even their number. All messages have positive priority fee.4
  2. The block producer always sees and sandwiches CFMM orders if he has enough capital available and it is profitable to do so.

There are a couple of scenarios in which option 1. could be close to a realistic model: perhaps the contents and number of incoming messages is somehow masked from the block producer using cryptographic techniques, or perhaps the block producer simply hasn’t invested time in designing a strategy that extracts MEV from incoming messages and interacts with his own node as an ordinary client.

Under such conditions, a rational block producer will:

  • include as many transactions as possible into the block
  • include higher priority transactions in preference to lower priority transactions (with his own transactions given highest priority).

A particular order $o$ makes it into a block as soon as it encounters a block with enough space left over after all higher priority messages are included. Let’s say blocks may contain at most $\beta$ messages, and let $$ N_i = \#\{m\in\mathrm{mempool} \mid \mathrm{priority}(m) > \mathrm{priority}(o) \} $$ be the number of messages in the mempool with priority greater than that of $o$.

Schematically, message arrivals and block construction processes look something like this (lower priority messages not shown):

mempool diagram

Then the probability of $o$ getting into any particular block $B_i$ is $$ P_\beta := \mathbb{P}(o\in B_i) =\mathbb{P}(o\in B_i\mid o\not\in B_{i-1}) = \mathbb{P}(N_i\leq\beta \mid N_{i-1}>\beta) $$ where we use a Markov property to eliminate dependence on events more than one block before $B_i$. In equilibrium, this probability can easily be computed by observing the blockchain! This uses a property of stationary processes called ergodicity, which in this case says that $P_\beta$ is the long-run fraction of blocks that are completely full of high priority transactions and are followed immediately by a block that is not full of high priority transactions. If no blockchain is available (suppose you’re studying this in preparation to launch your own), the numbers can also be calculated from fairly standard queueing models.

Equipped with these numbers, we can easily derive the distribution of the number of blocks to wait until $o$ is included: apart from the first block after $o$ appears in the mempool, which requires special treatment, it’s geometrically distributed with “success probability” $P_\beta$. Assuming also that block producers use priority ordering, a similar train of reasoning gives us the distribution of position of $o$ in the block.

Taken together, these give us a model of the number $K$ of messages that make it into the chain in front of $o$. Remember: we didn’t need to collect any data from the mempool itself to fit this model.

Execution price

Suppose Alina creates a market order $o$ on the Uniswapv2 USDC/WETH CPMM pool (we can leave limits for another day). Each message that hits the state ahead of $o$ has a certain chance of being a swap on the same pool and hence knocking the price out from what Alina saw when she created the order. If it’s a swap, then it has some size and direction which we can idealise as a real number $X_i$, say, with positive numbers being interpreted as BUYs and negatives as SELLs, with either denominated in USDC.

Then the USDC reserves of the pool by the time $o$ lands (disregarding fees) is then $$ S_K = x_0 + \sum_{i=0}^K X_i $$ where $x_0$ is the (known) starting reserves and $K$ is the number of swaps ahead in the queue. The marginal price then has the usual form $k/S_K^2$ where $k$ is the CFMM invariant.

How do we get a handle on the sequence $(X_0,X_1,\ldots)$? We could use Uniswap orderflow, of which we have abundant real-world data, but we still need a model to fit.

A simple-minded approach is to suppose the $X_i$ are a random sample from a distribution $F_X$ on the reals. This reduces our modelling problem to describing a single distribution, and it also gives us a nice expression for $S_K$: it’s the position of a random walk with step size $\sim F_X$ after $K$ steps. The moments (mean, variance, etc.) of this distribution can be easily calculated; for example, $$ \mathbb{E}(S_K)=x_0+\mathbb{E}(K)\cdot\mathbb{E}(X_i). $$

The marginal CPMM market price at execution time is then given by the usual formula $S_K^2/k$ where $k$ is the invariant level. We don’t necessarily have a nice analytic expression for the moments of this one, but sampling from it with a computer is as simple as sampling from $K$ and $X_i$.

This model for order flow appears in the econometrics and later econophysics literature under the attractive name “zero-intelligence.” Order flow is zero intelligence when no one else sees the contents of each others' messages, even to the point of not remembering their own previously sent messages. We also have to assume that order flow does not depend on time of message submission. In particular, traders don’t react to Ethereum state changes or condition their orders on the time elapsed since the most recently observed block. Zero intelligence indeed. Nonetheless, zero intelligence hypotheses have been used in academic research to simulate surprisingly realistic (albeit volatile) market dynamics.

So we get a model which you can use to compute things. Some of the hypotheses might not seem very convincing, but since we listed them explicitly, we can choose where to start relaxing them to get a better one. And it’s certainly better than no model.

What about sandwiches?

What about 2.? In the presence of a well-capitalised sandwicher, no such computer simulation is necessary: a trader can derive his execution price with certainty. On Uniswap it is always possible to pure profitably sandwich a marked order (or a limit order strictly within its limit), leaving AMM reserves as they would have been without the sandwich. In fact, this condition is equivalent to strict convexity of the CFMM invariant.

What do we take home from this (trivial) observation?

  • In the presence of MEV games, a naive queueing model for order execution position and price is not even approximately correct.
  • On the other hand, in such cases game or decision theoretic arguments can in fact have stronger predictive power than statistical arguments in environments where block producers have less information.

Reality now and in the future is somewhere between these extremes. That is, while block producers can in general see the contents of messages, they may not be interested in low-value transactions and hence treat those exactly as if they could not. So, we gain something from the generality of a family of models that specialises to either setting.

Conclusion

We established that you need both queueing theory and game theory to prove things about your special orderflow channel discipline, and we used a queueing theory model to prove something simple (and rather obvious) about two extreme cases.

The real measure of this kind of approach will be whether we can use it to prove things about more subtle and complex scenarios that without a rigorous model might be susceptible to “proof by obfuscation.”

If you want to dive deeper, check out the paper which is now on arXiv.org. TeX and Jupyter notebook sources are also available at https://github.com/awmacpherson/frp22-adversarial-queues/.

  1. Thanks to Emmanuel Awosika for comments and suggestions on an early draft of this post. ↩︎

  2. Even for mempool size dynamics, we at least need to assume that block producers stuff as many transactions as possible from the mempool into the block, a hypothesis that doesn’t always hold in practice. ↩︎

  3. See chapter 18 of Algorithmic game theory. ↩︎

  4. Please see the paper for a more precise statement of these hypotheses. ↩︎