This post is a brief overview of sequencing mechanisms and their effect on transaction execution fairness. Sequencing rules can be applied on different levels of the EVM application stack. The application of sequencing rules on different levels comes with its own trade-offs and fairness guarantees.

The first part of the post describes the taxonomy of fairness-aware sequencing mechanisms, and the last section discusses recent work on fair ordering using verifiable sequencing rules.

Transaction sequencing as a Knapsack problem (P vs NP)

This taxonomy was inspired by a Flashbots forum post from Quintus, where he classifies sequencing rules based on their runtime complexity. Transaction sequencing by block builders can be described as a Knapsack problem. Mikerah from Hashclock has a good explanation of this problem in their post.
Rational block builders solve an optimization problem to maximize their profit by constructing the most valuable block. We cannot expect builders to execute rules which cannot be solved in polynomial time. Hence, the taxonomy from Quintus explores this topic and classifies the rules to underline their feasibility.

Fairness-aware transaction sequencing rules

Most of the discussions around sequencing rules come from the problem of MEV and trading on decentralized exchanges. Rational block builders will always manipulate ordering to maximize profit. This implies that more sophisticated market participants will keep extracting profit from less involved traders. More research is conducted on returning MEV back to users and the notion of trade fairness. Flashbots is transitioning its focus from solely enhancing validator profits towards returning MEV rebates for transaction creators using MEV-share.

This paper started a new wave of discussions by presenting a new sequencing mechanism (Verifiable Greedy Sequencing Rule). While it is impossible to find a sequencing rule that would prevent block builders from obtaining risk-free profit, verifiable sequencing rules provide provable execution price guarantees.

The verifiable sequencing rule is not the first attempt to enshrine trade execution fairness in Ethereum. Aequitas and Themis are the result of research on order-fair consensus in permissionless setting. Taxonomy 2.0 is an attempt to summarize the state of knowledge around sequencing rules and evaluate sequencing mechanisms beyond verifiable sequencing rules.

Taxonomy: Fairness-aware consensus-level sequencing algorithms

Fairness in EVM blockchains can be enforced at a consensus-level. There is research that distinguishes order fairness as the third consensus property, along with consistency and liveness. Aequitas, Wendy, Quick, and Themis are examples of algorithms in this group.

Fairness is defined by the arrival time of transactions and does not involve trade fairness. Receive-order fairness, block-order fairness, and differential fairness tighten the formal definition of fairness. One of the main reasons we need to introduce more formal definitions is that different blocks have different views of the mempool. Determining which transaction came first in a distributed environment is more complex.

One interesting finding in consensus-level research is the Condorcet paradox, which parallels fair-ordering and majority voting theory. "Condorcet paradox (or voting paradox) is a situation where majority rule behaves in a way that is self-contradictory." Simply put, it is possible to create a situation where nodes cannot decide which transaction should go first and deterministically construct a block using consensus-level algorithm. This parallel can also be applied to verifiable sequencing rules (more details in the last section).

Taxonomy: Sequencer-level fair sequencing algorithms

Many rollups depend on centralized sequencers. These sequencers are responsible for transaction ordering. Most of the current research evaluates sequencing rules on this level of the application stack. Since this layer is often centralized, sequencers can use a first come first serve (FCFS) policy similar to centralized exchanges. This strategy frequently generates latency competition, where parties invest in latency reduction to be competitive in arbitrage trading.

First come first serve is not the only algorithm used by sequencers. This paper compiled a list of six ordering mechanisms applied in practice.

• Priority gas ordering mechanism: Sequencers solve the Knapsack problem using approximation algorithms and ordering public mempool transactions by gas price.

• Flashbots mechanism: Players participate in the transaction ordering mechanism by sending transactions through a private channel. Flashbots relayer builds the block by solving the Knapsack problem and including public and private candidate pool transactions.

• Random ordering mechanism: Transactions are included in a block randomly. The inclusion rate follows a uniform distribution.

• First input first output mechanism: Transactions are ordered using a local or pseudo-global timestamp.

• Dictatorship/Permissioned mechanism: The sequencer applies custom ordering rules. The rules can include arbitrary logic.

• Metadata mechanism: transactions are ordered by hashes using a generated field nonce.

Each ordering mechanism has its own effect on the validator's profit or trade fairness. Mechanisms such as priority gas ordering or flashbots auctions are designed to maximize validators' profits. The verifiable greedy rule can ensure that a given transaction receives an execution price as good as if this transaction were the only transaction in the block.

With many different rules, centralized sequencers can still violate mev-resistant properties such as timestamp-integrity, mempool privacy and extract MEV from protocols.

Taxonomy: On-chain application-level fair sequencing algorithms

Dapps can introduce application-specific rules to ensure fair execution of transactions. Most of the trades on Ethereum are executed on AMMs where application-level transaction ordering is tightly connected with consensus-level and sequencer-level ordering rules. However, there are different attempts to influence transaction ordering on the application level.

Gas auctions were the primary mechanism for determining transaction ordering in blocks for a long time. Gas auctions involve a bidding process where users compete to process their transactions first. Users submit bids indicating the gas price they are willing to pay to have their transactions processed. Transactions with higher gas prices are prioritized by miners and included in blocks more quickly.

An Auction-Managed Automated Market Maker is the new concept introduced in this paper. Authors propose a new way "to minimize liquidity provider losses to arbitrageurs while maximizing fee revenue from retail flow." The new mechanism adopts a two-stage approach where

1. "Potential managers bid for the right to set and earn the trading fee in a future block."

2. "Liquidity providers respond by adding or removing liquidity."

The new mechanism directly affects sequencing dynamics by introducing a notion of a "pool manager" who has an "exclusive right to capture some arbitrage profit from a pool." This benefit gives them an advantage in the block builder auctions.

Application developers don't have enough levers to enforce application-level transaction ordering. Auction-Managed Automated Market Maker is one of the recent examples showing promises in this research line.

Taxonomy: Off-chain application-level fair sequencing algorithms

Off-chain application-level sequencing algorithms abstract the optimal ordering of transactions away from the blockchain's constrained computational environment. Instead of solving complex optimization problems themselves, block builders can outsource solving NP-complete ordering problems to off-chain solvers.

In a batch auction, trade orders are grouped into "batches" and then offered for bidding to solvers who compete to find the most efficient execution method. The benefit of a batch auction is the ability to execute more sophisticated optimization algorithms to find the most optimal price for the trade. Off-chain optimizers do not have the time-sensitive requirements of block builders and have access to better computational resources to run optimization algorithms. CowSwap, 1inch fusion, and UniswapX are all examples of batch auctions.

Priority queues organize transactions based on predefined criteria, such as gas price, transaction size, or urgency. Priority queues are also a way to handle "all the bundles sequencers receive, and choosing how to feed them to the builder." Titan employs four different queues that handle transactions with varying priority levels.

Priority queues are part of sequencer-level ordering mechanisms. I have deliberately included them in the application-level group to underline that the lines between sequencer logic and application logic are blurred in decentralized applications.

Recent discussions: Condorcet paradox in verifiable sequencing rule

Verifiable sequencing rules became a go-to solution in many sequencing discussions. Provable execution guarantees are a significant improvement for sequencer design. One way to execute this rule is to apply it separately for each AMM pool. Swaps in each AMM pool can be ordered among themselves using the greedy verifiable rule. This technique prevents the sandwiching of transactions executed in each specific AMM pool.

We need to note that this rule does not work when transactions contain several swaps. It is possible to construct a Condorcet cycle by including conflicting swaps in the same transaction. Figure 3 shows a simplified example where there is no clear way to decide if txn 1 should be followed by txn 2 or txn 3. Based on the dex.trades history from the first four months of 2024 on Dune, 18.7% of dex trades are placed in multi-swap transactions. While they do not necessarily cause a Condorcet paradox, sequencers need to find different ways to provide mev-resistant guarantees.

Last remark

I wrote this post while I was writing my thesis on sequencing rules, where I tried to evaluate the effect of different sequencing rules on trade execution fairness. This taxonomy was my attempt to understand sequencing rules before trying to simulate any of them. Please, leave your comments or share different examples.