BitVM Knowledge: Implementation ideas of fraud proof and ZK Fraud Proof

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 as primitives, to the later BitVM2 based on ZK Fraud Proof and Groth16 verification circuits. The technical implementation path related to BitVM is constantly evolving and maturing, attracting the attention of many practitioners. The Bitlayer, Citrea, BOB, Fiamma and Goat Network projects that everyone has heard of all use BitVM as one of their technical foundations, and have implemented different versions on this basis.

Given that the information on the market that systematically explains BitVM is relatively scarce and obscure, we have launched a series of articles aimed at popularizing BitVM knowledge. Considering the deep-rooted relationship between BitVM and fraud proofs, this article will focus on fraud proofs and ZK Fraud Proofs, and will explain them to everyone in the easiest possible language.

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

(The mechanism principle of Optimism interactive 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. 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 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 from it. At this time, you can raise a question through the fraud proof system. The system will restrict, punish or not punish the sequencer based on the judgment result.

When it comes to the term "state set", the EVM blockchain often uses a Merkle Tree-style data structure to record the state set, 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 change of 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 will be aggregated into the World State Trie, and the stateRoot will be calculated accordingly.

Optimism's account system and its 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 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 verify the correctness of OutputRoot with a smart contract on the chain, the simplest 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 scheme is called 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 in Ethereum is limited, which does not support computational tasks with high complexity, so we cannot fully implement the OP node client on the chain. The first problem is equivalent to allowing the smart contract on the chain to read the data off the chain, 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 the PreimageOracle.

In theory, 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 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.

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 the OP 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 put all these opcodes into the MIPS virtual machine implemented by the on-chain contract to run, because the computing overhead and Gas consumption involved are too large.

(How the MIPS instruction set works)

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, observe which MIPS opcode is processed when the MIPS virtual machine of the OP sequencer has an error. If it is determined that there is an error, it can be determined 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 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 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 part of the 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 environmental 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 sophisticated design. As we all know, a program will take up 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 a total of 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 the 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, you also need to upload a 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 made up out of thin air.

Interactive Fraud Proof

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 can the challenger and the sequencer locate the controversial MIPS opcode instruction?

I believe many people have read a simple explanation of interactive fraud proofs on the Internet and have heard of its dichotomy. The OP team has 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 the challenger in FDG, and the sequencer will act as the defender. In order to locate 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, and its 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, that is, 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. The challenger and defender need to interact in the Merkle tree composed of OutputRoot to determine which block's OutputRoot is disputed. 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 after processing a certain opcode will show different performance.

After that, the two parties interacted on the chain many times, and finally located the disputed area and determined the 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, the 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. The opcode is executed 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 replaying a single instruction on the chain. However, this solution has several difficulties:

1. Multiple rounds of interaction need to be triggered on the Ethereum chain, which requires dozens of interactions and will generate a lot of gas costs;

2. The process of interactive fraud proof is long. Once the interaction is started, Rollup cannot execute transactions normally;

3. It is relatively complicated to implement a specific VM on the chain to replay instructions, and the development difficulty is extremely high

In order to solve these problems, Optimism officiallyproposedZK 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 evil.

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. 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 a proof every time a block is produced. It only temporarily generates a ZK proof when challenged, which also reduces the computing cost of the Rollup node.

The idea of ​​ZK-based fraud proof is also adopted by BitVM2. Projects that use BitVM2, such as Bitlayer, Goat Network, ZKM, Fiama, etc., use Bitcoin scripts to implement the ZK Proof verification program 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!