Forward Based Sequencing

by mteam building based at Spire Labs

Much thanks to Ladislaus, George Spasov, Drew, JJ Alicea, Noah Pravecek, Murat
.
tl;dr: To understand how multiple sequencers can work together while one still has monopoly sequencing powers, we use forward inclusion list research. We propose a based rollup design "Forward Based Sequencing" that enables traditional shared sequencers to force-include transactions in a future rollup block. This design can be extended to improve the CR of based rollups independently of Ethereum itself.
.

Terminology and assumptions:

• The term "sequencing" is used to refer to the ordering of transactions on a domain.
• The term "shared sequencer (ShSq)" is used to refer to traditional non-based shared sequencers. Explicitly, where a single party exclusively sequences (orders) transactions for multiple rollups.
• The term "based sequencing" is used to refer to something similar to Vanilla Based Sequencing, explicitly a system where the next opted-in L1 Proposer in the lookahead has monopoly sequencing rights for a rollup and monopoly sequencing rights for their own block.
• The term "based preconfirmations (preconfs)" is used to refer to a type of proposer commitment where an elected based sequencer makes cryptographicly enforceable "preconf commitments" about the sequencing that they will do in the future. We take a special interest in multi-block preconfs (preconfs that refer to a block in the future).
• We consider two types of preconfs: inclusion preconfs and execution preconfs. Inclusion preconf commitments are a commitment to include a specific L2 transaction hash before a specific L1 block. Execution preconf commitments are a commitment to executing an L2 transaction in a certain way (could be post state-root, post balance, etc.).
• We use the term "atomic inclusion" to refer to all-or-nothing inclusion guarantees across multiple chains. For this article, we assume inclusion always leads to finality. Atomic inclusion is half of synchronous composability (the rest is atomic execution and atomic withdrawals).

Shared Sequencing + Based Sequencing

In this section, we explain the unique benefits of based sequencing and shared sequencing. We start from first principles and attempt to derive why based sequencing and shared sequencing are individually valuable, and then examine some ways to get both.

Shared sequencing enables atomic inclusion across opted-in rollups.

Based sequencing enables atomic inclusion across based rollups and the Ethereum L1.

For a single block, naive implementations of based sequencing and shared sequencing are simultaneously incompatible. This is because based sequencing (with preconfs) requires monopoly sequencing rights over the domain they sequence for their block. Put simply, the L1 Proposer cannot "share" their sequencing powers.

Note that based rollups without based preconfs do not suffer from this incompatibility (a rollup could become semi-based and allocate some of its blockspace to based sequencing and shared sequencing).

To understand how we can get based preconfs and shared sequencing, let's examine the different types of sequencing powers that a rollup can give to sequencers:

• permanent monopoly sequencing: Give a single sequencer a complete monopoly over sequencing. aka a centralized sequencer, adopted by most rollups today (Optimism, Arbitrum, etc.).
• temporary monopoly sequencing: Give a single sequencer a complete monopoly over sequencing for a certain, limited amount of time. This is the design used by Taiko and Vanilla Based Sequencing.
• permanent partial sequencing: Give a single sequencer permanent power to sequence a part (any part) of every rollup block. The rest of the block can be sequenced in some other way (a permanent or temporary sequencer).
• temporary partial sequencing: Give a single sequencer temporary power to sequence a part of a limited number of rollup blocks. The rest of the block can be sequenced in some other way.

Next, let's examine which of these are required for based sequencing/preconfs and shared sequencing:

• Based Sequencing: Based sequencing can work with any sequencing power.
• Shared Sequencing: Shared sequencing can work with any sequencing power.
• Based Preconfs: Require permanent or temporary monopoly sequencing: to provide an execution preconf, a sequencer must be able to guarantee a sequence of all transactions until the execution occurs.

Let's talk through a few models of working around these requirements (or simply accepting them) that one might consider:

Blockspace futures/derivatives

Because shared sequencing can work with partial sequencing powers, an L1 Proposer could give some of their L1 blockspace to a ShSq. In such a model, the L1 Proposer must put up some collateral to guarantee that they will actually allocate blockspace to a ShSq.

Side note: Is this even based sequencing? I don't think so.

Pros:

• Cross-chain atomic inclusion is achieved for the ShSq.

Cons:

• Requires significant changes to the L1 block pipeline.
• Requires proposer collateral.
• Atomic inclusion is not enforced by the protocol (Proposer could renege).

Rollup Partial Blocks (multi-sequencing)

Every rollup block includes two+ sub-blocks. (Or a rollup has two+ blocks proposed at once, logically these are the same.) Assume that there is some mechanism to resolve problems like a transaction appearing in both blocks.

Pros:

• Cross-chain atomic inclusion is achieved for the ShSq.
• L1 Proposer maintains agency over sequencing L1.

Cons:

• Fundamentally incompatible with execution preconfs (unless ShSq is collateralized and communication occurs during sequencing - both heavy requirements).
• Incentives between L1 sequencers and ShSqs are not aligned.
• Subject to censorship attacks from L1 Proposers. An elected L1 Proposer may refuse to include a partial block proposal from a ShSq in order to increase block reward.

Sequencer Election

Choose to use ShSqs or based sequencing for a given rollup slot. This can be done using Execution Tickets/Auctions. Can use a lookahead, external fast finality gadgets etc. Espresso has introduced the idea of the Right of First Refusal (ROFR) to give the L1 Proposer first access to a based rollup.

Pros:

• Adding MEV retention for rollups is relatively simple.
• L1 Proposer and a ShSq maintain complete agency.
• The most valuable interop will consistently be chosen.

Cons:

• Composability is not simultaneous with L1 and other shared sequenced networks for a given rollup block. One or the other.
• The interop that is usually most valuable will become incumbent. This is because designs like Execution Tickets are based on the expected value (EV) of sequencing, and not live value. If preconf compatibility is sacrificed, a lookahead can be removed to get more accurate bids.

Inclusion Lists and Influencing Sequencing

After examining a few of the ways to get interop between traditional rollups, based rollups, and the Ethereum L1 we realize a few things.

In any system where multiple different entities can influence sequencing simultaneously, preconfs must be coordinated between both. This adds complexity and is incompatible (afaict) with many traditional shared sequencer designs.

Background on Ethereum L1

Interestingly, this same problem has been explored on Ethereum L1 with a focus on Censorship Resistance. The concept of Inclusion Lists (ILs) has been introduced to enable L1 Proposers to influence the sequencing of L1 blocks built by mev-boost builders.

Simply put, ILs are lists of transactions that must be included in/before a certain L1 block[s].

Over time, the research around ILs has evolved to become more robust.

from: my post here

A few important takeaways that we apply later:

Forward Inclusion Lists > Spot Inclusion Lists

Forward Inclusion Lists are created by the L1 Proposer at slot n and applied to the block at slot n+x.

… Forward inclusion lists increase censorship resistance (CR) of the chain, whereas spot inclusion lists do not.

The argument is as follows. Spot ILs are made by honest proposers, but they do not increase censorship-resistance since honest proposers do not connect to censoring builders anyways. Greedy proposers do not make a spot IL, since this would “turn off” the censoring builders they connect to. Censoring proposers also do not make a spot IL for themselves, so the amount of censorship remains the same as without spot ILs.

On the other hand, greedy proposers do not make a spot IL for themselves, but make a forward IL for others. This list may apply to honest proposers, for whom the list is “redundant”: Honest proposers were not connecting to censoring builders anyways. The increase in CR comes from honest or greedy proposers making a list for other greedy proposers. These proposers subjected to the list, while connected to all builders, can no longer receive bids from censoring builders, and thus CR is increased.

– Fun and games with inclusion lists - Barnabé Monnot

from: my post here

Cumulative Non-Expiring Inclusion Lists > Forward Inclusion Lists

Cumulative Non-Expiring Inclusion Lists are a type of Forward Inclusion Lists.

As a recap. Having proposers set ILs for their own blocks doesn’t make much sense and it relies purely on altruism to include censored transactions into one’s own blocks.

Having forward-ILs makes sense, allowing the current proposer to constrain the next proposer. This means that the current proposer could create an IL that either the current proposer itself or the next proposer must satisfy.

The problem with one-slot-forward ILs is that parties with multiple validators have an economic incentive to not constrain the next proposer in the case the next proposer is controlled by the same entity.
– Cumulative, Non-Expiring Inclusion Lists - Toni Wahrstätter

The solution? Inclusion lists apply to many blocks to make the chances of an incentive misalignment very low.

Summary (so far)

ILs on Ethereum can be used to enable a L1 Proposer to influence the sequencing of transactions in future L1 blocks. This concept (influencing future sequencing instead of current sequencing) can be applied to based sequencing

Forward Based Sequencing

Now it's time to apply what we've explored into a solution:

Construction

• Designate one or more forward sequencers for a given slot.
• Every designated forward sequencer may submit a Forward Set (unordered/ordered list of transactions) to the L1 rollup contract.
• d (for delay) blocks after being submitted, all transactions in a Forward Set are immediately added to the Inclusion Set. The Inclusion Set is somewhat similar to a "delayed inbox" in rollups like Arbitrum.
• At every rollup block, all transactions in the Inclusion Set (that were not previously included) must be included in order for the rollup block to be valid. (forced inclusion)

Considerations

• This system enables forward sequencers (who may be shared sequencers) to force include transactions in a rollup. This unlocks atomic inclusion for forward sequencers, which is enough for some types of composability.
• If a forward sequencer would like execution guarantees (not just the inclusion guarantees they receive from submitting a Forward Set) they might get execution preconfs from the relevant proposers. This enables other forms of composability, albeit somewhat optimistically.
• L1 proposers can provide inclusion/execution preconfs for up to d slots in advance.
• Forward sequencers become first class citizens in based rollups, enabling them to become more powerful than just users of a normal escape hatch. Forward Sets can be submitted in gas optimized ways (compression, external DA, and more) to make forward sequencing even cheaper and more practical for large volume.
• ShSqs always have the option of using regular based preconfs from relevant based sequencers in order to facilitate interop, forward sequencing is much more valuable when coordination with the based sequencer is to be avoided (maybe censorship, pricing problems, liveness issues).
• Censorship Resistance: One serious consideration of based sequencing today is that, although using Ethereum for sequencing sounds great, PBS really isn't all that amazing. A majority of Ethereum blocks are censoring, and Ethereum does not yet support things like ILs that will minimize these effects.
• What should d be? There is something to be said for d = 1. This design gives us the best CR and also makes execution preconfs easier to get (fewer preconfers to talk to). The downside of a low d is that execution preconfs over multiple blocks are no longer possible, which is most likely an acceptable tradeoff but this is an open question.

Pros:

• Compatible with based preconfs and based sequencing
• Enable interop between L1 and all types of rollups
• L1 Proposer maintains present agency
• Easy to add MEV capture for forward sequencer designation

Cons:

• If a single sequencer sequences d blocks in a row, they are incentivized to attempt to censor Forward Set inclusion, same as ILs on Ethereum.
• If using preconfs, proposers must put up some collateral. Forward based sequencing without preconfs does not itself require proposer collateral.

Conclusion

While progress is going well on based preconfs, I feel that the underlying based rollup technology is somewhat ignored by the research. A reminder: based preconfs run on based rollups.

A special note on MEV capturing based rollups

MEV is an essential consideration of any sequencing architecture.

One design goal of a sequencing system is to capture MEV for the blockchain that is being sequenced. With based sequencing, this consideration is very underexplored.

First of all, popular MEV capture designs at the sequencer level today (execution tickets/auctions) attempt to capture MEV with sequencer election mechanisms. With based rollups, sequencer election is limited by the L1 lookahead, but wrappers around a simple sequencer election (with something like execution tickets) are possible. The most important thing to consider when deciding on a sequencer election mechanism is composability with other based rollups (based rollups are only composable between each other if they share an elected sequencer). This means sequencer election mechanisms are path-dependent on how based rollups launch and GTM.

Forward Based Sequencing enables two ways to capture MEV through sequencer election:

• modifying based sequencer election: risks losing composability with other based rollups, captures most MEV, and maybe L1 interop fees too.
• modify forward sequencer election: no risk of losing composability, captures some MEV and L2 interop fees.

---

references and resources
TODO