Author: Shew & Noah, GodRealmX
As we all know, fraud proof is a widely used technical solution in the field of blockchain. It originated from the Ethereum community and was adopted by well-known Ethereum Layer2 such as Arbitrum and Optimism. After the rise of the Bitcoin ecosystem in 2023, Robin Linus proposed a solution called BitVM, which takes fraud proof as the core idea and provides a new security model for Bitcoin Layer 2 or bridge based on existing Bitcoin technologies such as Taproot.
BitVM has launched several theoretical versions, from the earliest BitVM0 based on logic gate circuits to the later BitVM2 based on ZK Fraud Proof and Groth16 verification circuits. The technical implementation paths related to BitVM are constantly evolving and becoming mature, attracting the attention of many practitioners. The Bitlayer, Citrea, BOB, Fiamma and GoatNetwork projects that everyone has heard of all use BitVM as one of their technical foundations and have implemented different versions on this basis.
Since there are few and obscure materials on the market that systematically explain BitVM, we have launched a series of articles to popularize BitVM knowledge. Considering the deep-rooted relationship between BitVM and fraud proofs, this article will focus on fraud proofs and ZK Fraud Proofs, and explain them in the easiest-to-understand language possible.
We will use Optimism's fraud proof scheme as material to analyze its scheme based on the MIPS virtual machine and interactive fraud proof, as well as the main ideas of ZK-based fraud proof.
OutputRoot and StateRoot
Optimism is a well-known Optimistic Rollup project whose infrastructure consists of a sequencer (the main modules include op-node, op-geth, op-batcher and op-proposer) and smart contracts on the Ethereum chain.
When the sequencer processes a batch of transaction data, the 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 computer, 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 the wrong state set hash to Ethereum, then the state set hash you calculated locally will be different. At this time, you can raise a question through the fraud proof system, and the system will restrict, punish, or not punish the sequencer based on the judgment result.
When it comes to the term "state set", EVM blockchains often use a Merkle Tree-style data structure to record state sets, called World State Trie. After a transaction is executed, the status of some accounts will change, the World State Trie will change, and its final hash will also change. Ethereum calls the final hash of the World State Trie StateRoot, which is used to represent the changes in the state set.
The figure below shows the composition of Ethereum stateRoot. We can see that the balances of different accounts in Ethereum, the code hash associated with the smart contract account and other data are aggregated into the World State Trie, and the stateRoot is calculated based on this.
Optimism's account system and its data structure are roughly consistent with Ethereum, and also use the StateRoot field to reflect changes in the state set. The OP sequencer will regularly upload a key field called OutputRoot to Ethereum, and the OutputRoot field is calculated by StateRoot and the other two fields.
Let's go back to the original question. When you run the OP's node client and calculate the StateRoot and the current OutputRoot locally, if you find that the result you calculated is inconsistent with the result uploaded by the OP sequencer, you can initiate a fraud proof. So what is the specific mechanism? Below we will introduce the MIPS virtual machine state verification and interactive fraud proof in turn.
MIPS virtual machine and memory Merkle Tree
As mentioned earlier, if I find that there is a problem with the OutputRoot submitted by the OP sequencer, I can initiate a "challenge". The challenge process requires a series of interactive actions on the chain. After the interaction is completed, the relevant smart contract will determine whether the OP sequencer has uploaded the wrong OutputRoot.
If you want to use smart contracts on the chain to verify the correctness of OutputRoot, the easiest way is to implement an OP node client on the Ethereum chain, use the same input parameters as the OP sequencer, execute the same program, and check whether the calculation results are consistent. This solution is called Fault Proof Program, which is easy to implement off-chain, but it is very difficult to run on the Ethereum chain. There are two problems:
1. Smart contracts on Ethereum cannot automatically obtain the input parameters required for fraud proof;
2. The Gas Limit of each block in Ethereum is limited, which does not support computational tasks that are too complex. We cannot fully implement the OP node client on the chain.
The first problem is equivalent to allowing the on-chain smart contract to read the off-chain data, which can be solved by a solution similar to the oracle. OP has specially deployed the PreimageOracle contract on the Ethereum chain, and the fraud proof-related contracts can read the required data in PreimageOracle.
Theoretically, anyone can upload data to the contract at will, but OP's fraud proof system has a way to identify whether the data is needed. The specific process will not be discussed here because it is not important to the core topic of this article.
For the second question, the OP development team wrote a MIPS virtual machine in Solidity, which implemented some functions in the OP node client, which is sufficient for the fraud proof system. MIPS is a common CPU instruction set architecture, and the OP sequencer code 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.
OP's development team used Golang to write the simplest program required for fraud proof, which is basically the same as the module functions of executing transactions, generating blocks and OutputRoot in OP's node. However, this simplified program still cannot be "fully executed".
That is to say, each OP block contains many transactions, and after processing this batch of transactions, an OutputRoot will be obtained. Although you know which block height has an error in the OutputRoot, it is unrealistic to put all the transactions contained in the block on the chain to prove that the corresponding OutputRoot is wrong.
In addition, the execution process of each transaction involves the orderly processing of a series of MIPS opcodes. You cannot run this series of opcodes in the MIPS virtual machine implemented by the on-chain contract because the computing overhead and gas consumption involved are too large.
To this end, the Optimism team designed an interactive fraud proof system, the purpose of which is to deeply refine the transaction processing flow of OP. From the entire calculation process of OutputRoot, it is observed that when processing which MIPS opcode, the MIPS virtual machine of the OP sequencer has an error. If it is determined that there is an error, it can be concluded that the OutputRoot provided by the sequencer is invalid.
Then the problem becomes clear: the process of OP sequencer processing transaction packaging blocks can be broken down into the orderly processing of a huge number of MIPS opcodes. After each MIPS opcode is executed, the state hash of the virtual machine will change, and these records can be summarized into a Merkle tree.
In the interactive fraud proof process, we need to determine which MIPS opcode the OP sequencer executes and the virtual machine state hash has a problem. Then, we need to reproduce the state of the MIPS virtual machine at that time on the chain, execute the opcode, and observe whether the state hash after that is consistent with the result submitted by the sequencer. Since only one MIPS opcode is executed on the chain, the complexity is not high, and the calculation process can be completed on the Ethereum chain. But to do this, we need to upload the state information of the MIPS virtual machine, such as some memory data, to the chain.
At the code implementation level, the smart contract related to fraud proof on the Ethereum chain will complete the final MIPS opcode execution process through the following function named Step:
The _stateData and _proof in the above function parameters represent the dependent data items of a single MIPS opcode execution, such as the register state of the MIPS virtual machine, the memory state hash, etc. The schematic diagram is as follows:
We can input the environment parameters of these MIPS virtual machines through _stateData and _proof, run a single MIPS instruction on the chain, and obtain the authoritative result. If the authoritative result obtained on the chain is inconsistent with the result submitted by the sequencer, it means that the sequencer is doing evil.
We generally call the hash of _stateData statehash, which can be roughly understood as the hash of the entire MIPS virtual machine state. Among the several fields of _stateData, memRoot is the most ingenious design. As we all know, a program will occupy a lot of memory during execution, and the CPU will have read and write interactions with the data in some memory addresses. So when we execute a MIPS opcode through the VM.Step function on the chain, we need to provide the data in some memory addresses of the MIPS virtual machine.
OP uses a 32-bit MIPS virtual machine, whose memory contains 2 to the power of 27 addresses, which can be organized into a 28-layer binary Merkle Tree. The bottom layer has 2 to the power of 27 leaves, and each leaf records the data in a memory address of the virtual machine. After the data in all leaves are aggregated, the calculated hash is memRoot. The following figure shows the structure of the Merkle tree that records the memory data of the MIPS virtual machine:
We need to provide a part of the content in the memory address, which is uploaded to the Ethereum chain through the _proof field in the step function. Here we also need to upload the Merkle proof based on the memory Merkle tree to prove that the data provided by you/sequencer does exist in the memory Merkle tree, and is not fabricated out of thin air.
Interactive Fraud Proofs
In the above, we have solved the second problem and completed the on-chain execution of the MIPS opcode and the verification of the virtual machine status, but how do the challenger and the sequencer locate the controversial MIPS opcode instruction?
I believe that many people have read a simple explanation of interactive fraud proofs on the Internet and have heard of its dichotomy. The OP team developed a protocol called Fault Dispute Game (FDG). In FDG, there are two roles: challenger and defender.
If we find that there is a problem with the OutputRoot submitted by the sequencer to the chain, then we can act as a challenger in FDG, and the sequencer will act as a defender. In order to facilitate the location of the MIPS opcodes mentioned above that need to be processed on the chain, the FDG protocol requires all participants to build a Merkle tree locally, called GameTree, whose specific structure is as follows:
We can see that GameTree is actually quite complex, with a hierarchical nested relationship, consisting of a first-level tree and a second-level subtree. In other words, the bottom leaf of the first-level tree itself contains a tree.
As we have introduced before, each block generated by the sequencer contains an OutputRoot, and the leaf nodes of the first-level tree of GameTree are the OutputRoots of different blocks. Challengers and defenders need to interact in the Merkle tree composed of OutputRoot to determine which block's OutputRoot is controversial.
After determining the disputed block, we will dive into the second level of GameTree. The second-level tree is also a Merkle tree, and the bottom leaf is the state hash of the MIPS virtual machine introduced above. In the fraud proof scenario, some leaf nodes of the GameTree constructed locally by the disputing parties will be inconsistent, and the virtual machine state hash will show different results after processing a certain opcode.
After that, the two parties interacted multiple times on the chain, and finally located the disputed area and determined the single MIPS opcode that needed to be run on the chain.
So far, we have completed the entire process of interactive fraud proof. In summary, interactive fraud proof contains two core mechanisms:
1. FDG first locates the MIPS opcode that needs to be executed on the chain and the VM status information at that time;
2. Execute the opcode in the MIPS virtual machine implemented on the Ethereum chain to obtain the final result.
ZK-ized Fraud Proofs
We can see that the interaction of the above traditional fraud proof is extremely complex, requiring multiple rounds of interaction in the FDG process, and then replaying a single instruction on the chain. However, this solution has several difficulties:
1. Multiple rounds of interactions need to be triggered on the Ethereum chain, which requires dozens of interactions and will incur a lot of gas costs;
2. The interactive fraud proof process is long. Once the interaction is initiated, Rollup cannot execute transactions normally.
3. Implementing a specific VM on the chain to replay instructions is relatively complex and extremely difficult to develop
In order to solve these problems, Optimism officially proposed the concept of ZK Fraud Proof. The core is that when the challenger makes a challenge, he specifies a transaction that he thinks needs to be replayed on the chain. The Rollup sequencer gives the ZK proof of the challenged transaction, which is verified by the smart contract 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 done anything malicious.
The Challenger in the above figure is the challenger, and the Defender is the OP sequencer. Under normal circumstances, the OP sequencer generates blocks based on the received transactions and submits the status commitments of different blocks to Ethereum, which can be simply regarded as the hash value of the block. The Challenger can challenge based on the block hash. After the Defender accepts the challenge, it will generate a ZK proof to prove that there is no error in the generation result of the block. The Bonsai in the above figure is actually a ZK Proof generation tool.
Compared to interactive fraud proofs, the biggest advantage of ZK Fraud Proof is that it changes multiple rounds of interactions into one round of ZK proof generation and on-chain verification, saving a lot of time and gas costs. Compared to ZK Rollup, OP Rollup based on ZK Fraud Proof does not need to generate proofs every time a block is produced, but only temporarily generates a ZK proof when challenged, which also reduces the computing cost of Rollup nodes.
The idea of ZK-based fraud proof is also adopted by BitVM2. Projects using BitVM2, such as Bitlayer, Goat Network, ZKM, Fiama, etc., use Bitcoin scripts to implement ZK Proof verification procedures and greatly simplify the size of the program that needs to be on the chain. Due to space limitations, this article will not elaborate on it. You can wait for our subsequent articles on BitVM2 to deeply understand its implementation path. Stay tuned!
