Sequencing API Design (Draft & Discussion)

[nashqueue]

This API proposal will be going through how there could be a common interface between shared sequencers and rollup frameworks. We are making some assumptions about the architecture of shared sequencers and rollup frameworks, so we invite rollup frameworks, shared sequencers, da-layers and others to comment.

This top comment will display the most up-to-date API and will be edited while the discussion is ongoing and keeping a log of edits. The reasoning will be explained throughout the other threads. We split assumptions into threads so we can have more focused discussions. There are still open questions, and solutions to some are proposed. Please comment on your thoughts about each problem and whether you agree with our assumptions.

Shared Sequencer Write Path

// End user uses BroadcastMetaTx to send their transaction to a 
// shared sequencer.
// params: 
type SequencerTx struct {
   AppTxData []byte
   SequencerFee uint64
   SequencerGasLimit uint64
   Namespace uint64
   NamespaceDA string
   SequencerTxSignature []byte
}
//
// A AppTx could look something like this:
// type struct AppTx {
// Data           []byte
// Fee            uint64
// Limit          uint64
// AppTxSignature []byte
// }
// 
func BroadcastMetaTxs(txs []SequencerTx) error

Shared Sequencer Read Path

// Header producer of the rollup is calling the RPC network of 
// the shared sequencer to retrieve the batch for the rollup
// params: namespace: Identifier for the rollup
// params: namespaceHeight: Height of the namespace (group of rollups)
// params: namespaceDA is the DA-Layer you want the SS to submit to
// returns: batchData is the rollup batch, which is a batch of transactions
// which holds at least one transaction.
// returns: SSHeight is the height of the shared sequencer
// returns: proof is a proof that verifies the SS sequenced the batch
func RetrieveBatch(namespace uint64, namespaceHeight uint64, namespaceDA string) (batchData []byte, SSHeight uint64, proof []byte, accumulatedDataHash []byte)

// Rollup network full/light nodes (includes header producer full node)
// runs a shared sequencer light node (SSLN) and queries it via VerifyBatch
// to verify the soft commitment
// params: SSHeight is the shared sequencer height
// params: accumulatedDataHash is the hash of previous accumulatedDataHash, 
// and the current dataHash, which is available in the rollup header
// params: proof is a proof that verifies the SS sequenced the batch
// returns: bool to report the verification state
func VerifyBatch(SSHeight uint64, accumulatedDataHash []byte, proof []byte) error

[nashqueue]

1. Why should we use a shared sequencer?

• Positive:
  • Flexibility for developers in terms of deploying rollups as easily as smart contracts because developers don’t need to deploy sequencer infra (out-of-the-box sequencing)
  • Decentralization by default, don’t have to bootstrap your own sequencer set
  • Guarantee of atomic inclusion between rollups that use the same shared sequencer
  • Faster block times than DA and soft commitments for rollups
  • Fixed DA-cost per byte gets spread and amortized through aggregation
• Bad:
  • Profitable Censorship MEV (PCM)
  • More complex rollup infrastructure that might be harder to debug as there are more moving parts
• Neutral:
  • Inherit DA throughput of shared sequencer
  • Inherit censorship resistance of shared sequencer
  • Inherit the liveness of shared sequencer
  • Inherit trust assumptions of a shared sequencer light node
  • Inherit block time of a shared sequencer

[norswap]

I'm not sure "shared sequencer" is a term where everybody agrees what it means ;)

Do you have in mind a "naive shared sequencer" (my own term) that simply sequences a bunch of rollups together as though they were one big rollup?

[nashqueue]

Totally agree, I try to differentiate what it means and what it does not mean in Point 3. I guess the interface assumes a "naive shared sequencer" that can be context-separated (so not one big rollups but many in parallel). What happens under the hood is up to the implementer ;).

[mastergaurang94]

For naming convention, would it be worth naming it SequencerFee and SequencerGasLimit and dropping "Shared"? There could be users who prefer centralized / trusted sequencers even though they are disfavored?

[nashqueue]

Great suggestion ty. Edited

[nashqueue]

2. Why should we have a standard interface between shared sequencers and rollup frameworks?

• Positive:
  • Any conforming shared sequencer can get users by supporting multiple rollup frameworks.
  • Any conforming rollup framework can tap into different shared sequencer networks depending on their needs and get the above benefits.
  • Integrations between SS x RF are engineering/time costly, and each SS and RF have different assumptions, so for now, this was only possible with custom-built changes. A standard can relieve the core engineering teams as they only have to comply with one interface, and integrations will be easier.
  • When developers work with standardized interfaces, they can often build systems more quickly since they already know what to expect from the components they're working with.
  • If the interface is future-proof and new developments happen, the interface can stay while SS and RF improve independently.
  • The interface will give transparency to the developer, which trust-assumptions the other component is making.
  • The interface will help us with the slow game. It is easier to switch SS; therefore, the SS cannot hold the rollup hostage. Keeping switching costs low is essential to prevent extractive behavior. Source: https://www.youtube.com/watch?v=PUBvZRhOTAo&t=55s
  • An Interface will foster collaboration and innovation on both sides of the components.
• Negative
  • Standardizing may mean that some specialized or unique features are no longer supported, as they must conform to the new standard. This can limit innovation and lead to a "one-size-fits-all" approach that might not suit all needs.
  • Achieving a standardized interface across components and markets may be a complex task involving negotiations, alignment of technical specifications, and potentially significant changes to existing systems.
  • Changing or adapting can sometimes be challenging once a standard is set. This rigidity might stifle innovation or make it harder to respond to new technological advances.

[norswap]

I think one solution to some of the negatives is a "modular standard". i.e. a standard that includes a core an extension, with the idea that further extensions can be added later. If necessary, the core or the extension can also receive new versions.

[nashqueue]

Yeah, something future-proof would be ideal.

[sveitser]

Generally agree. The Espresso Sequencer doesn’t have a set block time, is compatible with any virtual machine (VM) and doesn’t impose rules on transaction structure. Our OP Stack integration contains an example of mapping our sequencer block time to the fixed OP block time.

Transactions submitted to the Espresso Sequencer have an accommodating format and consist of the payload bytes plus an identifier for the rollup, e.g. Chain ID for ETH (see multi-rollup blocks for detail).

[nashqueue]

Does that mean that you run a different Espresso Sequencer Set with each Integration ? Isn't the blocktime determined by the underlying consensus of the Shared Sequencer which in this case is Hotstuff?

As you are using an NMT is should be compatible with what I called namespace here.

[sveitser]

No it's a shared sequencer so the idea is to only have one. I don't think it makes too much sense for a rollup to have a shorter block time than the shared sequencer but it's up to the rollup to define how it derives it's L2 blocks.

For example, the Espresso Sequencer doesn't have a fixed block time, but OP has a fixed 2 second block time so we came up with a way to do this for our integration. I don't think we have a write up but it's on github if anyone is interested. See for instance this commit.

[nashqueue]

3. How does a shared sequencer communicate with an executor?

For this proposal, we will show how we think about what a shared sequencer does and does not.

A shared sequencer does ordering and inclusion. It does not execute the transactions and, therefore, does not commit over the state root or app hash. A “Header Producer” or executor does the execution and produces the rollup header, which is metadata about the block, which, at minimum, includes a commitment to the transactions in that block. The header producer and the shared sequencer are 2 different logical entities. Additional reading can be done in Redefining Sequencers.

Let’s see how a shared sequencer works with an optimistic rollup. In this diagram, a centralized header producer performs the execution for simplicity.

graph TB
  
  style U fill:#EE82EE
  style FN fill:#008000
	style HP fill:#FA8072
  
  subgraph HP["Execution"]
  CHP -- "Header and Stateroots" --> DAL2["DA-Layer"]
  end
  CHP -- "Soft Commitment Headers" --> LN["Rollup Light Node"]

  style LN fill:#D8BFD8
  DAL2 -- "Header" --> LN
  DAL2 -- "Header and Stateroots" --> FN["Rollup Full Node"]
	CHP -- "Soft Commitment Rollup Headers \n and Stateroots \n" --> FN
  FN -- "Fraud Proof" --> LN


  style U fill:#FFA07A
  style FN fill:#98FB98
  style LN fill:#D8BFD8
  style HP fill:#FA8072


  U["User"] -- "Transaction" --> SA["Shared Sequencer"]
  style U fill:#FFA07A
  style A fill:#87CEFA
  style FN fill:#98FB98
  subgraph A["Ordering"]
 
  SA -- "Ordered Batch" --> DAL["DA-Layer"]

  end
  SA -- "Soft Committed Ordered Batch " --> CHP
 SA -- " Shared Sequencer Header+ " --> CHP
   DAL -- "Ordered Batch" --> FN
    SA -- "Soft Committed Ordered Batch  " --> FN

 SA -- " Shared Sequencer Header+ " --> FN
 
  SA -- "Shared Sequencer Header+ " --> LN

  DAL -- "Ordered Batch" --> CHP["Centralized Header Producer"]
  style FN fill:#98FB98



linkStyle 0 stroke:#00FF00,stroke-width:2px;
linkStyle 1 stroke:#000000,stroke-width:2px;
linkStyle 2 stroke:#00FF00,stroke-width:2px;
linkStyle 3 stroke:#00FF00,stroke-width:2px;
linkStyle 4 stroke:#000000,stroke-width:2px;
linkStyle 5 stroke:#00FF00,stroke-width:2px;
linkStyle 6 stroke:#FF0000,stroke-width:2px;
linkStyle 7 stroke:#FF0000,stroke-width:2px;
linkStyle 8 stroke:#000000,stroke-width:2px;
linkStyle 9 stroke:#00FF00,stroke-width:2px;
linkStyle 10 stroke:#FF0000,stroke-width:2px;
linkStyle 11 stroke:#000000,stroke-width:2px;
linkStyle 12 stroke:#FF0000,stroke-width:2px;
linkStyle 13 stroke:#FF0000,stroke-width:2px;
linkStyle 14 stroke:#00FF00,stroke-width:2px;

Loading

The arrows in black are optional and used for better UX. The arrows in red are necessary for Rollup Full Nodes to function. The arrows in green are necessary for Rollup Light Nodes to function.

[norswap]

A caveat here is that "sequencer does only ordering" only works until it's profitable to manipulate the ordering, which usually requires simulating (executing) the transactions.

An extremely short simplified practical theory of MEV; you gotta worry about:

• frontruns — mostly people stealing arb, hacks, and "solutions to puzzles"
• sandwiches — mostly impossible without a flashbots-like bundle auction layer
• backruns — probably the most common, arbing on the back of an oracle update or big transaction, sniping new token deployments & mints, ...

If you don't restrict sequencer behaviour, a flashbot-like layer might develop if profitable, or the sequencer might just start extracting ad-hoc.

Restricting sequencer behaviour almost impossible to do technically, this has to be a social contract, then you can slash them if they misbehave. This can avoid obvious frontruns and sandwiches, but policing backruns is extremely hard ... unless you add an ordering component to your system. This could be a FIFO system like Chainlink FairOrdering (terrible fucking name), or an encrypted mempool like Shutter Network.

So basically my point is you gotta take into account that execution might start happening upstream of your execution block if profitable, or build in some (mostly social/governance) countermeasures.

The existence of such a builder layer can also present opportunities though!

[nashqueue]

I am not making any assumptions on how MEV is handled to keep the interface as simple as possible. The goal would be to see different solutions emerge, given that constraint. I will certainly expect builders/searchers to emerge that will do execution. The SS itself would not have to do it, though.
And SSs are already trying to be novel and implement things like encrypted mempools like Fairblock.

One thing that you did not mention is that is still possible to build on top of the ordering with block-specific rules, and tackle MEV from the app side. Let`s say I have a canonical / validity rule that all cow-swap transactions will be on top of the block. I can enforce this rule after the SS has already ordered it and reorder the transactions according to my rules.

This gives the protocol the ability to use something like Skips POB. What I mean by that is that you can attempt to deal with MEV after the SS ordered the block and reorder them to your liking, something naive like first all buys and then all sells.

You could have protocol-owned arbitrage in between each swap where the revenue goes back to the protocol, which is similar to Osmosis ProtoRev.

Or you could even have an on-chain auction where multiple header producers compete to build the best block after some user-welfare function that I attempt to explain here, where the SS only does Inclusion and Ordering and Execution is on the Header Producer.

[sveitser]

• This diagram is awesome, we’re mostly aligned on this section.
• We have a generalized system diagram and an Optimistic rollup diagram for comparison.

[bowenyou]

Generally agree with discussion here. Should be worth mentioning that different rollups have different ways of dealing with MEV, so having it in the unified interface of shared sequencer is probably not necessary.

We (Fairblock) have encrypted mempools, but one can just as well have auctions. But at the end of the day, this shouldn't affect a unified interface of a shared sequencer.

[mtgnoah]

I agree with @bowenyou here because their are different ways to decouple the builders from the proposer/sequencers as well so one shared sequencer could support transactions coming from various different block builders who may have an encrypted mempool or may have a public mempool similar to private and public orderflow on other chains like Ethereum.

[nashqueue]

4. Why must the shared sequencer publish the ordered batches to a DA-Layer?

graph TB

  style U fill:#EE82EE
  style FN fill:#008000


  style U fill:#FFA07A
  style FN fill:#98FB98

  U["User"] -- "Transaction" --> SA["Shared Sequencer"]
  style U fill:#FFA07A
  style A fill:#87CEFA
  style FN fill:#98FB98
  subgraph A["Ordering"]
 
  SA -- "Ordered Batch" --> DAL["DA-Layer"]

  end
   DAL -- "Ordered Batch" --> FN["Rollup Full Node"]
    
 
  DAL -- "Ordered Batch" --> CHP["Centralized Header Producer"]
  style FN fill:#98FB98

Loading

We need the ordered batches on a DA-Layer, as this is how we get a data availability guarantee for rollups.

This is also a requirement for rollup full nodes to execute the blocks canonically, reading from the DA-Layer as the source of truth and creating a zk or fraud-proof when needed to enable trust-minimized rollup light nodes (execution light nodes).

[enandini]

Sequencer spelling!

[sveitser]

The Espresso Sequencer design currently uses our DA layer, Tiramisu, nothing prevents developers from using other DA systems on top, e.g. posting to Ethereum, Celestia, EigenDA, etc., for a different set of benefits. More in Q8.

[nashqueue]

Yes, I think the point that I am trying to make is that if Espresso, for example, wants to support Rollups that want to use EigenDA or Avail for DA then Espresso needs to post the ordered batch from them to the DA-Layer, as that is where they will be deriving the canonical state from.

[mtgnoah]

Are we assuming one batch is equal to one block or not?

[nashqueue]

Depends on how the rollup interprets it but we can say one batch is one block for simplicity.

[nashqueue]

5. Why does a shared sequencer have to commit over the ordering?

Let's imagine we are posting ordered batches to the DA-Layer. The picture shows three blobs in the DA-Layer, but only 1 and 3 are from the shared sequencer we want to follow.

To differentiate between which transactions to execute, we need to know which transactions are from the shared sequencer and which are not. That way, we can ignore the second blob. We can only start executing the transactions after we get and trust the commitment over the ordered batch.

Let’s call this commitment the order-commitment.

The following threads assume we commit over the ordering. There are other ways to prove that a blob comes from a shared sequencer, like signing over each blob. We are happy to discuss other paths, but we found this solution to be one of the more optimal ones.

[noot]

to confirm, this order-commitment means the shared sequencer block producer includes the commitment to the blobs that will be posted for that block inside the block header?

[nashqueue]

Yes. Let's say the DA-Layer has a block time of 10 seconds, and the Shared Sqeucner has a block time of 5 seconds. Then, we can fit 2 Shared Seqeucner blocks inside a DA-Layer Block. A Shared Srqeucner Block contains multiple Rollup Transaction Batches, SS transactions and a SS Header. All Rollup transaction batches need their commitment, and the aggregation of all those commitments lives in the SS header.

[norswap]

Posting to DA involves posting a signed tx anyway, so just checking the origin address should be enough for filtering purposes? Then blobs can include a sequence number for ordering. This is this works on the OP stack (+ extra nasty complexity due to compression etc).

You will need to commit to the blob/tx history on the settlement layer (L1) whenever it is different from the DA. This is necessary, if only to tie output roots posted to L1 with a specific tx history on the DA.

You could use a block/blob number, but that's not resilient to DA reorgs etc. The hash of the last block/blob should be secure, as long as it includes a hash of its parent. There might be reasons to commit to every single blob (I think the Celestia op-stack fork does that, though I can't remember why).

Anyway, my point is: it's probably much simpler from an implementation perspective to just check the blob's sender then a sequencer number within rather than comparing to a separately maintained list of L1 commitments.

[nashqueue]

Some nuances with that approach:

• The SS Validator might want to use a different account (A) on the consensus level to sign SS blocks and on the DA-Layer to hold DA funds (B) and post them with a different account (C), which has only limited permission to (B),
  • so SS Light Nodes have to keep track of that mapping and its validity
  • Does this assume there has to exist a Settlement Layer where this mapping is stored? This would exclude all sovereign rollups that don't use a settlement layer
• The SS Validator might use a different signature scheme than the DA-Layer.
• A Rollup Full Node has to now at least run a DA-Layer Partial Node. I define a partial node as a node that checks and validates all execution transactions of the DA-Layer.
  • To make the example concrete, let's take Celestia for example. Celestia already puts all PFB(PayforBlob) transactions into one namespace, which makes separation for this problem easier.
  • We would still have to read all PFB Transactions and check all transactions against all accounts that could possibly be a SS. That imposes new overhead for execution and storage.
• What if the SS uses the account for something else? It might pose a problem if validators do not use it exclusively for the SS
• Let's assume the SS runs a Tendermint Consensus. How does a SS Conseseus react if a SS Validator posts a blob that he should not have posted?
  • Let's say this is Fraud and the SS gets slashed.
    • That is something that you have to implement and make the SS Light Nodes able to verify! If you do not make SS Light Nodes verify this fraud, then 1 single entity, the person, the SS Validator who posts the blob, can lie to the Header Procuder.
    • This Fraud Proof also has to be smaller than the SS block or else it's not a Light Node + It would require a SS Execution Light Client OR everyone has to run a SS Full node that wants to use a SS
    • For the fraud to be validated by the SS consensus, we would need to be able to check which blob is not contained, so by contraposition, the consensus has to agree which blob IS contained, which means that we have to identify the blobs aka we have a reference to the blob which I call here an order-commitment
    • Does this Fraud have a recovery mechanism?
      • No -> consensus halt: 1 actor can create a liveness failure instead of 1/3
      • If yes, how?
  • If you want to have a zk-proof over the validity then you would need to have a zk-proof over all PFB transactions (or your preferred DA-Layer equivalent), as you need to make sure that nothing is additional or missing.

[sveitser]

Agreed and this is currently a property of the Espresso Sequencer. In the transaction flow, a commitment to the block containing the transactions is persisted in the L1, e.g. Ethereum, sequencer contract (along with a proof that the block has been finalized by consensus).

[nashqueue]

6. How do we validate that the order-commitment is correct?

We validate that the order commitment is correct through a shared sequencer light client. This light client can validate the shared sequencer header under its trust assumptions following the chain.

The shared sequencer set would sign over this commitment or a reference to it that the shared sequencer light client can derive and validate.

This light client can either be on-chain or a node in the network communicating through P2P.

On-chain light clients are light clients that are built in as modules or smart contracts on another blockchain. A classic smart contract rollup will have an on-chain rollup light client to verify the ZK or fraud proofs. The same goes for Tendermint light clients that connect IBC connections. These are also on-chain light clients verifying the Tendermint consensus. The limitation is that you need a successful transaction or interaction with the blockchain to update the on-chain light client. A Light node is something a user can run where they can do the same verification locally and get the proofs through the P2P network without needing to wait for the inclusion of the transaction and without running a node of the blockchain where the on-chain light client is running.

[sveitser]

In addition to the above (Q5) commitment to the Espresso Sequencer contract and a proof of a finalized block, light nodes can verify a namespace proof to ascertain whether a certain set of ordered rollup transactions were included in a block commitment from the Espresso Sequencer. Any rollup specific transformations pertaining to the set of ordered rollup transactions can be verified via a proof of correct derivation.

[nashqueue]

That is perfect and should make the Implementation of VerifyBatch easier. The concept of espresso light nodes that can verify those proofs aligns very well with how we have been thinking about this.

[nashqueue]

7. Why does the order-commitment need to be in the header?

This is an implementation detail from the shared sequencer, so feedback on how other teams think about it would be appreciated.

Let's imagine we have a simple merkle tree over all order-commitments. Let's call it the commitment root. The sequencer signs over this commitment root. A shared sequencer full node can reconstruct the header and check the validity of the commitment root. It can now respond to queries against a certain order-commitment from light nodes against this root and respond with a merkle proof from the order-commitment to the root.

The shared sequencer light node depends on getting the proof of the order-commitment to the commitment root. We can eliminate the need for queries by creating an extended header with the original header and a list of all order-commitments. That way, a light client can check the commitment root's correct construction.

An on-chain light client would only have a commitment root, but an SS light node could get an extended header with all order commitments. There is an argument against it that having all those commitments in the extended header will be too big of a storage overhead, but you can safely prune them as a light node after verification. This will make trust-minimized SS execution light clients more light. However, it could be over-optimized, as SS light nodes still have a 2/3 honest majority assumption at this point in time.

[mtgnoah]

I don't know if their will be many or any shared sequencer light nodes. It just doesn't seem like something that people will demand as much.

[nashqueue]

Let`s say someone uses Tendermint for their consensus. Then, we can have an SS light client with a 2/3 honest majority assumption. All Header Producers will run an SS light client so they can validate the SS soft commitment, don't have to trust the RPC, and don't have to wait until it hits the DA-Layer. If you want to have a trust-minimized version of that, then you will start running into problems that the solution above will help to solve. I agree that currently, the end-user is trusting the RPC and is not running a node at all, but hopefully, that will change in the future. Most end users will never choose trust-minimized security over comfort so i believe it's in the developers building the protocols to make sure that the end user does not have to make this choice.

[sveitser]

IIUC the idea is that a shared sequencer "header producer" can run a light client and fetch its rollup specific transactions from the RPC then validate against the block header's rollup specific order commitment (without having to fetch an additional proof to compute the root).

The Espresso Sequencer doesn’t have this extended header today and we currently don’t have plans to add it. We would consider prioritizing it based on customer demand.

[nashqueue]

Could you explain how Espresso currently commits over the order? I know you are using an NMT, so I assume the validators are singing over the DataRoot of the Namespace Merkle Tree.

The Idea here was that you could remove the need for an inclusion proof of the order commitment to the data root. But I am on the fence if this is an optimization that we need to go for and only consider it, as you said, based on customer demand.

[nashqueue]

8. Why does the shared sequencer and, by extension, the order-commitment need to be DA-aware?

The first assumption that we are making is that a shared sequencer will want to support all kinds of rollups, and those rollups might want to run on different DA-Layers. Even if your shared sequencer only supports one DA-Layer we want to point out that the order-commitment has to use the same commitment scheme as the DA-Layer.

The argumentation will be the following: We will try to construct something for a da-agnostic commitment scheme and show how that scheme runs into a problem.

1. A shared sequencer uses a da-agnostic commitment scheme, which differs from the DA-Layer to which the blobs are posted.

2. Let's use a simple construction as an example. This diagram shows eight transactions, numbered 0 to 7, ordered by the shared sequencer. We create a binary merkle tree over those transactions, and the root will be our order-commitment OC. Let’s assume for simplicity that the shared sequencer only orders one rollup, and the eight transactions will be one blob posted to the DA-Layer.

   

3. The shared sequencer scheme now has consensus over this root, and we can find this OC inside the shared sequencer header.

4. The SS will push the ordered batch of transactions to a DA-Layer

   1. In the optimistic case, we will get the ordered batch as a soft commitment over an RPC. We can validate the order commitment with our shared sequencer light client.
   2. In the pessimistic case, the header producer will get the blob with the ordered batch from the DA-Layer

5. The header producer creates a new state root while executing the transactions.

6. Inside the rollup header there is also a dataHash. We need the dataHash inside the Header for various things:

   1. For rollups that use a fraud-proof scheme, this is needed to verify a transition fraud-proof. One example is explained in 4.4 of Fraud and Data Availability Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities
   2. This is needed for rollups that use a zk-proof scheme because you need to verify that the bytes of the transactions in the DA-Layer result in the correct appHash.
   3. We need the DataHash inside the Header to match the blob of the rollup data to the rollup header if the header and blobs are posted as different blobs, which will be the case using a shared sequencer.
   4. We need it to verify blob inclusion proofs so rollup light nodes know that this data was inside the DA-Layer as a blob.

7. For this example, let's assume the rollup uses Celestia as a DA-Layer. The DataHash, in this case, would be the PFB (PayforBlob) commitment.

   1. The PFB commitment can be calculated like this. which converts bytes into a 32 byte hash.
   2. This Datahash is DA-aware because we have to reference a blob inside the DA-Layer, and is used internally in Celestia to match PFB transactions to the corresponding blobs.

8. This concludes that we have two different commitment schemes, one for ordering and one for DA for the same data inside the DA-Layer. Both of those hashes will be present in the rollup header.

9. Let’s assume a malicious header producer wants to execute on a batch not ordered by the shared sequencer.

   1. The shared sequencer orders blob 1 and blob 3. The malicious header producer inserted blob 2 on the DA-Layer level.

   

   2. The shared sequencer commits over blob 1 with OC_1 and over blob 3 with OC_3.
   3. The header producer executes over blobs 1 and 2 and not 3.
   4. The first block looks good and has the correct OC_1, datahash_1, and apphash_1 in the header.
   5. The second block should have OC_3, datahash_3, and apphash_3, but instead, it will be set as OC_3, datahash_2 and apphash_2. Here datahash_2 is correctly derived from blob 2, and apphash_2 would be correct after executing the transaction of blob 2 on top of blob 1. The only malicious behavior is that the header producer is using OC_3 to trick a SS light node that the SS committed this blob.

10. How do we prevent a light node from getting tricked by this?

    1. We cannot give the light node the whole blob and let them compute both commitments because this would mean that the light node gets the whole rollup data for a rollup block, which, by definition, it does not and only receives the rollup header.
    2. We can give the light node an equivalence proof of the two commitments. This will be tied to the DA-Layer ↔ Shared Sequencer combination, as every pairwise combination might have its own equivalence proof. The order commitment is now DA-Agnostic, but the equivalence proof has to be DA-Aware. This seems like a valid but complex solution and would require a lot of engineering efforts for each new DA/SS pair.
    3. We give the light node a fraud-proof that those commitments are not equal. If you want to proof that a hash scheme does not match another hash scheme over the same data you will need the whole data to show that those do not match where we run into the same problem as in i).
    4. The order-commitment and da-commitment are the same so you don't have to proof equivalency.

[noot]

For this example, let's assume the rollup uses Celestia as a DA-Layer. The DataHash, in this case, would be the PFB (PayforBlob) commitment.

it's unclear why this is the case - from what I understand the DataHash is just some commitment to the transactions in the block, but it's up to the rollup node to determine how it's created. is the motivation for having the rollup use the DA commitment for the DataHash be for rollup light nodes to easily check if the data is available?

it seems the simplest solution is to have rollup nodes use the ordering commitment as the data hash.

[nashqueue]

is the motivation for having the rollup use the DA commitment for the DataHash be for rollup light nodes to easily check if the data is available?

Yes! Availability and Inclusion are two different concepts. To check availability the DA-Layer light node has to sample the DA-Layer Block. DA-Layer block is available implies the rollup`s namespace is available. To check inclusion, you have to check that the bytes from the Rollup Data are available in the DA-Layer. In Celestia you would do an inclusion proof a merkle proof to the subtree roots from the shares that include the rollup data. Celestia does this already natively which would result in a PFB commitment. If you only save the order commitment you would have the same problem backwards. You can check the order is correct easily but now you need to check the equivalency between the DA-layers commitment and the order commitment. You will need both to be correct.

[nashqueue]

9. Why do the Shared Sequencer and Rollup Network have to agree on Serialization / Deserialization?

For a header producer and rollup full nodes to read the transactions from the DA-Layer and execute on top of them, you must be able to deserialize the bytes correctly. The SS might only see raw bytes from the user. This means that they will order raw bytes next to each other. Now, the challenge lies at the header producer part to know when a transaction ends and when to start reading new transaction bytes.

If we use a compression algorithm, we must also be aware of that one to decompress accordingly.

Another challenge will be optimistic rollups that use single-round fraud proofs that need an inclusion proof to the rollups transaction inside a blob. The related discussion on this topic is here. The proposed solution we are following now is to post ISR (Intermediate state roots) and transactions next to each other. This will not be possible anymore as we are separating ordering and execution now, so the Shared Sequencer will not be able to execute the root, and they will have to live in separate namespaces/blobs. Furthermore, Rollkit wraps transactions in celestia`s compact shares transaction format. This enables us to read any share in the blob and be able to parse out the transactions.

If we want to keep this feature a shared sequencer might want to adopt this and make transactions self-parsable. This is an open problem and suggestions are welcome.

[nashqueue]

10. Why do we need an accumulated Datahash?

The problem statement is the following. We assume the shared sequencers block time will define the rollups blocktime 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.

How does a rollup light node know whether or not a shared sequencer height had a rollup blob for a given namespace? And what if the header producer skipped a shared sequencer height? We need to differentiate if he did that maliciously or not. We could create a fraud-proof for that behavior so that a light node can detect it. Another option would be to have an exclusion proof for a given namespace. Still, a shared sequencer might not use a namespace merkle tree, so creating an exclusion proof for a given namespace would be difficult. An open question is if a Rollup skips an SS height if it only contains invalid transactions / random bytes or if that is just an empty block. Having empty blocks could be a solution itself, but that would be wasteful posting of bytes to the DA-Layer from the header producer's perspective.

The next option is to bake this distinction into the verification logic itself. We can let the dataHash/order-commitment for rollup height x in shared sequencer height (a) influence the dataHash/order-commitment for rollup height x+1 in shared sequencer height (b). We gave it the name of accumulated Datahash, and it works as follows. Let's say DH is the DataHash for a batch of transactions for a rollup height. Let's say CR is the commitment root over the DataHashes. Let DataHash(Height(x)) = Hash(Datahash(height x-1), Datahash(txbatch)). Imagine it being a chain of hashes of hashes.

The Diagram shows 3 SS heights and 3 namespaces(green, blue, red) . You can see how the namespace green skips SS height 2 but is still connected through the chain of hashes.

Here is another diagram of the blue`s accumulated Datahash.

[noot]

How does a rollup light node know whether or not a shared sequencer height had a rollup blob for a given namespace? And what if the header producer skipped a shared sequencer height? We need to differentiate if he did that maliciously or not. We could create a fraud-proof for that behavior so that a light node can detect it.

this is essentially what we do at Astria - the shared sequencer includes a commitment to the rollup chain IDs in the block in the header (in the form of a merkle root), so if this never gets posted to DA or a rollup node fails to execute the data for that block, it's detectable via a merkle inclusion proof.

[nashqueue]

How big would the fraud-proof be in your case?

[noot]

should be log2(number of rollup chain IDs in the block) * 32 bytes - haven't looked into optimizing this yet, we just went with a simple solution for now :)

[sveitser]

The Espresso Sequencer uses a namespaced commitment, so currently don't have a need for the accumulated Datahash.

Thinking about this some more, as the interface is meant to be a generic sequencing API it would be nice if it could be more abstract and (in this example) not expose in the API design a SS/rollup implementation detail. Ideally the generic API would be abstract over how the SS (and rollups) implement their SS block -> rollup block derivation.

[nashqueue]

I see, with a namespace Merkle tree, you guys don't have this problem, as you can have quite cheap exclusion proofs that a namespace does not exist in a block.

Maybe instead of the accumulated Data Hash, we would call it something like an identifier to abstract away the implementation. Now, my question would still persist what is the best way for a rollup to know when nothing has been committed maybe that is an implementation detail that the rollup does not have to think about but the SS just has to provide.

[nashqueue]

11. Why are we calling it the namespace, namespaceHeight, and namespaceDA, not rollupID, rollupHeight, and rollupDA?

While researching, we discovered that multiple rollups can use the same namespace, which is just a matter of how you interpret it. One example of how you can explore this is if the rollups inside the namespace are aware of each other's state.

For simplicity, let’s assume the person executing (header producer) the transaction would be the same for both rollups. This could give us atomic execution between rollups. It would be like taking Shared Validity Sequencing but separating ordering and execution. It also aligns with the recent blog post by anoma. To use their terminology, each namespace would be a chimera state partition in this case. Either way, there are many unexplored ways to use a namespace for cross-communication, so we should not limit it to one rollup.

Of course, if anybody can post to the namespace, then you are susceptible to the woods attack

[jbowen93]

blog post by anoma.

broken link, should be https://anoma.net/blog/chimera-chains

[mastergaurang94]

Given the overlapping association namespace has with NMT's, how does clusterID, clusterHeight and clusterDA sound instead?

A cluster would be defined as one or many rollups that share trust assumptions of its underlying infra, i.e. executor / sequencer.

Inspired by this: https://blog.celestia.org/clusters/

[nashqueue]

12. Who is running what?

Node	DA-Layer LN	Shared Sequencer LN	Execution LN (Rollup LN)
DA-Layer Validator	❌	❌	❌
DA-Layer FN	❌	❌	❌
Shared Sequencer Validator	✅	❌	❌
Shared Sequencer FN	✅	❌	❌
Header Producer	✅	✅	❌
Rollup FN	✅	✅	❌
End-User	✅	✅	✅
Trust-minimized Bridge	✅	✅	✅

[noot]

Thanks for posting this and starting the discussion!

type SequencerTx struct {
AppTxData []byte
SharedSequencerFee uint64
SharedSequencerGasLimit uint64
Namespace uint64
NamespaceDA string
SequencerTxSignature []byte
}

SharedSequencerGasLimit should probably be named something like SharedSequencerMaxFee as there's no gas.

Astria calls Namespace chain_id and it's a 32-byte array right now, was previously just a string.

Astria also doesn't have NamespaceDA as the DA namespace is deterministically derived from the chain_id.

[nashqueue]

Thank you for the comments :) . I see that namespaceDA name might need to be clarified. It is not supposed to be the namespace you want to use in the DA-Layer; It is supposed to mean which DA-Layer you want to use for this "chain_id" in your case. I also assumed that the DA namespace is deterministically derived from the chain_id. Will clarify this at the top.

[noot]

that makes sense, thanks!

[mastergaurang94]

re: (#1208 (reply in thread))

[evan-forbes]

Is the user signing twice with

// End user uses BroadcastMetaTx to send their transaction to a 
// shared sequencer.
// params: 
type SequencerTx struct {
   AppTxData []byte
   SharedSequencerFee uint64
   SharedSequencerGasLimit uint64
   Namespace uint64
   NamespaceDA string
   SequencerTxSignature []byte
}

?

[nashqueue]

yes

[nashqueue]

An example of a DA-Layer like Celestia implementing the Sequencing API would be the user signing the tx and then the User signing a PayForBlob Transaction and posting it to the DA-Layer

[mtgnoah]

This API proposal will be going through how there could be a common interface between shared sequencers and rollup frameworks. We are making some assumptions about the architecture of shared sequencers and rollup frameworks, so we invite rollup frameworks, shared sequencers, da-layers and others to comment.

This top comment will display the most up-to-date API and will be edited while the discussion is ongoing and keeping a log of edits. The reasoning will be explained throughout the other threads. We split assumptions into threads so we can have more focused discussions. There are still open questions, and solutions to some are proposed. Please comment on your thoughts about each problem and whether you agree with our assumptions.

Shared Sequencer Write Path

// End user uses BroadcastMetaTx to send their transaction to a 
// shared sequencer.
// params: 
type SequencerTx struct {
   AppTxData []byte
   SharedSequencerFee uint64
   SharedSequencerGasLimit uint64
   Namespace uint64
   NamespaceDA string
   SequencerTxSignature []byte
}
//
// A AppTx could look something like this:
// type struct AppTx {
// Data           []byte
// Fee            uint64
// Limit          uint64
// AppTxSignature []byte
// }
// 
func BroadcastMetaTxs(txs []SequencerTx) error

Shared Sequencer Read Path

// Header producer of the rollup is calling the RPC network of 
// the shared sequencer to retrieve the batch for the rollup
// params: namespace: Identifier for the rollup
// params: namespaceHeight: Height of the namespace (group of rollups)
// params: namespaceDA is the DA-Layer you want the SS to submit to
// returns: batchData is the rollup batch, which is a batch of transactions
// which holds at least one transaction.
// returns: SSHeight is the height of the shared sequencer
// returns: proof is a proof that verifies the SS sequenced the batch
func RetrieveBatch(namespace uint64, namespaceHeight uint64, namespaceDA string) (batchData []byte, SSHeight uint64, proof []byte, accumulatedDataHash []byte)

// Rollup network full/light nodes (includes header producer full node)
// runs a shared sequencer light node (SSLN) and queries it via VerifyBatch
// to verify the soft commitment
// params: SSHeight is the shared sequencer height
// params: accumulatedDataHash is the hash of previous accumulatedDataHash, 
// and the current dataHash, which is available in the rollup header
// params: proof is a proof that verifies the SS sequenced the batch
// returns: bool to report the verification state
func VerifyBatch(SSHeight uint64, accumulatedDataHash []byte, proof []byte) error

For the read path I think we should instead do something by timestamp because it may be easier to standardize across the board and easier for rollups to integrate especially in frameworks like OP Stack. It also gives a bit more flexibility in general across DA layers.

[nashqueue]

Could you propose what you would change ?

[mtgnoah]

I would propose instead of using namespaceHeight we instead have 2 uint64 parameters allowing for a start and end time. This would modify RetrieveBatch. It would look like this

// Header producer of the rollup is calling the RPC network of 
// the shared sequencer to retrieve the batch for the rollup
// params: namespace: Identifier for the rollup
// params: start: Start time of the namespace (group of rollups) Measured in Unix Milliseconds
// params: end: End time of the namespace (group of rollups) Measured in Unix Milliseconds
// params: namespaceDA is the DA-Layer you want the SS to submit to
// returns: batchData is the rollup batch, which is a batch of transactions
// which holds at least one transaction.
// returns: SSHeight is the height of the shared sequencer
// returns: proof is a proof that verifies the SS sequenced the batch
func RetrieveBatch(namespace uint64, start uint64, end uint64, namespaceDA string) (batchData []byte, SSHeight uint64, proof []byte, accumulatedDataHash []byte)

[nashqueue]

You would then receive a range of batches, which could be over multiple shared sequencer heights .

I do believe that you could still map the height to the blocktime and unwrap it somehow with the previous interface.

[mtgnoah]

Are we assuming when you submit a SequencerTx you get the namespace height back that way you can use it in the RetrieveBatch?

[nashqueue]

You could get back a response the moment it is included. But the person who is retrieving the batch is the Executor, not the User who submitted the transaction.

So, I would assume that the Executor can do regular pulls in the frequency of the block time. If there is a push-based system, then the Executor could subscribe to it and not make frequent requests. But here, there is some trust involved.
In a pull-based system, you could potentially validate exclusion proofs of the batch not being inside the shared sequencer.
In a push-based system, there is nothing stopping the person from showing that a batch was included. So the most optimal but still trustless approach would probably be a push-based one that pushes on every height, either the batch or the exclusion proof.

This now goes into the risk of pushing to somebody who does not want it anymore, so you may request an acknowledgment. This will give a round trip again, which is equivalent to pulling and requesting on each height.

[mastergaurang94]

This is quite a thorough exploration of sequencing design. I learned a lot in just reading it. Thanks for putting it together. A few initial thoughts and clarifications:

1. IIUC, RetrieveBatch allows an executor to begin before a soft commitment from the sequencer via VerifyBatch. I’m trying to get a grasp of the impact this would have on overall performance? What is like the napkin math of it for an average rollup (in units of seconds / ms)?

2. It seems an executor can repeatedly query the sequencer using RetrieveBatch . How does an executor know how often, i.e. block time? What if the sequencer adjusts that value? Would it make sense to have a GetSequencerConfig for initialization? I don’t know if there’s other pertinent information the rollup might need to be aware of but ideally, less the better..

3. The Espresso Docs mentions the use of a subscribe model for rollup nodes to pick up ordered blocks that have been committed. I’m not sure how it’s done atm. But, the choice between push - pull certainly is an implementation detail for sequencers. So, I feel it makes sense to support both models. Though if I were to pick one, the subscribe model feels more natural. Is this interface compatible with both?

4. Would a user interact directly with sequencers via BroadcastMetaTxs? Or, it it more likely there is a RPC / client as the entry point?

5. Is there a distinction between header producer and executor? Maybe it makes sense to pick one term - executor seems to be generally used by other teams.

Overall, I like the simplicity of the interface. Lends itself to iteration nicely.

[nashqueue]

Thank you for the questions and comments:

1. RetrieveBatch gets you a proof that the Sequencer sequenced it. The soft commitment is the fastest you can go. I think Astria is aiming for 2 2-second block time, so you would get a 6x improvement from the 12-second block time that Celestia provides, for example.
2. Yes, either you can query repeatedly, or you have it pushed based. The Rollup block time can be derived for convenience from the sequencer block time or a multiple of that. But you can also make it asynchronous to the sequencer. Depends on the implementation.
3. This Interface currently only supports pull as the naive way. A subscription should be a worthwhile addition down the line.
4. It is either the mempool of the p2p sequencer network or through an rpc if the user is not running a node.
5. I agree, Executor will probably prevail as a term. They are the same thing.