An Ethereum Node executes transactions in blocks.

Execution mutates two key data structures:

• The state, which tracks, e.g the account balance.
• The storage, which is a huge array of integers, per-account.

Ethereum nodes expose information about the transactions over RPC, e.g:

• The specific changes to the storage tries.
• Changes to account balance in the state trie.

The state execution correctness is then asserted by the zkEVM prover in evm_arithmetization, relying on starky and plonky2.

Prover perfomance is a high priority.

The aformentioned data structures are represented as tries, which may have subtries hashed out. That is, any node (and its children!) may be replaced by its hash, while maintaining provability of its contents:

    A               A
   / \             / \
  B   C     ->    H   C
 / \   \               \
D   E   F               F

(where H is the hash of the D/B\E subtrie).

The principle concern of this module is to step through the transactions, and reproduce the intermediate tries, while hashing out all possible subtries to minimise prover load (since prover performance is sensitive to the size of the trie). The prover can therefore prove each batch of transactions independently.

Non-goals

• Performance - this will never be the bottleneck in any proving stack.
• Robustness - this library depends on other libraries that are not robust, so may panic at any time.