Fraud Proof and the Implementation Idea of ZK Fraud Proof

Fraud proof is a widely used technical solution in the blockchain field, originating from the Ethereum community and adopted by Layer 2 solutions such as Arbitrum and Optimism. After the rise of the Bitcoin ecosystem in 2023, Robin Linus proposed the BitVM solution, which centers around fraud proof and provides a new security model for Bitcoin Layer 2 or bridges.

BitVM has undergone multiple version evolutions, from the early logic gate circuit solutions to the later ZK fraud proof solutions. Several projects such as Bitlayer, Citrea, BOB, etc., have implemented different versions based on BitVM technology.

This article will take the fraud proof scheme of Optimism as an example to analyze its implementation based on the MIPS virtual machine and interactive fraud proof, as well as the idea of ZK-based fraud proof.

OutputRoot and StateRoot

The infrastructure of Optimism includes sequencers and smart contracts on the Ethereum chain. After processing transactions, the sequencer sends the DA data to Ethereum. Anyone can run an Optimism node, download data, and execute transactions locally to calculate the current state set hash.

If the sequencer uploads an incorrect state set hash, the local computation results will differ, and at this point, a fraud proof challenge can be initiated.

Optimism uses a StateRoot field similar to Ethereum to represent the changes in the state set. The sequencer regularly uploads the OutputRoot to Ethereum, which is calculated from the StateRoot and other fields.

MIPS Virtual Machine and Memory Merkle Tree

To verify the correctness of OutputRoot on the chain, the Optimism team implemented the MIPS virtual machine using Solidity and designed an interactive fraud proof system.

The system refines the transaction processing flow into a sequence of MIPS operation codes. By observing which operation code causes the virtual machine state to error, it determines whether the OutputRoot is valid.

The state information of the MIPS virtual machine is organized into a Merkle tree. Only a single MIPS opcode needs to be executed on the chain, and it is necessary to compare whether the resulting state hash is consistent.

The memory data of the virtual machine is also organized into a 28-layer binary Merkle tree, with the root hash referred to as memRoot. When executing the opcode, it is necessary to upload part of the memory data and the Merkle proof.

Interactive fraud proof

Optimism has developed the Fault Dispute Game ( FDG ) protocol, which includes two roles: challenger and defender. Both parties need to build a GameTree locally, which includes a two-level Merkle tree:

• The leaf nodes of the first-level tree are the OutputRoots of different blocks.
• The second-level leaf node is the state hash of the MIPS virtual machine.

Both parties interacted on the chain multiple times, ultimately pinpointing the disputed MIPS opcode.

The core mechanism of interactive fraud proof:

1. The opcode and VM state for FDG positioning need to be executed on-chain.
2. Execute the opcode in the on-chain MIPS virtual machine to obtain the result.

ZK Fraud Proof

Traditional interactive fraud proofs have issues such as complex interactions, high gas costs, and the pausing of Rollup execution. To address this, Optimism has proposed the concept of ZK Fraud Proofs:

• The challenger specifies the transaction to be replayed
• The Rollup sequencer generates the ZK proof for the transaction.
• Ethereum contract verification of ZK proof

Compared to interactive solutions, ZK Fraud Proof simplifies multiple rounds of interaction into a single round of ZK proof generation and verification, saving time and gas costs. Compared to ZK Rollup, it generates proofs only when challenged, reducing computational costs.

BitVM2 also adopts a similar approach, implementing ZK Proof verification through Bitcoin scripts, and has significantly streamlined the on-chain program.