State Commitment

Intro

We look for a data structure to commit the Ethereum State Trie equivalent.

In Eth1: State Trie is a Merkle Patricia Trie

properties:
- State Trie items are constantly updating
- Need collision resistence so that people cannot create a different state leaf to print money out of air.
options:
- x-nary tree with poseidon hash

A state in the vector is

State {
    Nonce            254 bits
    Balance          254 bits
    StorageCommit    
    CodeCommit       
}

CodeCommit is the commitment of the bytecode.

In Eth1: CodeHash is keccak256 of the bytecode
property: CodeCommit requires no updates
options:
- do we have the use case that we want to split in chunks and open only part of the whole bytecode?
  - yes: polynomial commitment [plookup table index map to opcodes] (when to do randomness?)

We want to construct indexed opcode like this

t_opcodes = [0add, 1mul, 2jump, 3add, 4mul, 5jumpdest, 6term]

We index the opcode with 2 bytes, since the max code size is bounded by 0x6000 per EIP 170^[1]. Opcode can be represented in 1 byte.

t_opcodes = [0x000001, 0x000102, 0x000256, 0x000301, 0x000402, 0x00055B, 0x0006F3]

replaced the last one with RETURN. The code is used for demonstration of encoding and it does not make sense.

t_opcodes can then be encoded/serialized.

In Eth1: storageTrie is the root of the storageTrie

128 level deep binary tree using poseiden hash

too shallow: risk colliding hashes in a slot
too deep: more cost of witness
Max SLOAD people can do in a eth1 block: 5770.
- SLOAD post Berlin 2600 (Cold sload gas cost).
- assuming 15M block gas limit
Max SLOAD in the circuit: 1580.
- poseiden 166 con/hash at 128 level deep tree at 2^25 constraints
property: storage is constantly updating