State-root and batch submission to L1

[protolambda]

Sequencer interactions with L1 in the 1.0 spec need to be integrated with existing infra well and with minimal risk. The systems team already implemented similar Go functionality, and so we should integrate their insights/work in the reference 1.0 spec and implementation.

This relates to the following milestones / features:

• Proposer state root commitment: the state-root of each L2 block (or in 1.0: of the end of each sequencing window) should be submitted to L1.
  • Withdrawals will depend on this as well.
• Batch submission: sequencer data needs to become available on L1

Before we can complete the above state/batch submission design, we need to address the dependencies (not part of deposit rollup):

• Spec commitment: Instead of state-roots, submit a merkleized ExecutionPayload (eth2 SSZ type of eth1 block structure with nice merkle properties), possibly mixing in other useful commitments to shorten proof length (e.g. hash(hash_tree_root(exec_payload), withdrawal_accumulator_root)
• Sequencer blocks need to be defined/implemented before we can submit the sequencer data
• Sequencer windows need to be defined before the state-roots can be posted to L1 with the correct frequency etc.

@tynes can you help outline what the system team has already implemented, what you think is critical, and what we can improve in the 1.0 upgrade?

[tynes]

Overview

The current batch-submitter is responsible for making the L2 data (transactions) and state commitments (merkle roots) available. It does this by sending transactions to a particular L1 contract. Validating nodes can listen for events emitted from this L1 contract to locate the data. This data can then be executed, and the results of the execution can be compared against the state commitments. When the computed state does not equal the proposed state, a fault proof can be executed to punish the sequencer.

Existing Implementations

There are currently 2 implementations:

• Go
• Typescript

The Typescript implementation is currently the production ready implementation, but work is ongoing to switch to the Go rewrite.

General Considerations

• Security of the funds
  • The existing batch submitter holds a hot key that has a lot of ETH in it and the implementation does not support sending from a multisig. Threshold ecdsa could help here, but is relatively unproven cryptography. The batch submitter needs to be refilled pretty consistently, is there an alternative design where the funds can be held in a smart contract wallet instead of an EOA?
• Gas costs
  • Any savings in costs of the batch submission process can be passed onto users, meaning cheaper fees for users
• Statelessness
  • The existing batch submitter is stateless, it can look at L1 and determine what the next batch to submit is. This is a very nice property as the batch submitter does not need to scan and index L1 to know what to do next

How it works

The batch-submitter is split up into 2 components. One is responsible for submitting transaction batches while the other is responsible for submitting state root batches. It is recommended that these components use different private keys as to not run into nonce issues when both components are sending transactions concurrently.

Transaction Batch Submitter

• Fetch the total number of transactions that have been batched up so far from the CTC - link
• Fetch the total number of transactions in L2, which is currently the block height because there is a single transaction per block - link
• For each transaction that has not been batched up to L1 so far, fetch it - link
• Serialize the batch - link
• Submit the transaction to the CTC

Considerations for 1.0

• Will the batch submitter be able to keep track of the total number of transactions that have been posted to L1 so far?
• Can the state commitment be easily fetched via JSON-RPC?
• Do we change the transaction batch serialization?
  • If RLP encoded transactions are not used, then forwards compatibility becomes a problem
  • Custom encoding could save calldata size, but if not designed thoughtfully, can break functionality
  • Should we have a batch header to allow for a version bit/compression algo?
  • What compression algo should we use?

State Root Batch Submitter

• Fetch the total number of state roots that have been submitted so far - link
• Fetch the number of transactions that have been batch submitted so far - link
• For each state root that hasn't been submitted so far, fetch it - link
• Serialize the state roots into a batch - link
• Submit the transaction to the SCC

Considerations for 1.0

• It would be ideal to have the end of the sequencer window be guaranteed to be a state root that is included in a block header (post block state) for API simplicity
• Is it possible to fetch intermediate state roots with the debug_traceBlock endpoint or another way? I don't think so, might need to implement this functionality in upstream for the binary search
• What should the batch serialization look like? It should enable a stateless batch submitter

Questions

• There has been talk about simply using an EOA that sends txs to itself/nowhere for batch submission and never calling a smart contract. How is this safe?

[ben-chain]

Comments on the OP:

Spec commitment

I think this is one of the most important parts to decide on and I like both of the suggestions. I think a withdrawal_accumulator_root is absolutely the most important, as it would allow us to minimize withdrawal costs which are currently very high (500k). We could amortize some of that cost with batching at the application/contract layer, but it's never going to get as cheap as something native. The only alternative I could see is running a different cannon program on the finalized payloads. I'm dubious that that would actually be cleaner, but it could theoretically minimize geth diff by shifting the calculation of the root to a different package.

Note also that committing ExecutionPayload in an ETH2 serialization format will require that we can run the serialization in cannon. I'm sure we can, but should be de-risked.

the state-root of each L2 block (or in 1.0: of the end of each sequencing window) should be submitted to L1

nit: the sequencing window is a parameter that has to do with ordering rights; the frequency on which the dispute game finalizes new state roots to L1 can be different. See Karl's writeup here.

[ben-chain]

comments on @tynes 's post:

WRT the multisig/fund security, what is the concrete security improvement you're looking for? Is the idea to run multiple batch submitters, which have to agree, but are run in different environments so that it is harder to hack all of them than any 1? Also seems like it would increase gas costs without the threshold crypto. If we just want to manually top up the batch submitter less often, I think there are ways we could do that separately from 1.0.

Do we change the transaction batch serialization?

I think this is a strong yes; we should do it however is best. The point of squash merge will be to avoid forwards compatibility issues.

It would be ideal to have the end of the sequencer window be guaranteed to be a state root that is included in a block header (post block state) for API simplicity

See nit in previous comment for why the sequencer window is not the right word here, but we can absolutely take this as a given. It's actually not even decided that it will be a state root (vs. a full blockhash or something else -- this is the Specify commitment section in the OP), but I think exposing whatever it is as an API would surely be the right path.

[protolambda]

Note also that committing ExecutionPayload in an ETH2 serialization format will require that we can run the serialization in cannon. I'm sure we can, but should be de-risked.

SSZ is both a serialization and merkleization format, but they are separate things. We don't need any of the serialization logic, just the merkleization. I'm maintaining 2 implementations (Python and Go), and there are many others out there, used by eth2 clients in production: ethereum/consensus-specs#2138 And there are spec-tests for that ExecutionPayload type.

I would propose some type structure like:

class OptimismCommitment(Container):
  chain_head: ChainHead
  withdrawal_tree_root: Bytes32  # Binary merkle tree accumulator root, matching type List[OptimismWithdrawal, 2**20]

class ChainHead(Container):
  state_root: Bytes32  # MPT root
  latest_payload: ExecutionPayload  # SSZ type matching an execution-layer block

class OptimismWithdrawal(Container):
  amount: uint256
  other_field: foobar
  ...

This would look like:

                          root
                /                            \
          (ChainHead)                     withdrawal_tree_root
    /                        \
state_root              latest_payload
                           /          \
                         /   \        /  
                      /  \  /  \    /  \  
                    /\  /\ /\  /\  /\  /\    (= 14 fields, thus 4 layers deep)
                   ....  the individual fields (parent_hash, fee_recipient, etc.). transactions-list is also a SSZ tree, nesting transaction leaf values deeper

So the withdrawal_tree_root is cheap to access (32 byte witness of left-hand sub-tree), the state_root is close too, and the lasted payload is there for any other usage (e.g. someone needs to read the L2 receipt_root or fee recipient data)

The withdrawal_tree_root can be the hash-tree-root of a SSZ list, e.g. List[OptimismWithdrawal, 2**20], which is a binary tree with 20 layers (= capacity of 2**20 = 1048576 items for 20*32=640 bytes of proof data, plus some bytes for the length mix-in).

After a certain amount of withdrawals it makes sense to clear the tree in some way (e.g. move it to a deeper tree for more costly retrieval), to keep the tree-depth low, and thus the call-data low (cheaper withdrawals).

If we had KZG or other fancy crypto on L1 it could have been a 48 byte withdrawal proof (flat vector commitment over all withdrawals), but 640 bytes + 20 hash calls seems nice compared to a MPT proof to the L2 account and then storage slot. And maybe there are other accumulators / parameters (10 deep binary tree and more frequent moves of old withdrawals to deeper tree?) to reduce cost further.

[norswap]

@tynes Thanks for the writeup 🙏

The batch-submitter is split up into 2 components. One is responsible for submitting transaction batches while the other is responsible for submitting state root batches.

Is there any reason the batch submitter and the state root submitted need to be coupled? Can't they be fully independant components? (I thought they were before reading this!)

Can the state commitment be easily fetched via JSON-RPC?

If submitted as calldata that can be used in proofs later, no (unless you have a proof handy, but then you're not relying solely on JSON-RPC). If they're stored in EVM storage, then yes (just eth_Call a function we made for this purpose).

We could add a JSON-RPC call to get the proofs on the L2 nodes, which can then be verified with a JSON-RPC call to L1.

This will depend on how much we feel like we need to gas-golf state submissions. Might be okay to store everything in storage.

Custom encoding could save calldata size, but if not designed thoughtfully, can break functionality

Could you speak more to the potential problems here?

The existing batch submitter is stateless, it can look at L1 and determine what the next batch to submit is. This is a very nice property as the batch submitter does not need to scan and index L1 to know what to do next

How much of an issue is it to require a backwards scan to find the latest submitted batch? The calldata of the batch submission could include some kind of running total?

I'm` also wondering how this works in a multi-sequencer world.

Is it possible to fetch intermediate state roots with the debug_traceBlock endpoint or another way? I don't think so, might need to implement this functionality in upstream for the binary search.

If you're talking about the dispute game, we'd "bisect" the execution trace (i.e. a record of all execution instructions) and the intermediate hash would be a hash of the geth program state.

There has been talk about simply using an EOA that sends txs to itself/nowhere for batch submission and never calling a smart contract. How is this safe?

If the fault proof program hardcodes the sequencer's L1 addresses (or reads them on the L1 chain), then it can process a L1 block, filter for transactions sent to the EOA from the sequencer's authorized addresses, and process these as batch submissions. What's unsafe here?

This does however preclude a stateless batch submitter.

@protolambda Love that design, it's very clean!

If we had KZG or other fancy crypto on L1 it could have been a 48 byte withdrawal proof

This could be an EIP we push for post-1.0.

[ben-chain]

WRT output (prev known as state root) submission vs. sequencer batch submission -- the more I think about these, the more I notice differences in requirements which should be considered. Notes on those just to share:

• The failure mode of a tx not being posted in time is very different (for sequencer batches it causes a reorg which will be handled by the driver, for outputs it delays withdrawals a little bit but not much else)
• The outputs submitted must be more actively tracked to play the dispute game. Once an output proposal is submitted, there is the chance for anyone to challenge it. This must all be handled by the dispute/challenge agent.

[ben-chain]

One more note on relationship between this and cannon: one input to the l2 minigeth will be the previous output commitment. Currently, cannon expects a vanilla blockhash, merklized as in L1, in main.go. So we will need to update this as well if we don't do L1 merklization.

One last consideration is whether app devs will want to read other blockdata, such as ENS, and they will want to verify it in solidity. This could be an argument for including the L1 merklization, though they probably read just MPT stateroot in the above case.