Evaluate including state roots in the L1Block predeploy

[maurelian]

I think we could fairly easily add an extra _stateRoot argument to the L1Block.sol contract.

Based on community input from here.

This issue is for tracking purposes. Brief comments are welcome below, for long form discussions, please open a Discussion and link back to this issue.

[protolambda]

The commitment doesn't have to be exactly the block-hash or state-root, as long as the fault proof can determine the final output. We could post the hash of the block-hash and state-root, to make either one of these simple and efficient to access (only provide 32 byte witness, instead of full header).

Generalizing this: we can post SSZ hash-tree-roots of typed data. Eth2 already defines a SSZ format for ExecutionPayload (typed structure matching the eth1-block contents that we also use in the execution-engine). As well as ExecutionPayloadHeader if you don't need the transaction data. And arbitrary merkle partials + multi-proofs are possible too.

The format is efficient and well-defined, there are implementations in many languages, and it integrates nicely with other merkle-proofs of the beacon-state that we might see after The Merge.

More about SSZ: it defines both encoding/decoding, as well as merkleization, for typed data-structures. The merkleization is a simple binary tree shape.

More resources:

• Specs: https://github.com/ethereum/consensus-specs/blob/dev/ssz/simple-serialize.md
• Visual representation of binary-tree merkleization here: https://github.com/protolambda/eth2-docs/blob/master/eth2-htr.svg
• Type definition of ExecutionPayload here: https://github.com/ethereum/consensus-specs/blob/dev/specs/bellatrix/beacon-chain.md#executionpayload

And many many implemenations: ethereum/consensus-specs#2138 (2 of which I actively maintain)

[norswap]

@protolambda Sounds great! Is there a Solidity library for SSZ proofs? I think if we go with this and it doesn't exist, we'll need to commit to make such a library available.

[protolambda]

@norswap no solidity library yet, although there is a multi-proof format that early light client implementations use (lodestar, and teku as server I believe).

The multi-proof format is simple:

• total tree size (2 bytes)
• list of left-subtree-sizes (2 bytes each)
• list of witness nodes (32 bytes each)

All subtree-sizes at any position can be determined by subtracting the left from the parent to get the right. Navigation through the proof is O(log(N)) using these offsets. And total count to the left of the node, times 32, is the offset into the witness nodes list.

More realistically though, most contracts only need specific data, and would just hardcode the specific proof decoding and not need any offsets (the tree shape is statically defined based on the type).

We could also define a SSZ type like:

class StateClaim(Container):
    state_root: Root
    block: ExecutionPayload

So e.g. your solidity might end up looking like root = hash(calldata[4:36] aka stateroot, calldata[36:68] aka HTR of block) to proof the state_root against root (the commitment on-chain).

Or root = hash(calldata[4:36], hash(hash(calldata[...], hash(calldata[...], hash(calldata of field_7, caldata[...])))), calldata[...]) if you need a proof for field index 7 from the ExecutionPayload (block field = right, then left, right, right, right = 0b0111 = 7 = gas_limit`. Or even proof a slice of transaction-data.

In this tree-encoding you basically collapse (just present the hash) all nodes that serve as witness or value, and expand every node that has children.

SSZ uses SHA-256. Some of the libraries can easily swap for KECCAK-256, but we could also just use the SHA-256 precompile to compute the merkled form.

You can find more merkle tree proofs/types/background/etc from ETH2 here: https://github.com/protolambda/eth-merkle-trees

[protolambda]

I believe this was lost because it was not linked to the project board, and not critical to the deposit rollup release. Moving this to Tender Loving Care milestone for future consideration of improvement.