# Optional execution proofs - High level overview *Chuck Norris once generated an execution proof so fast that the verifier reached finality before the block was even proposed.* Special thanks to @kevaundray for answering my questions! :::warning **⚠️ WARNING ⚠️** **Optional execution proofs** are a rapidly evolving topic. This document may already be outdated by the time you read it. ::: :::info **INFO** Unless explicitly specified: - "State" refers to the **execution** state - "Block" refers to the **execution** block ::: ## Purpose of this document This document: 1. Describes the current state of execution-layer verification in Ethereum. 2. Briefly describes the shard chain design, which has since been abandoned. 3. Explains the path that led to the Optional execution proofs specification (EIP-8025) and (informally) demonstrates why this design is safe against various dishonest prover attacks. 4. Analyzes the new interaction model between the consensus client, the execution client, and the prover. ## Useful links - [zkevm.ethereum.foundation](https://zkevm.ethereum.foundation/) - [zkevm.fyi](https://zkevm.fyi/) - [EIP-8025](https://eips.ethereum.org/EIPS/eip-8025) - [EIP-8025 consensus specifications](https://github.com/ethereum/consensus-specs/tree/master/specs/_features/eip8025) - [EIP-8025 consensus specifications open pull requests](https://github.com/ethereum/consensus-specs/issues?q=state%3Aopen%20label%3Aeip8025) ## The problem we are trying to solve ### The current situation Ethereum is a state machine. Every Ethereum node maintains state, which is modified each time a block is applied through a state transition function (STF): ``` STF(pre_state, block) -> post_state ``` Every Ethereum node must execute this state transition function for each block to stay at the tip of the chain. Additionally, we want Ethereum nodes to remain suitable for consumer-grade hardware, which creates two constraints: 1. The STF must not take too long to execute on a consumer-grade CPU, thus limiting the number of operations per block (represented by the gas limit). 2. The state itself must not be too large, so it can fit in a consumer-grade computer. **Requiring every node in the Ethereum network to run the STF for each block hinders the network's scaling process.** ### Initial (abandoned) attempt: Multiple shard chains with a one beacon chain to rule them all Instead of requiring all nodes to execute the STF on each block, we could "divide" the chain into multiple lightweight shard chains. These shard chains would be coordinated by a single beacon chain. :::info The name "beacon chain" comes from its role in providing guidance to the sharded execution chains. The names of some beacon clients reflect this idea: - **Lighthouse**: The light guiding ships across the ocean. - **Lodestar**: The star guiding travelers through the night. - **Prysm**: A light beam (beacon chain) that, when passed through a prism, decomposes into multiple colored beams (shard chains). ![image](https://hackmd.io/_uploads/Hk6yNqwB-g.png) [*Source*](https://www.youtube.com/watch?v=g0jJax5pOeA) Other consensus clients with a non-beacon related name: - **Grandine**: The Lithuanian word for "chain". - **Nimbus**: Named after its programming language, Nim. - **Teku**: Who knows? ::: This sharding design was originally divided into multiple phases (phase0, phase1, etc.). It has since been abandoned. Only the [phase0](https://github.com/ethereum/consensus-specs/tree/master/specs) remains in the consensus specification, and star-themed names replaced the subsequent phases. ### Paradigm change: Execute once, verify many times. We want a single, (potentially powerful) node to execute the STF and generate a proof that it did so correctly. This node is called the **prover**. All other nodes (called **verifiers**) in the network need only verify that the proof is correct. They don't need to run the STF themselves. The proof should be orders of magnitude cheaper to verify than running the STF. This is where validity proofs come in. ## High-level view of ZK proofs applied to Ethereum ### General principles of ZK proofs #### The problem There is a function `f` and a result `Y`, such that for some input `X`: ``` f(X) = Y ``` Assume `f` is a CPU and memory intensive function. Now imagine two actors: a prover and a verifier. - Both the prover and the verifier know `f` and `Y`. - Only the prover knows `X`. The prover wants to convince the verifier that they know an `X` such that `f(X) = Y`, without revealing `X` itself. #### Prover's role When executing `f` with parameter `X`, the prover outputs `Y` and also generates a proof `π`. As mentioned, executing `f` is CPU and memory intensive. Moreover, generating the proof is even more computationally expensive. The prover then sends `Y` and `π` to the verifier. #### Verifier's role Instead of executing `f` with `X`, the verifier runs: ``` verify(f, Y, π) -> bool ``` Running `verify` is much cheaper than running `f` itself. If verify returns `True`, the verifier is convinced that the prover knows an `X` such that `f(X) = Y`. ### Application to Ethereum's state transition function (first attempt) Let's substitute: - The generic function `f` with the `STF` - The generic argument `X` with `pre_state, block` - The generic output `Y` with `post_state` The prover now runs `STF(pre_state, block)` and outputs `post_state` along with a proof `π`. The prover sends `π` and `post_state` to the verifier, who then only needs to run: ``` verify(STF, post_state, π) -> bool ``` If `verify` returns `True`, the verifier knows that the prover possesses a `pre_state` and a `block` such that: ``` STF(pre_state, block) -> post_state ``` :::warning ⚠️ **WARNING** ⚠️ The immediate issue here is that the prover could use any `pre_state` and any `block`, not necessarily the state corresponding to our chain after applying the latest block, and not necessarily the expected block. ::: We need to refine the formal definition of the zero-knowledge process. There is a function `f` and a result `Y`, such that for some input `X_public` and `X_private`: ``` f(X_public, X_private) = Y ``` - Both the prover and verifier know `f`, `X_public`, and `Y`. - Only the prover knows `X_private`. #### Prover's role (refined) When executing `f` with parameters `X_public` and `X_private`, the prover outputs `Y` along with a proof `π`. #### Verifier's role (refined) Instead of executing `f` with `X_public` and `X_private`, the verifier runs: ``` verify(f, X_public, Y, π) -> bool ``` If verify returns `True`, the verifier is convinced that the prover knows an `X_private` such that `f(X_public, X_private) = Y`. When applied to Ethereum's state transition function: #### Prover's role ``` STF(pre_state, block) -> post_state ``` Here, both `pre_state` and `block` are public. The prover sends `π` and `post_state` to the verifier, who then only needs to run: ``` verify(STF, pre_state, block, post_state, π) -> bool ``` If `verify` returns `True`, the verifier is now convinced that the prover correctly executed the STF with `pre_state` and `block` as parameters, producing `post_state`. This is already a huge improvement. The verifier can be convinced that `post_state` results from applying the STF to `pre_state` with `block`, without actually running the STF. :::warning ⚠️ **WARNING** ⚠️ However, with this approach, the new state must be gossiped across the network to all Ethereum nodes. This state can be quite large. While only the differences between `pre_state` and `post_state` could be transmitted to reduce bandwidth usage, there is actually a better approach. ::: ## Stateful, stateless and proving nodes ### Stateful node A stateful node is an Ethereum node as it exists today. It runs the STF for every block to compute the next state. No zero-knowledge computation is involved. A stateful node requires both a consensus client and an execution client. ### Stateless node A stateless node can stay at the tip of the chain without needing to: 1. Execute the STF 2. Maintain a copy of the state (hence "stateless") The previous design already solved point `1.`. This design also solves point `2.`. A stateless node wants to be convinced that someone (a prover) correctly executed: ``` STF(pre_state, block) -> post_state ``` **without** knowing either `pre_state` or `post_state`. In the original definition, the prover didn't want to reveal the input `X`. Here, it's actually the verifier who wants to be convinced [without knowing](https://www.youtube.com/watch?v=OLv6ycYcpGI) `X`, because `X` is too large to store. A stateless node requires only a consensus client. ### Proving node A proving node is a stateful node that, in addition to running the state transition function, generates proofs that stateless nodes will eventually use. ## The path to the specification ### The goal The verifier wants to be convinced that a prover applied `block` to `pre_state` using the STF and obtained `post_state`, without executing the STF itself. Additionally, the verifier does **not** need to store any state. ### The specification You can now explore the [specification](https://github.com/ethereum/consensus-specs/tree/master/specs/_features/eip8025), particularly the [generate_zkevm_proof](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/zkevm.md#generate_zkevm_proof) and [verify_zkevm_proof](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/zkevm.md#verify_zkevm_proof) functions. At first glance, it's probably not obvious how this specification achieves the goal outlined in the previous section. We'll now walk through it step by step, starting from the STF we already know and building toward the structure defined in the specification. ### Making `pre_state` and `post_state` private Let's modify the STF slightly: - `pre_state` is **private** (known only to the prover) - `block` is **public** (known to both the prover and the verifier) ```Python def STF(pre_state, block) -> root: post_state = process_block_header_and_transactions(pre_state, block) assert block.state_root == hash_tree_root(post_state) return block.state_root ``` The verifier (which received `block` from peers via gossip) extracts the post-state root using `block.state_root` (see [ExecutionPayload](https://github.com/ethereum/consensus-specs/blob/master/specs/deneb/beacon-chain.md#executionpayload)). If ``` verify(STF, block, block.state_root, π) = True ``` then the verifier is convinced that the prover ran ``` STF(pre_state, block) ``` and that the internal STF produced a post-state `post_state` for which ``` hash_tree_root(post_state) == block.state_root ``` ### Making `block` private The verifier needs assurance that the prover used `block` to compute the new state, but it does not actually need the full block. A commitment representing the block is sufficient. The block's hash tree root serves this purpose well. Let's modify the STF again: - `pre_state` is **private** (known only to the prover) - `block` is **private** (known only to the prover) ```Python def STF(pre_state, block) -> (root, root): post_state = process_block_header_and_transactions(pre_state, block) assert block.state_root == hash_tree_root(post_state) return block.state_root, hash_tree_root(block) ``` The verifier (which received `block` from peers via gossip) must extract the block hash via `block.block_hash`. If ``` verify(STF, block.state_root, block.block_hash, π) = True ``` then the verifier is convinced that the prover ran ``` STF(pre_state, block) ``` with the correct block, and that the STF produced a`post_state` for which ``` hash_tree_root(post_state) == block.state_root ``` ### Replacing `pre_state` with a witness Even though `pre_state` is private (known only to the prover), its size is very large (on the order of hundreds GBs for mainnet). Providing the full state to the prover would be prohibitively expensive. Instead, we use a state proof, also known as an execution witness. Geth defines the [execution witness](https://github.com/ethereum/go-ethereum/blob/494908a8523af0e67d22d7930df15787ca5776b2/core/stateless/witness.go#L36-L47) as: ```go // Witness encompasses the state required to apply a set of transactions and // derive a post state/receipt root. type Witness struct { context *types.Header // Header to which this witness belongs to, with rootHash and receiptHash zeroed out Headers []*types.Header // Past headers in reverse order (0=parent, 1=parent's-parent, etc). First *must* be set. Codes map[string]struct{} // Set of bytecodes ran or accessed State map[string]struct{} // Set of MPT state trie nodes (account and storage together) chain HeaderReader // Chain reader to convert block hash ops to header proofs lock sync.Mutex // Lock to allow concurrent state insertions } ``` The witness contains everything needed to **execute the block** and **prove the execution was correct** against the pre-state root, without requiring the full state. Let's modify the STF again: - `witness` is **private** (known only to the prover) - `block` is **private** (known only to the prover) ```Python def STF(witness, block) -> (root, root): post_state_root = process_block_header_and_transactions(witness, block) assert block.state_root == post_state_root return post_state_root, hash_tree_root(block) ``` :::warning ⚠️ **WARNING** ⚠️ Now that we have replaced the input `pre_state` with `witness`, how can the verifier be certain that the prover used the correct pre-state root when generating the witness? ::: ### Introducing the `parent_hash` The witness itself contains the block header (`context`) and the parent block header (`Headers[0]`). Let's modify the STF once more: ```Python= def STF(witness, block) -> (root, root): assert block.parent_hash == hash_tree_root(witness.Headers[0]) assert block.block_hash == hash_tree_root(witness.context) post_state_root = process_block_header_and_transactions(witness, block) assert block.state_root == post_state_root return parent_hash, block_hash ``` Note that `STF` now returns the parent hash and the block hash, rather than the post-state root and the block hash. Now, if the verifier runs: ``` verify(STF, parent_hash, block_hash, π) = True ``` then it is convinced that the prover executed the state transition function: - From the pre-state whose root is `parent.state_root`, where `parent_hash = hash_tree_root(parent)` - With the block satisfying `block_hash == hash_tree_root(block)` - Producing a new state with root `block.state_root` If the prover tries to cheat by: - using the wrong pre-state, then line `2.` will fail - using the wrong block, then line `3.` will fail - not applying correctly the block, then line `6.` will fail ### Conclusion The goal has been achieved: the verifier is now convinced that a prover applied `block` to `pre-state` using the STF and obtained `post-state`, without executing the STF itself. Additionally, the verifier does not need to store any state. Our design now matches the [generate_zkevm_proof](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/zkevm.md#generate_zkevm_proof) and [verify_zkevm_proof](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/zkevm.md#verify_zkevm_proof) signatures. ## Clients interactions. In the following diagrams: - `signedBeaconBlock` is a [SignedBeaconBlock](https://github.com/ethereum/consensus-specs/blob/master/specs/phase0/beacon-chain.md#signedbeaconblock) - `execution_payload` is an [ExecutionPayload](https://github.com/ethereum/consensus-specs/blob/master/specs/deneb/beacon-chain.md#executionpayload), obtained via `signedBeaconBlock.message.body.execution_payload`. - `executionWitness` is a [ZKExecutionWitness](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/zkevm.md#cryptographic-types) - `zkEVMProof` is a [ZKEVMProof](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/zkevm.md#zkevmproof) The following diagrams illustrate the interactions between a beacon node, its peers, its execution layer client (if any), and a prover (if any) when a beacon node receives a beacon block via gossip. ### Stateful node, as of today (Fulu) A beacon node works with an execution client, no ZK computation is involved. Link to [process_execution_payload](https://github.com/ethereum/consensus-specs/blob/master/specs/fulu/beacon-chain.md#modified-process_execution_payload). ```sequence Peers->BN: signedBeaconBlock via the \n beacon_block topic gossip Note over BN: Beacon block validation \n ... Note over BN: process_execution_payload(...) \n (first part) BN->EL: engine_newPayloadV4(execution_payload, ...) Note over EL: Execute \n STF(pre-state, block) -> post-state \n (Expensive computation) EL->BN: {status: VALID, ...} Note over BN: process_execution_payload (final part) Note over BN: ... \n Block imported ``` ### Proving node When receiving a beacon block via gossip, the beacon node, execution client, and prover generate an execution proof. This proof is then gossiped across the network. :::info **INFO** The `stateless_validation` parameter of `process_execution_payload` is set to `False`. ::: Link to modified [process_execution_payload](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/beacon-chain.md#modified-process_execution_payload). ```sequence Peers->BN: signedBeaconBlock via the \n beacon_block topic gossip Note over BN: Beacon block validation \n ... Note over BN: process_execution_payload(..., stateless_validation=False) \n (first part) BN->EL: engine_newPayloadWithWitnessV4(execution_payload, ...) Note over EL: Execute \n STF(pre-state, block) -> post-state \n (Expensive computation) \n and compute the execution witness EL->BN: {status: VALID, execution_witness: executionWitness, ...} Note over BN: process_execution_payload(..., stateless_validation=False) \n (final part) Note over BN: ... \n Block imported BN->Prover: generate_zkevm_proof(execution_payload, execution_witness, ...) Note over Prover: Generate the proof Prover->BN: zkEVMProof BN->Peers: zkEVMProof via the \n execution_proof topic gossip ``` ### Stateless node Unlike the other cases, no execution client (and no prover) is needed here. However, in addition to the beacon block, the execution proof is also required to validate the beacon block. :::info **INFO** The `stateless_validation` parameter of `process_execution_payload` is set to `True`. ::: ```sequence Peers->BN: signedBeaconBlock via the \n beacon_block topic gossip Peers->BN: zkEVMProof via the \n execution_proof topic gossip Note over BN: Beacon block validation \n ... Note over BN: process_execution_payload(..., stateless_validation=True) \n (first part) Note over BN: verify_execution_proof(zkEVMProof, parent_hash, block_hash, ...) Note over BN: process_execution_payload(..., stateless_validation=True) \n (final part) Note over BN: ... \n Block imported ``` Link to modified [process_execution_payload](https://github.com/ethereum/consensus-specs/blob/master/specs/_features/eip8025/beacon-chain.md#modified-process_execution_payload).