# Boosting Gas Revenues of Ethereum Miners

Togzhan Barakbayeva, Soroush Farokhnia, Amir Kafshdar Goharshady, Sergei Novozhilov

► To cite this version:

Togzhan Barakbayeva, Soroush Farokhnia, Amir Kafshdar Goharshady, Sergei Novozhilov. Boosting Gas Revenues of Ethereum Miners. International Conference on Software Engineering, Apr 2026, Rio De Janeiro, Brazil. [hal-05458791](https://hal.science/hal-05458791v1)

HAL Id: hal-05458791

https://hal.science/hal-05458791v1

Submitted on 14 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Boosting Gas Revenues of Ethereum Miners

Togzhan Barakbayeva

tbarakbayeva@connect.ust.hk

Hong Kong University of Science and Technology

Hong Kong, China

Amir Goharshady

amir.goharshady@cs.ox.ac.uk

University of Oxford

Oxford, United Kingdom

Soroush Farokhnia

sfarokhnia@connect.ust.hk

Hong Kong University of Science and Technology

Hong Kong, China

Sergei Novozhilov

snovozhilov@connect.ust.hk

Hong Kong University of Science and Technology

Hong Kong, China

## Abstract

In cryptocurrency networks, transaction-fee revenue serves as the primary financial incentive for miners to participate in the consensus mechanism, securing the network by validating transactions and extending the blockchain. Maximizing this revenue is therefore a key optimization problem for miners. While this has been studied for UTXO blockchains like Bitcoin, where transaction fees are fixed, we focus on Ethereum, where the challenge is significantly greater. On Ethereum, the fee paid by a transaction depends on its execution cost (gas), which can change based on the ordering of preceding transactions in a block. This creates a combinatorial explosion, as miners must select not only a subset of transactions but also their optimal permutation to maximize revenue.

In this work, we present a randomized framework to address this problem. Our approach first uses randomized testing, executing sample permutations of pending transactions to profile their gas usage. From this data, we employ decision trees to learn transaction interdependencies, identifying a small “neighborhood” of transactions that influence each other’s execution costs. These dependencies are then encoded as a set of logical rules that predict gas usage based on local transaction ordering. Finally, we translate these rules and other constraints (e.g., block gas limit, nonce ordering) into an integer linear programming (ILP) instance, which we solve to find a block composition that maximizes total tip revenue. Our experimental results demonstrate significant gains: our method outperforms real-world Ethereum miners by an average of 73.45 percent per block, which corresponds to roughly 63 million USD per annum.

## 1 Introduction

Our goal in this work is to develop an optimization approach to increase the transaction-fee (gas) revenues of Ethereum miners. Although we focus on Ethereum, our techniques are general in nature and can be applied to other programmable blockchains as well. There are two reasons for the emphasis on Ethereum: First, Ethereum is currently the world’s second largest cryptocurrency by market cap, behind only Bitcoin. At the time of writing, it has a total value of around 250 billion USD [15]. It is also by far the largest programmable cryptocurrency, with support for arbitrary smart contracts written in a Turing-complete language [54]. Second, Ethereum has an account-based execution model which is significantly different than the UTXO (Unspent Transaction Output) model of Bitcoin. Thus, there is a research gap as the techniques

developed for Bitcoin and other UTXO miners, such as [8, 40], are not applicable in our context.

We start by defining our problem and summarizing our contributions in Section 1.1. Preliminaries and necessary background are covered in Section 2. We present the basics of blockchain and mining in Section 2.1. This part can be safely skipped by readers who are already familiar with the topic. Next, in Section 2.2, we present details of Ethereum’s architecture and the account-based model. Section 3 is a summary of related works, including examples that illustrate the differences between our setting and that of Bitcoin. We omit many details which are orthogonal to the problem at hand.

### 1.1 Problem Definition and Our Contributions

**Our Focus.** In this work, we address the problem of maximizing the total transaction fee revenue of an honest miner, i.e. a miner who does not perform attacks or seek revenue from non-transaction-fee sources such as smart contract interactions. Such a miner listens for newly-broadcast transactions not yet added to the blockchain and selects an ordered subset to form her block. The goal is to maximize the sum of tips paid by the transactions.

**Formal Definition of the Problem.** Suppose that the miner intends to add the k-th block to the blockchain. Let Pool be the set of new valid transactions known to the miner which are not yet added on the blockchain. A block is a sequence $B = \langle tx_1, tx_2, \dots, tx_n \rangle$ of transactions from Pool such that for every $i < j$, if $tx_i$ and $tx_j$ belong to the same user $a$, then $tx_i$'s nonce is smaller than $tx_j$'s nonce. Moreover, if there is a transaction from $a$ with nonce $v \ge 1$, then there should be a previous transaction from the same user $a$ with nonce $v-1$ either in the same block or in previous blocks that are already added to the blockchain. This ensures that every transaction is added at most once and that the transactions by the same user cannot be reordered. Denote the world state at the end of the previous block ($k-1$) by $s_0 \in S$. For all $1 \le i \le n$, define

$$s_i = \delta_{tx_i}(s_{i-1}) \qquad y_i = \text{gas}_{tx_i}(s_{i-1}) \qquad \tau_i = \text{tip}_{tx_i}(s_{i-1}).$$

Intuitively, assuming that the miner appends $B$ to the blockchain, $s_i$ is the world state after $tx_i$ has finished running, $y_i$ is the gas usage of $tx_i$ and $\tau_i$ is the total tip paid by $tx_i$ to the miner (formal definitions and details can be found in Section 2). The miner aims to maximize the tips, while not exceeding the block gas limit $L$. Thus, the optimization problem is to find a valid block $B$ so as to:

$$\max \quad \sum_{i=1}^{n} \tau_i \qquad \text{s.t.} \quad \sum_{i=1}^{n} y_i \le L$$
**OUR ALGORITHMIC CONTRIBUTION.** In Section 4, we design and present a randomized algorithm that combines testing, decision trees, localization techniques and integer linear programming (ILP) to handle the optimization problem above. We start by executing several test cases, i.e. random permutations of the transactions in our Pool, and profiling their gas usage. Then, using decision trees, for every transaction $tx \in \text{Pool}$, we find a set of other transactions that can affect its gas usage. We call this the neighborhood of $tx$ and denote it as nbhd($tx$). Intuitively, we expect the neighborhood of every vertex to be small since, in real-world instances, most transactions are completely independent of each other. For example, a pair of transactions that do not access the same smart contracts cannot affect each other's gas usage, either. We provide a probabilistic argument showing that with high probability our testing covers every possible permutation of each neighborhood. Thus, we can cut, mix and glue together parts of our test cases in order to create a block that maximizes the miner's total tip revenue. This part is modeled as an integer linear programming instance and solved by an external optimization suite. All steps of our algorithm are parallelizable and, except for the ILP solver, run in polynomial time. Due to its reliance on randomized sampling and ILP-solvers, our algorithm is not guaranteed to always produce an optimal result.

**OUR PRACTICAL CONTRIBUTION.** We implemented our algorithm and performed extensive experimental results on 50,000 Ethereum blocks. For each block, we gathered real-world transaction pool data and executed our algorithm. We then compared the tip revenues obtained by our framework and those of real-world miners. Our approach increased tip revenues by a significant margin of 73.45 percent on average per block, corresponding to roughly 24.1 USD per block and 63,357,892 USD per year at current exchange rates. We also compared our tool against the default Ethereum implementation and found that our approach increased tip revenues by 18.56 percent on average per block, corresponding to roughly 17.3 USD per block and 45,416,764 USD per year. Our tool is free, open-source and dedicated to the public domain with a perpetual copyright waiver. It is accessible at https://anonymous.4open.science/r/boosting_gas_revenues_of_ethereum_miners/.

**OUR APPROACH IN THE ETHEREUM ECOSYSTEM.** Our algorithm remains relevant in the context of current practices in the Ethereum ecosystem, such as taking advantage of the Miner Extractable Value (MEV) [23] opportunities and working under Proposer-Builder Separation (PBS) [24] pipeline. Moreover, proposed framework has a broad impact on the Ethereum, including maximizing validator revenue, contributing to higher throughput, diversifying validator participants, and strengthening overall security and decentralization. This is discussed in detail in Section 6.

# 2 Preliminaries

## 2.1 Blockchain Background

**BLOCKCHAIN AND CONSENSUS.** As pioneered by Bitcoin [41], most modern cryptocurrencies use a blockchain protocol. There are three fundamental objects: transactions, blocks, and the blockchain. Transactions are the basic units of record keeping, defining the cryptocurrency's history and order. In Bitcoin, transactions transfer money in the underlying cryptocurrency. Anyone can create and

broadcast transactions, which must be validated, e.g. by checking digital signatures to prove ownership. Valid transactions are spread across the network using a peer-to-peer gossip protocol. To ensure consensus and prevent double-spending, not every propagated transaction is finalized immediately. Instead, valid transactions are grouped into blocks of fixed maximum size, and each block contains a hash pointer to the previous block, forming a singly-linked list called the blockchain. Each node maintains a local copy of the blockchain, so its history consists of all transactions in its chain, which also provides their ordering.

**MINING.** A consensus mechanism ensures nodes agree on the blockchain's contents and prevents forks. The most prominent protocols [7, 14, 20, 55, 58] are Proof of Work (PoW), used by Bitcoin [41], and Proof of Stake (PoS) [33, 34], used by systems like Ethereum [54] and Cardano [19]. In PoW, miners solve a computational puzzle to add a block, with success proportional to their computational power. In PoS, a node's chance is proportional to its economic stake. As our work is independent of the consensus mechanism, we treat it as a black box and use the term miner for all block creators (including PoS validators or block builders).

**TRANSACTION FEES.** Given that consensus heavily relies on miners and that mining is often costly, especially in proof-of-work settings, the protocol must provide rewards to incentivize mining. The miners are paid a fixed reward for every block they add to the blockchain. This is also how new units of currency are created. Additionally, to incentivize the miners to create non-empty blocks, a user who creates a transaction can decide on a transaction fee, which will be paid to the miner who adds it to the blockchain. It is well-known in the community that transactions with low fees are often ignored by the miners.

**UTXO [41].** In the UTXO model, used by Bitcoin and Cardano, transactions consume outputs from prior transactions (inputs) to create new ones. These Unspent Transaction Outputs (UTXOs) represent spendable coins. Each output can be spent only once, preventing double-spending. For efficient validation, nodes maintain a current set of all UTXOs. The total value of a transaction's inputs must exceed its outputs; the remainder is a fixed fee paid to the miner.

**PROGRAMMABLE BLOCKCHAINS.** Unlike Bitcoin's limited scripting, programmable blockchains like Ethereum [54] support Turing-complete smart contracts. These are immutable on-chain programs with their own storage and currency, where funds are controlled exclusively by the code. This design decouples consensus from transaction type, enabling applications beyond simple payments. Transactions can transfer funds, deploy new contracts as Ethereum Virtual Machine (EVM) bytecode, or call functions on existing ones. Since all nodes execute these transactions, network consensus on history extends to the state of every contract.

## 2.2 Ethereum Architecture

**ACCOUNT MODEL.** Unlike Bitcoin's UTXO model, Ethereum maintains a world state [54] composed of accounts. There are two types of accounts: Externally-Owned Accounts (EOAs), controlled by users, and contract accounts. While all accounts have a balance, contract accounts additionally contain their code and persistent
storage. Contracts are not autonomous; they only execute their code when invoked by a transaction from an EOA or a call from another contract, therefore all transactions originate from EOAs.

**GAS.** As the EVM language is Turing-complete, one can write and invoke contracts whose execution uses huge or even infinite time and memory. This is undesirable given that every transaction has to be run by all nodes on the network. Thus, intentionally executing long or resource-intensive contracts is a type of denial-of-service (DoS) attack. To combat this, Ethereum introduced the concept of gas [22]. Gas is a measure of the total resources required to run an invocation. A gas cost is assigned to every atomic operation in the EVM language, including memory usage or deploying code. The costs of atomic operations are part of the protocol and provided as a table in [18]. The initiator of a transaction has to pay a transaction fee proportional to the total gas cost of its execution. This effectively disincentivizes long and resource-hungry executions. Moreover, every block has a gas limit, which was originally set at 30,000,000 units of gas but has recently increased to 36,000,000. If the sum of gas usages of all transactions in a block exceeds this limit, the block is considered invalid and will not be added to the blockchain. This ensures that every node will have to perform only a limited amount of computation for each block.

**DETAILS OF TRANSACTION FEES [18, 22].** When creating a transaction, the user should set a maximum amount *m* of gas that the transaction is allowed to consume. They should also set a price *p* that they are willing to pay per unit of gas. Right before the transaction's execution, a deposit of *m*·*p* is taken from the user's account. If the transaction uses *g* ≤ *m* units of gas in its execution, then the transaction fee will be *g*·*p* and the user receives a refund of (*m* − *g*)·*p*. Otherwise, if *g* > *m*, an out-of-gas error is raised. This sets *g* = *m*. When running out of gas, all effects of the transaction are reverted. However, the deposit is not refunded and the entire *m*·*p* is taken as a transaction fee.

**BASE FEES AND TIPS [18, 22].** The gas price *p* = *b* + *t* consists of two parts: a base fee *b* which is the same for all transactions in the block and a tip *t* which is picked by the user starting the transaction. If the transaction uses *g* units of gas, the user pays a transaction fee of *g*·*p* as mentioned above. Of this, *g*·*b* units are burned and *g*·*t* is paid to the miner who added the transaction to the blockchain. There are two clear reasons behind the base fee: (i) it controls inflation by destroying some units of currency, and (ii) the protocol can balance the supply and demand of block space. Ethereum aims to have blocks that use roughly 15,000,000 units of gas which is almost half of the block gas limit. If a block uses more than this amount, it shows that demand for gas is high and thus the base fee goes up in future blocks. Conversely, if a block uses less than 15,000,000 units, e.g. if it is almost empty, the base fee drops.

**STRUCTURE OF AN ETHEREUM TRANSACTION.** A formal specification for Ethereum transactions is given in [18]. Each transaction tx contains a nonce, a counter showing the number of transactions issued by the current user to date. It also contains the gas parameters *m* and *p* = *b* + *t* above. If the transaction transfers money, it includes the recipient address and amount. Similarly, if it deploys a contract it includes its code, and if it calls a function, it includes its parameters. We ignore these details and focus on the fact that, given the world state before the execution of tx, its gas usage and the total

tip paid to the miner are uniquely determined. Thus, letting *S* be the set of all possible world states, from the miner's point-of-view, the transaction tx induces two functions:

$$gas_{tx} : S \to \mathbb{N} \qquad tip_{tx} : S \to \mathbb{N}.$$

Note that $tip_{tx} \equiv t \cdot gas_{tx}$. Similarly, since executing tx changes the world state, the transaction induces a transition function $\delta_{tx} : S \to S$ between world states.

## 3 Related work

**OPTIMAL MINING ON UTXO BLOCKCHAINS.** The problem of optimizing the transaction-fee revenues obtained by honest cryptocurrency miners has previously been considered in [8, 40], which are the closest related works. However, these works focus on UTXO blockchains such as Bitcoin and Cardano. In the UTXO model, transactions can have dependencies and conflicts. For example, if Alice receives money in $tx_1$ and uses it to pay Bob in $tx_2$, i.e. an input of $tx_2$ is an output of $tx_1$, then $tx_2$ can only be added to the blockchain after $tx_1$. On the other hand, if Alice receives money in $tx_1$ and then creates distinct transactions $tx_2$ and $tx_3$ that use the same coin twice then at most one of them can be added to the consensus chain. Thus, optimizing a miner's revenues on UTXO blockchains is equal to solving a variant of the knapsack problem in which items may have pairwise dependencies and conflicts. A transaction's weight is its size and its value is the transaction fee. Crucially, the transaction fees are fixed and known apriori. Moreover, when the miner chooses the subset of transactions that are included in her block, their order does not matter and any topological ordering leads to the same total revenue. Despite this, the problem is shown to be strongly NP-hard and can only be solved on sparse instances [8, 40].

In contrast, our setting on Ethereum is considerably more challenging. Due to the gas model, the transaction fees are dynamic and depend on the actual resources used in runtime. The same transaction might pay vastly different fees based on the world state before its execution, which is determined by the transactions that precede it in the block. As a toy example, consider the smart contract below:

```c
uint n = 0;
function f() public { n = 1000; }
function g() public {
    for (uint i = 0; i <= n; i++) {
        /*write to storage*/
    }
}
```

Suppose $tx_1$ calls $f$() and $tx_2$ calls $g()$. If the miner places $tx_1$ before $tx_2$ in the block, *n* becomes 1000, so $g$() incurs a high fee. If $tx_2$ is first, *n* = 0 when $g$() runs, resulting in a much lower gas usage and fee. Thus, transaction ordering directly affects fees. Unlike the UTXO model, one cannot determine if $tx_1$'s gas usage depends on $tx_2$ by inspecting just the pair; dependencies may only arise in the presence of other transactions. For example, consider the smart contract below:

```c
uint n = 0, m = 0;
function f() public { m = 1000; }
function g() public {
    for (uint i = 0; i <= n; i++) {
        /*write to storage*/
    }
}
```
```python
function h() public {n = m;}
```

Suppose that the miner observes a transaction $tx_1$ calling $f()$ and another transaction $tx_2$ calling $g()$ in the mempool. These two transactions are clearly independent in terms of gas usage and each transaction's inclusion or their order cannot affect the fee paid by the other transaction. However, if a new transaction $tx_3$ calling $h()$ is observed, then $tx_1$ and $tx_2$ suddenly become dependent and the miner must use the ordering $tx_1, tx_3, tx_2$ to maximize her payoff. Note that $tx_2$ and $tx_3$ are also independent in the absence of $tx_1$. Thus, we cannot talk of gas dependencies between a pair of transactions without specifying all transactions available in Pool.

**GAS UPPER-BOUNDS.** Out-of-gas exceptions are the root cause of several well-known vulnerabilities and hacks on Ethereum [4]. Thus, there is a wide variety of static analysis tools in the literature focusing on finding tight bounds on the gas usage of a given smart contract. These tools abstract away the context, i.e. the world state before a function call, and focus on obtaining worst-case gas bounds. Examples of methods in this direction are [1, 2, 13, 28, 42].

**GAS OPTIMIZATION.** In 2024, Ethereum users paid over 4 billion USD in gas fees [57]. Thus, optimizing gas usage is crucial in smart contract compilers. The standard Solidity compiler, the most widely-used high-level language for smart contracts, applies various gas optimization rules [51]. There is also significant research on static and dynamic analysis to reduce gas usage [1, 3, 43]. Another approach is to shift most computations off-chain. Layer-2 solutions, such as channels, sidechains, and rollups [50]. While users and developers aim to minimize gas costs, our focus is on miners, who are incentivized to maximize them.

**MEV [23].** The term *Miner Extractable Value* or *Maximal Extractable Value* (MEV) was popularized by [17] to describe the maximum profit a dishonest miner can obtain by exploiting their knowledge of transactions. This is often called “toxic” MEV in the blockchain community. For instance, miners can engage in front-running, back-running, and sandwich attacks, leveraging their ability to manipulate, reorder, or censor transactions [35, 39, 59]. Such attacks can even threaten the security of Ethereum’s consensus layer [17]. Several countermeasures against transaction reordering have been proposed [30], and formal verification tools exist to identify profitable MEV opportunities [5, 32].

MEV attacks typically involve the miner interacting with a smart contract. In most front-running attacks, for example, the miner observes a pending transaction $tx_1$ and uses its disclosed data to create their own transaction $tx_2$, placing it before $tx_1$ in the block to capture the payoff. Here, the miner's extra revenue comes not from mining or transaction fees, but from exploiting a vulnerable contract. In contrast, our work focuses on honest miners. In our formalization (Section 1.1), the miner seeks to maximize revenue from the available transactions, without attacking contracts, forking the blockchain, or creating new transactions. This distinction makes our approach suitable for reference implementations of programmable blockchains, which are widely used by real-world miners. Notably, all major consensus protocols, including proof of work and proof of stake, rely on the assumption that the majority of mining power is held by honest miners.

# 4 Our Algorithm

We start this section with a high-level overview of our algorithm and then provide the details of each step. The fundamental idea behind our approach is a simple observation: in real-world instances of the problem, each transaction interacts with only a few other transactions, which we call its neighborhood. Thus, when forming a block, we do not need to search over all possible permutations of transactions, but can instead find rules that encode the gas usage of each transaction based on the portion of its neighborhood that precedes it in the block.

**OVERVIEW.** Our approach consists of the following steps:

(1) **Sampling and Testing.** We start by sampling random permutations of the transactions available in our Pool and executing them, keeping track of the amount of gas used by each transaction in each sample permutation.

(2) **Neighborhood Estimation.** For each transaction $tx$, we identify a neighborhood, i.e. a set $nbhd(tx)$ of transactions whose inclusion before $tx$ has the potential to change the amount of gas consumed by $tx$. To estimate each transaction's neighborhood, we rely on a decision tree generated from our samples.

(3) **Extracting Gas Usage Rules.** Using the neighborhoods and samples, we extract gas usage rules. We define a simple grammar that can encode rules such as “if $tx_1$ appears before $tx_2$ which in turn appears before $tx_3$, then $tx_3$ will have a gas usage of $g$” for $tx_1, tx_2 \in nbhd(tx_3)$. We show that such rules can be mined from our samples, using a different decision tree.

(4) **Translating Gas Usage Rules to ILP.** Our goal is to obtain a block that orders a subset of transactions in a manner that maximizes the total tip earned by the miner. To do this, we have to choose which rules from the previous step to follow, i.e. which local orderings to include, but cannot choose rules that require conflicting orders on the transactions. Our algorithm translates this problem to integer linear programming (ILP).

(5) **Solving the ILP.** Finally, we call an external off-the-shelf ILP-solver to handle the ILP instance generated in the previous step. This yields the desired block.

We now present each step in more detail.

**STEP (1): SAMPLING AND TESTING.** The input to our algorithm is the initial world state $s_0$ and a set Pool = {$tx_1, tx_2, ..., tx_n$} of valid transactions which are not yet added to the blockchain. In this step, we randomly and uniformly generate several permutations $\Pi = \{\pi_1, \pi_2, ..., \pi_k\}$ of our Pool. The number of samples, $k$, is a user-defined parameter. Note that the $\pi_i$'s are not necessarily valid blocks as they might exceed the block gas limit.

We need to perform some simple housekeeping at this point. Recall that transactions originating from the same account should appear in the order of their nonces. We say a transaction $tx$ is an *a*-transaction if it originates from an account with address $a$. For every $i$ and $a$, we sort all the *a*-transactions in $\pi_i$ by their nonce, thus ensuring that every sample $\pi_i$ respects nonce orders. If there are several *a*-transactions with the same nonce in $\pi_i$, we only keep the first and remove the rest. Thus, $\pi_i$ might end up containing only a subset of the transactions in Pool.
We then execute every sample $\pi_i$ starting from the initial world state $s_0$ and keep track of the amount of gas used by each transaction $tx_j$ in the execution of $\pi_i$. We denote this by gas($\pi_i$, $tx_j$).

**EXAMPLE.** Suppose we have 6 transactions in our pool and the tip value set by the users is $t[tx_1, tx_2, tx_3, tx_4, tx_5, tx_6] = [24, 9, 5, 29, 24, 2]$, i.e. $tx_1$ pays a tip of 24 for each consumed unit of gas, $tx_2$ pays 9, etc. We generate $k = 10$ random permutations $\pi_1, \dots, \pi_{10}$ of the pool, execute them, and keep track of the gas used by each transaction in each sample. See Figure 1.

**STEP (2): NEIGHBORHOOD ESTIMATION.** In this step, we consider each transaction $tx_i \in \text{Pool}$ separately and our goal is to identify a neighborhood for it, i.e. a set of transactions $\text{nbhd}(tx_i) \subseteq \text{Pool}$ whose inclusion before $tx_i$ can potentially change the amount of gas consumed by $tx_j$. We observe that the transactions usually exhibit only a few different possible gas usage values. Thus, we can use the amount of gas used by $tx_i$ as a label in a classification problem. We introduce one binary attribute for each $tx_j$, which is set to 1 if $tx_j$ precedes $tx_i$ in the sample permutation. We then generate a decision tree. At each node of the tree, we choose the best possible attribute to branch on, based on the Gini impurity metric [12, Chapter 4.6]. After generating the decision tree, if the attribute corresponding to $tx_j$ appears in one of the decisions, we add $tx_j$ to the neighborhood $\text{nbhd}(tx_i)$.

**EXAMPLE.** Consider the samples of the previous example (Figure 1). In this step, our algorithm finds a neighborhood for every transaction. Let us consider $tx_3$. We can encode each permutation $\pi_i$ as a vector $v_i$ such that $v_i[j] = 1$ if $tx_j$ precedes $tx_3$ in $\pi_i$ and $v_i[j] = 0$ otherwise. The label associated with $v_i$ is the gas usage of $tx_3$ in the execution of $\pi_i$. In this case, there are only two possible labels: 2 and 4. See Figure 3 (left). When we generate a decision tree, shown in Figure 3 (right), it only looks at the attribute corresponding to $tx_2$. Hence, we set $\text{nbhd}(tx_3) = \{tx_2\}$. In other words, at least in our samples, the gas usage of $tx_3$ is only dependent on whether $tx_2$ precedes it. This is shown in Figure 2.

**STEP (3): EXTRACTING GAS USAGE RULES.** Now that we have estimated the neighborhood of every transaction, our next goal is to extract a set of rules that define the gas usage of each transaction $tx$ based on the subset of neighbors that precede $tx$ in the block and their order of appearance.

**SYNTAX.** Our rules are defined by the grammar below:

$$ 
\begin{align*}
\langle \text{predicate} \rangle &:= \diamond \text{tx} \mid \text{tx} \prec \text{tx} \mid \neg \langle \text{predicate} \rangle \\
\langle \text{predicate-list} \rangle &:= \langle \text{predicate} \rangle \mid \langle \text{predicate} \rangle, \langle \text{predicate-list} \rangle \\
\langle \text{clause} \rangle &:= \langle \text{predicate} \rangle \mid \text{atleast}(k, \langle \text{predicate-list} \rangle) \mid \\
& \phantom{:=} \quad \langle \text{clause} \rangle \wedge \langle \text{clause} \rangle \\
\langle \text{rule} \rangle &:= \langle \text{clause} \rangle \Rightarrow \text{expected-gas}(\text{tx}) = g \\
& \phantom{:=} \quad g, k \in \mathbb{N}, \text{tx} \in \text{Pool} \tag{1}
\end{align*}
$$

**SEMANTICS.** Given a sequence of distinct transactions $\pi = \langle \pi[1], \dots, \pi[m] \rangle$, we have:

$$ 
\begin{align*}
\pi &\models \diamond \text{tx}_i &\iff \exists i' (\pi[i'] = \text{tx}_i) \\
\pi &\models \text{tx}_i \prec \text{tx}_j &\iff \pi \not\models \text{tx}_j \lor \exists i', j' (i' < j' \land \\
& & \phantom{\iff \pi \not\models \text{tx}_j \lor \exists i', j' (} \pi[i'] = \text{tx}_i \land \pi[j'] = \text{tx}_j) \\
\pi &\models \neg p &\iff \pi \not\models p \\
\pi &\models c_1 \land c_2 &\iff \pi \models c_1 \land \pi \models c_2 \\
\pi &\models \text{atleast}(k, p_1, \dots, p_m) &\iff \exists i_1, \dots, i_k (1 \le i_1 < \dots < i_k \le m \land \\
& & \phantom{\iff \pi \models \text{atleast}(k, p_1, \dots, p_m) \iff \exists i_1, \dots, i_k (} \forall j \ \pi \models p_{i_j}) \tag{2}
\end{align*}
$$

Intuitively, $\pi$ satisfies the predicate $\diamond \text{tx}_i$ if it includes $\text{tx}_i$. It satisfies the predicate $\text{tx}_i \prec \text{tx}_j$ if it either excludes $\text{tx}_j$ altogether or has $\text{tx}_i$ preceding $\text{tx}_j$. A clause is simply a conjunction of predicates. We also allow clauses of the form $\text{atleast}(k, p_1, \dots, p_m)$ which require $\pi$ to satisfy at least $k$ of the predicates $p_1, \dots, p_m$. Although the latter could be left as syntactic sugar, including it as a separate clause is helpful in practice. This is because of a common scenario in smart contracts, especially those modeling NFT or token giveaways, in which the first $k$ transactions to call a function can receive the token. In such cases, all transactions calling this function are dependent in terms of gas, but the gas usage of each of them is only dependent on how many other transactions precede it. Finally, a rule of the form $C \Rightarrow \text{expected-gas}(\text{tx}_i) \ge g$ signifies a prediction: if $C$ is satisfied, we expect the gas usage of the transaction $\text{tx}_i$ to be at least $g$.

**STEP (3.1): GENERATING A DECISION TREE.** In this step, we generate a set of rules for each transaction $\text{tx}_i \in \text{Pool}$. We process each such transaction separately. When generating the rules for $\text{tx}_i$, we narrow our focus down to its neighborhood $\text{nbhd}(\text{tx}_i)$ since we believe these are the only transactions that can affect the gas usage of $\text{tx}_i$. Let $\pi_j$ be one of the sample permutations. We define $\pi_j^*$ as the subsequence of $\pi_j$ induced by $\text{nbhd}(\text{tx}_i) \cup \{\text{tx}_i\}$, i.e. the subsequence obtained by removing every element that is not in the neighborhood or not $\text{tx}_i$ itself. If $\pi \not\models \diamond \text{tx}_i$, we ignore this sample as it does not include $\text{tx}_i$ and cannot give us any information about its gas usage. We use $\Pi^*$ to denote the set of neighborhood-induced samples.

As in Step 2, our goal is to form a decision tree that predicts the gas usage of $\text{tx}_i$ based on features that encode the set of neighbors that precede it in the block and their order. Thus, for every neighboring $\text{tx}_j \in \text{nbhd}(\text{tx}_i)$ we define a corresponding feature

$$ w[j] = \begin{cases} j' - i' & \text{if } \pi^* \models \text{tx}_j \prec \text{tx}_i \wedge \pi^*[i'] = \text{tx}_i \wedge \pi^*[j'] = \text{tx}_j \\ 0 & \text{otherwise} \end{cases} $$

Informally, if $\pi^*$ puts $\text{tx}_j$ before $\text{tx}_i$, then $-w[j]$ is the distance between the two transactions in $\pi^*$. Otherwise, $w[j] = 0$. In other words, we care about the distance only if $\text{tx}_j$ precedes $\text{tx}_i$. This is because if $\text{tx}_j$ does not appear before $\text{tx}_i$, it cannot affect $\text{tx}_i$'s gas usage. In addition to the $w[j]$'s, we also add an extra feature $r$ which models the number of neighbors that precede $\text{tx}_i$, or equivalently, the index in $\pi^*$ at which $\text{tx}_i$ appears. We generate a decision tree using the same method as in Step 2, where the samples are the subsequences $\pi^*$, the features are $r$ and the $w[j]$'s, and the labels are different possible gas usage values of $\text{tx}_i$. Note that our features are no longer binary.
<figure><img src="image_2.png" /><figcaption>Figure 1: An example execution of 10 samples of a pool of 6 transactions, profiling the gas usage and tip revenue obtained from each transaction.</figcaption></figure>

<table><thead><tr><th>Sample (π<sub>i</sub>)</th><th>Encoding (v<sub>i</sub>)</th><th>Label (γ<sub>3</sub>)</th></tr></thead><tbody><tr><td>π<sub>1</sub></td><td>[1, 1, 0, 1, 1, 0]</td><td>4</td></tr><tr><td>π<sub>2</sub></td><td>[1, 1, 0, 1, 0, 0]</td><td>4</td></tr><tr><td>π<sub>3</sub></td><td>[0, 1, 0, 0, 0, 0]</td><td>4</td></tr><tr><td>π<sub>4</sub></td><td>[1, 0, 0, 1, 0, 0]</td><td>2</td></tr><tr><td>π<sub>5</sub></td><td>[1, 1, 0, 1, 1, 1]</td><td>4</td></tr><tr><td>π<sub>6</sub></td><td>[0, 0, 0, 1, 0, 1]</td><td>2</td></tr><tr><td>π<sub>7</sub></td><td>[1, 0, 0, 0, 1, 1]</td><td>2</td></tr><tr><td>π<sub>8</sub></td><td>[1, 0, 0, 1, 1, 0]</td><td>2</td></tr><tr><td>π<sub>9</sub></td><td>[0, 0, 0, 0, 0, 0]</td><td>2</td></tr><tr><td>π<sub>10</sub></td><td>[1, 1, 0, 0, 0, 0]</td><td>4</td></tr></tbody></table>

<figure><img src="image_3.png" /><figcaption>Figure 3: The classification problem is based on the gas used by $tx_3$ (left) and the resulting decision tree (right).</figcaption></figure>

**EXAMPLE.** For step 2 of the algorithm in our previous example, suppose we know that $\text{nbhd}(\text{tx}_1) = \{\text{tx}_4, \text{tx}_5\}$. Then for $\pi_1 = \langle\text{tx}_4, \text{tx}_5, \text{tx}_1, \text{tx}_2, \text{tx}_3, \text{tx}_6\rangle$ the induced sample is $\pi_1^* = \langle\text{tx}_4, \text{tx}_5, \text{tx}_1\rangle$. The encoding $w[\text{tx}_4] = 0-2$ as the position of $\text{tx}_4$ is 0 and the position of $\text{tx}_1$ is 2. Similarly, $w[\text{tx}_5] = 1-2 = -1$ and $w[\text{tx}_1] = 2-2 = 0$. The feature $w[r] = 2$ as the number of neighbors that precede $\text{tx}_1$ is 2. The encoding of the rest of the samples is shown in Figure 4.

**STEP (3.II): EXTRACTING RULES FROM THE DECISION TREE.** In the decision tree generated for $\text{tx}_i$ in Step (3.i), every leaf is labeled by one possible gas usage value of $\text{tx}_i$. Let $\ell$ be a leaf labeled by $g_\ell$. Consider a feature $w[j]$. We know that $-n \le w[j] \le 0$. In the path from the root of the decision tree to the leaf $\ell$, some decisions bound $w[j]$ from above or below. Let $m_j$ be the largest lower-bound and $M_j$ the smallest upper-bound imposed on $w[j]$ in the root-to-leaf path ending at $\ell$. Thus, in all samples modeled by this leaf, we have $w[j] \in [m_j, M_j]$. Similarly, we can define the tightest possible segment $[m_r, M_r]$ for values of $r$ in these samples. For each leaf $\ell$, we generate a gas usage rule containing a clause $\varphi_\ell$ as follows:

* We add the conjunct $\diamond\text{tx}_i$ to $\varphi_\ell$.

<figure><img src="image_4.png" /><figcaption>Figure 2: The gas usage of $tx_3$ only depends on whether $tx_2$ preceded it in the sample permutation.</figcaption></figure>

<table><caption>Figure 4: The classification problem based on the gas used by $tx_1$</caption><thead><tr><th>Sample (π<sub>i</sub>)</th><th>nbhd(tx<sub>i</sub>)-induced Sample (π<sub>i</sub><sup>*</sup>)</th><th>Encoding (w) |tx<sub>1</sub>, tx<sub>4</sub>, tx<sub>5</sub>, r|</th><th>Label (tx<sub>1</sub>'s gas)</th></tr></thead><tbody><tr><td>π<sub>1</sub></td><td>⟨tx<sub>4</sub>, tx<sub>5</sub>, tx<sub>1</sub>⟩</td><td>[0, -2, -1, 2]</td><td>6</td></tr><tr><td>π<sub>2</sub></td><td>⟨tx<sub>4</sub>, tx<sub>1</sub>, tx<sub>5</sub>⟩</td><td>[0, -1, 0, 1]</td><td>8</td></tr><tr><td>π<sub>3</sub></td><td>⟨tx<sub>1</sub>, tx<sub>5</sub>, tx<sub>4</sub>⟩</td><td>[0, 0, 0, 0]</td><td>10</td></tr><tr><td>π<sub>4</sub></td><td>⟨tx<sub>4</sub>, tx<sub>1</sub>, tx<sub>5</sub>⟩</td><td>[0, -1, 0, 1]</td><td>8</td></tr><tr><td>π<sub>5</sub></td><td>⟨tx<sub>4</sub>, tx<sub>5</sub>, tx<sub>1</sub>⟩</td><td>[0, -2, -1, 2]</td><td>6</td></tr><tr><td>π<sub>6</sub></td><td>⟨tx<sub>4</sub>, tx<sub>1</sub>, tx<sub>5</sub>⟩</td><td>[0, -1, 0, 1]</td><td>8</td></tr><tr><td>π<sub>7</sub></td><td>⟨tx<sub>5</sub>, tx<sub>1</sub>, tx<sub>4</sub>⟩</td><td>[0, 0, -1, 1]</td><td>2</td></tr><tr><td>π<sub>8</sub></td><td>⟨tx<sub>1</sub>, tx<sub>4</sub>, tx<sub>5</sub>⟩</td><td>[0, 0, 0, 0]</td><td>10</td></tr><tr><td>π<sub>9</sub></td><td>⟨tx<sub>5</sub>, tx<sub>1</sub>, tx<sub>4</sub>⟩</td><td>[0, 0, -1, 1]</td><td>2</td></tr><tr><td>π<sub>10</sub></td><td>⟨tx<sub>1</sub>, tx<sub>5</sub>, tx<sub>4</sub>⟩</td><td>[0, 0, 0, 0]</td><td>10</td></tr></tbody></table>

* If for two transactions $tx_j, tx_{j'} \in \text{nbhd}(\text{tx}_i)$, we have $M_j \le m_{j'}$, then $tx_j$ is always preceding $tx_{j'}$ in the samples corresponding to $\ell$. Thus, we add the conjunct $tx_j < tx_{j'}$ to $\varphi_\ell$.

* If for a transaction $tx_j \in \text{nbhd}(\text{tx}_i)$, we have $m_j \ge 0$, then $tx_j$ is never appearing before $\text{tx}_i$ in the samples corresponding to $\ell$. Thus, we add the conjunct $\text{tx}_i < \text{tx}_j$ to $\varphi_\ell$.

* If $m_r > 0$, then in every sample corresponding to $\ell$, at least $m_r$ neighboring transactions preceded $\text{tx}_i$. Let the neighborhood of $\text{tx}_i$ be $\text{nbhd}(\text{tx}_i) = \{\text{tx}_{j,1}, \dots, \text{tx}_{j,q}\}$. To capture this, we add the conjunct $\text{atleast}(m_r, \text{tx}_{j,1} < \text{tx}_i, \dots, \text{tx}_{j,q} < \text{tx}_i)$ to $\varphi_\ell$.

* Similarly, if $\text{nbhd}(\text{tx}_i) = \{\text{tx}_{j,1}, \dots, \text{tx}_{j,q}\}$ and $M_r < q$, then at most $M_r$ neighbors precede $\text{tx}_i$ in each of the samples corresponding to $\ell$. Therefore, $\text{tx}_i$ precedes at least $q - M_r$ neighbors in each such sample. Hence, we add the conjunct $\text{atleast}(q - M_r, \text{tx}_i < \text{tx}_{j,1}, \dots, \text{tx}_i < \text{tx}_{j,q})$ to the clause $\varphi_\ell$.

By definition-chasing, it is easy to prove that for every sample $\pi^* \models \varphi_\ell$ corresponding to the leaf $\ell$ of the decision tree, we have $\pi^* \models \varphi_\ell$.
Hence, one might assume that the expected gas usage of $tx_i$ in a sample satisfying $\varphi_\ell$ is the same as $\ell$'s label $g_\ell$. However, $\varphi_\ell$ might be satisfied by other samples, i.e. samples corresponding to other leaves, too. This is rare in practice, but to handle it, our algorithm takes the average gas usage of $tx_i$ over all samples $\pi^*$ that model $\varphi_\ell$. Formally, let $J = \{j | 1 \le j \le k \wedge \pi_j^* \models \varphi_\ell\}$. Our algorithm computes

$$ \bar{g}_{\ell} = \frac{\sum_{j \in J} \text{gas}(\pi_j, \text{tx}_i)}{|J|}. $$

In almost all real-world cases, we have $\bar{g}_{\ell} = g_{\ell}$. Finally, our algorithm generates the following gas usage rule:

$$ \varphi_{\ell} \Rightarrow \text{expected-gas}(\text{tx}_i) = \bar{g}_{\ell}. \qquad (3) $$

We remark that for each transaction $tx_i$ and every leaf $\ell$ of the decision tree corresponding to $tx_i$, our algorithm generates one instance of the gas usage rule in Equation (3).

**EXAMPLE.** Let Figure 5 be the decision tree generated for $tx_1$ in our previous example. The tree has 6 leaves $l_1 - l_6$ labelled 10, 2, 10, 8, 6, 6 respectively. Consider the leaf $l_5$, taking the negations into the account, the predicates along the path evaluate to: $w[tx_4] < 0.0$, $w[tx_5] \ge -1.5$, $w[tx_4] < -1.5$, which after rounding to integers, gives us the intervals $w[tx_4] \in (-\infty, -2] = (m_4, M_4]$, $w[tx_5] \in [-1, \infty) = [m_5, M_5]$. Notice that $M_4 \le 0$ which generates the clause $tx_4 < tx_1$, and $M_4 \le m_5$ which generates the clause $tx_4 < tx_5$. Therefore, the rule's body is $\diamond tx_1 \wedge (tx_4 < tx_1) \wedge (tx_4 < tx_5)$. Observe that $\{\pi_1, \pi_2, \pi_4, \pi_5, \pi_6\} \models \diamond tx_1 \wedge (tx_4 < tx_1) \wedge (tx_4 < tx_5)$, with average gas usage of $tx_1$ equal to $(6 + 8 + 8 + 6 + 8)/5 = 7.2$. The remaining rules are given in Figure 6.

Notice that no permutation can satisfy the rule $l_4$ and we assign the undefined $\perp$ average usage to it. We exclude such rules from consideration in the rest of the algorithm.

**STEP (4): TRANSLATING GAS USAGE RULES TO ILP.** In this step, our goal is to design an integer linear programming (ILP) instance that picks the transactions we shall include in the block and orders them. For every transaction $tx_i$, if we satisfy a rule of the form (3) generated in the previous step, we can expect to get the corresponding gas usage. However, we have to be careful not to double-count the gas usage of the same transaction in case several of its corresponding rules are satisfied. Thus, in our ILP instance, we define the following constants, variables and constraints:

* **Transaction Inclusion.** For every transaction $tx_i$, we define a binary variable $b_i$ and add the constraint $0 \le b_i \le 1$. Intuitively, $b_i = 1$ signifies that $tx_i$ should be included in the block.

* **Maximum Number of Transactions.** Let $\mu$ be a constant that is strictly more than the maximum number of transactions that can possibly fit in a block. At the time of writing, the block gas limit $L$ is 36,000,000 and each transaction uses at least 21,000 units of gas. Thus, $\mu = 1715$ works in practice.

* **Transaction Ordering.** For every transaction $tx_i$, we define an integer rank variable $r_i$ with the constraint $0 \le r_i < \mu$. We also add the constraint $b_i \le r_i \le \mu \cdot b_i$. Thus, $r_i = 0$ if and only if $tx_i$ is not included in the block. For two transactions $tx_i, tx_j$ with positive ranks, we interpret $r_i < r_j$ as $tx_i$ preceding $tx_j$ in the block.

* **Rule Selection.** Let $\rho = \varphi_\rho \Rightarrow \text{expected-gas}(\text{tx}_\rho) = g_\rho$ be a gas usage rule extracted in the previous step. We define a binary

variable $0 \le b_\rho \le 1$. We interpret $b_\rho = 1$ to mean that (i) the clause $\varphi_\rho$ should be satisfied, and (ii) we claim the gas usage $g_\rho$ for the transaction $\text{tx}_\rho$ in our total gas estimate.

* **No Double-counting.** For every transaction $tx_i$, let $\rho_1, \dots, \rho_q$ be the set of rules that assign a gas usage to $tx_i$. We add the constraint $\sum_{j=1}^q b_{\rho_j} \le 1$ to our ILP instance. This encodes the requirement that we can claim the gas usage for $tx_i$ only once but does not preclude the possibility that the preconditions of more than one of these rules are satisfied.

* **Block Gas Limit.** Let $R$ be the set of all rules generated in the previous step. Since we should not exceed the block gas limit $L$, we add the following constraint: $\sum_{\rho \in R} b_\rho \cdot g_\rho \le L$.

* **Objective Function.** Our goal is to maximize the total tip revenue for the miner. Given a rule of the form $\rho = \varphi_\rho \Rightarrow \text{expected-gas}(\text{tx}_\rho) = g_\rho$, if we pick $b_\rho = 1$, then our estimated tip revenue is $t(\text{tx}_\rho) \cdot g_\rho$. Note that $t(\text{tx}_\rho)$ is a constant, i.e. the tip a user has declared they are willing to pay per consumed unit of gas. Therefore, we set our objective as

$$ \max \sum_{\rho \in R} b_{\rho} \cdot t(\text{tx}_{\rho}) \cdot g_{\rho}. $$

* **Enforcing Rules.** Given a rule $\rho = \varphi_\rho \Rightarrow \text{expected-gas}(\text{tx}_\rho) = g_\rho$, if we set $b_\rho = 1$, we have to make sure that the transactions are picked and ordered in such a way that the clause $\varphi_\rho$ is satisfied. To achieve this, we assign an ILP expression $[C]$ to every clause $C$ such that $[C] \ge 1$ iff $C$ is satisfied and $[C] \le 0$ otherwise. We also add the constraint $b_\rho \le [\varphi_\rho]$ to the ILP instance.

* **Encoding Clauses.** For any clause $C$ generated from the grammar of Equation (1), we define its ILP encoding $[C]$ by structural induction:

- The simplest case is $\diamond tx_i$. We have $[\diamond tx_i] = b_i$. This is because $b_i$ precisely captures whether $tx_i$ is included in the block.

- We define $[\neg \rho] = 1 - [\rho]$.

- We set $[tx_i < tx_j] = 4 \cdot \mu \cdot [\neg \diamond tx_j] - 2 \cdot \mu \cdot [\neg \diamond tx_i] + r_j - r_i$. This works because (i) if both $tx_i$ and $tx_j$ are included in the block, then $[tx_i < tx_j] = r_j - r_i$ captures the requirement that $tx_i$ appears before $tx_j$; (ii) if $tx_j$ is excluded, then $[tx_i < tx_j]$ is guaranteed to be positive; (iii) if $tx_i$ is excluded but $tx_j$ is included, then $[tx_i < tx_j]$ is guaranteed to be negative.

- To define $[c_1 \wedge c_2]$ we introduce two fresh binary variables $v_1, v_2$ and add the constraints $v_1 \le [c_1]$, $v_2 \le [c_2]$, $0 \le v_1, v_2 \le 1$. We then set $[c_1 \wedge c_2] = v_1 + v_2 - 1$.

- Similarly, for $[\text{atleast}(k, p_1, \dots, p_m)]$, we introduce $m$ fresh binary variables $v_1, \dots, v_m$ and then add the constraints $v_i \le p_i$ and $0 \le v_i \le 1$. Finally, we set $[\text{atleast}(k, p_1, \dots, p_m)] = 1 - k + \sum_{i=1}^m v_i$.

* **Nonce Uniqueness.** For every user $a$ and nonce $v$, let $tx_{i,1}, tx_{i,2}, \dots, tx_{i,q}$ be the $a$-transactions with nonce $v$. We can include at most one of these transactions in our block. Thus, we add the ILP constraint $\sum_{j=1}^q b_{i,j} \le 1$.

* ** Nonce Succession.** Let $tx_i$ be an $a$-transaction with nonce $v$ and assume that there are no $a$-transactions with nonce $v-1$ in the previous blocks that are already added to the blockchain. In this case, we are required to include an $a$-transaction with nonce $v-1$ before we can add $tx_i$. We encode this requirement by adding the
<figure><img src="image_5.png" /><figcaption>Figure 5: The resulting decision tree for $tx_1$.</figcaption></figure>

<table><caption>Figure 6: The gas usage rules generated for $tx_1$.</caption><thead><tr><th></th><th>m<sub>4</sub>, M<sub>4</sub></th><th>m<sub>5</sub>, M<sub>5</sub></th><th>rule</th><th>expected-gas(tx<sub>1</sub>)</th></tr></thead><tbody><tr><td>l<sub>1</sub>:</td><td>[0, ∞)</td><td>[0, ∞)</td><td>◇tx<sub>1</sub> ∧ (tx<sub>1</sub> &lt; {tx<sub>4</sub>, tx<sub>5</sub>})</td><td>⇒ 10</td></tr><tr><td>l<sub>2</sub>:</td><td>[0, ∞)</td><td>(-∞, -1]</td><td>◇tx<sub>1</sub> ∧ (tx<sub>1</sub> &lt; tx<sub>4</sub>) ∧ (tx<sub>5</sub> &lt; tx<sub>1</sub>)</td><td>⇒ 2</td></tr><tr><td>l<sub>3</sub>:</td><td>[-1, -1]</td><td>[0, ∞)</td><td>◇tx<sub>1</sub> ∧ (tx<sub>4</sub> &lt; tx<sub>1</sub>) ∧ (tx<sub>1</sub> &lt; tx<sub>5</sub>)</td><td>⇒ 8</td></tr><tr><td>l<sub>4</sub>:</td><td>[-1, -1]</td><td>[-1, -1]</td><td>◇tx<sub>1</sub> ∧ ({tx<sub>4</sub>, tx<sub>5</sub>} &lt; tx<sub>1</sub>) ∧ (tx<sub>4</sub> &lt; tx<sub>5</sub>) ∧ (tx<sub>5</sub> &lt; tx<sub>4</sub>)</td><td>⇒ ⊥</td></tr><tr><td>l<sub>5</sub>:</td><td>(-∞, -2]</td><td>[-1, ∞)</td><td>◇tx<sub>1</sub> ∧ (tx<sub>4</sub> &lt; tx<sub>1</sub>) ∧ (tx<sub>4</sub> &lt; tx<sub>5</sub>)</td><td>⇒ 7.2</td></tr><tr><td>l<sub>6</sub>:</td><td>(-∞, -1]</td><td>(-∞, -2]</td><td>◇tx<sub>1</sub> ∧ ({tx<sub>4</sub>, tx<sub>5</sub>} &lt; tx<sub>1</sub>)</td><td>⇒ 6</td></tr></tbody></table>

following constraint to our ILP instance:

$$ \llbracket \text{atleast}(1, tx'_1 < tx_i, \dots, tx'_q < tx_i) \rrbracket $$

where $tx'_1, \dots, tx'_q$ are the a-transactions with nonce $v-1$.

**EXAMPLE.** Suppose $\mu = 7$. For each transaction $tx_i \in \{tx_1, \dots, tx_6\}$ we generate a binary variable $b_i$ and an integer variable $r_i$ constraint to $b_i \le r_i < 7 \cdot b_i$. We mechanically transform the set of rules for each transaction into ILP constraints. as shown in Appendix A.1 Table 3. For brevity, we replaced the set of rules obtained in the previous step for $tx_1$ with a shorter set of rules.

**STEP (5): SOLVING THE ILP AND FORMING THE BLOCK.** We pass the ILP instance generated in the previous step to an external ILP-solver. When the ILP-solver finds a solution, we can directly translate it to a block as follows: We include a transaction $tx_i$ if $b_i$ is set to 1 in the solution. This uniquely determines the set of transactions. To form the block $B$, we simply sort the included transactions by their rank, i.e. if $r_i < r_j$, then we put $tx_i$ before $tx_j$. This concludes our algorithm.

**EXAMPLE.** Upon submitting the ILP instance to a solver, we obtain the following possible solution: all $b_i$ are set to 1, ranks are set as follows: $r_1 = 1, r_2 = 3, r_3 = 4, r_4 = 2, r_5 = 5, r_6 = 5$; and the following set of rules are set to 1: $\rho_{1,1}, \rho_{2,2}, \rho_{3,1}, \rho_{4,1}, \rho_{5,2}, \rho_{6,1}$. Note that $r_5 = r_6$ which means we can put $tx_5$ and $tx_6$ in any order. Therefore a possible block corresponding to this ILP solution is $\langle tx_1, tx_4, tx_2, tx_3, tx_5, tx_6 \rangle$, with total revenue $240+58+72+20+240+20 = 650$. Note that the sample blocks did not feature this revenue. Moreover, the greedy ordering in the order of the tips yields the permutation $\pi_1 = \langle tx_4, tx_5, tx_1, tx_2, tx_3, tx_6 \rangle$ with total revenue 554, which is much less than 650.

**POTENTIAL FAILURES.** There are rare cases where our algorithm might fail to produce a valid block, forcing the miner to fall back on the default algorithm of the Ethereum reference implementation. Despite this, as we will see in Section 5, we achieve significant improvements in miner revenue. A failure can occur for two reasons: (i) the ILP-solver might fail to find a solution, or (ii) the gas usage estimates in our rules might be low, leading to the formation of a block $B$ that, in practice, uses more than $L$ units of gas. This

can happen if our sample tests do not provide sufficient coverage for the gas consumption scenarios of some transactions. Coverage issues can be avoided with high probability by taking sufficiently many samples. Another possible fix is to simply add $B$ to our set of samples and rerun the algorithm.

We note that, in theory, such failures are inevitable for any efficient algorithm since the problem is strongly NP-hard, i.e. NP-hard even if all the numbers in our input are written in unary, in the much simpler UTXO model [40]. The UTXO variant of the problem is a special case of our setting, corresponding only to our nonce-related constraints. Thus, our problem is strongly NP-hard, too. Moreover, the revenue optimization problem is decidable only due to the existence of gas limits for blocks and transactions. Without such limits, Rice's theorem [46] would be applicable and the problem becomes undecidable.

**SUFFICIENT SAMPLE SETS.** As mentioned above, our algorithm might fail if an insufficient number of samples are taken. This naturally leads to the following question6: How many random samples are enough to guarantee success? We now address this point with a simple coupon-collecting argument. We say a set $\Pi$ of samples is sufficient if for every transaction $tx$ in the pool, the set $\Pi^*$ of induced samples over $nbhd(tx)$ contains all permutations of $nbhd(tx)$. Of course, if we take all possible $|Pool|$! permutations as samples, then we will have a sufficient sample set, but our goal is to show that a much smaller randomly-picked set of samples would also be sufficient with high probability. Let $\Delta = \max_{tx \in Pool} |nbhd(tx)|$ be the maximum neighborhood size. The following theorem shows that a sample set of size $O(\Delta! \cdot (\log(|Pool|) + \log(\Delta!)))$ is sufficient for all transactions with high probability.

**Theorem 1.** Assume there are no nonce dependencies and the neighborhood of every transaction is known. Consider the following stochastic process: We start with an empty sample set. In each step, we uniformly sample a new permutation of the transactions in Pool and add it to $\Pi$. The process stops at the moment $T$ when the sample set $\Pi$ becomes sufficient. Then, for any $\epsilon \in (0, 1)$, the following holds:

$$ \mathbb{P} \left[ T < \Delta! \cdot \log \frac{|Pool| \cdot (\Delta + 1)!}{\epsilon} \right] \ge 1 - \epsilon. $$
The proof can be found in Appendix B.1.

# 5 Experimental Results

**IMPLEMENTATION.** We implemented our approach in Python 3 and Rust. Our tool is available at https://github.com/destrat18/boostingGasRevenuesOfEthereumMiners. We used Anvil [27] and Erigon [21] to execute Ethereum transactions in our samples and obtain their gas usage. Moreover, we used Linfa [38] to generate decision trees and relied on SCIP [11] for solving Integer Linear Programming (ILP) instances.

**MACHINE.** All experimental results were obtained on an Intel Xeon Gold 5115 Machine (2.40GHz, 16 cores) with 64 GB of RAM, running Ubuntu 22.04.

**BENCHMARKS.** As our benchmark suite, we collected a dataset of real-world mempools, i.e. unmined transactions, that were available on the Ethereum network before each block. Our data spans 50,000 blocks, numbered 21800000 to 21849999, corresponding to approximately one week of activity on Ethereum in the period from February 8, 2025, 06:27:11 (UTC) to February 15, 2025, 06:18:35 (UTC). This data was gathered from Blocknative [10].

**SAMPLES AND RUNTIME.** For each of the 50,000 blocks, we generated 300 sample permutations and limited our solver's execution time to 12 seconds, i.e. Ethereum's block time. We note that the results were obtained on a relatively modest machine. The testing and decision-tree generation steps of our algorithm are parallelized, thus increasing the computational power would allow one to cover more samples for each block. We expect real-world miners to have much higher computational power than us.

**BASELINES.** For each block, we compare the total tip revenue obtained by our approach with the real-world block that was mined and added to the Ethereum blockchain. In the experiments, we observed that some Ethereum miners routinely miss lucrative transactions when forming their blocks. This might be due to a suboptimal block formation strategy or network connectivity issues that prevented the miner from seeing the transactions, e.g. due to the censorship of the Ethereum network in some countries. Thus, it is conceivable that the miner might not have the same mempool as us. We believe this does not affect the fairness of the comparison since the onus is on the miners to ensure they have reliable connectivity to the network. However, to demonstrate that our improvements are not merely due to better connectivity, as a second baseline, we used Ethereum's reference implementation and applied it to the exact same mempools as our algorithm. The reference implementation sorts transactions greedily based on their effective gas tip value, prioritizing transactions with higher tips for miners and ordering same-sender transactions by nonce [26, 27].

**REVENUE GAINS.** The revenue gains obtained by our algorithm are summarized in Table 1 and Figure 7. Our approach outperformed real-world miners in 45,609 of the 50,000 blocks (91% of the cases), increasing the total revenue over all blocks by 1,204,475 USD<fnref n="1" />. On average, this represents an increase of nearly 24.1 USD per block, which translates to an annualized improvement of around 63 million USD. Our approach obtained significant gains compared to the Ethereum reference implementation, as well. It outperformed

<figure><img src="image_6.png" /><figcaption>**Figure 7:** Comparison of the tip revenues obtained by our algorithm (x-axis) and the real-world blocks added to the Ethereum blockchain (y-axis). Each point corresponds to one block. Green points (91.22%) are the blocks on which our algorithm obtained a higher revenue than real-world miners. For clarity, we excluded 265 data points.</figcaption></figure>

the reference implementation in 38,505 blocks (77% of the cases), yielding an additional revenue of 863,385 USD over our 50,000 benchmark blocks. This translates to approximately **45 million USD** annually. On average, our algorithm earned almost 17.3 USD more per block. The data in Table 1 should be taken with the usual grains of salt: (i) Ether's value and its exchange rate to USD are highly volatile and unpredictable, and (ii) the reported numbers are the sums of improvements over individual blocks. Figures 8 and 9 and provide histograms of the gained revenues in USD. Figures 10 and 11 show similar histograms based on the percentage of improvement obtained in each block.

<figure><img src="image_7.png" /><figcaption>**Figure 8:** Histogram of the transaction fee improvements obtained over each block compared to real-world miners (in USD). The y-axis is in logarithmic scale. For clarity, 411 data points outside the range are omitted.</figcaption></figure>

**SAMPLE SIZE SENSITIVITY.** To investigate the effect of sample size on our approach, we reran our experiments with sample sizes of

<footnote n="1">¹We used the ETH/USD conversion rates provided by [15].</footnote>
<table><caption>Table 1: Improvements obtained by our approach compared to real-world miners and the Ethereum reference implementation.</caption><thead><tr><td>Metric</td><td>Improvement compared to Real-World Miners</td><td>Improvement compared to Reference Implementation</td></tr></thead><tbody><tr><td>Number of improved blocks</td><td>45,609 (91.22%)</td><td>38,505 (77.01%)</td></tr><tr><td>Total increase in tip revenue over 50,000 blocks</td><td>1,204,475 USD</td><td>863,385 USD</td></tr><tr><td>Annualized increase in tip revenue</td><td>63,357,892 USD</td><td>45,416,764 USD</td></tr><tr><td>Average earning increase per block</td><td>24.1 USD</td><td>17.3 USD</td></tr><tr><td>Average improvement percentage per block</td><td>73.45%</td><td>18.56%</td></tr></tbody></table>

<figure><img src="image_8.png" /><figcaption>Figure 9: Histogram of the transaction fee improvements obtained over each block compared to the Ethereum reference implementation (in USD). The y-axis is in logarithmic scale. For readability, 868 blocks with improvements over 150 USD are omitted from the plot.</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 11: Histogram of the transaction fee improvements obtained over each block compared to the Ethereum reference implementation (in percentages). The y-axis is in logarithmic scale. 2021 points outside the range omitted for clarity.</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 10: Histogram of the transaction fee improvements obtained over each block compared to real-world miners (in percentages). 608 points outside the range omitted for clarity.</figcaption></figure>

<table><caption>Table 2: Pairwise differences in annualized revenue across sample sizes of 50, 100, 200, and 300 in thousands of USD.</caption><thead><tr><td>Sample Size</td><td>50</td><td>100</td><td>200</td><td>300</td></tr></thead><tbody><tr><td>50</td><td>0</td><td>-1457.53</td><td>-2910.24</td><td>-3253.29</td></tr><tr><td>100</td><td>1457.53</td><td>0</td><td>-1452.71</td><td>-1795.76</td></tr><tr><td>200</td><td>2910.24</td><td>1452.71</td><td>0</td><td>-343.047</td></tr><tr><td>300</td><td>3253.29</td><td>1795.76</td><td>343.047</td><td>0</td></tr></tbody></table>

50, 100, 200, and 300. The improvement in revenue slows as sample size increases. We observed that the marginal gain from 200 to 300 samples is less pronounced. See Table 2 for details. Moreover, the average neighborhood size is 1.21, which, according to Theorem 1, indicates that relatively small sample sizes suffice.

**RUNTIME PERFORMANCE.** In practice, executing one block sample took 2.42 seconds on average. The end-to-end processing took an average of 5.7 seconds (without parallelization). Moreover, the pure ILP solving time (Step 5) was only 0.4 seconds. Refer to Figures 12 for details. We emphasize that steps 2-4 can be parallelized, allowing for runtime reduction with additional computational power. The ILP performance depends primarily on instance sparsity rather than mempool size. We observed that increasing the number of transactions in the mempool leads to ILP instances that are easier and faster to solve. See Figure 13 for details. A detailed breakdown of results by sample size can be found in Appendix C.

<figure><img src="image_11.png" /><figcaption>Figure 12: Histogram of the end-to-end (green) and ILP solver (blue) processing times per block. The y-axis is in logarithmic scale.</figcaption></figure>
<figure><img src="image_12.png" /><figcaption>Figure 13: Scatter of ILP solver time (seconds) versus number of transactions per mempool, with sample size fixed at 300.</figcaption></figure>

# 6 Discussion

**OUR APPROACH AND MEV.** The proposed approach is well-suited to handle MEV opportunities, which often involve transaction dependencies and ordering constraints. The logical language is expressive enough to natively model and optimize MEV opportunities, such as those found in Flashbots bundles, directly. More specifically, an MEV bundle B composed of an ordered sequence of transactions $\langle tx_1, tx_2, \dots, tx_k \rangle$ and a promised bundle reward r can be modeled as a gas usage rule with the following logical formula:

$$ \phi_B = \diamond tx_B \wedge \underbrace{(tx_B < tx_1) \wedge \dots \wedge (tx_{k-1} < tx_k)}_{\text{ordering}} $$

with an associated gas usage rule

$$ \phi_B \Rightarrow \text{expected-gas}(tx_B) = r, $$

where $tx_B$ is a synthetic transaction that represents the entire bundle. The main obstacle to a full experimental validation of this approach is the closed-source, proprietary nature of most MEV strategies and the general lack of public, real-time data feeds for MEV bundles [36].

**OUR APPROACH AND PROPOSER-BUILDER SEPARATION (PBS).**

The advent of Proposer-Builder Separation (PBS) on Ethereum fundamentally changes the block production pipeline by separating block building from block proposal [24]. Despite this, our algorithm remains relevant in this setting. PBS and its adoption is widely studied in the Ethereum community [6, 29, 56]. Under PBS, the consensus client (the proposer) outsources the complex and resource-intensive task of block construction to a competitive market of specialized builders. Proposers can access this market via a specialized middleware, such as MEV-Boost [25]. These builders construct full blocks and submit them to the proposer, who simply selects the one with the highest declared bid, which corresponds to the block's total value. This creates an intense, winner-take-all competition among builders. Any marginal increase in block value can be the deciding factor in having a block accepted. Our algorithm directly addresses this by providing a method to maximize the tip-revenue component of a block's total value.

**OUR APPROACH AND HISTORICAL OBSERVATIONS.** The modular design of our framework allows for significant optimizations by incorporating historical observations and prior knowledge. The

neighborhood estimation and rule extraction components can be augmented for transactions involving known contracts. For instance, a block builder could integrate existing static analysis plug-in tools [1, 13] that recognize interactions with high-volume contracts (e.g., popular DEXs or lending platforms) and directly provide the known dependency rules to the ILP solver.

**OUR ALGORITHM IMPACT ON THE ETHEREUM ECOSYSTEM.** Our algorithm has the potential for a significant positive impact on the Ethereum ecosystem. Research has demonstrated that heterogeneity in information and skill across block producers can lead to centralization, with blockchain protocols potentially dominated by only a few of the most capable block producers. However, the extent of centralization depends on the number of block producers with near-competitive capabilities. PBS can reduce proposer heterogeneity through auction-theoretic mechanisms, but only if the builder ecosystem is sufficiently competitive [6]. Consequently, the results of this work can increase the revenue potential of builders while requiring only modest computational resources, thereby fostering a more competitive builder ecosystem and mitigating centralization risks. Furthermore, external factors such as geographic location [16] and capital requirements [29, 31] can limit participation and affect participant earnings [48]. To overcome these barriers, individuals often join staking pools [37, 47, 52]. However, this can inadvertently increase centralization by consolidating control among a few entities. This work makes individual participation more profitable, as it does not require extreme computational resources and is more sustainable, which in turn promotes greater decentralization. Moreover, Our approach extends beyond Ethereum mainnet to any protocol supporting custom transaction ordering, including major Ethereum-compatible Layer 2s such as Optimism [44], Base [9], Scroll [49], StarkNet [53], zkSync Era [60], Polygon zkEVM [45]. These protocols share Ethereum's account-based model and allow sequencers to accrue transaction fees. Since our method only requires a black-box execution tool for bundle ordering, it can be readily adopted to improve revenue across these platforms.

# 7 Conclusion

In this work, we presented a novel randomized approach to boost miners' transaction-fee revenues on the Ethereum blockchain. We observed that a transaction's gas usage is often influenced by a small subset of other transactions, termed its neighborhood. Our algorithm uses testing and decision trees to estimate these neighborhoods, then extracts gas usage rules to predict each transaction's fee based on its preceding neighborhood in the block. These rules are translated into an integer linear programming (ILP) instance, which is solved using an external ILP-solver. We implemented our approach as an open-source tool and conducted extensive experiments, showing significant tip revenue gains over real-world Ethereum miners. Our algorithm achieves an annualized increase of nearly 63 million USD in transaction-fee revenues.

# Acknowledgments

This work was partially supported by the ERC Starting Grant 101222524 (SPES) and the Ethereum Foundation Research Grant FY24-1793. T. Barakbayeva was supported by the Hong Kong PhD Fellowship Scheme. Authors are ordered alphabetically.
References

[1] Elvira Albert, Jesús Correas, Pablo Gordillo, Guillermo Román-Díez, and Albert Rubio. 2020. GASOL: Gas Analysis and Optimization for Ethereum Smart Contracts. In TACAS (2). 118–125.

[2] Elvira Albert, Jesús Correas, Pablo Gordillo, Guillermo Román-Díez, and Albert Rubio. 2021. Don't run on fumes - Parametric gas bounds for smart contracts. *J. Syst. Softw.* 176 (2021), 110923.

[3] Elvira Albert, Pablo Gordillo, Alejandro Hernández-Cerezo, Albert Rubio, and Maria Anna Schett. 2022. Super-optimization of Smart Contracts. *ACM Trans. Softw. Eng. Methodol.* 31, 4 (2022), 70:1–70:29.

[4] Elvira Albert, Pablo Gordillo, Albert Rubio, and Ilya Sergey. 2019. Running on Fumes - Preventing Out-of-Gas Vulnerabilities in Ethereum Smart Contracts Using Static Resource Analysis. In *VECOs*, Vol. 11847. 63–78.

[5] Kushal Babel, Philip Daian, Mahimna Kelkar, and Ari Juels. 2023. Clockwork Finance: Automated Analysis of Economic Security in Smart Contracts. In *SP. 2499–2516*.

[6] Maryam Bahrani, Pranav Garimidi, and Tim Roughgarden. 2024. Centralization in Block-Building and Proposer-Builder Separation. In *FC*. 331–349.

[7] Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. 2017. Proofs of Useful Work. *IACR Cryptol. ePrint Arch.* (2017), 203.

[8] Togzhan Barakbayeva, Soroush Farokhnia, Amir Kafshdar Goharshady, Markus Gufler, and Sergei Novozhilov. 2024. Piuxi: Optimal Block Production Revenues on Cardano. In *IEEE Blockchain*. 491–496.

[9] Base. 2025. Base: Open Stack for Ethereum Layer 2 Builders. https://base.org/. Accessed on 15 November 2025.

[10] Blocknative. 2025. Mempool Archive. https://docs.blocknative.com/data-archive/mempool-archive

[11] Suresh Bolusani, Mathieu Besançon, Ksenia Bestuzheva, Antonia Chmiela, João Dionisio, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Mohammad Ghannam, Ambros Gleixner, Christoph Graczyk, Katrin Halbig, Ivo Hedtke, Alexander Hoen, Christopher Hojny, Rolf van der Hulst, Dominik Kamp, Thorsten Koch, Kevin Kofler, Jurgen Lentz, Julian Manns, Gioni Mexi, Erik Mühmer, Marc E. Pfetsch, Franziska Schlösser, Felipe Serrano, Yuji Shinano, Mark Turner, Stefan Vigerske, Dieter Weninger, and Lixing Xu. 2024. *The SCIP Optimization Suite 9.0*. Technical Report. Optimization Online. https://optimization-online.org/2024/02/the-scip-optimization-suite-9-0/

[12] L. Breiman, J. Friedman, C.J. Stone, and R.A. Olshen. 1984. *Classification and Regression Trees*. https://books.google.com.hk/books?id=JwQx-WOMsyQC

[13] Zhuo Cai, Soroush Farokhnia, Amir Kafshdar Goharshady, and S. Hitarth. 2023. Asparagus: Automated Synthesis of Parametric Gas Upper-Bounds for Smart Contracts. *Proc. ACM Program. Lang.* 7, OOPSLA2 (2023), 882–911.

[14] Krishnendu Chatterjee, Amir Kafshdar Goharshady, and Arash Pourdamghani. 2019. Hybrid mining: exploiting blockchain's computational power for distributed problem solving. In *SAC*. 374–381.

[15] CoinMarketCap. 2025. Cryptocurrency Prices, Charts and Market Capitalizations. https://coinmarketcap.com/

[16] Mikel Cortes-Goicoechea, Tarun Mohandas-Daryanani, Jose Luis Muñoz-Tapia, and Leonardo Bautista-Gomez. 2023. Unveiling Ethereum's Hidden Centralization Incentives: Does Connectivity Impact Performance?. In *BCCA*. IEEE, 89–96.

[17] Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xueyuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. 2020. Flash Boys 2.0: Frontrunning in Decentralized Exchanges, Miner Extractable Value, and Consensus Instability. In *SP. 910–927*.

[18] Micah Dameron. 2018. Beigepaper: An Ethereum Technical Specification. https://github.com/chronaon/eigepaper/blob/master/eigepaper.pdf

[19] Bernardo David, Peter Gazi, Aggelos Kiayias, and Alexander Russell. 2018. Ouroboros Praos: An Adaptively-Secure, Semi-synchronous Proof-of-Stake Blockchain. In *EUROCRYPT*. 66–98.

[20] Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. 2015. Proofs of Space. In *CRYPTO*, Vol. 9216. 585–605.

[21] ErigonTech. 2023. Erigon. https://github.com/erigontech/erigon

[22] Ethereum Foundation. 2025. Gas and fees. https://ethereum.org/en/developers/docs/gas/

[23] Ethereum Foundation. 2025. Maximal Extractable Value (MEV). https://ethereum.org/en/developers/docs/mev/

[24] Ethereum Foundation. 2025. Proposer-builder separation. https://ethereum.org/roadmap/pbs/

[25] Flashbots. 2025. What is MEV-Boost? https://docs.flashbots.net/flashbots-mev-boost/introduction

[26] Ethereum Foundation. 2025. Go Ethereum (Geth) Client. https://geth.ethereum.org/

[27] Foundry. 2023. Anvil CLI Reference. https://book.getfoundry.sh/reference/cli/avnil

[28] Neville Grech, Michael Kong, Anton Jurisevic, Lexi Brent, Bernhard Scholz, and Yannis Smaragdakis. 2018. MadMax: surviving out-of-gas conditions in Ethereum smart contracts. *Proc. ACM Program. Lang.* 2, OOPSLA (2018), 116:1–116:27.

[29] Lioba Heimbach, Lucianna Kiffer, Christof Ferreira Torres, and Roger Wattenhofer. 2023. Ethereum's Proposer-Builder Separation: Promises and Realities. In *IMC*. 406–420.

[30] Lioba Heimbach and Roger Wattenhofer. 2022. SoK: Preventing Transaction Reordering Manipulations in Decentralized Finance. In *AFT*. 47–60.

[31] Kose John, Barnabé Monnot, Peter Mueller, Fahad Saleh, and Caspar Schwarz-Schilling. 2025. Economics of ethereum. *Journal of Corporate Finance* 91 (2025), 102718.

[32] Aljsha Judmayer, Nicholas Stifter, Philipp Schindler, and Edgar R. Weippl. 2022. Estimating (Miner) Extractable Value is Hard, Let's Go Shopping!. In *Financial Cryptography Workshops*. 74–92.

[33] Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. 2017. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In *CRYPTO*, Vol. 10401. 357–388.

[34] Sunny King and Scott Nadal. 2012. Pcoin: Peer-to-peer crypto-currency with proof-of-stake. (2012).

[35] Satpal Singh Kushwaha, Sandeep Joshi, Dilbag Singh, Manjit Kaur, and Heung-No Lee. 2022. Ethereum Smart Contract Analysis Tools: A Systematic Review. *IEEE Access* 10 (2022), 57037–57062.

[36] Zihao Li, Jianfeng Li, Zheyuan He, Xiapu Luo, Ting Wang, Xiaoe Ni, Wenwu Yang, Xi Chen, and Ting Chen. 2023. Demystifying DeFi MEV Activities in Flashbots Bundle. In *CCS. ACM*, 165–179.

[37] Lido Finance. 2025. Lido Liquid Staking. urlhttps://lido.fi/. Accessed on 15 November 2025.

[38] Linfa. 2025. Linfa. https://github.com/rust-ml/linfa/tree/master

[39] Loi Luu, Due-Hiep Chu, Hrishi Olickel, Prateek Saxena, and Aquinas Hobor. 2016. Making Smart Contracts Smarter. In *CCS*. 254–269.

[40] Mohsen Alambardar Meybodi, Amir Kafshdar Goharshady, Mohammad Reza Hooshmandasl, and Ali Shakiba. 2022. Optimal Mining: Maximizing Bitcoin Miners' Revenues from Transaction Fees. In *Blockchain*. IEEE, 266–273.

[41] Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. (2008).

[42] Behkish Nassirzadeh, Huaiying Sun, Sebastian Banescu, and Vijay Ganesh. 2022. Gas Gauge: A Security Analysis Tool for Smart Contract Out-of-Gas Vulnerabilities. In *MARBLE*. 143–167.

[43] Quang-Thang Nguyen, Do Bao Son, Thi Tam Nguyen, and Ba-Lam Do. 2022. GasSaver: A Tool for Solidity Smart Contract Optimization. In *BSCL* 125–134.

[44] Optimism. 2025. Optimism: Ethereum Layer 2 Scaling using Optimistic Rollups. https://optimism.io/. Accessed on 15 November 2025.

[45] Polygon zkEVM. 2025. Polygon zkEVM: Ethereum Layer 2 with Zero-Knowledge Rollups. https://polygon.technology/solution/polygons-zkevm/. Accessed on 15 November 2025.

[46] Henry Gordon Rice. 1953. Classes of recursively enumerable sets and their decision problems. *Transactions of the American Mathematical society* 74, 2 (1953), 358–366.

[47] Rocket Pool. 2025. Rocket Pool: Decentralised Ethereum Liquid Staking Protocol. https://rocketpool.net/. Accessed on 15 November 2025.

[48] Ashish Rajendra Sai, Jim Buckley, Brian Fitzgerald, and Andrew Le Gear. 2021. Taxonomy of centralization in public blockchain systems: A systematic literature review. *Inf. Process. Manag.* 58, 4 (2021), 102584.

[49] Scroll. 2025. Scroll: Native zkEVM Layer 2 for Ethereum. https://scroll.io/. Accessed on 15 November 2025.

[50] Cosimo Sguanci, Roberto Spatafora, and Andrea Mario Vergani. 2021. Layer 2 Blockchain Scaling: A Survey. *CoRR* abs/2107.10881 (2021).

[51] Solidity. 2025. Solidity documentation. https://docs.soliditylang.org/en/latest/

[52] StakeWise. 2025. StakeWise: Ethereum Proof Of Stake Pool and Solo Staking. https://www.stakewise.io/. Accessed on 15 November 2025.

[53] StarkNet. 2025. StarkNet: zk-STARK Powered Ethereum Layer 2 Scaling Solution. https://docs.starknet.io/. Accessed on 15 November 2025.

[54] Gavin Wood et al. 2014. Ethereum: A secure decentralised generalised transaction ledger. *Ethereum project yellow paper* 2014 (2014), 1–32.

[55] Jie Xu, Cong Wang, and Xiaohua Jia. 2023. A survey of blockchain consensus protocols. *Comput. Surveys* 55, 13s (2023), 1–35.

[56] Sen Yang, Fan Zhang, Ken Huang, Xi Chen, Youwei Yang, and Feng Zhu. 2024. SoK: MEV Countermeasures. In *DeFi@CCS. ACM*, 21–30.

[57] YCharts. 2025. Ethereum Gas Used Per Day. https://ycharts.com/indicators/ethereum_gas_used_per Day

[58] Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan-Gueta, and Ittai Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In *PODC*. 347–356.

[59] Liyi Zhou, Kaihua Qin, Christof Ferreira Torres, Duc Viet Le, and Arthur Gervais. 2021. High-Frequency Trading on Decentralized On-Chain Exchanges. In *SP. 428–445*.

[60] zkSync Era. 2025. zkSync Era: Ethereum Layer 2 Scaling with zk-Rollups. https://zksync.io/. Accessed on 15 November 2025.
# A Running Example

## A.1 Translating Gas Usage Rules to ILP

The full transformation table can be found in Table 3.

<table><caption>Table 3: Translating the gas usage rules in our running example to ILP.</caption><thead><tr><th>tx</th><th>ρ</th><th>φ</th><th>g<sub>ρ</sub></th><th>||φ||</th><th>maximize</th></tr></thead><tbody><tr><td>tx<sub>1</sub></td><td>ρ<sub>1,1</sub></td><td>◇tx<sub>1</sub> ∧ (tx<sub>1</sub> &lt; {tx<sub>4</sub>, tx<sub>5</sub>})</td><td>⇒ 10</td><td><table><tbody><tr><td>b<sub>1</sub> ≥ b<sub>ρ<sub>1,1</sub></sub></td><td>+10 · 24 · b<sub>ρ<sub>1,1</sub></sub></td></tr><tr><td>28 · (1 − b<sub>4</sub>) − 14 · (1 − b<sub>1</sub>) + r<sub>4</sub> − r<sub>1</sub> ≥ b<sub>ρ<sub>1,1</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>5</sub>) − 14 · (1 − b<sub>1</sub>) + r<sub>5</sub> − r<sub>1</sub> ≥ b<sub>ρ<sub>1,1</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>1</sub></td><td>ρ<sub>1,2</sub></td><td>◇tx<sub>1</sub> ∧ (tx<sub>4</sub> &lt; tx<sub>5</sub> &lt; tx<sub>1</sub>)</td><td>⇒ 6</td><td><table><tbody><tr><td>b<sub>1</sub> ≥ b<sub>ρ<sub>1,2</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>5</sub>) − 14 · (1 − b<sub>4</sub>) + r<sub>5</sub> − r<sub>4</sub> ≥ b<sub>ρ<sub>1,2</sub></sub></td><td>+6 · 24 · b<sub>ρ<sub>1,2</sub></sub></td></tr><tr><td>28 · (1 − b<sub>1</sub>) − 14 · (1 − b<sub>5</sub>) + r<sub>1</sub> − r<sub>5</sub> ≥ b<sub>ρ<sub>1,2</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>1</sub></td><td>ρ<sub>1,3</sub></td><td>◇tx<sub>1</sub> ∧ (tx<sub>4</sub> &lt; tx<sub>1</sub> &lt; tx<sub>5</sub>)</td><td>⇒ 8</td><td><table><tbody><tr><td>b<sub>1</sub> ≥ b<sub>ρ<sub>1,3</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>1</sub>) − 14 · (1 − b<sub>4</sub>) + r<sub>1</sub> − r<sub>4</sub> ≥ b<sub>ρ<sub>1,3</sub></sub></td><td>+8 · 24 · b<sub>ρ<sub>1,3</sub></sub></td></tr><tr><td>28 · (1 − b<sub>5</sub>) − 14 · (1 − b<sub>1</sub>) + r<sub>5</sub> − r<sub>1</sub> ≥ b<sub>ρ<sub>1,3</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>1</sub></td><td>ρ<sub>1,4</sub></td><td>◇tx<sub>1</sub> ∧ (tx<sub>5</sub> &lt; tx<sub>1</sub> &lt; tx<sub>4</sub>)</td><td>⇒ 2</td><td><table><tbody><tr><td>b<sub>1</sub> ≥ b<sub>ρ<sub>1,3</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>1</sub>) − 14 · (1 − b<sub>5</sub>) + r<sub>1</sub> − r<sub>5</sub> ≥ b<sub>ρ<sub>1,4</sub></sub></td><td>+2 · 24 · b<sub>ρ<sub>1,4</sub></sub></td></tr><tr><td>28 · (1 − b<sub>4</sub>) − 14 · (1 − b<sub>1</sub>) + r<sub>4</sub> − r<sub>1</sub> ≥ b<sub>ρ<sub>1,4</sub></sub></td><td></td></tr><tr><td>b<sub>ρ<sub>1,1</sub></sub> + b<sub>ρ<sub>1,2</sub></sub> + b<sub>ρ<sub>1,3</sub></sub> + b<sub>ρ<sub>1,4</sub></sub> ≤ 1</td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>2</sub></td><td>ρ<sub>2,1</sub></td><td>◇tx<sub>2</sub> ∧ (tx<sub>6</sub> &lt; tx<sub>2</sub>)</td><td>⇒ 9</td><td><table><tbody><tr><td>b<sub>2</sub> ≥ b<sub>ρ<sub>2,1</sub></sub></td><td>+9 · 9 · b<sub>ρ<sub>2,1</sub></sub></td></tr><tr><td>28 · (1 − b<sub>2</sub>) − 14 · (1 − b<sub>6</sub>) + r<sub>2</sub> − r<sub>6</sub> ≥ b<sub>ρ<sub>2,1</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>2</sub></td><td>ρ<sub>2,2</sub></td><td>◇tx<sub>2</sub> ∧ (tx<sub>2</sub> &lt; tx<sub>6</sub>)</td><td>⇒ 8</td><td><table><tbody><tr><td>b<sub>2</sub> ≥ b<sub>ρ<sub>2,2</sub></sub></td><td>+8 · 9 · b<sub>ρ<sub>2,2</sub></sub></td></tr><tr><td>28 · (1 − b<sub>6</sub>) − 14 · (1 − b<sub>2</sub>) + r<sub>6</sub> − r<sub>2</sub> ≥ b<sub>ρ<sub>2,2</sub></sub></td><td></td></tr><tr><td>b<sub>ρ<sub>2,1</sub></sub> + b<sub>ρ<sub>2,2</sub></sub> ≤ 1</td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>3</sub></td><td>ρ<sub>3,1</sub></td><td>◇tx<sub>3</sub> ∧ (tx<sub>2</sub> &lt; tx<sub>3</sub>)</td><td>⇒ 4</td><td><table><tbody><tr><td>b<sub>3</sub> ≥ b<sub>ρ<sub>3,1</sub></sub></td><td>+4 · 5 · b<sub>ρ<sub>3,1</sub></sub></td></tr><tr><td>28 · (1 − b<sub>3</sub>) − 14 · (1 − b<sub>2</sub>) + r<sub>3</sub> − r<sub>2</sub> ≥ b<sub>ρ<sub>3,1</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>3</sub></td><td>ρ<sub>3,2</sub></td><td>◇tx<sub>3</sub> ∧ (tx<sub>3</sub> &lt; tx<sub>2</sub>)</td><td>⇒ 2</td><td><table><tbody><tr><td>b<sub>3</sub> ≥ b<sub>ρ<sub>3,2</sub></sub></td><td>+2 · 5 · b<sub>ρ<sub>3,2</sub></sub></td></tr><tr><td>28 · (1 − b<sub>2</sub>) − 14 · (1 − b<sub>3</sub>) + r<sub>2</sub> − r<sub>3</sub> ≥ b<sub>ρ<sub>3,2</sub></sub></td><td></td></tr><tr><td>b<sub>ρ<sub>3,1</sub></sub> + b<sub>ρ<sub>3,2</sub></sub> ≤ 1</td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>4</sub></td><td>ρ<sub>4,1</sub></td><td>◇tx<sub>4</sub></td><td>⇒ 2</td><td><table><tbody><tr><td>b<sub>4</sub> ≥ b<sub>ρ<sub>4,1</sub></sub></td><td>+2 · 29 · b<sub>ρ<sub>4,1</sub></sub></td></tr><tr><td>b<sub>ρ<sub>4,1</sub></sub> ≤ 1</td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>5</sub></td><td>ρ<sub>5,1</sub></td><td>◇tx<sub>5</sub> ∧ (tx<sub>5</sub> &lt; {tx<sub>2</sub>, tx<sub>4</sub>})</td><td>⇒ 10</td><td><table><tbody><tr><td>b<sub>5</sub> ≥ b<sub>ρ<sub>5,1</sub></sub></td><td>+10 · 24 · b<sub>ρ<sub>5,1</sub></sub></td></tr><tr><td>28 · (1 − b<sub>2</sub>) − 14 · (1 − b<sub>5</sub>) + r<sub>2</sub> − r<sub>5</sub> ≥ b<sub>ρ<sub>5,1</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>4</sub>) − 14 · (1 − b<sub>5</sub>) + r<sub>4</sub> − r<sub>5</sub> ≥ b<sub>ρ<sub>5,1</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>5</sub></td><td>ρ<sub>5,2</sub></td><td>◇tx<sub>5</sub> ∧ (tx<sub>4</sub> &lt; {tx<sub>5</sub>, tx<sub>2</sub>})</td><td>⇒ 10</td><td><table><tbody><tr><td>b<sub>5</sub> ≥ b<sub>ρ<sub>5,2</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>5</sub>) − 14 · (1 − b<sub>4</sub>) + r<sub>5</sub> − r<sub>4</sub> ≥ b<sub>ρ<sub>5,2</sub></sub></td><td>+10 · 24 · b<sub>ρ<sub>5,2</sub></sub></td></tr><tr><td>28 · (1 − b<sub>2</sub>) − 14 · (1 − b<sub>4</sub>) + r<sub>2</sub> − r<sub>4</sub> ≥ b<sub>ρ<sub>5,2</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>5</sub></td><td>ρ<sub>5,3</sub></td><td>◇tx<sub>5</sub> ∧ (tx<sub>2</sub> &lt; tx<sub>4</sub> &lt; tx<sub>5</sub>)</td><td>⇒ 2</td><td><table><tbody><tr><td>b<sub>5</sub> ≥ b<sub>ρ<sub>5,3</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>4</sub>) − 14 · (1 − b<sub>2</sub>) + r<sub>4</sub> − r<sub>2</sub> ≥ b<sub>ρ<sub>5,3</sub></sub></td><td>+2 · 24 · b<sub>ρ<sub>5,3</sub></sub></td></tr><tr><td>28 · (1 − b<sub>5</sub>) − 14 · (1 − b<sub>4</sub>) + r<sub>5</sub> − r<sub>4</sub> ≥ b<sub>ρ<sub>5,3</sub></sub></td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>5</sub></td><td>ρ<sub>5,4</sub></td><td>◇tx<sub>5</sub> ∧ (tx<sub>2</sub> &lt; tx<sub>5</sub> &lt; tx<sub>4</sub>)</td><td>⇒ 4</td><td><table><tbody><tr><td>b<sub>5</sub> ≥ b<sub>ρ<sub>5,4</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>5</sub>) − 14 · (1 − b<sub>2</sub>) + r<sub>5</sub> − r<sub>2</sub> ≥ b<sub>ρ<sub>5,4</sub></sub></td><td>+4 · 24 · b<sub>ρ<sub>5,4</sub></sub></td></tr><tr><td>28 · (1 − b<sub>4</sub>) − 14 · (1 − b<sub>5</sub>) + r<sub>4</sub> − r<sub>5</sub> ≥ b<sub>ρ<sub>5,4</sub></sub></td><td></td></tr><tr><td>b<sub>ρ<sub>5,1</sub></sub> + b<sub>ρ<sub>5,2</sub></sub> + b<sub>ρ<sub>5,3</sub></sub> + b<sub>ρ<sub>5,4</sub></sub> ≤ 1</td><td></td></tr></tbody></table></td></tr><tr><td>tx<sub>6</sub></td><td>ρ<sub>6,1</sub></td><td>◇tx<sub>6</sub> ∧ (tx<sub>3</sub> &lt; tx<sub>6</sub>)</td><td>⇒ 10</td><td><table><tbody><tr><td>b<sub>6</sub> ≥ b<sub>ρ<sub>6,1</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>6</sub>) − 14 · (1 − b<sub>3</sub>) + r<sub>6</sub> − r<sub>3</sub> ≥ b<sub>ρ<sub>6,1</sub></sub></td><td>+10 · 2 · b<sub>ρ<sub>6,1</sub></sub></td></tr></tbody></table></td></tr><tr><td>tx<sub>6</sub></td><td>ρ<sub>6,2</sub></td><td>◇tx<sub>6</sub> ∧ (tx<sub>6</sub> &lt; tx<sub>3</sub>)</td><td>⇒ 5</td><td><table><tbody><tr><td>b<sub>6</sub> ≥ b<sub>ρ<sub>6,2</sub></sub></td><td></td></tr><tr><td>28 · (1 − b<sub>3</sub>) − 14 · (1 − b<sub>6</sub>) + r<sub>3</sub> − r<sub>6</sub> ≥ b<sub>ρ<sub>6,2</sub></sub></td><td>+5 · 2 · b<sub>ρ<sub>6,2</sub></sub></td></tr><tr><td>b<sub>ρ<sub>6,1</sub></sub> + b<sub>ρ<sub>6,2</sub></sub> ≤ 1</td><td></td></tr></tbody></table></td></tr></tbody></table>
# B Proofs

## B.1 Proof of Theorem 1

PROOF. For a transaction tx, the probability that an induced permutation $\pi^*$ does not appear after one step is $1 - \frac{1}{(|nbhd(tx)|+1)!} \le 1 - \frac{1}{(\Delta+1)!}$. By the independence of trials, the probability that the induced permutation remains unseen after $r$ steps is $(1 - \frac{1}{(\Delta+1)!})^r \le \exp(-\frac{r}{(\Delta+1)!})$. As for each tx there are at most $(\Delta + 1)!$ induced blocks, by the union bound, the probability that there exists a transaction tx such that the induced permutation $\pi^*$ does not appear after $r$ steps is at most $\mathbb{P}[T \ge r] \le |\text{Pool}| \cdot (\Delta + 1)! \cdot \exp(-\frac{r}{(\Delta+1)!})$. After plugging in $r = (\Delta + 1)! \cdot \log(\frac{|\text{Pool}| \cdot (\Delta+1)!}{\epsilon})$, and rearranging the terms, we obtain the desired result.

□

<figure><img src="image_13.png" /></figure>
C Detailed Experimental Results

We observe that increasing the number of transactions in the mem-
pool leads to ILP instances that are easier and faster to solve. Fig-
ure 14 demonstrates that this trend holds across different sample
sizes: 50, 100, 200, and 300. For a sample size of 50, the top 20%
of mempools by transaction count (bins 910–1015 and 1015–1120)
exhibit average ILP solve times of 1.142 and 1.042 seconds, respec-
tively, whereas the middle 20% (bins 387–492 and 492–597) have
average solve times of 0.812 and 0.876 seconds. For a sample size
of 100, the top 20% (bins 782–870 and 870–959) have average solve
times of 0.936 and 1.066 seconds, while the middle 20% (bins 339–428
and 428–516) have average solve times of 0.749 and 0.704 seconds.
For a sample size of 200, the top 20% (bins 564–625 and 625–687)
have average solve times of 0.343 and 0.274 seconds, compared to
0.526 and 0.515 seconds for the middle 20% (bins 257–319 and 319–
380). Similarly, for a sample size of 300, the top 20% (bins 517–572
and 572–628) have average solve times of 0.135 and 0.273 seconds,
while the middle 20% (bins 240–295 and 295–351) have average
solve times of 0.455 and 0.449 seconds. These results indicate that
mempools with higher transaction counts generally correspond to
lower ILP solve times, supporting the observed trend that larger
mempools yield easier ILP instances.

Additionally, we observe that for less sparse mempools, the ILP
requires more time to find the optimal solution. Figure 15 shows that
for higher neighborhood sizes (i.e., less sparse mempools), the ILP
tends to require more time. For a sample size of 50, neighborhood
sizes in the range 2.094–2.250 have an average ILP time of 8.172 sec-
onds, while sizes in the range 1.000–1.156 have an average ILP time
of 0.169 seconds. For a sample size of 100, the top bin 2.225–2.361
averages 6.676 seconds compared to 0.107 seconds in the bottom
bin 1.000–1.136. For a sample size of 200, the top bin 2.251–2.407
averages 3.911 seconds compared to 0.084 seconds in the bottom
bin 1.000–1.156. For a sample size of 300, the top bin 2.579–2.754
averages 3.254 seconds compared to 0.075 seconds in the bottom
bin 1.000–1.175. However, comparing the effect of neighborhood
size on ILP performance across different sample sizes suggests that
increasing the number of samples provides improvements to ILP
solving time.

A key practical aspect of implementing our algorithm is the ob-
servation that neighborhood estimation is significantly less sample-
intensive than the extraction of precise gas-usage rules, which
enables a *dynamic sample size selection* strategy. The algorithm first
estimates the maximum neighborhood size, Δ, from a small, initial
set of samples. This empirical Δ then dictates the sufficient sample
size needed to satisfy the conditions of Theorem 1. If the initial set
is too small, the algorithm performs targeted upsampling to meet
the required threshold before proceeding. Refer to Figure 16 for
more details.

<figure><img src="image_14.png" /><figcaption>(a) Sample size 50</figcaption></figure>

<figure><img src="image_15.png" /><figcaption>(b) Sample size 100</figcaption></figure>

<figure><img src="image_16.png" /><figcaption>(c) Sample size 200</figcaption></figure>

<figure><img src="image_17.png" /><figcaption>(d) Sample size 300</figcaption></figure>

<caption>Figure 14: Scatter of ILP solver time (seconds) versus number of transactions per mempool for different sample sizes.</caption>
<figure><img src="image_18.png" /><figcaption>(a) Sample size 50</figcaption></figure>

<figure><img src="image_19.png" /><figcaption>(b) Sample size 100</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>(c) Sample size 200</figcaption></figure>

<figure><img src="image_21.png" /><figcaption>(d) Sample size 300</figcaption></figure>

Figure 16: Histogram of neighborhood size per block for different sample sizes.

<figure><img src="image_22.png" /><figcaption>(a) Sample size 50</figcaption></figure>

<figure><img src="image_23.png" /><figcaption>(b) Sample size 100</figcaption></figure>

<figure><img src="image_24.png" /><figcaption>(c) Sample size 200</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>(d) Sample size 300</figcaption></figure>

Figure 15: Scatter of ILP solver time (seconds) versus average neighborhood size per block for different sample sizes.