ZK Fraud Proofs
Overview
Fraud proofs are retroactive disputes submitted by validators to contest the validity of a state update. They prove that fraud was committed at a certain transaction and state transition.
Traditional optimistic rollups make use of interactive fraud proofs that simulate state transitions directly on-chain. This is both inefficient, and unsafe. Inefficient because the process of submitting interactions between prover and verifier is extremely time and compute costly on Ethereum. This method of proving leads to the long 7 day withdrawal periods1. Second, the engineering overhead of making sure that the simulated execution on-chain is exactly the same as the off-chain execution environment is extremely burdensome, and can introduce subtle attack vectors2.
Layer N solves these problems by introducing a novel zero-knowledge based fraud-proving mechanism.
The process for a verifier detecting and reporting fraud on Layer N is as follows:
Replay
Verifier replays state on local machine after reading transaction level data posted on data availability layer;
Detection
Verifier detects that state root update posted to Ethereum does not match the state root that is obtained from DA replay;
Initiate verification process
Verifier calls fault proof contract on Ethereum to freeze the deposits and withdrawals on the rollup, and posts a significant stake;
Proof generation
The Ethereum contract now initiates a dispute period during which the verifier runs the state simulation on a zero-knowledge virtual machine, that returns a cryptographic receipt as a proof of fraud.
On-chain verification
The verifier then submits the receipt directly to the on-chain verifier that uses the program hash to verify the proof.
State recovery mode
If this proof is submitted to the contract and it proves fraud, the Ethereum contract will go into state recovery mode.
Implementation
We use RISC Zero for exposition, but any sufficiently-close alternative such as SP1 and Jolt work equivalently well. Our implementation is equally portable to all options, which the choice being primarily contingent on performance.
The guest program to prove receives the following inputs:
- The byte payload of the message to execute.
- A partial state of the storage for all storage accesses needed to execute the message as a Merkle tree, with the leaves being provided for any storage access needed by the action, and otherwise hash commitments for all other branches as high as possible.
After executing the message, the guest provides an attestation containing:
- A commitment to the input state.
- A commitment to the output state.
- A commitment to the outbound messages.
This is sufficient construct a proof of execution of a single message. To prove a sequence of messages, note that proofs of adjacent messages can be combined by comparing the output state of one message with the input state of the one after it. With recursive proofs, we can efficiently construct proofs of sequences of messages. The attestation is then used to challenge a proposed block on the L1. Note that this proof can be used to either challenge the resulting state of the storage or the messages sent.
The obvious implementation would be to use a wasm interpreter within the prover. However, to improve performance, we directly hook into the program’s entrypoint. To do so, we write a program which uses the wasm program as a library and invokes the entrypoint of the program with the given message, with pre- and post-execution logic for computing the commitment. We additionally patch the syscalls to instead access the in-memory partial state. The resulting program is then compiled to rv32im and ran directly in the prover.