Authors: Mantle Research team (Aodhgan, Franck, Andreas, AFK, Arun)
Rollups (L2s) provide off-chain execution of transactions in batches and post the result of a batch to L1 or a data availability layer. The result is a significant increase in throughput from around 15 transactions per second on L1 to theoretically thousands of transactions per second for a typical L2 (reportedly up to 40k TPS for Arbitrum, and up to 100k TPS for zkSync).
The off-chain execution is managed by the sequencer. At the moment, all the major rollups operate their own sequencers and that comes with some risks:
Solutions have emerged to remedy the previous problems and a lot of serious research efforts (e.g. Espresso, Astria) are delving into the design of decentralised and shared sequencers. Although the idea is appealing it comes at a cost: decentralising the sequencer may create opportunities but remains complex to implement (relying on a consensus protocol) and several key problems pertaining to decentralising the sequencer are still open (e.g. rewards, revenue sharing). In this context, it is not surprising that no major rollup operators offer decentralised or shared sequencers in production yet.
In this article we propose an alternative light-weight practical solution to provide fair sequencing for rollups. We set out to provide a solution for L2 sequencers that has the following properties:
In an optimistic or validity rollup, the sequencer is in charge of preparing and executing batches of transactions. Most rollups rely on a centralised sequencer, Figure 1 below, managed by the rollup operator, that performs two tasks: extracting and processing batches.
As a result, the rollup operator can decide:
A consequence of this architecture is that if the sequencer is malicious (or biased) the rollup is not censorship resistant. To mitigate this, some rollups like Arbitrum or Optimism provide mechanisms for users to bypass the sequencer to ensure censorship resistance. However, by utilizing the bypass, a user misses out on low fees on the rollup. Another consequence of this design is that the sequencer decides the order of transactions and can take advantage of MEV opportunities, extracting profits from users' transactions (e.g. sandwich attack).
Note also that there is no guarantee that the execute batch module executes the transactions in the order of the created batch, so even if the create batch module is trusted (no censorship) this does not imply that the sequencer is censorship resistant.
To address those issues, a popular approach is to decentralise the sequencer. The idea is to use a Byzantine Fault-Tolerant (BFT) consensus protocol, Figure 2, to agree on i) the transactions to be processed in a batch, and ii) the ordering of the transactions in the batch. There are several solid projects e.g., Espresso, Astria, that develop decentralised versions of the sequencer.
Figure 2: A decentralised sequencer architecture.
The expectation is that the decentralised sequencer fairly orders the transactions and proposes the ordered list to the L2 to execute them. In this context, a common and strong assumption is that the L2 is going to execute the transactions in the order given by the decentralised sequencer, thus will not tamper with the ordering.
The decentralised sequencer is claimed to be censorship resistant under another assumption: enough honest participants are present in the consensus protocol – usually 2/3. In this case, a transaction can eventually make it into a batch, as it will be picked up by an honest party. Note that it is not guaranteed that a transaction will make it, as participants may (agree to) use specific ordering policies to order transactions.
The addition of so-called order-fairness to consensus protocols was proposed in Order-Fairness for Byzantine Consensus. The presentation by M. Kelkar of this paper at CRYPTO is a great overview of the topic. In a nutshell, order-fairness is an agreement by a majority of participants that some transaction
All of the above approaches use a BFT consensus protocol and:
We may also argue that any consensus mechanism to build a batch is necessarily unfair and not MEV attacks resistant as the participants follow protocol specific fairness criteria that may not be reflected and considered fair in other protocols.
It follows that decentralising the sequencer using a consensus protocol does not necessarily solve the problem of censorship, and certainly does not eliminate MEV attacks. Note that rotating a set of sequencers (potential solution mentioned by OPtimism) rotates centralisation and is subject to the same censorship and MEV attacks issues.
A shared sequencer is a decentralised sequencer that can be used by multiple chains, and has the same weakness as a decentralised sequencer.
We refer to the Systematisation of Knowledge paper SoK: Decentralized Sequencers for Rollups by Shashank Motepalli, Luciano Freitas and Benjamin Livshits for a comprehensive analysis of the main concepts and desired properties of decentralised sequencers.
Fair sequencing has already received some attention in the past. Some prominent Web3 actors like ChainLink may be credited to have introduced the concept of a fair sequencing service. This approach has been refined into PROF (protected order flow) to integrate with profit-seeking MEV strategies, targeting L1 proposer-builder-separation (PBS) architecture.
The PROF proposal relies on a consensus protocol (decentralisation) and allows for customising the notion of fairness. It is unclear how it provides censorship resistance and the PROF article reads: "PROF supports a policy for ordering transactions that doesn’t involve intentional extraction of MEV." where intentional may need to be defined more precisely.
With this ambiguity on the implications of a decentralised sequencer, what is the true motivation for the decentralization of the sequencer. What problems does it solve? And does it solve the right problems?
It is common to refer to fairness as unpredictable (and unbiased) and hence hard to manipulate. A fair coin is probably the simplest example of fairness: when flipped, it should yield heads or tails and both events should have 50% chance of occurrence.
We argue that the problem to solve in sequencing (and batch-building) is not necessarily related to decentralisation. The problems to solve are censorship resistance and fairness which includes MEV attacks resistance.
We propose a solution that separates these issues and is based on verifiable random functions (VRFs) and zero-knowledge (ZK) proofs that has three essential properties and is provably fair:
A consequence of (1) is that this solution is effectively censorship resistant. A consequence of (2) is that it eliminates MEV attacks as the order of transactions is random and by definition unpredictable. In fact building a batch is a provably fair random process. Given a set of transactions, the distribution of the ordering of a set of transactions is uniform. (3) ensures that the executor cannot tamper with the order. Overall, we have an end-to-end secure process to ensure and verify fairness.
In the rest of this article, we first introduce our architecture and its properties in a simple setting. We then discuss security and how to design a (Byzantine) fault-tolerant version of the architecture, and some possible extensions.
Finally, we address the problem of spamming the mempool with transactions and propose some solutions.
The lifecycle of a transaction starts with a user who submits a transaction to a (centralised) mempool (Figure 3). If the transaction successfully reaches the mempool, the user is notified with a receipt that contains the batch number
Figure 3: Submission phase – Pool Manager
The pool manager builds the batches (and starts a new batch when the previous one is full), schedules batches in the order they are constructed and publishes the batches (e.g. Merkle tree hash) to the DA layer (Figure 3). As a result, a user can verify that the promise to be included in batch
Given a batch
Figure 4: Random ordering phase – Fair Sequencer
The batch to execute is
Because the permutation is provably random, the ordering is fair.
At the end of the pipeline the executor processes the batch
Figure 5: Executing phase – Executor
The actors have distinct tasks and are separtely accountable for each of them, which makes our design highly modular. Publishing the results of each task to the DA layer enables us to identify malicious actors and slash them if they misbehave, thus ensuring attributability (identify who to blame in case of a misbehaviour).
Note also that fair sequencing with dVRF as proposed above differs from threshold encryption protocols where transactions in the mempool are encrypted. In the threshhold encryption scheme, users can collude with the sequencer by communicating the encryption of their transaction. In our setting, the choice of ordering is random and does not depend on the content of transactions or their encryption.
In our design, cryptoeconomic security is ensured via a staking mechanism. The operators (mempool manager, sequencer, executor) must stake some assets. If an actor is caught misbehaving, the staked assets are slashed and additional social measures (temporary ban, etc) can be agreed upon.
As an example, re-staking protocols like EigenLayer enable other protocols to leverage Ethereum’s security at low cost.
In our design we have left open the choice of the DA layer. Settlement can happen at layer 1 as the DA layer, or for example use Celestia's DA layer or Eigen Layer's EigenDA layer.
In the simplest settings, we can have a single mempool manager, sequencer and executor. This implementation makes every module a single-point-of-failure.
This can be addressed by a simple fault-tolerant mechanism, detecting when a component is not operating properly or with delays and replacing it with a back up component.
The mempool manager can be decentralised by operating multiple nodes to which users can submit their transactions. Reliable broadcast protocols can be employed that provide guarantees on message receival to a distributed mempool and provide a high degree of security and, moreover, byzantine fault-tolerance (BFT). This increases the chances of a transaction getting in the mempool.
Both the sequencer and the executor have effectively no influence on the batch content and transaction order. Thus, there is a lack of motives to decentralise these components. However, for the sequencer a VRF acts as input, which can be decentralised as is discussed in the following.
Verifiable Random Functions (VRF) can be provided by oracles. Currently Chainlink and Supra propose VRF as a service. In our proposed design, both oracles can be used. As per the documentation the Chainlink VRF service seems to be centralised and a single-point-of-failure, which may be an issue.
However, decentralised byzantine-fault-tolerant VRFs are well understood and are provided by e.g. drand or Supra dVRF. Employing such solutions significantly increases the level of reliability of this service. Another feature of Supra dVRF is that the output (random value) can be made private, communicated and known only to the recipient. We can leverage this feature by querying the dVRF oracle in advance, as soon as a batch is full in the mempool, hereby reducing the delay between the extraction and the computation of the permutation.
Note that the decentralisation of the VRF means that the secret key used to generate random numbers is shared among a set of partcipants, and increases the reliability of the availability of the service. It is different to decentralising the sequencer.
The objective of fair sequencing is to protect users against front and back-running attacks. However, if need be, our approach can accomodate some (hopefully "good", arbitrage?) MEV strategies. This is just a matter of granularity. Instead of submitting unique transactions, we can allow users (or block builders) to submit bundles (ordered sequences of transactions) and treat a bundle as a unique transaction in the permutations.
More generally, it is possible to make sure that the randomly ordered list of transactions is a total order extension of some independent partial orders (e.g. timestamps on different nodes).
Ideally, users would have the choice to submit their transactions in a bundle via an intermediary (e.g. DeFi dApp) or to submit directly and privately to the mempool. Note that because different bundles are still randomly ordered, users who opt-in for direct submission are (probabilisticly) protected from front-back running. Moreover, independent bundles are shuffled in a non predictable manner making multi-block MEV attacks (securing consecutive blocks) very unlikely to succeed.
The architecture we propose is fair in the sense that the ordering of transactions is random. However, malicous actors could try to spam the mempool with identical transactions to try and increase their chances of front running some transactions.
To tackle the issue of spamming, priority fees can be introduced. Firstly, to disincentive excessive spamming and protect the mempool a base fee is applied. Nevertheless, this leaves the concern that a user may still spam transactions to gain an improvement in their position and front-run a competing transaction. This may be the case, if the expected gain is higher than the accumulation of the fees. Consequently a base fee alone does not provide a remedy.
A more flexible approach is to allow for a user adjustable priority fee, and where the fee size should impact the probabilistic position distribution in a fair manner. As a result, it becomes equally expensive to issue a single transaction with a high priority fee, compared to multiple with low fees. Furthermore, and similar to the approach described by Offchain Labs, the priority fee should be considered per gas, rather than the absolute fee value, to disincentivise the bundling of unrelated transactions.
With the above modifications, the risk (or at least the motivation) for spam has been reduced substantially. The approach also provides the means for users to select a suitable ratio for the priority-fee against the expected return, to probabilistically protect the successful execution of their transaction. And consequently make it prohibitively expensive to be front-run.
What this achieves, in essence, is a provably-fair all-pay auction. A significant advantage of all-pay auctions is that payment is internal to the system and, therefore, value can be captured and utilized within the protocol to, for example, subsidize protocol operation costs, rather than the value being lost to external factors, such as latency infrastructure.
The approach can be enhanced by sealed-bidding and encryption of transactions to reduce latency races, see e.g. TimeBoost (Offchain Labs) or Sharma et al. However, these mechanisms may be less required in our setting. Consider an arbitrage price - in a first-price all-pay auction only the highest bid can win and thus actors may issue their transaction as late as possible to only issue the highest bid. Ultimately this incentivises investiments into latency races. In contrast in our setting, fees of the same actor for the same price would accumulate, thus increasing the likelihood to capture investments in priority fees instead.
We have a proposed a design for a sequencer that provides censorship resistance (cryptoeconomics security) and fairness (provably random ordering). Our proposal is light-weight in the sense that it does not rely on a consensus layer. It is modular and the three main modules, pool manager, sequencer and executor can be further refined to integrate some fault-tolerance mechanisms.
It is worth noting that we achieve censorship and fairness resistance with a combination of first-come-first-serve (FCFS) policy and random ordering. FCFS allows us to fill in the batches, and each batch is randomly ordered. This prevents transactions from being indefinitely delayed or delayed by an unbounded (finite bnut arbitrary large) amount of time.
What is not covered in this article is the details of the crypto-economics strategy and the rewards and incentives for the participants (mempool manager, sequencer, executor).
Decentralising using a BFT algorithm provides a way of reaching a consensus. It does not protect against censorship. Censorship resistance is a function of the diversity of the participants in the consensus protocol.
We argue that the censorship resiliance can be handled by a different approach than decentralising the sequencer.
The general approach taken is as follows.
The first point can be addressed in several ways.
We can require the sequencer to provide a timestamped signed receipt of the transaction, which would make the sequencer accountable for timely processing.
The sequencer may be seperated from the user through a network of other nodes. For example, this may be to protect the sequencer from spam through a group of load balancing nodes. In a network setting, broadcast protocols become relevant, which provide guarantees that a transaction is submitted and received by all nodes or none (including self), even in the presence of faults (or byzantine actors).
Broadcast mechanisms can provide partial ordering, without imposing atomic broadcast. Examples are Reliable, FIFO, or Causal Broadcast, see this lecture. The properties that Reliable Broadcast holds (and that we are interest in), are
Several relevant broadcast protocols have been proposed, which provide guarantees on delivery, in the presence of byzantine actors, see Das et al. This opens the opportunity for a trustless network of transmitting nodes to the sequencer. In a (partially) synchronous setting this can provide guarantees on when transactions should be received by the pool manager or sequencer and does not necessarily require trusted receipt issuance.
While this introduces decentralization, the utilised protocols can be substantially more simple and performant than comparable BFT consensus engines required for the decentralization of the sequencer.
We assume the following scenario. In order to frontrun a transaction an adversary must obtain a position in the block that is higher than the transaction that she wants to frontrun. Since the order is random, the adversary cannot guarantee the allocated slot in the block but increase the probability to suceed by issuing multiple, effectively identical transactions.
This raises the following concerns.
(1.) An honest user that issues a single transaction can be easily frontrun, while potentially having to bear the full cost of their transaction. This can be in contrast to models, where users get refunded part of their fees. (2.) An adversary is incentivised to spam transactions, which lowers the available free bandwidth, degradate the network performance and in the worst case can bring down the sequencer node. (3.) Depending on the policy, bundling of independent transactions could increase the chance to have a higher probability to obtain a higher position. (4.) Users could be motivated to submit their txs as late as possible towards the closing of a batch, to gather additional information about competing txs.
However.
In regards to (1.), in the case of a first-price auction, a well informed adversary may have certainty to win an auction (e.g. better information on bet distribution). While in contrast in our model the outcome is still down to chances. For example, given two bidders with almost identical value, in an auction model only the highest bidder can win, while in a fair model the chances would still remain almost equal. This can be achieved in our model.
In regards to (2.), the incentive for spaming is reduced through a) employ an all-pay policy, which makes spamming costly. And b) modifiable priority fees, and account in the randomisation for the fee. More particularly, choosing the probability to being selected linear to the invested fee, would result in a probabilistically fair ordering. This removes incentives to spam identical transactions, as a single tx with a high fee would have the same probability to be selected, as if the fee would be distributed between many txs.
In regards to (3.), one can apply priority fee per gas, see e.g. here. This would counter the bundling of unrelated txs, as an individual tx has the same probability to obtain a certain position, as a bundle that would combine several of these independent txs.
In regards to (4.), one may address this by sealed-bid auctions.
Assume a user
Ignoring size of transactions (batches), influence of fees, gas, etc.,
where
The expected return on such a game is
Naturally
The figure below illustrates the winning chance for
The figure can be reproduced, visting the code here.
As seen, it may be advantageous for a user or adversary to spam transactions, which would consume valuable networking resources.
One option to disincentivise such behaviour is to introduce
A simple model is the following. Let
This has the following impacts: