Author: Shew & Noah, Xianrang GodRealmX

As we all know, fraud proof is a technical solution that is widely used in the blockchain field. It first originated in 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 with logic gate circuits as the basis, to later BitVM2 with ZK Fraud Proof and Groth16 verification circuits as the core, the technical implementation paths related to BitVM are constantly evolving and maturing, attracting the attention of many practitioners. The projects such as Bitlayer, Citrea, BOB, Fiamma and GoatNetwork that everyone has heard of are all based on BitVM, and have implemented different versions on this basis.

In view of the fact that the system interpretation of BitVM is relatively scarce and obscure on the market, we have launched a series of articles with the purpose of popularizing BitVM knowledge. Considering the deep-rooted relationship between BitVM and fraud proof, this article will focus on fraud proof and ZK Fraud Proof as the main topics, and interpret it in the language as easy to understand as possible.

We will use Optimism's fraud proof solution as material to analyze its solution based on MIPS virtual machines and interactive fraud proof, as well as the main ideas of ZK-based fraud proof.

(The principle of the mechanism of Optimism interactive fraud proof)

OutputRoot and StateRoot

Optimism is a well-known Optimistic Rollup project with infrastructure consisting of sequencers (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, these 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 locally. After that, you can execute these transactions locally and calculate the current status set of Optimism (including but not limited to the current balance of each account and other data).

If the sequencer uploads the wrong status set hash to Ethereum, then the status set hash you calculate locally will be different from it. At this time, you can initiate a question through fraud proof system, and the system will restrict or punish or not punish the sequencer based on the judgment result.

When mentioning the term "state set", EVM blockchains often use Merkle Tree-like data structures to record state sets, called World State Trie. After a transaction is executed, the status of certain accounts will change, the World State Trie will change, and its ultimate hash will also change. Ethereum calls the final hash of World State Trie StateRoot, using it to represent changes in the state set.

The following figure shows the composition of Ethereum stateRoot. We can see the balances of different accounts in Ethereum, the code hash and other data associated with smart contract accounts will be summarized into the World State Trie, and stateRoot will be calculated based on this.

Optimism's account system and data structure are roughly consistent with Ethereum, and the StateRoot field is also used to reflect the changes in the state set. The OP sequencer regularly uploads a key field called OutputRoot to Ethereum, and the OutputRoot field is calculated by StateRoot and the other two fields.

Continue to go back to the original question. When you run the OP's node client and calculate the StateRoot locally, if you find that the result you calculated is as determined by the OPIf the results of the sequencer upload are inconsistent, fraud proof can be initiated. So what is the specific mechanism? Below we will introduce MIPS virtual machine status verification and interactive fraud proof in turn.

MIPS virtual machine and memory Merkle Tree

We mentioned earlier that 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 interaction 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 to verify the correctness of OutputRoot on the chain, the easiest way is to implement the 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 the Fault Proof Program, which is easy to implement off-chain, but it is very difficult to run on the Ethereum chain. Because there are two problems: 1. The smart contract on Ethereum cannot automatically obtain the input parameters required for fraud proof; 2. The Gas Limit of each block of Ethereum is limited and does not support excessively complex computing tasks. We cannot fully implement the OP node client on the chain

The first problem is equivalent to letting the on-chain smart contract read off-chain data, which can be solved through an oracle-like solution. OP has specially deployed the PreimageOracle contract on the Ethereum chain, and fraud proof related contracts can read the required data in PreimageOracle.

In theory, anyone can upload data to the contract at will, but the 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 used Solidity to write a MIPS virtual machine, which implemented some functions in the OP node client, which was enough for fraud proof system use. 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 the program written by Golang/Rust into a MIPS program, and then process it through the MIPS virtual machine on the Ethereum chain.

OP's development team used Golang to write the simplified program required for fraud proof, which is basically consistent with the module functions of executing transactions, generating blocks and OutputRoot in the OP node. However, this simplified program cannot be "completely executed".

In other words, each OP block contains many transactions. After the transaction is processed, an OutputRoot will be obtained. Although you know which block height has an error, it is unrealistic to prove that the corresponding OutputRoot is wrong.

In addition, the execution process of each transaction involves an orderly processing of a series of MIPS opcodes. You cannot put this series of opcodes into the MIPS virtual machine implemented by the on-chain contract to run, because the calculation overhead and Gas consumption involved are too large.

(How to work in MIPS instruction sets)

To this end, the Optimism team designed an interactive fraud proof system, with the purpose of in-depth refinement of the OP's transaction processing process. From the entire computing process of OutputRoot, when observing which MIPS opcode is processed, an error occurred in the MIPS virtual machine of the OP sequencer. 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 the OP sequencer processing transaction packaging blocks can be disassembled into an orderly processing of a huge amount of MIPS opcode. 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, it is necessary to determine which MIPS opcode is executed by the OP sequencer, and then the status of the MIPS virtual machine at that time is reproduced on the chain, and the operation code is executed, and whether the status hash after observation 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 put MThe status information of the IPS virtual machine, such as part of the memory data, is uploaded to the chain.

At the code implementation level, smart contracts 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 executed by a single MIPS opcode, such as the register status, memory status hash of the MIPS virtual machine. The schematic diagram is as follows:

We can enter the environment parameters of these MIPS virtual machines through _stateData and _proof to run a single MIPS instruction on the chain to obtain authoritative results. If the authoritative results obtained on the chain are inconsistent with the results submitted by the sequencer, it means that the sequencer is doing evil.

We generally call the hash of _stateData a state hash, which can be roughly understood as the hash of the entire MIPS virtual machine state. Within several fields of _stateData, memRoot is the most exquisite design. As we all know, a program will occupy a lot of memory during execution, and the CPU will 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 the memory address of the MIPS virtual machine.

OP uses a 32-bit architecture MIPS virtual machine, whose memory contains 2 addresses to the power of 27, which can be organized into a 28-layer binary Merkle Tree. The underlying leaves have 2 to the power of 27, and each leaf records the data in a memory address of the virtual machine. After the data in all leaves are summarized, 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 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 Merkle proof based on the memory Merkle tree to prove that the data provided by you/sequencer does exist in the memory Merkle tree, rather than fabricated out of thin air.

Interactive fraud proof

In the above, we have solved the second problem, completing the on-chain execution of the MIPS opcode and the virtual machine state verification, but how should the challenger and sequencer locate that controversial MIPS opcode instruction?

I believe many people have read more or less the simple explanation of interactive fraud proofs online, and have heard about the idea of ​​the dichotomy. The OP team developed a protocol called Fault Dispute Game (FDG), which includes two roles: Challenger and Defender.

If we find that there is a problem with the sequencer submitting to the OutputRoot on the chain, then we can act as a challenger in the FDG, and the sequencer will act as a defender. In order to facilitate the positioning of the MIPS opcodes mentioned above that need to be processed on the chain, the FDG protocol requires participants to build a Merkle tree locally called GameTree. Its specific structure is as follows:

We can see that GameTree is actually quite complex, with hierarchical nesting relationships, composed of a tree at the first level and a subtree at the second level. That is to say, the bottom leaf of the tree at the first level itself contains a tree.

We have introduced earlier that each block generated by the sequencer contains an OutputRoot, and the leaf node of the first level tree of GameTree is the OutputRoot 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 to the second level of GameTree. The second level tree is also a Merkle tree, and the bottom leaf is the MIP introduced aboveThe status of the S virtual machine hash. In the fraud proof scenario, some leaf nodes of GameTree constructed locally by the two parties will be inconsistent, and the virtual machine state hash after processing a certain opcode will show different.

After that, the two parties interacted multiple times on the chain, and finally located to a controversial place, and determined a single MIPS opcode that needed to run on the chain.

At this point, we have completed the entire process of interactive fraud proof. In summary, interactive fraud proof includes two core mechanisms: 1. FDG first locates the MIPS opcode that needs to be executed on the chain and the VM status information at this time; 2. Execute the operation code in the MIPS virtual machine implemented on the Ethereum chain to obtain the final result.

ZK-based fraud proof

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 a single instruction is reproduced on the chain. However, there are several difficulties in this solution: 1. Multiple rounds of interactions need to be triggered on the Ethereum chain, which requires almost dozens of interactions, which will incur a large amount of gas costs; 2. The process of interactive fraud proof is long, and once the interaction is started, Rollup cannot execute transactions normally; 3. It is more complicated to implement specific VMs on the chain to play instructions, and the development is extremely difficult. In order to solve these problems, Optimism officially proposed the concept of ZK Fraud Proof. The core is to specify a transaction that the challenger believes needs to be played on the chain when he/she challenges. The Rollup sequencer gives the ZK proof of the challenged transaction and is verified by a smart contract on Ethereum. If the verification is passed, it can be considered that the processing process of the transaction is not wrong and the Rollup node does not do evil.

The Challenger in the above picture isChallenger, and 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 a hash of the block. Challenger can challenge based on block hashing. After the Defender accepts the challenge, it will generate a ZK proof to prove that the block generation results are not error-free. The Bonsai in the picture above is actually a ZK Proof generation tool.

Compared with interactive fraud proof, the biggest advantage of ZK Fraud Proof is that it modifies multiple rounds of interactions into one round of ZK proof generation and on-chain verification, saving a lot of time and gas costs. Compared with ZK Rollup, OP Rollup based on ZK Fraud Proof does not need to generate proofs every time a block is generated, and only temporarily generates a ZK proof when it is challenged, which also reduces the computing cost of the Rollup node.

The idea of ​​ZK fraud proof has also been adopted by BitVM2. Project parties that use BitVM2, such as Bitlayer and Goat Network, ZKM and Fiama, implement the ZK Proof verification program through Bitcoin scripts, and greatly simplify the size of the program that needs to be chained. Due to space limitations, this article will not go into details. You can wait for our later article on BitVM2 to deeply understand its implementation path. Stay tuned!