Low Latency Rollup Design Proposal

Motivation

• The default latency (2 Tezos blocks) makes DApps feel clunky and limits the kind of applications people can write.

Approaches

• Keep lowering block times. The Mumbai proposal for 15s will help a lot
  • But 15s is still a long time, and severly limits what can put on-chain.
  • 1s response times seem to be the upper bound, after which users will report an app feels slow.
• Instant finality via bonded baker receipts.
  • See this thread in Slack
  • This is great, but there is still the limit of one manager operation per block
    • Batching could be used to get around the this limit, but this places a larger burden on DApp developers
• Speculative execution of transactions
  • There is some prior art on this in the Speculatra framework
    • However, this places extra burdens on DApp developers: they must be careful to program their DApps in a way ammenable to specualtive execution, and run the infrastructure required for it (i.e a specialized Tezos node and/or a specialized rollup node)
• Use an off-chain sequencer.
  • Prior art in Arbitrum and Optimism

Proposal

We propose:

• building an off-chain sequencer
• Writing a Rust library for using this sequencer in kernel development
• Integrating this sequencer into the EVM rollup kernel currently in development.

Intuition

The basic idea is to have an authority, or comittee of authorities, known as the sequencer that batches user transactions faster than the rate of Tezos blocks. The sequencer submits this batch to a DAC, and then submits all the transactions that occured for a given Tezos level as a single preimage reveal.

With some specializations to the rollup kernel described below, the sequencer gains sufficient control over the transaction order so as to be able to guarantee the order of message processing to users with minimal latency.

To fill out this design, we'll describe it in phases that move from less to more decentralization.

Phase 1: Fully Centralized Sequencer, no censorship resistance

Let us coin a distinction between kernel state - the rollup state which the kernel can directly modify during the course of execution - and full state, which includes everything (such as the current tick number).

Note, I assume the sequencer is running a rollup node and playing refutation games, or else someone is doing so on the sequencer's behalf. The sequencer can always choose to quit or stop answering queries from users, which will have the same effect in either case.

In phase 1, we want to give the sequencer full control over the order in which messages are processed. The sequencer maintains a monotonic counter corresponding to the the number of messages processed. Users post messages to the sequencer, and if they are well formed, recieve back a signature from the sequencer certifying the data received and the level at which that message will be processed.

Sequencer-compatible kernels are implemented in the following way:

• They keep track of the current message level in their kernel state
• Every message processed by the input handler is a no-op unless:
  • It has the form: <signature><counter><message>
  • The signature is a valid signature from the sequencer for the messsage <counter><message>
  • The <counter> is equal to the kernels internal counter

After executing a message, the rollup kernel increments its counter. This ensures that, at least w.r.t to kernel state, the sequencer has full control over message order.

To finalize the state of the rollup for a given block level on the L1, the sequencer rollup node bundles all its intra-block transactions into a Merkle tree of DAC reveal input messages and the post the root on the L1 shared inbox. Once a block is finalized, the sequencer rollup node can determine the finalized full state and post a state commitment to the L1. The sequencer rollup node can also publish Merkle proofs linking the kernel state with the full state that was comitted on the L1 [^1].

Note this model includes the power to censor or re-order any transaction. This opens up an attack where a malicious or compromised sequencer could simply halt the rollup until users signed over some signicant portion of the funds.

Nonetheless, this model achieves very low latency - assuming, the rollup node and the sequencer are colocated, users could submit a transaction and get a receipt of inclusion and the resulting state in a single round trip. The receipt would act as finality on the inclusion of the tx (since nothing precludes the user from submitting the transaction). The finality of the returned state would have the usual rollup guarantees.

Footnote 1: I still need to do some thinking to make sure that thte sequencer distributing a proof linking the kernel state to the full state commitment on the L1 is sufficient in every case for users to verify the intermediate results returned to them by the sequencer.

Phase 2: Fully Centralized Sequencer + L1 transactions

We can do much better than Phase 1 by allowing users to include operations in the rollup via the L1 without the signature of the sequencer. This can be done by providing some deterministic method of including L1 transactions in the sequence of transactions processed by the kernel.

As an example of such a rule, suppose that the sequencer modifies his counter to be relative to some Tezos block level. For each Tezos block level, the sequencer must commit to one and only one sequence of txs to be executed for that level. Additionally, the kernel maintains a queue of transactions submitted to the L1 independently of the sequencer, where, txs submitted to the shared inbox at a given Tezos level are processed by the kernel on the following level.

In this model, the sequencer's ability to order transactions is partially limited. Within a given Tezos block, the sequencer can choose to the order transactions submitted directly to itself, including omitting all of them, but cannot omit sufficiently old txs submitted through the L1, else his state commitments will be rejected in a refutation game.

Note: I don't know of any rollups in production that have all three of 1. a working refutation system, 2. a sequencer, 3. a fallback if the sequencer fails. Thus it seems that just implementing Phase 2 would bring us to the state of the art.

Phase 3: Sequencing Comittee with Rotating Leaders

The robustness of Phase 2 can be improved by adding multiple sequencers, with the leader chosen round-robin based on the Tezos block level.

We could additionally require a quorum of signatures. By requiring 2f+1 signatures, I think there are additional guarantees we could provide - e.g. a faulty leader could not convince a quorum of two different orderings. But I'm also not confident of this statement, nor am I convinced it would be valuable to implement if true.

Phase 4?: More decentralized sequencing?

A valuable decentralization measure to implement would be a sanctioning system whereby a committee of stakeholders could remove sequencers from play in case of bad behavior.

There are other schemes for increasing the decentralization, but they mostly focus on improving MEV-resistance, which gets murky quickly.

I believe Arbitrum has a design for multiple decentralized sequencers, where conflicting orderings are resolved via a Condorcet ranking.

There is also an interesting proposal for a Frequent Batch Auction-sytle First Come First Serve sequencing. There is also the Themis protocol, from which this proposal draws.

I personally need to do more research to have strong opinions on how to advance beyond Phase 3. However, we can go very long way to improve user experience and adoption before worrying about MEV, and there are also mitigations possible at the application level.

Implementation

No L1 protocol changes are needed.

Using the above phases, we can create milestones for the implemenation:

Milestone 1: Fully Centralized Sequencer, no censorship resistance

The first milestone is to implement:

• A sequencer node that runs

To achieve what's described in Phase 1, we'll need the following:

• A sequencer that accepts users transactions and returns signatures determining the message sequence
• A "low latency rollup node" that receives messages signed by the sequencer and executes them immediatley in order. Perhaps running locally with the sequencer, or even in the same process. Can be queried for the state intra-block.
• The low latency rollup node will also need to bundle up transactions in a Merkle tree and post them to the DAC.
• The sequencer will need to submit the a shared inbox message witnessing root of this Merkle tree so it can be revealed by the kernel.
• The kernel (Arith, EVM, whatever) will need to be modified to respsect the sequencer's ordering.

Milestone 2: Fully Centralized Sequencer + L1 Transactions

TODO: discuss the steps needed to implement this

Milestone 2: Fully Centralized Sequencer + L1 transactions

TODO: discuss the steps needed to implement this

Milestone 3: Fully Centralized Sequencer, no censorship resistance

TODO: discuss the steps needed to implement this

Milestone 3: Sequencing Comittee with Rotating Leaders

TODO: discuss the steps needed to implement this