Honest MEV: a Theoretical Perspective
Greetings
Hi there! We are a research team Togzhan, Soroush, Amir, Sergei who cares about blockchain research, algorithms, and optimization.
TL;DR; (aka abstract)
We propose a new research direction: using graph parameters to solve the honest MEV problem (the problem of forming a block with maximum gas fees by an honest miner). The method was successfully tested on real-world data from other blockchains, increasing miners’ revenue by 13.4% on Bitcoin (~100 million USD/year) and by 55.7% on Cardano (~0.5 million USD/year). However, Ethereum presents unique challenges that are yet to be overcome: non-trivial transaction dependencies, a unique reward model, and a non-UTXO model which causes undecidability. We look forward to the community’s opinions and suggestions regarding the challenges we face.
Related Works
Our previous for other blockchains:
- Bitcoin: https://hal.science/hal-03232783v2/file/OptimalMining.pdf
- Cardano: https://hal.science/hal-04616639/file/main.pdf
Similar work on ethresear.ch:
The Project
What is Honest MEV? Let’s consider the perspective of an honest validator – one who refrains from frontrunning, sandwiching, and other dishonest behaviors. The reward we receive for validating a block includes the base reward, and the gas fees paid by transactions. The gas fees are the only variable we can influence, so naturally, we’re interested in maximizing them.
What do we want to do? We have only one degree of freedom: how to take an ordered subset of the transactions from the pool to a new block to maximize the gas fees. Our main ambition is to make this decision procedure optimal, fast, and accessible for everyone.
I’m not a block proposer, why care? Besides the obvious benefits to an honest block proposer, the indirect impact of our project is far greater:
- It helps validators achieve maximum block utilization
- It helps with throughput, allowing more transactions to be added to the consensus chain faster
- The increase in revenues also incentivizes more people to become validators, helping more decentralized consensus.
- In addition to protocol constraints (e.g. dynamic pricing policy for gas), external constraints also commonly influence miners’ decisions. For example, miners may choose to produce smaller blocks to speed up block propagation or adjust the algorithm to manage different sets of transactions within the pool. The primary goal of the divine algorithm is to allow miners to maximize their profitability, within the constraints. This means that even if a miner has to create a small block, she can still maximize her revenue by picking a better set of transactions.
What has been done already? If the problem is so fundamental, someone must have done something about it already, right? Right. Our team has a line of research devoted to developing optimal mining algorithms, i.e. algorithms that produce blocks with maximum rewards, for different blockchains, we successfully tested, implemented and published optimal approaches for the Bitcoin and Cardano blockchains. We tested our approach on the real world data and achieved a 13.4% increase in transaction fees on Bitcoin (~100 million USD/year) and a 55.7% growth on Cardano (~0.5 million USD/year). Moreover, the problem has independently attracted the attention of other Ethereum researchers
Why not just reuse the previous algorithms? The Ethereum execution model is inherently complex as it does not follow the UTXO model; the final gas fees as well as gas consumption of one transaction might depend on others, it makes a huge tractability gap compared to other networks.
While for two transactions it is simple to say if they are not conflicting (by checking a set of predefined rules, like nonce, balance, etc), it is really hard to say if one transaction interferes with others gas consumptions; if not a block gas limits, the gas dependency problem is theoretically undecidable, and if having a gas bound it is EXPTIME-complete.
So what is your plan? Our plan has several subgoals:
- Find a way to detect all dependencies between the transactions in a pool
- Formulate the problem as an optimization instance with a graph input
- Implement the algorithm and test it on real pools and blocks
Where can I see more technical details? Sure, in the next few paragraphs we want to give a deeper introduction for our framework, and what challenges we are facing.
Transaction Interference
There are three ways how transactions might affect each other: they might
- depend on each other, i.e. one transaction cannot be included to a block unless another is included
- conflict, i.e. cannot both appear in the same block
- gas dependent, i.e. depending on co-occurrence of two transactions, their gas fees might be different
We will illustrate all interference types with a simple example.
Dependency Interference
In a correct block, transactions originating from the same account must have sequential nonce, lower nonce must appear before transactions with higher nonce to preserve the ordering. When a miner observes the transaction pool, she should choose transactions in a way that preserves an increasing nonce order for a particular account.
This requirement creates the dependency relations, captured as oriented dependency edges in the interference graph.
Conflict Interference
Transactions originating from the same account must have sequential nonce, it is not allowed to have two transactions with the same nonce. When the miner encounters two transactions with the same nonce, he has to choose only one of them to be included in the block.
We introduce undirected conflict edges to the graph to represent this restriction.
Gas Dependency Interference
The last one is the most complicated relation, we will demonstrate it using a simple example. Consider a smart contract with the following two functions f and g:
function f(): x = 1000
function g(): for i=1 to x { do something }
Assume that x is originally 0 and there are two transactions Tx1 calling f and Tx2 calling g. If the validator puts Tx2 before Tx1, the for loop in g terminates immediately, using very little gas. However, if Tx1 is put before Tx2, then much more gas is used in g, leading to higher revenues for the validator.
DCG Graph
We call a DCG graph a graph with each vertex representing a transaction in the mempool and edges of three sorts, with one for each type of interference.
A graph abstraction is an important step in our framework as it splits the problem into two subtasks: constructing the graph from the mempool and solving the optimization problem over the graph.
Graphs and Optimizations
Many graph problems are known for being very difficult. Our case is no exception: having only conflict-type edges makes the problem of choosing an optimal subset of vertices for the answer set strongly NP-hard. This essentially means we cannot hope for an algorithm that is fast, optimal, and works on all inputs. When we cannot have all three, we can still choose two, and that is what happens in practice:
- {works on all inputs, fast,
optimal}: if we discard optimality, we find ourselves in the realm of approximate and heuristic algorithms. - {works on all inputs,
fast, optimal}: discarding the requirement to be fast leads to exponential time algorithms. While they might work on tiny inputs, it is unfeasible to run them on real data. - {
works on all inputs, fast, optimal}: generally hard problems become very easy in the special cases. For instance, a three coloring problem is trivial for tree graphs. We claim that real-world graphs are well-structured, and this structure can be exploited to build fast and optimal algorithms.
However, we don’t provide an exact definition of a well-structured graph, there is a [zoo of graph classes](https://www.graphclasses.org/). For some graph classes, there often exists a specially tailored algorithm which works well within the given class (see our previous publications). One step of our research program is to identify the most suitable class the real graphs belong to and design an algorithm which works within that class.
An Example
We will demonstrate our ideas with an example. The oversimplifications here are intentional, allowing us to showcase the main techniques without getting bogged down in technical details.
The classical knapsack problem is [weakly NP-hard](https://en.wikipedia.org/wiki/Weak\_NP-completeness), and there are polynomial algorithms when all item volumes are discrete and each volume belongs to the set [1,…,N]. In this case, there is a dynamic programming algorithm that is polynomial in:
- The size of the knapsack S
- The maximum possible volume N
Consider an extremely simple version of the knapsack problem: all item volumes are equal to 1. How can we find an optimal value packing when the capacity of the knapsack is S? The algorithm is trivial: sort the items in decreasing order of price and select the top S most valuable items.
Translating this to the optimal block mining language, all transactions pay an equal gas fee of 1, and have no conflicts or dependencies, the optimal block would consist of the transactions offering the highest tips. This holds when there are no conflicts or dependencies.
What happens when we add interference edges? Again, let’s keep it simple and assume that we have only conflicts. Going back to the knapsack formulation, for some pairs of items, we cannot pack them together.
The problem suddenly became very hard. It’s not just NP-hard, it’s strongly NP-hard. The reason for that, that the problem of finding a [maximal independent set](https://en.wikipedia.org/wiki/Maximal\_independent\_set) is a special case of our problem: by setting the knapsack capacity to infinity and all weights to 1, finding the optimal knapsack becomes equivalent to finding a maximal independent set.
Although it is clear that not all graphs can be achieved as a conflict graph of a set of transactions (and in fact, the dependency graph is always a union of cliques), this aligns with our final goal: exploit specific graph patterns to design a faster algorithm.
Do demonstrate how, assume that the conflict edges form a binary tree. The full list assumptions we are making till this point are:
- Each transaction uses 1 unit of gas
- We don’t make a restriction on the tips the transactions can pay
- The only type of interference edges we have are conflict edges, and they form a binary tree (the least realistic assumption)
This problem from strongly NP hard becomes again polynomial time solvable! The main algorithmic technique for this is dynamic programming, we will demonstrate it on a concrete example.
Consider a pool of 6 transactions {a, b, c, d, e, f} with unit gas usage and with the miner tips given in the table
| Tx: | a | b | c | d | e | f |
|---|---|---|---|---|---|---|
| Total tip: | 6 | 7 | 1 | 3 | 7 | 5 |
| Gas usage: | 1 | 1 | 1 | 1 | 1 | 1 |
Let us fix the size of the block to be 3. Further suppose that the miner observed a set of conflicts which form a binary tree with the edges {(a, b), (a, c), (b,d), (c,e), (c,f)}:
Introduce a tensor table opt[tx, IsIncl, Cap] with tx ∊ {a, b, c, d, e, f}; IsIncl ∊ {“no”, “yes”} and Cap ∊ {0, 1, 2, 3, 4}.
The value of the tensor is defined as:
opt[tx, “no”, c] := “the best revenue a miner can get, only using transactions from the subtree of tx, when tx is not included, if the block capacity is c”
And the similar rule for “yes”:
opt[tx, “yes”, c] := “the best revenue a miner can get, using only transactions from the subtree of tx, when tx is included, if the block capacity is c”.
Now our goal is to fill this table with values, then we can find the maximum possible benefit as
max(opt[a, “no”, 3], opt[a, “yes”, 3]),
I.e. as maximum profit which can be achieved using the subtree of a (which is the whole set {a, b, c, d, e, f}) and a block of capacity 3.
The filling out strategy is called bottom-up dynamic approach, we are going to fill the tables starting from the leaves of the tree, advancing to the root.
The values in the leaves are determined as:
opt[tx, “no”, *] := 0
As if we don’t take the leaf transaction, the bag is forced to be empty
opt[tx, “yes”, 0] := - inf
It is merely a convention to put the negative infinity profit, as such a configuration is not feasible: the “yes” field forces us to take the item tx to the set, but the value 0 constrains the block capacity to be 0. And the last case for the leaf table:
opt[tx, “yes”, ≥ 1] := tip(tx),
As we are forced to include transaction tx to the block, and including it does not exceed the block capacity.
For the running example after the initialization step we will have:
To fill out the tables for the internal nodes, we again will consider two cases, if the node is forced to be included or not “yes”/”no”. Let’s start from the “yes” case, when a note tx is forced to be included to the block. The node tx has up to two children, suppose that it has exactly two children tx_l and tx_r (the case of one child can be handled by introducing a fake node with unit gas usage and zero tips).
Then to find the value of opt[tx, “yes”, c] first we need to allocate one unit of our capacity to the transaction tx, and the remaining capacity is split between two subtrees. Observe that if we took tx, then we cannot take neither tx_l or tx_r to the block because of the conflict edges from tx. Therefore
opt[tx, “yes”, c] := tip(tx) +
max (opt[tx_l, “no”, i] + opt[tx_r, “no”, c - i - 1])
for i in [0, c)
The i indicates the capacity allocated to the left child, and all remaining capacity is allocated to the right child.
Similar reasoning leads us to the formula for the “no” case:
opt[tx, “no”, c] := max(
max{opt[tx_l, “no”, i], opt[tx_l, “yes”, i}
+ max{opt[tx_r, “no”, c - i - 1], opt[tx_r, “no”, c - i - 1]})
where having to have max{opt[tx_l, “no”/”yes”, *]} is caused by necessity to consider two cases whether to include or exclude the child from the set. Filling the tables using these formulas, we end up with:
We can see that the optimal block of size 3 will produce revenue 19 from the table at the root, which is the case for the block {b, e, f}. Finding not only the answer but also the block itself is achieved by a standard technique of keeping the optimal capacity split between the children when evaluating the formula for the internal nodes, as well as keeping the optimal decision whether to take a child to the set or not.
Despite the oversimplifications we made, our general algorithms for other blockchains have the same flavor: we find a way to build the graph starting from elementary parts (leafs for this case) using simple combining operations (combining two children subtrees into the node’s tree in this case) and providing the way to recompute the objective function during the combination operation.
Challenges
We identified the challenges we need to address during the project. The challenges vary in nature: some are related to engineering and computation, while other are purely theoretical.
We anticipate to face the following challenges:
- to have a well-connected node to access the transaction pool.
- to be able to execute transaction bundles and obtain their gas usage.
- to be able to Identify if two transactions are exactly gas dependent is possible if we execute every possible subset of transactions and in every possible order. One way is to use various tools which include symbolic execution tools and static analysis tools.
- to examine the structure of the transactions interference graph, choose the closest class from the zoo of graph classes and create an efficient algorithm solving the optimization problem
Opinion Request
We truly believe it is possible to obtain an increase in the transaction revenue for Ethereum and beat real-world miner results. If we do this, it would greatly benefit both miners and the Ethereum ecosystem. What do you think about this project? Please feel free to share your opinion and potential concerns. Let’s have a discussion below! 