# Shared Sequencer Protocol

## Introduction

### Purpose

This document specifies a minimal shared sequencer protocol that aggregates and orders transactions across multiple rollups and collectively publishes them on Celestia. It is meant as a standalone document that aims to cover the necessity of a shared sequencer, how it functions the tradeoffs made in its design, and future work and optimizing its purpose.

### Scope

This document aims to include sufficient information to implement a minimal working version of the shared sequencer network for someone familiar with the Cosmos SDK and Celestia. Further developments are listed under `Future Work`.

## Background

### Modular Thesis

The modular thesis is spun out from Etheteum's attempt at solving the issue of scalability of web3 applications. Chiefly, it constitutes the rise of proof-based execution systems. These are then divided into smaller systems (rollups) by their domain and run by one or more nodes (called sequencers). The proofs from executing the rollup transactions are then "rolled up" to a highly economically secured chain like Ethereum, which acts as a central hub for validating the state of multiple rollups.

Ethereum was and continues to act as the point for publishing the data, which was needed to prevent that same sequencer from equivocating, generating a fork, and profiting from the difference. This was known as the data availability problem. The modular thesis came about as a claim that breaking down a single "monolithic" system into multiple purpose-built systems specializing in a single task would be more successful for scaling.

Celestia was launched as a system specialized in publishing large amounts of transactions. It included a novel way light nodes could verify the entire set of published transactions: data availability sampling.

Continuing along the lines of modularity, the role of the sequencer has started to become deconstructed. The sequencer previously was the machine that received signed transactions from its users, published them on the DA layer, executed the transactions, and then published the commitment of the state and the proofs themselves.

Within this, the task of receiving, batching, and submitting transactions is distinct from executing those transactions, generating a commitment to state along with the proofs, and submitting that data to the DA layer. The former doesn't require knowledge of the current state of that rollup and thus could easily scale across several domains. The latter is state-machine specific, but this is beginning to be abstracted into prover networks. Networks that pay for transactions to be executed and the relevant proofs to be generated.

The former is the basis of the shared sequencer specified in this document.

### Categorisation of Shared Sequencers

There are a few ways that a rollup may want to use a shared sequencer:

- Exclusive Sequencing: Only blobs submitted by the sequencer are valid. All other blobs published in a namespace are automatically deemed invalid and skipped over. With exclusive sequencing, the moment the share sequencer confirms the ordering of a set, execution nodes can already execute those transactions, knowing that the order can't possibly change. At a later point, when the DA confirms those transactions, the executions have a stronger commitment that there was no equivocation. The cost of the execution speed-up is that now the rollup inherits the censorship resistance and liveness of the shared sequencer. If the sequencer censors a transaction, there is no other way that that transaction can be processed by the execution node and enter into the state of the rollup.
- Permissionless Sequencing: As the polar opposite, permissionless sequencing means all transactions submitted to the namespace must be executed (and, if invalid, are skipped). Shared sequencers merely batch transactions for economic gain. If a permissionless sequencer is prominent, the execution node can optimistically execute transactions but may need to rebase if the DA layer publishes other blobs. This has the strength that users can still fall back if they are being censored. There are other more complex constructions where the guarantee of the shared sequencer holds stronger. The downside is that the user has to wait a little longer for the inclusion of their transaction in the rollup block.

## Protocol Architecture

### Objectives

The following are a set of characteristics that define the quality of a shared sequencer:

- Confirmation speed: how quickly the network agrees on a set of transactions and how quickly the DA layer finalizes them.
- Censorship resistance: how difficult is it for an actor to censor a user's transactions.
- Data Cost: how cheap is it to publish data.
- Usability: how easy is it to build with.

### Data Flow

The shared sequencer can be described as a standard Cosmos SDK chain using CometBFT with modifications to the commitment scheme of the data and the addition of a module for managing the actual submission of the agreed-upon blobs on Celestia or any other DA layer.


Above is a diagram of how the different networks interoperate. Note there is some flexibility in whether the execution node reads from the shared sequencer or only from the DA layer.


The shared sequencer can be viewed as an empheral system were data is published at a faster frequency than the DA and is eventually replaced by the data on the DA itself (in the same form). Only the payments and receipts need to be persisted.

### Block Construction

The shared sequencer reaches consensus over both a data and state root. The state root is derived from as the merkle root in a tree encompassing all sdk modules. The data root is derived from a special data structure that commits over the order and inclusion of the transactions themselves.

The properties of that data structure are the following:
- light clients can easily verify if the shared sequencer ordered a certain piece of data
- the data root appends new data, and you can verify the inclusion of any data at any given point in time
- The shared sequencer does not extend a guarantee of data being available beyond the underlying DA-Layer
- The shared sequencer should prune the data entry to be a pointer the moment the data is included in the DA-Layer
- light clients can easily verify if something was posted to a rollups namespace or not
- The commitment over one piece of data is the same on the SS Level as it is on the DA-Layer

The namespace range is 29 bytes large, mimicking Celestia's namespace size and its limits.
The commitment over data is using the same [Blob Share Commitment Rules](https://github.com/celestiaorg/celestia-app/blob/main/specs/src/specs/data_square_layout.md#blob-share-commitment-rules) as Celestia. The [ShareCommitment](https://github.com/celestiaorg/celestia-app/blob/defff08dee71949aec42dc4e75a2adf812396581/x/blob/README.md#generating-the-sharecommitment) over a data is calculated using [CreateCommitment](https://github.com/celestiaorg/go-square/blob/ef245e5e92aa52b1b1f2cbc60d86faedb167752c/inclusion/commitment.go#L19). The rationale of why the commitment has to be the same as the commitment in the DA-Layer for trust-minimized light client verification is outlined in Question 8 of the [Sequencing API Discussion](https://github.com/rollkit/rollkit/discussions/1208#discussioncomment-7102166).

The moment the same data, aka the same commitment, is present in the DA-Layer and the Shared Sequencer, the Shared Sequencer can prune the data and replace it with a pointer to the DA-Layer. This means that the inclusion on the DA-Layer has to be verified by the SS state machine, which has to happen for the payment anyway.

We assume the shared sequencer block time will define the rollups block time in the general case. This, of course, is not a must. A rollup can interpret the bytes however they want. With the original assumption, each rollup height will be at least one shared sequencer height. This only goes in one direction, as not every shared sequencer height will have rollup transactions for that height. Therefore, it should be easy to query for rollup height X in the shared sequencer. The other option is to query every shared sequencer height. Now, you have to differentiate if there is data to be read for your namespace without reading the full shared sequencer block.

Due to its nature, the data structure of how the data is saved can be heavily optimized. We should point out that a rollup full node will expect information on a continuous basis from the same part of the data structure. The next section will outline various options that can be used and should be chosen depending on the technical feasibility.

#### IAVL

This solution is the simplest to implement from a cosmos-sdk perspective, with various IAVL improvements already in the works. The key in the tree is a concatenation of namespace and rollup height. This way, a user can query the tree on each rollup height while still only caring about his namespace. The benefit of having the height be part of the key is that you can easily differentiate if a rollup height exists or not. It also has the benefit that relevant data is next to each other.

The value in the kv-store is the data's share commitment. You do not actually have to store the data, only the commitment, as the data will be available on the DA-Layer. The validators of the shared sequencer will be able to derive the commitment from the transactions submitted by the user.


You can derive the blob from the transaction bytes and the share commitment from the blob.


After the data is included in Celestia, the share commitment will be appended by the Celestia height when it was included. This way, every query to the data that is unique to the (namespace | rollup height) can be converted and proxied to Celestia with (namespace | share commitment | Celestia height ). The yellow share commitments are not inside Celestia yet. The green values were already proven inside Celestia.

To reduce latency, the shared sequencer might decide to keep a local copy of the data and serve it directly to the user. Another option is to run a Celestia full node or, in the future, a Celestia partial node.

### Blob Submission on Celestia

As the network is only capable of publishing the agreed-upon transactions, submitting them to the DA layer must be achieved through relayers. Like the IBC design, the relayers pull from the shared sequencer network, wrap the blobs into a PFB, calculate the necessary fees, and submit them to the DA layer. As there are likely to be multiple shared sequencer blocks to DA blocks, relayers can wait and batch all these blobs together just before the proposer begins to propose.

#### Handling redundancy

Relaying is permissionless. Multiple competing relayers can be used, and redundancy ensures that if one fails, others can submit the blobs. While this helps to ensure minimal delay between blobs being published by the sequencer and relayed to the DA layer, it also introduces the problem of duplicate submission.

This problem can be mitigated in the same way that IBC handles duplicate submissions. Nodes keep a cache of recent blob commitments and reject transactions with at least one blob that matches a blob already in the node's mempool. This check is done during `CheckTx`. Relayers can handle the error and then resubmit with the blobs the node does not currently have.

#### Rebates

There must be sufficient incentivization to encourage relayer participation. The shared sequencer includes an additional SDK module that allows the relayer to submit a message proving the publication of their PFB and corresponding blobs. These are known as receipts. This also informs the shared sequencer network of what has been published and can be pruned.

service Msg {
  rpc SubmitDAHeader(MsgSubmitDAHeader) returns (MsgSubmitDAHeaderResponse)

  rpc SubmitReceipt(MsgSubmitReceipt) returns (MsgSubmitReciptResponse)
}

message MsgSubmitDAHeader {
	cometbft.SignerHeader da_header = 1;
	cometbft.ValidatorSet da_validator_set = 2;
}

message MsgSubmitDAHeaderResponse {}


message MsgSubmitReceipt {
	sdk.Tx pay_for_blobs_tx = 1;
	celestia.NMTProofs proofs = 2;
	int64 da_header_height = 3;
}

message MsgSubmitReceiptResponse {}

The first message, `SubmitDAHeader`, verifies a tendermint header in the exact way that IBC does

> Note: Given the significant overlap in the header verification system to that of IBC, it is more optimal if this module piggybacks off the `IBCKeeper`. IBC relayers would submit the header and its proof; thus, Blob relayers would only need to submit the NMT proofs and the `MsgPayForBlobs`.

Validators would execute the second message by finding the corresponding DA `DataRoot` at the height specified. Then, they would use the `NMTProofs` to verify the inclusion of the shares that make up the PFB Transaction. Once the transaction has been proven to be included, they would unwrap the `MsgPayForBlobs`. They would loop through each blob commitment and check that it matched an unclaimed blob that was previously published by the shared sequencer network. It would then check the fee and rebate the signer based on the fee in the IBC-wrapped TIA token.

#### Spam prevention

The protocol enforces a cap on how much can be rebated to encourage the relayer to submit the blobs with the lowest gas price and not "waste" the accrued TIA in the network. This is set as a governance parameter: `max_rebate_gas_price`. The formula includes a small bonus compensation to the relayer proportional to the low fees. Thus, the revenue to the relayer from the shared sequencer is:

bonus = (max_rebate_gas_price - actual_gas_price)*relayer_bonus_percentage
revenue = min(max_rebate_gas_price, actual_gas_price + bonus) * estimated_gas

where

- `estimated_gas` is some deterministic number calculated from the PFB itself.
- `relayer_bonus_percentage` is a governance parameter between 0 and 1.
- `actual_gas_price` is calculated by dividing the fee amount by the gas limit.

The `max_rebate_gas_price` is additionally used as the minimum fee a user can submit their transaction. This ensures that no more funds are spent in rebates than accrued from processing the transaction.

#### Alternative patterns

One alternative to this design was to submit the blobs using a modified version of ICA. Using this approach, the Celestia validators themselves verify the signatures from the shared sequencer network, and thus, rollup users only need to check that the signer of the blobs in their namespace matches the address of the ICA account connected to the shared sequencer network.

### Value Flow


For simplicity we assume that the shared sequencer uses TIA as the gas token and does not have its own token. We assume that the rollups use there own token , although if they used TIA it would make the design and accounting even easier. I think that depends on what the customer wants but giving the option to use TIA as a the gas token would probably be a desired feature down the line.

To summarize the flow the user pays the executor gas to execute the transaction that they submitted. This transaction is wrapped in a shared sequencer transaction. The user signs again and pays in TIA which he has in a shared sequencer account. This is submitted to the shared squencer mempool. The shared sequencer batches are submitted by a relayer to Celestia which they have to pay in TIA.

They can rebate the TIA by provinding a proof of inclusion of the submitted data inside the Celestia block back to the shared sequencer. If they relayed the block efficiently with small fees they get a bonus paid. The validators of the shared sequencer only get paid *after* the blob was submitted and included in Celestia. That is an incetive to relay the blob to Celestia succesfully.

From the diagram above the revenue of the shared sequencer is calculated the follwoing:

Revenue = X - (Y + Z) + MEV

As the chain does not have a token the validators cannot generate revenue through inflation. Therfore the amount charged to the user should be greater than the amount paid by the relayer. In a permissionless sequencer setting, why would the user choose to pay the shared sequencer instead of posting it directly to the DA-Layer.

## Security Guarantees and Considerations

The rollup has a 2/3 honest majority assumption on the shared sequencer. This could be reduced down the line as the execution environment is very minimal and could be zk-proven. In an exclusive setting, the rollup relies on a 1/3 honest minority for liveness. This is elevated if the rollup decides to use permissionless sequencing instead. Therefore, if the shared sequencer would go down, the rollup could fall back to a different form of sequecning in the worst case. This is also true of censorship resistance. If the shared sequencer censors, then in a permissionless setting, the rollup user could fall back to something else.

Initially, the shared sequencer has a 2/3 honest majority assumption on Celestia. In the future, this assumption can be reduced by having each shared sequencer node sample Celestia and Celestia implement full coverage of fraud or zk proofs of the consensus rules. The network uses Celestia for rebates and making sure the data is available. This has direct limitations on the capacity of the shared sequencer and its users. Each rollup can use the shared sequencer to some capacity, but the total capacity cannot exceed Celestia's maximum capacity.

There should never be a case where the shared sequencer batches more bytes than Celestia can publish in one block.
Let\`s say the shared sequencer has a 1-second block time, and Celestia has a 12-second block time. With Celestia\`s current maximum capacity of 2 MB per Block (8 after a governance vote), that would give the shared sequencer 166 kB (666 kB) per Block today. With further improvements down the line, the capacity will increase, but it has to be accounted for. Furthermore, there could be congestion spikes on the DA-Layer, so fees paid by the relayers have to be adjusted, hopefully in an automated way. These adjustments should also be reflected on the user by how much he is paying for the shared sequencer, as that has to cover the cost for DA.

Another liveness issue could be the relayer needing to be incentivized more or being offline. In the future, this could be changed with a permissionless submission from a shared account of TIA gated by the validity of the shared sequencer consensus. This could eventually be possible using [snark-accounts](https://forum.celestia.org/t/celestia-snark-accounts-design-spec/1639) with a [few tweaks](https://forum.celestia.org/t/customize-your-namespace-rollup-resource-pricing-account-abstraction-and-native-restaking/1666) and [Tendermint X](https://blog.succinct.xyz/tendermintx/).

If the shared sequencer is not paid in TIA, it has to account for conversion rates, and treasury management is more complicated. The easiest way to pay would be with TIA or a liquid-staked version of it.

## Future Work

### Ordering Auctions

While having the right to order transactions, there is an inherent value to be captured by the shared sequencer through MEV.

The entity searching for those opportunities has to be aware of execution. A shared sequencer should not do this and can be delegated to an abstract entity we can call the builder. In most cases, the conversation is about proposer builder separation, and inspiration can be taken from chains with high MEV capture, currently Ethereum and Solana.

There are various reasons for [enshrining proposer builder separation](https://ethresear.ch/t/why-enshrine-proposer-builder-separation-a-viable-path-to-epbs/15710), which can be a clear differentiator from other shared sequencers if done early and properly.

Another stance could be to "forbid" validators from extracting MEV by monitoring and punishing them with consequences when caught. Inspiration can be taken from [dydx](https://www.dydxgrants.com/grants/mev-dashboard-maintenance-and-infrastructure). The question remains if this is a long-term viable path and if incentives will be pushed to maximal extraction anyways.

Either way, MEV will not be a problem in the beginning, and there is some time to choose the most viable option. Furthermore, the biggest bottleneck in the beginning will be the adoption and integrations with other stacks rather than the mitigation of MEV.

### Signature Aggregation

The end goal would be for the executor only to run a tendermint light client of the shared sequencer to verify the consensus of the shared sequencer. That would be enough to validate soft confirmations from the shared sequencer. An optimization here would be to use signature aggregation to reduce the header size which will be an optimization rollups might want to do down the line as it influences how much they have to pay for DA.

### DA Sampling

In the current design, the shared sequencer network relies on tendermint proofs submitted by the relayer. The security model could be further improved if the validators of the shared sequencer network ran their own celestia light nodes and sampled for the publication of the data they submitted. This would additionally circumvent the need for relayers to post proofs that they submitted the PFBs for rebates.

### Tree structure

There are various ways that the tree structure can be optimized. One insight should be that namespaces will mostly be random and sporadic, but rollup heights will be saved next to each other.

An alternative could be a data structure that starts as an SMT, with the namespaces being the keys and the values being the roots of the rollup namespaces. This would reflect the sparsity of picking a namespace.

The second layer is a Merkle Patricia Trie. The trie has 32-byte keys, and the values are the data's commitments. The key represents the rollup height or how often a rollup blob has been created by the shared sequencer. This is a way for the rollup light to know if a shared sequencer height has a rollup blob or not.

All rollup blob commitments for the same namespace will be next to each other, so you can query multiple for easy syncing. Just as in the first option, the value starts as a share commitment but appends the height the moment inclusion is proven on-chain.

Why should the tree be split? This keeps the keys under 32 bytes. Implementing just a patria Merkle tree with (namespace | rollup height) as the key might also be an alternative, but further investigation has to be done to say which structure outperforms clearly. This optimization might also not be the bottleneck to target so option one might suffice.