The inspiration for this article came after attending the excellent MEV-day at Amsterdam Blockchain Week. Originally, I wanted to try to pin down a definition of MEV that better reflected how people are actually using it than the one current in academia. After some consideration, it became clear that what I was looking for is not a single definition, but better models and more precise terminology in various subdomains of a field of research designated by the term.

The definition I have seen of MEV in the literature (cf. e.g. Babel et al. (2021)) is as a maximum over possible blocks on a set of transactions of utility for the miner. Since the miner chooses the block, this set of blocks is also a set of actions of the miner in a scheduling game; taking the maximum translates to taking the best-response strategy. Hence we arrive at the following reformulation the definition of MEV:

Pseudo-definition. MEV is the utility of a best-response strategy of miners in a scheduling game.

The definition is only “pseudo” because we didn’t define the notion of a scheduling game — this is where the nuance lies. We already mentioned the miner’s action space, but there are other players: the clients, whose messages define the miner’s view and hence his action space and payoffs. A treatment of MEV that neglects the influence of these clients on block construction is necessarily incomplete.

Indeed, the seminal work that brought the phenomenology of the real-life scheduling game to public attention observed clients, or so-called searchers, optimising and largely capturing supposed “miner” extractable value (Daian et al, 2020). Although miners really do have the final say about transaction ordering, in practice the miners of the blocks observed in op. cit. were content to accept the suggested ordering implied by the outcomes of priority gas auctions. The goal of this article is to exhibit a more realistic scheduling game that admits this strategy profile.

Pseudo-definition. MEV searching is the process of optimising over client strategies in a scheduling game.

Contents of the article

In this article we discuss a class of scheduling games in which clients dispatch messages containing explicit scheduling requests of various types that enclose a reward for the scheduler (miner) if a predicate is satisfied. This game provides a language for discussing of client-side or searcher strategies. We explore how “naive,” PGA, and Flashbots-based scheduler and client strategies can be expressed in this framework.

We define both types of agents, action spaces, information sets, and what it means for a protocol to admit payments for scheduling requests of a certain type. We treat the full specification of payoffs as well as internal structure of state and transaction as opaque variables. The strategy space of the scheduler, as we have mentioned already, is the space of blocks on the set of messages it can see. Clients participate by sending messages to the scheduler; in other words, their strategies control the action space, hence payoffs, of the scheduler. Clients may extract value by bundling expressive scheduling requests with their messages along with promises of payoffs for the scheduler.

MEV is commonly associated with the practice of watching the public mempool and reacting adaptively. This association is incorporated into our game by expressing the action space of all parties in terms of their view of pending transations.

Scheduling games

We model the scheduling game as a game with two types of agents:

  • Schedulers who have the power to commit blocks directly to the blockchain. (In Nakamoto consensus, these would be the miners; in PoS Ethereum, they are the block proposers). The strategy space of a scheduler is the set of possible blocks on its message pool view.
  • Clients (a.k.a. searchers) who send messages to schedulers over various channels (public or private). Their strategy space is defined by the types of messages schedulers understand.

All agents of either type are referred to as nodes. Any player with sufficient capital can choose to act as a scheduler and client simultaneously and hence deploy correlated strategies, but a discussion of this is beyond the scope of in the present article.

In a real-life system with distributed block production, agents may only intermittently or probabilistically have scheduler actions available to them. Our model is static, and captures the residual game that occurs given a fixed scheduler agent at a particular block. We elide the subtleties of how the block commitment process actually works, i.e. the consensus mechanism.

Preliminaries

Transactions and blocks

In our model a transaction is just an opaque element of some set. The reader can imagine it to be some arbitrary bitstring; its internal structure is not essential to the present discussion.

Definition. A block on the set $\mathcal{P}$ is a finite subset $B\subseteq \mathcal{P}$ together with a total order $<$ on $B$. We intepret the ordering as a schedule: $m<m'$ if $m$ is before $m'$ in the block (i.e. gets applied first). Blocks may be required to satisfy additional validity conditions, for example that the map be injective, but these will be treated informally in this article.

We introduce the following notation: if $B\subseteq\mathcal{P}$ is a block, $m\in B$, and $m'\in\mathcal{P}\setminus B$, then we write $$ B_{m\mapsto m'} := B\sqcup\{m'\}\setminus\{m\}\subseteq \mathcal{P} $$ for the block obtained from $B$ by switching out $m$ for $m'$.

Scheduling predicates

A scheduling predicate on $\mathcal{P}$ is a predicate on the set of blocks $(B,<)\subseteq\mathcal{P}$. We have various linguistic elements to express such predicates. Here are some examples, roughly in order of increasing complexity:

  • Elements of $\mathcal{P}$.
  • Set membership in $B$: $m\in B$, where $m$ is a message.
  • Order formulas $m<m'$, where $m$ and $m'$ are messsages.
  • Boolean logic operations (AND, OR, NOT); tautology $\top$ and contradiction $\bot$.
  • Index expressions $B[i]$, i.e. the $i$th element of $B$.
  • Successor operation $s(m)$, i.e. the message immediately after $m$ in $B$.
  • Universal or existential quantification over $B$.
  • Predicates of $n$ message-valued variables (whose form may depend on the internal structure of a transaction).
  • Predicates of “execution state” immediately before a given message (undefined in the present model but would be valid in the context of Ethereum).

Note that a block validation rule is a scheduling predicate.

Messages

A message predicated on the set $\mathcal{T}$ is a tuple $m:=(t,R,p,Y)$, where:

  • $t\in \mathbb{B}^*$ is a “transaction”;
  • $R$ is a scheduling predicate on the set $\mathcal{T}\sqcup\{\mathtt{this}\}$, where $\mathtt{this}$ is a special symbol referring to the message of which $R$ is a component;
  • $p>0$ is a “bid;”
  • $Y$ is a client, called the signer of the message.

Action and information sets

Views

Every participant $X$ in the network has a view $\mathtt{in}_{X,t}$ of its inbox at time $t$, which is a set of messages. Of these, a subset $\mathtt{in}_{X,t}^\mathrm{pub}\subseteq \mathtt{in}_{X,t}$ are in the public mempool; others may be known to $X$ alone through other channels. Both these sets are monotone increasing on the interval $[0,T)$ where $T$ is the time at which the next block is committed.

Assuming a connected network, the public mempool has the special property of being cofinal for any two (mempool-watching) participants. That is, if $X,X'$ are two participants, then $\mathtt{in}_{X,t}^\mathrm{pub}\subseteq \mathtt{in}_{X',t+\Delta}^\mathrm{pub}$ where $\Delta$ is the network propagation delay between $X$ and $X'$.

Since time doesn’t play a huge role in the present discussion, we’ll suppress the second subscript for the rest of this article.

Client

Each client $X$ can create and sign messages with scheduling predicates on the message pool $\mathtt{in}_X$ and send them to other nodes over various channels, for example:

  • publicly over a standard peer to peer network, so they eventually appear in $\mathtt{in}_Y^\mathrm{pub}$ for all connected nodes $Y$;
  • over a private channel (e.g. an encrypted email that reads “I will pay you €500 to include my transaction $t$ in position $i$").

Hence, strategies for $X$ are sets of messages predicated on $\mathtt{in}_X$, with signer $X$, together with a channel to send them over.

Scheduler

An action for a scheduler $X$ given view $\mathtt{in}_X$ is a block on $\mathtt{in}_X$. Note that this means schedulers create blocks of messages rather than transactions.

Since this view is made up of messages sent by clients, the scheduler’s action set depends on previous actions taken by clients. Schedulers can also act as clients, so they are also free to create their own signed messages, add them to $\mathtt{in}_{X}$, and use them to create blocks.

In particular, the scheduler may:

  • Omit any message from $\mathtt{in}_{X,T}$ (censoring);
  • Insert any number of its own transactions;
  • Put messages in $\mathtt{in}_{X,T}$ and its own messages in any order.

However, it cannot create transactions signed by other parties.

Remark. The reader may object that this model does not take into account block or chain validation rules, but these may be incoroporated into the payoff functions by adding a large negative term (or $-\infty$) to the payoff functions of invalid blocks.

We can aggregate these rules by modelling them as the scheduling request of a message $m_\mathrm{valid}$ signed by a special “validity actor,” such that the scheduler’s payoff is $-\infty$ if $m_\mathrm{valid}$ is not included (say at the top of the block).

Remark. While in principle a scheduler’s strategy space is the set of all blocks on the transaction set, in practice they may choose to optimise over a restricted strategy space in order to save on operational costs.

Utility

First, a bit of notation: for the utility of a player $X$ under strategy profile $(s_X,s_\mathrm{other})$ we write $u_X[s_\mathrm{other}](s_X)$ (so the argument in square brackets is the strategy of players other than $X$). All parties' payoffs depend only on the block produced by the scheduler.

If clients' scheduling preferences are to be respected by the scheduler at equilbrium, its utility ought to depend on them in some way. Here is one simple way of doing this:

Definition. Let $m=(t,R,p,Y)$ be a message and write $m':=(t,\top,0,Y)$ for the corresponding message sent with trivial scheduling request. We say that the game supports fees for $m$ if the payoff function for a scheduler $X$ satisfies the formula: $$ u_X(B) - u_X(B_{m\mapsto m'}) = p \text{ if }R(B)\text{ else }0 $$

for all blocks $B$ containing $m$, while the signer $Y$’s payoff satisfies $$ u_Y[B](S) - u_Y[B_{m\mapsto m'}](S') = -p \text{ if }R(B) \text{ else } 0 $$ for any $B$ and sets of messages $S$, $S'$ such that $m\in S$ and $m'\in S'$ (the latter condition being necessary for the formula to be defined, since $Y$-signed messages must have been sent by $Y$).

In other words, if $X$ receives the message $(t,R,p,Y)$ from $Y$ and $X$ produces a block $B$, $Y$ pays $X$ $p$ if and only if $R(B)$.

The quantity $p$ would ordinarily be denominated in a “native asset” whose transactions are recorded in the chain to which $B$ is to be appended. In this case, this asset is also the numéraire for the utility function. However, our theoretical model allows also for clients that send messages to schedulers out-of-band, in which case it is up to the scheduler whether to a) parse the scheduling predicate and b) trust that the fee $p$ will be delivered according to the above formulae.

Anecdotally, if the reward is large enough, clients and schedulers will invest in the infrastructure necessary to communicate scheduling preferences not explicitly supported by the core protocol.1

Remark. This model is limited and/or unrealistic in a number of ways.

  • Payments in-protocol would usually require that $Y$ have a current balance of at least $p$ of a native asset in the state reached immediately before the message $m$ is applied. I don’t know.
  • There are at least two reasons that the payoff of the scheduler may be strictly less than the amount $p$ paid by the client:
    1. The scheduler does not completely trust that the client will pay in the event the predicate is satisfied, for example if they are using an out-of-band channel. The trust level can be modelled by a discount to the payoff.
    2. An EIP-1559 style mechanism in which a proportion of the payment is “burned.”
  • A further design direction is to add a third branch to the scheduler’s payoff function, where they receive a penalty for including a message into a block that doesn’t satisfy its scheduling predicate. For example, the protocol might consider a block invalid in this case.

Despite these limitations, it is rich enough to start discussing some real-world cases that it seems to me were not properly modelled by the existing literature.

Examples

The space of possible scheduling predicates, and hence pricing mechanisms, seems likely to be intractably large. Rather than attempt to gain a view of the whole space, we content ourselves here by exhibiting some real-life examples in the context of the scheduling game.

A simple payments protocol

A simple distributed ledger of payments might support fees for messages of the following form: a client $Y$ submits a message of the form $$ (t,(t\in B_\mathtt{tx}),p,Y) \qquad (\dagger) $$ where the transaction $t$ contains the full data of the other three components in a format understandable to the standard block validation protocol, $p$ is denominated in a native asset possession of which is assumed to yield constant payoff, and $Y$ has a balance of at least $p$ in this asset. The scheduling predicate here is “first order” in the sense that it only refers to the bundled transaction.

It is possible to effectively send the transaction without the scheduling request by setting the gas fee to zero. That is, the following messages are strategically equivalent: $$ (t,(t\in B_\mathtt{tx}), 0,Y) \sim (t,\top,0,Y). $$ Modulo identifying these two messages, the scheduling game does indeed support fees for messages of the form $(\dagger)$.

Richer predicates via gas auctions

The reference node implementation for many blockchain protocols implements a simple default strategy for scheduling blocks.

Definition. The greedy block stuffing strategy orders transactions of the form $(\dagger)$ in terms of their gas price, up to some protocol-determined limit.2

In practice, the assumption that schedulers run greedy block stuffing has often been satisfied (less so nowadays with Flashbots extensions). That is, miners behave as if greedy block stuffing were part of the block validation rule. If we incorporate this assumption into our model, setting the gas price for a transaction guarantees a much richer scheduling condition, expressed by the first order formula $$ \phi_\lambda(s) := \forall m\in B \quad [(p_m<\lambda\rightarrow s<m) \wedge(p_m > \lambda\rightarrow s<m)] \quad (*). $$ Note that this formula includes a universal quantification over a set of messages not visible to the client at the time of submitting the request. In practice, this is equivalent to a finite set of quantifier-free predicates bounded by the maximum block size divided by the minimum message size.

Clients $Y$ may use the formula $(*)$ as a primitive to construct more sophisticated scheduling requests such as top-of-block or backrunning. However, this approach has limited expressive power: $Y$ cannot request an ordering of elements of $\mathtt{in}_Y$, and may only request a special kind of ordering of $t$ relative to the view of the scheduler $X$: that $t$ sit in the middle of a slice of the gas price function $\mathtt{in}_X\rightarrow \mathbb{N}$.

The actual Ethereum protocol fees market does not explicitly support fees for this predicate in the sense defined above: in general, there is no in-band message one can send to a miner such that a fee is paid if and only if the block satisfies $(*)$. This is a point of divergence between the actual game as defined by the full node code and the game that agents appear to think they are playing — perhaps in a form of social consensus.

Out of band requests

Suppose that a client $Y$ wishes to express a more complex request $P$ than is explicitly supported by the protocol, and that a messaging address is known in advance for the scheduler $X$ of the next block.3 Then $Y$ can send a private message $(t,P,p,Y)$ to $X$ expressing his request. The core protocol does not guarantee delivery of $p$ native tokens if the request $P$ is satisfied, but this may be guaranteed in other ways, for example, by a third party that $X$ and $Y$ trust, with the level of trust integrated as a discount to $X$’s payoff.

For example, the Flashbots relay provides a channel over which a client may send messages of the form $(t, \phi, p, Y)$ where:

  • $t$ is a “null” transaction, that is, it contains only a commitment to the other three components (this condition lives at the level of the Ethereum interpretation of our model; it isn’t defined within the model itself);

  • $\phi$ has the form $$ \phi(B) = [B[0]=m_0\wedge \cdots\wedge B[k]=m_k] $$ where $m_0,\ldots,m_n\in\mathtt{in}_{Y}\sqcup{t}$.

Flashbots also allows its clients to bundle a set $S$ of more than one transaction with a predicate on $\mathtt{in}_Y\sqcup S$. This move can be approximated in our model by sending each $t\in S$ in a separate message $(t,\top,0,Y)$ having trivial scheduling predicate and bid followed by a message $((),\phi,p,Y)$ with trivial transaction. This model is not quite strategically equivalent to bundling the schedule request with the transaction because miners may include the transactions in $S$ without the scheduling message. Whether or not it is theoretically possible to do this, Flashbots-enabled miners seem to avoid this strategy4, that is, they behave as though it has large negative utility — presumably another example of social consensus.

Future work

The space of possible scheduling requests, and hence of protocol validation rules or pricing mechanisms, is huge and probably intractable. I propose a number of different questions and avenues along which research on this subject could continue:

  • Try to establish criteria under which searchers' best strategies are to send transactions to the public mempool.
  • Obtain expressions for the space of all possible pricing or validation mechanisms for scheduling predicates. Try to find restrictions on the space of “realistic” mechanisms, either by restricting to closed subspaces or via some sort of complexity measure (for example, based on length of the predicate expressed in a fixed language).
  • Packing a block with messages having more complex scheduling requirements than inclusion is a “higher-order” analogue of the knapsack problem in which the value of each item depends on its position relative to other items. In particular, inclusion of some messages invalidates others in ways that can be quite complex to check, which means the greedy block stuffing strategy is no longer applicable. Which classes of predicates still permit reasonably tractable solutions to this problem, perhaps in an idealised model with unbounded blocks?
  • Study further examples of pricing mechanisms that do not currently exist in the wild, and hence develop proposals for novel extensions to blockchain protocols. One direction I find particularly promising is to mimic well-studied concurrency primitives in computing, such as the property that a transaction “block on” another transaction ($m' < m$).
  • Classify ways in which MEV strategies affect users of important classes of dapps, major examples being AMMs, lending protocols, and NFT auctions. Which classes of predicate give greatest utility in these strategies?
  • How can the design of these classes of dapps be made “MEV-aware” so that the negative UX effects of these strategies is mitigated? Explore dapp designs that assume (some) clients will use nontrivial MEV strategies, both in existing blockchain protocols and in extensions by novel concurrency primitives.

References

  • Babel, K., Daian, P., Kelkar, M. and Juels, A., 2021. Clockwork finance: Automated analysis of economic security in smart contracts. arXiv preprint arXiv:2109.04347.
  • Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L. and Juels, A., 2020, May. Flash boys 2.0: Frontrunning in decentralized exchanges, miner extractable value, and consensus instability. In 2020 IEEE Symposium on Security and Privacy (SP) (pp. 910-927). IEEE.
  • Dantzig, G.B., 1957. Discrete-variable extremum problems. Operations research, 5(2), pp.266-288.
  • Kulkarni, K., Diamandis, T., Chitra, T., 2022. Towards a theory of maximal extractable value I: Constant function market makers. self-published preprint https://people.eecs.berkeley.edu/~ksk/files/MEV_CFMM.pdf
  • Obadia, A., Salles, A., Sankar, L., Chitra, T., Chellani, V. and Daian, P., 2021. Unity is Strength: A Formalization of Cross-Domain Maximal Extractable Value. arXiv preprint arXiv:2112.01472.

  1. Source: MEV day dark stage. See for example https://www.youtube.com/watch?v=9iHlyaRsgYI&list=PLRHMe0bxkuel3w3C7P_WVvp9ShLi3HKRI&index=20 ↩︎

  2. This strategy might more commonly be termed a greedy approximation algorithm for the bounded 0-1 knapsack problem (Dantzig, 1957). ↩︎

  3. Even if the address of $X$​​ is not known in advance, as is the case in PoW systems, $Y$​​ can achieve a similar effect by sending his message to many miners. Payoffs to this strategy are multiplied by the (weighted) proportion of miners to which $Y$​​ sends messages. ↩︎

  4. I’ve seen this written down somewhere, but can’t seem to track down the link. ↩︎