# 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](https://stackoverflow.com/a/4210173/7895330), after which users will report an app feels slow.
- Instant finality via bonded baker receipts.
- See [this thread in Slack](https://tezos-dev.slack.com/archives/GB0UR34N8/p1670882620423149)
- 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](https://www.gsd.inesc-id.pt/~jpbarreto/data/uploads/thesis/leonor_loureiro_dissertacao.pdf)
- 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](https://developer.arbitrum.io/sequencer) and [Optimism](https://community.optimism.io/docs/protocol/2-rollup-protocol/#block-production)

## 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](https://en.wikipedia.org/wiki/Condorcet_method#Condorcet_ranking_methods).

There is also an interesting proposal for a [Frequent Batch Auction-sytle First Come First Serve](https://research.arbitrum.io/t/transaction-ordering-policy/127/2) sequencing. There is also the [Themis protocol](https://eprint.iacr.org/2021/1465.pdf), 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