As is well known, fraud proofs are a widely used technical solution in the blockchain space. They originated in the Ethereum community and were adopted by well-known Ethereum Layer 2 solutions such as Arbitrum and Optimism. After the rise of the Bitcoin ecosystem in 2023, Robin Linus proposed a solution called BitVM, which, based on existing Bitcoin technologies like Taproot, centers on fraud proofs and provides a new security model for Bitcoin Layer 2 or bridges.

BitVM has launched several theoretical versions, from the earliest BitVM0, which used logic gate circuits as primitives, to later versions like BitVM2, which focused on ZK Fraud Proofs and Groth16 verification circuits. The technical implementation paths related to BitVM have been evolving and maturing, attracting the attention of many industry professionals. Projects such as Bitlayer, Citrea, BOB, Fiamma, and Goat Network all use BitVM as one of their core technologies, implementing different versions based on this foundation.

Given the scarcity and complexity of publicly available explanations about BitVM, we have launched a series of articles aimed at popularizing BitVM knowledge. Considering the deep-rooted connection between BitVM and fraud proofs, this article will focus on fraud proofs and ZK Fraud Proofs, using simple and understandable language to explain these concepts.

(Principle of Optimism’s Interactive Fraud Proof Mechanism)

OutputRoot and StateRoot

Optimism is a well-known Optimistic Rollup project, and its infrastructure consists of a sequencer (with main modules including op-node, op-geth, op-batcher, and op-proposer) and smart contracts on the Ethereum chain.

After the sequencer processes a batch of transaction data, this DA data will be sent to Ethereum. As long as you are capable of running an Optimism node client, you can download the data uploaded by the sequencer to your local machine. You can then execute these transactions locally and calculate the current state set hash of Optimism (including but not limited to the current balance of each account, etc.).

If the sequencer uploads an incorrect state set hash to Ethereum, the state set hash you calculate locally will be different. In this case, you can raise a challenge through the fraud proof system. Based on the judgment, the system will either impose restrictions or penalties on the sequencer or take no action.

When mentioning the term “state set,” EVM-based blockchains commonly use a Merkle Tree-like data structure to record the state set, called the World State Trie. After a transaction is executed, the state of certain accounts will change, and the World State Trie will also change, resulting in a change to its final hash. Ethereum refers to the final hash of the World State Trie as the StateRoot, which represents the changes in the state set.

The following diagram illustrates the structure of Ethereum’s stateRoot. As we can see, the balances of different accounts, the code hash associated with smart contract accounts, and other data are all aggregated into the World State Trie, from which the stateRoot is calculated.

Optimism’s account system and data structure are generally consistent with Ethereum’s, also using the StateRoot field to represent changes in the state set. The OP sequencer periodically uploads a key field called OutputRoot to Ethereum, which is calculated based on the StateRoot and two other fields.

Returning to the initial question, when you run the OP node client and calculate the StateRoot and current OutputRoot locally, if you find that the results you calculated do not match the ones uploaded by the OP sequencer, you can initiate a fraud proof. So, what is the specific mechanism behind this? Below, we will sequentially introduce MIPS virtual machine state verification and interactive fraud proofs.

MIPS Virtual Machine and Memory Merkle Tree

As mentioned earlier, suppose you find that the OutputRoot submitted by the OP sequencer is incorrect, and you want to initiate a “challenge.” The challenge process requires completing a series of interactions on-chain, after which the relevant smart contracts will determine whether the OP sequencer uploaded an incorrect OutputRoot.

To verify the correctness of the OutputRoot on-chain using smart contracts, the simplest method would be to implement an OP node client on the Ethereum chain, using the same input parameters as the OP sequencer, executing the same program, and checking whether the calculated result matches. This approach is called a Fault Proof Program. While it is relatively easy to implement off-chain, it is very difficult to run on the Ethereum chain due to two issues:

1. Smart contracts on Ethereum cannot automatically obtain the input parameters needed for fraud proofs.

2. Ethereum’s block gas limit is limited, and it does not support highly complex computational tasks. Thus, we cannot fully implement the OP node client on-chain.

The first issue is equivalent to requiring the on-chain smart contract to read off-chain data, which can be solved using a solution similar to an oracle. OP has deployed the PreimageOracle contract on the Ethereum chain, and fraud-proof related contracts can read the necessary data from this contract. Theoretically, anyone can upload data to this contract, but OP’s fraud proof system has a way to verify whether the data is required, though this process will not be elaborated here, as it is not crucial to the core topic of this article.

For the second issue, the OP development team wrote a MIPS virtual machine in Solidity to implement some of the functions of the OP node client that are sufficient for the fraud proof system. MIPS is a common CPU instruction set architecture, and the OP sequencer’s code is written in higher-level languages like Golang/Rust. We can compile the Golang/Rust programs into MIPS programs and process them through the MIPS virtual machine on the Ethereum chain.

The OP development team wrote a simplified program in Golang for the fraud proof, which essentially mimics the modules in the OP node that execute transactions, generate blocks, and produce the OutputRoot. However, this simplified program still cannot “execute completely.” In other words, each OP block contains many transactions. After processing this batch of transactions, an OutputRoot is generated. While you know which block height’s OutputRoot is incorrect, it would be unrealistic to run all the transactions in that block on-chain to prove that the corresponding OutputRoot is wrong. Furthermore, during the execution of each transaction, a series of MIPS opcodes are processed in sequence. It would be impractical to run this entire series of opcodes on the MIPS virtual machine implemented in an on-chain contract, as the computational overhead and gas consumption would be too large.

(MIPS Instruction Set Working Principle)

To address this, the Optimism team designed an interactive fraud-proof system aimed at deeply analyzing the transaction processing flow of OP. By observing the entire calculation process of the OutputRoot, the system identifies at which MIPS opcode the OP sequencer’s MIPS virtual machine made an error. If an error is confirmed, it can be concluded that the OutputRoot provided by the sequencer is invalid.

Thus, the issue becomes clear: the process of OP sequencer packaging transactions into blocks can be broken down into the ordered processing of a large number of MIPS opcodes. After each MIPS opcode is executed, the virtual machine’s state hash changes. These records can be aggregated into a Merkle tree.

In the interactive fraud-proof process, the goal is to determine after which MIPS opcode the OP sequencer’s virtual machine state hash became incorrect, and then reproduce the state of the MIPS virtual machine on-chain, executing the opcode and observing whether the resulting state hash matches the one submitted by the sequencer. Since only one MIPS opcode is executed on-chain, the complexity is low and the calculation process can be completed on the Ethereum chain. However, to achieve this, we need to upload the MIPS virtual machine’s state information, such as partial memory data, to the chain.

In terms of code implementation, the smart contracts on the Ethereum chain related to fraud-proof will complete the final MIPS opcode execution process through a function called Step:

The parameters in the above function, _stateData and _proof, represent the dependent data items for the execution of a single MIPS opcode, such as the MIPS virtual machine’s register state, memory state hash, etc. The diagram is shown below:

We can input these MIPS virtual machine environment parameters through _stateData and _proof, run a single MIPS instruction on-chain, and obtain an authoritative result. If the authoritative result obtained on-chain differs from the result submitted by the sequencer, it indicates that the sequencer is malicious.

We generally refer to the hash of _stateData as statehash, which can be roughly understood as the hash of the entire MIPS virtual machine state. Among the several fields in _stateData, memRoot is the most ingenious design. As we know, during the execution of a program, a large amount of memory is used, and the CPU interacts with data in certain memory addresses by reading and writing. Therefore, when we execute a MIPS opcode on-chain through the VM.Step function, we need to provide data from certain memory addresses in the MIPS virtual machine.

OP uses a 32-bit architecture for the MIPS virtual machine, and its memory contains 2^27 addresses, which can be organized into a 28-level binary Merkle Tree. The leaf nodes at the lowest level number 2^27, with each leaf recording the data from a specific memory address of the virtual machine. The hash calculated from all the data in the leaves is memRoot. The diagram below shows the structure of the Merkle tree that records the MIPS virtual machine memory data:

We need to provide the content from certain memory addresses, and this content is uploaded to the Ethereum chain through the _proof field in the step function. Additionally, a Merkle proof based on the memory Merkle tree must be uploaded to prove that the data you (or the sequencer) provided indeed exists in the memory Merkle tree, rather than being fabricated.

Interactive Fraud Proof

In the previous section, we addressed the second issue by completing the on-chain execution of MIPS opcodes and virtual machine state verification. But how can the challenger and the sequencer pinpoint the specific disputed MIPS opcode instruction?

Many people may have read simple explanations of interactive fraud proofs online and heard about the binary search approach behind them. The OP team has developed a protocol called the Fault Dispute Game (FDG). The FDG protocol includes two roles: the challenger and the defender.

If we find that the OutputRoot submitted by the sequencer on-chain is incorrect, we can act as the challenger in the FDG, with the sequencer acting as the defender. To help locate the MIPS opcode that needs to be processed on-chain, the FDG protocol requires participants to locally construct a Merkle tree called the GameTree, whose specific structure is as follows:

We can see that the GameTree is quite complex, with a hierarchical nested structure, consisting of a first-level tree and second-level subtrees. In other words, the leaf nodes of the first-level tree contain a subtree.

As mentioned earlier, each block generated by the sequencer contains an OutputRoot, and the leaf nodes of the first-level tree in the GameTree represent the OutputRoots of different blocks. The challenger and the defender need to interact within the Merkle tree formed by the OutputRoots to determine which block’s OutputRoot is in dispute.

Once the disputed block is identified, we dive into the second level of the GameTree. The second-level tree is also a Merkle tree, with its leaf nodes being the state hashes of the MIPS virtual machine, as introduced earlier. In the fraud proof scenario, the challenger and the defender will have inconsistencies in the leaf nodes of the GameTree they construct locally. The state hash after processing a particular opcode will differ.

After multiple interactions on-chain, the parties ultimately pinpoint the exact disputed opcode, determining the specific MIPS opcode that needs to be run on-chain.

At this point, we have completed the entire process of interactive fraud proof. To summarize, the two core mechanisms of interactive fraud proof are:

1. The FDG (Fault Dispute Game) first locates the MIPS opcode that needs to be executed on-chain, along with the VM state information at that point in time;

2. The MIPS virtual machine implemented on the Ethereum chain executes the opcode, yielding the final result.

ZK Fraud Proof

ZK Fraud Proof As we can see, the traditional fraud proof approach involves very complex interactions, requiring multiple rounds of interaction in the FDG process and replaying individual instructions on-chain. However, this solution has several challenges:

Multiple rounds of interaction need to be triggered on the Ethereum chain, resulting in tens of interactions that incur significant gas costs. 2. The interactive fraud proof process takes a long time, and once the interaction starts, the Rollup cannot process transactions normally. 3. Implementing a specific VM on-chain to replay instructions is quite complex, with high development difficulty.

To address these issues, Optimism introduced the concept of ZK Fraud Proof. The core idea is that when a challenger raises a challenge, they specify the transaction they believe needs to be replayed on-chain. The Rollup sequencer provides a ZK proof for the challenged transaction, which is then verified by a smart contract on the Ethereum chain. If the verification is successful, it is concluded that there were no errors in processing the transaction, and the Rollup node is not at fault.

In the diagram, the Challenger refers to the party that raises the challenge, and the Defender is the OP sequencer. Under normal circumstances, the OP sequencer generates blocks based on received transactions and submits the state commitments of different blocks to Ethereum. These state commitments can be simply seen as the hash values of the blocks. The Challenger can challenge based on the block hash. After accepting the challenge, the Defender generates a ZK proof to demonstrate that the block generation results are correct. In the diagram, Bonsai is actually a ZK proof generation tool. Compared to interactive fraud proofs, the biggest advantage of ZK Fraud Proof is that it replaces multiple rounds of interaction with a single round of ZK proof generation and on-chain verification. This significantly saves time and reduces gas costs. Furthermore, unlike ZK Rollups, OP Rollups based on ZK Fraud Proof do not require generating proofs every time a block is produced. Instead, they only generate a ZK proof temporarily when challenged, which also reduces the computational costs for Rollup nodes.

The concept of ZK Fraud Proof is also adopted by BitVM2. Projects using BitVM2, such as Bitlayer, Goat Network, ZKM, and Fiama, implement the ZK Proof verification program through Bitcoin scripts, significantly simplifying the size of the programs that need to be brought on-chain. Due to space limitations, this article will not go into further detail on this topic. Stay tuned for our upcoming article on BitVM2 to gain a deeper understanding of its implementation path!

Disclaimer:

1. This article is reproduced from [GodRealmX], the copyright belongs to the original author [Shew & Noah], if you have any objections to the reprint, please contact the Gate Learn team, and the team will handle it as soon as possible according to relevant procedures.

2. Disclaimer: The views and opinions expressed in this article represent only the author’s personal views and do not constitute any investment advice.

3. Other language versions of the article are translated by the Gate Learn team and are not mentioned in Gate.io, the translated article may not be reproduced, distributed or plagiarized.