Author: Shew & Noah, Xianrang GodRealmX
As we all know, fraud proofs are a widely used technical solution in the blockchain field, originating from the Ethereum community and 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 is centered around the concept of fraud proofs. Based on existing Bitcoin technologies like Taproot, it provides a new security model for Bitcoin Layer 2 or bridges.
BitVM has released several theoretical versions, from the earliest BitVM0 based on logic gate circuits to the later BitVM2, which focuses on ZK Fraud Proof and Groth16 verification circuits. The technical implementation paths related to BitVM are continuously evolving and maturing, attracting the attention of many industry professionals. Projects such as Bitlayer, Citrea, BOB, Fiamma, and GoatNetwork are all based on BitVM as one of their technical foundations, implementing different versions on this basis.
Given the scarcity and complexity of materials explaining BitVM in the market, we have launched a series of articles aimed at popularizing knowledge about BitVM. Considering the deep-rooted relationship between BitVM and fraud proofs, this article will focus on fraud proofs and ZK Fraud Proof, using language that is as easy to understand as possible.
We will use Optimism's fraud proof solution as material to analyze its scheme based on the MIPS virtual machine and interactive fraud proofs, as well as the main ideas behind ZK fraud proofs.
OutputRoot and StateRoot
Optimism is a well-known Optimistic Rollup project, whose infrastructure consists of sequencers (main modules include 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 have the ability to run the Optimism node client, you can download the data uploaded by the sequencer to your local machine, and then you can execute these transactions locally to calculate the current state set hash of Optimism (including but not limited to the current balance of each account and other data).
If the sequencer uploads an incorrect state set hash to Ethereum, then the state set hash you calculate locally will differ from it. At this point, you can initiate a challenge through the fraud proof system, and the system will take restrictions or penalties against the sequencer based on the judgment results, or not impose any penalties.
When mentioning the term "state set," EVM-based blockchains commonly use a Merkle Tree-like data structure to record the state set, known as 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 in its final hash. Ethereum refers to the final hash of the World State Trie as StateRoot, which reflects the changes in the state set.
The following diagram shows the composition of Ethereum's stateRoot. We can see that the balances of different accounts within Ethereum, the code hashes associated with smart contract accounts, and other data will be aggregated into the World State Trie, from which the stateRoot is calculated.
The account system and data structure of Optimism are roughly consistent with Ethereum, also using the StateRoot field to reflect changes in the state set. The OP sequencer periodically uploads a key field called OutputRoot to Ethereum, which is calculated from the StateRoot and two other fields.
Returning to the initial question, when you run the OP node client and calculate the StateRoot and the current OutputRoot locally, if you find that your calculated result is inconsistent with the result 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, if I find that there is an issue with the OutputRoot submitted by the OP sequencer, I can initiate a "challenge." The challenge process requires completing a series of interactive actions on-chain, and after the interaction is completed, 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 is to implement the OP node client on the Ethereum chain, using the same input parameters as the OP sequencer, executing the same program, and checking whether the calculation results are consistent. This solution is called the Fault Proof Program, which is easy to implement off-chain but very difficult to run on the Ethereum chain due to two issues:
Smart contracts on Ethereum cannot automatically obtain the input parameters required for fraud proofs;
Each block on Ethereum has a limited Gas Limit, which does not support overly complex computational tasks, making it impossible to fully implement the OP node client on-chain.
The first issue is equivalent to allowing on-chain smart contracts to read off-chain data, which can be solved through oracle-like solutions. OP has specifically deployed a PreimageOracle contract on the Ethereum chain, allowing fraud proof-related contracts to read the required data from the PreimageOracle.
In theory, anyone can upload data to this contract at will, but OP's fraud proof system has a way to identify whether the data is what it needs. The specific process will not be elaborated here, as it is not important to the core topic of this article.
For the second issue, the OP development team wrote a MIPS virtual machine in Solidity, implementing part of the functionality needed for the OP node client, sufficient for the fraud proof system. MIPS is a common CPU instruction set architecture, and the code of the OP sequencer is written in high-level languages such as Golang/Rust. We can compile programs written in Golang/Rust into MIPS programs and then process them through the MIPS virtual machine on the Ethereum chain.
The OP development team wrote the most simplified program required for fraud proofs in Golang, which is basically consistent with the functionality of executing transactions, generating blocks, and OutputRoot in the OP node. However, this simplified program still cannot "fully execute."
In other words, each OP block contains many transactions, and after processing this batch of transactions, an OutputRoot is obtained. Although you know which block height has an incorrect OutputRoot, it is unrealistic to run all the transactions contained in that block on-chain to prove that the corresponding OutputRoot is wrong.
Moreover, the execution process of each transaction involves a series of ordered processing of MIPS opcodes, and you cannot run this entire sequence of opcodes in the MIPS virtual machine implemented in the on-chain contract, as the computational overhead and Gas consumption would be too high.
To address this, the Optimism team designed an interactive fraud proof system aimed at deeply refining the transaction processing flow of OP. From the entire calculation process of OutputRoot, it observes which MIPS opcode the OP sequencer's MIPS virtual machine made an error while processing. If an error is confirmed, it can be concluded that the OutputRoot provided by the sequencer is invalid.
Thus, the question becomes clear: the process of the OP sequencer processing transaction-packed blocks can be broken down into the ordered processing of a large number of MIPS opcodes. After executing each MIPS opcode, the state hash of the virtual machine will change, and these records can be aggregated into a Merkle tree.
In the interactive fraud proof process, it is necessary to determine after which MIPS opcode the state hash of the virtual machine went wrong during the execution by the OP sequencer, and then reproduce the state of the MIPS virtual machine on-chain, execute the opcode, and observe whether the subsequent state hash is consistent with the result submitted by the sequencer. Since only one MIPS opcode is executed on-chain, the complexity is not high, and the calculation process can be completed on the Ethereum chain. However, to achieve this, we need to upload the state information of the MIPS virtual machine, such as part of the memory data, to the chain.
At the code implementation level, the smart contracts related to fraud proofs on the Ethereum chain will complete the final MIPS opcode execution process through the following function called Step:
The parameters in the above function, _stateData and _proof, represent the dependent data items for executing a single MIPS opcode, such as the state of the MIPS virtual machine's registers, memory state hash, etc. The schematic diagram is as follows:
We can input the environmental parameters of the MIPS virtual machine through _stateData and _proof to run a single MIPS instruction on-chain and obtain an authoritative result. If the authoritative result obtained on-chain is inconsistent with the result submitted by the sequencer, it indicates that the sequencer has acted maliciously.
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, a program occupies a large amount of memory during execution, and the CPU interacts with data in certain memory addresses for reading and writing. Therefore, when we execute a certain MIPS opcode on-chain through the VM.Step function, we need to provide data from certain memory addresses of the MIPS virtual machine.
OP uses a 32-bit architecture MIPS virtual machine, which has a total of 2^27 addresses in its memory, organized into a 28-layer binary Merkle Tree, with 2^27 leaves at the bottom, each recording data from a memory address of the virtual machine. The hash calculated from the aggregated data of all leaves is memRoot. The following diagram shows the structure of the Merkle tree that records the memory data of the MIPS virtual machine:
We need to provide the contents of certain memory addresses, which are 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/the sequencer provided indeed exists in the memory Merkle tree and is not fabricated.
Interactive Fraud Proof
In the previous text, we have resolved the second issue, completing the on-chain execution of the MIPS opcode and the verification of the virtual machine state. But how do the challenger and the sequencer locate the disputed MIPS opcode instruction?
Many people may have read simple explanations of interactive fraud proofs online and have heard about its binary search approach. The OP team developed a protocol called the Fault Dispute Game (FDG), which includes two roles: the challenger and the defender.
If we find that the OutputRoot submitted by the sequencer to the chain has issues, we can act as the challenger in the FDG, while the sequencer will act as the defender. To facilitate the identification of the MIPS opcode that needs to be processed on-chain, the FDG protocol requires participants to locally construct a Merkle tree called GameTree, whose specific structure is as follows:
We can see that the GameTree is quite complex, with a hierarchical nested relationship, consisting of a first-level tree and second-level subtrees. In other words, the leaves of the first-level tree themselves contain a tree.
As mentioned earlier, each block generated by the sequencer contains an OutputRoot, and the leaves of the first-level tree of the GameTree are the OutputRoots of different blocks. The challenger and defender need to interact within the Merkle tree formed by the OutputRoots to determine which block's OutputRoot is disputed.
Once the disputed block is identified, we will dive into the second level of the GameTree. The second-level tree is also a Merkle tree, with the bottom leaves being the state hashes of the MIPS virtual machine introduced earlier. In the fraud proof scenario, the leaves of the GameTree constructed locally by both parties will be inconsistent, and the state hash of the virtual machine after processing a certain opcode will show differences.
Subsequently, both parties will interact multiple times on-chain, ultimately pinpointing the disputed area and determining the single MIPS opcode that needs to be executed on-chain.
At this point, we have completed the entire process of interactive fraud proof. In summary, interactive fraud proof includes two core mechanisms:
FDG first locates the MIPS opcode that needs to be executed on-chain and the current VM state information;
The opcode is executed in the MIPS virtual machine implemented on the Ethereum chain to obtain the final result.
ZK Fraud Proof
We can see that the traditional interactive fraud proof process is extremely complex, requiring multiple rounds of interaction in the FDG process and then replaying a single instruction on-chain. However, this solution has several challenges:
Multiple rounds of interaction need to be triggered on the Ethereum chain, requiring dozens of interactions, which incurs a large amount of gas costs;
The process of interactive fraud proof is lengthy, and once the interaction starts, the Rollup cannot execute transactions normally;
Implementing a specific VM on-chain to replay instructions is quite complex and has a high development difficulty.
To address these issues, the Optimism team proposed the concept of ZK Fraud Proof. The core idea is that when the challenger initiates a challenge, they specify a transaction they believe needs to be replayed on-chain. The Rollup sequencer provides a ZK proof for the challenged transaction, which is verified by smart contracts on Ethereum. If the verification passes, it can be considered that the processing flow of the transaction is correct, and the Rollup node has not acted maliciously.
In the above image, the Challenger is the challenger, while the Defender is the OP sequencer. Under normal circumstances, the OP sequencer generates blocks based on the received transactions and submits the state commitments of different blocks to Ethereum, which can be simply viewed as the hash value of the block. The Challenger can challenge based on the block hash. After accepting the challenge, the Defender will generate a ZK proof to demonstrate that the block generation result is correct. The Bonsai in the image is actually a ZK Proof generation tool.
Compared to interactive fraud proofs, the greatest advantage of ZK Fraud Proof is that it modifies multiple rounds of interaction into a single round of ZK proof generation and on-chain verification, saving a significant amount of time and gas costs. Additionally, unlike ZK Rollup, the OP Rollup based on ZK Fraud Proof does not need to generate proofs for every block; it only generates a ZK proof temporarily when challenged, which also reduces the computational costs for Rollup nodes.
The idea of ZK Fraud Proof has also been adopted by BitVM2. Projects using BitVM2, such as Bitlayer, Goat Network, ZKM, and Fiama, implement ZK Proof verification programs through Bitcoin scripts and have greatly simplified the size of programs that need to be on-chain. Due to space limitations, this article will not elaborate further; please look forward to our upcoming article on BitVM2 for a deeper understanding of its implementation path!
免责声明：本文章仅代表作者个人观点，不代表本平台的立场和观点。本文章仅供信息分享，不构成对任何人的任何投资建议。用户与作者之间的任何争议，与本平台无关。如网页中刊载的文章或图片涉及侵权，请提供相关的权利证明和身份证明发送邮件到support@aicoin.com，本平台相关工作人员将会进行核查。
