A Simplified Interpretation of BitVM: How to Verify Fraud Proofs on the BTC Blockchain

TL;DR

Introduction:

This article provides an interpretation of the BitVM whitepaper, explaining BitVM’s approach: Data does not need to be on-chain initially; it is published and stored off-chain, with only a Commitment stored on the blockchain.

Forwarded Original Article Title: A Simplified Interpretation of BitVM: How to Verify Fraud Proofs on the BTC Blockchain (Executing EVM or Other VM Opcodes)

Preface: Currently, Bitcoin Layer 2 has become a trend, with dozens of projects self-identifying as “Bitcoin Layer 2.” Many of these, claiming to be “Rollups,” state they are utilizing the approach proposed in the BitVM whitepaper, positioning BitVM as a prominent part of the Bitcoin ecosystem.

However, most of the existing literature on BitVM does not explain its principles in layman’s terms. This article, based on our reading of the 8-page BitVM whitepaper and after consulting resources related to Taproot, MAST trees, and Bitcoin Script, offers a simplified summary. To aid understanding, we have altered some expressions from those found in the BitVM whitepaper, assuming the reader has some knowledge of Layer 2 and can grasp the basic idea of “fraud proofs.”

The preliminary concept of BitVM can be summarized in a few sentences: it eliminates the need for data on-chain, initially publishing and storing data off-chain, with only a Commitment stored on the blockchain. In cases of challenges or fraud proof, only the necessary data is brought on-chain to demonstrate its association with the Commitment on the blockchain. Subsequently, the BTC mainnet verifies the on-chain data for any issues and whether the data producer (the node processing the transactions) has engaged in malicious activities. This approach adheres to Occam’s Razor principle—“Entities should not be multiplied unnecessarily” (if it can be off-chain, keep it off-chain).

Main Text: The so-called BTC blockchain fraud proof verification scheme based on BitVM, in layman’s terms:

1.Firstly, a computer/processor is an input-output system composed of a large number of logic gate circuits. One of the core ideas of BitVM is to use Bitcoin Script to simulate the input-output effects of logic gate circuits. As long as the logic gate circuits can be simulated, in theory, a Turing machine can be achieved, completing all computable tasks. This means that if you have enough resources and manpower, you can gather a team of engineers to first simulate the logic gate circuits using the rudimentary Bitcoin Script code, and then use a massive amount of logic gate circuits to implement the functionalities of EVM or WASM.

(This screenshot is from an educational game: “Turing Complete”, where the core content is to build a complete CPU processor, especially using logic gate circuits like NAND gates.)

Some have likened BitVM’s approach to building an M1 processor in “Minecraft” using redstone circuits. Or, it’s akin to constructing the Empire State Building in New York with LEGO blocks.

(It is said that someone spent a year building a “processor” in “Minecraft”.)

1. So, why use Bitcoin Script to simulate EVM or WASM? Isn’t that very cumbersome? The reason is that most Bitcoin Layer 2 solutions often choose to support high-level languages such as Solidity or Move, while the only language that can currently run directly on the Bitcoin blockchain is Bitcoin Script. This language is primitive, composed of a bunch of unique opcodes, and is not Turing complete.

(An example of Bitcoin Script code)

If Bitcoin Layer 2 aims to verify fraud proofs on Layer 1 like Ethereum’s Layer 2 solutions such as Arbitrum, to greatly inherit BTC’s security, it needs to directly verify “a disputed transaction” or “a disputed opcode” on the BTC blockchain. This means that the Solidity language / EVM opcodes used by Layer 2 need to be re-executed on the Bitcoin blockchain. The challenge boils down to:

Using Bitcoin Script, a native but rudimentary programming language of Bitcoin, to achieve the effects of EVM or other virtual machines.

Therefore, from the perspective of compilation principles, the BitVM approach translates EVM / WASM / JavaScript opcodes into Bitcoin Script opcodes, with logic gate circuits serving as an intermediate representation (IR) between “EVM opcodes —> Bitcoin Script opcodes”.

(The BitVM whitepaper discusses the general approach to executing certain “disputed instructions” on the Bitcoin blockchain)

Anyway, the ultimate effect simulated is to process instructions, that could originally only be handled on EVM / WASM, directly on the Bitcoin blockchain. Although this solution is feasible, the difficulty lies in how to use a large number of logic gate circuits as an intermediate form to express all EVM / WASM opcodes. Moreover, using combinations of logic gate circuits to directly represent some extremely complex transaction processing flows might result in a massive workload.

1. Let’s discuss another core concept mentioned in the BitVM whitepaper, which is the “Interactive Fraud Proofs” highly similar to those used by Arbitrum.

Interactive Fraud Proofs involve a term known as assert. Typically, the proposer of Layer 2 (often acted by a sequencer) publishes an assert on Layer 1, declaring that certain transaction data and state transition results are valid and error-free.

If someone believes that the assert submitted by the proposer is problematic (associated data is incorrect), a dispute occurs. At this point, the proposer and the challenger exchange information in rounds and use a binary search method on the disputed data to quickly locate a very fine-grained operation instruction and its associated data segment.

For this disputed operation instruction (OP Code), it’s necessary to execute it directly on Layer 1 along with its input parameters and validate the output result (Layer 1 nodes compare the output result they computed with the output result previously published by the proposer). In Arbitrum, this is known as “Single-Step Fraud Proofs”. (In Arbitrum’s interactive fraud proof protocol, binary search is used to quickly locate the disputed instruction and its execution result, and then a single-step fraud proof is sent to Layer 1 for final verification).

Following up on this:

1. The process is interactive, with both parties taking turns. One party segments the historical data contained in a Rollup Block, and the other party points out which data segment is problematic. This is akin to a binary method (in reality, a process of progressively narrowing down the range, N/K).

2. Subsequently, it’s possible to further locate which transaction and result are problematic, and then further narrow down to a specific machine instruction within that transaction that is disputed.

3. The ChallengeManager contract only checks whether the “data segment” produced by subdividing the original data is valid.

4. Once the challenger and the challenged have located the machine instruction to be challenged, the challenger invokes oneStepProveExecution(), sending a single-step fraud proof to demonstrate that there is an issue with the execution result of this machine instruction.

(In the interactive fraud proof protocol of Arbitrum, the process involves using binary search to quickly locate the disputed instruction and its execution result from the data published by the Proposer. After identifying the contentious piece of data or opcode, a single-step fraud proof is sent to Layer 1 for final verification.)

References:

Former Arbitrum technical ambassador explains Arbitrum’s component structure (Part 1)

(Arbitrum’s interactive fraud proof flow chart, the explanation is relatively rough)

By this point, the concept of single-step fraud proofs becomes quite straightforward: the vast majority of transaction instructions occurring on Layer 2 do not need to be re-verified on the BTC blockchain. However, if a particular disputed data segment/opcode is challenged, it must be replayed on Layer 1.

If the verification outcome indicates that the data previously published by the Proposer is problematic, then the Proposer’s staked assets are slashed. If the Challenger is found to be at fault, then the Challenger’s staked assets are slashed. Provers who fail to respond to challenges in a timely manner can also be slashed.

Arbitrum implements the aforementioned effects through contracts on Ethereum, while BitVM aims to achieve similar functionality using Bitcoin Script to implement time locks, multisig, and other features.

4.After discussing “Interactive Fraud Proofs” and “Single-step Fraud Proofs,” we will talk about MAST trees and Merkle Proofs. Previously, we mentioned that in the BitVM solution, the vast amount of transaction data and logic gate circuits processed off-chain at Layer 2 are not directly put on-chain. Only a minimal amount of data/logic gate circuits are put on-chain when necessary. However, we need a way to prove that this data, which was originally off-chain and now needs to be put on-chain, is not fabricated. This is where the concept of Commitment in cryptography comes into play, and Merkle Proof is one form of such a Commitment.

First, let’s talk about MAST trees. The full name of MAST is Merkelized Abstract Syntax Trees, which are a transformation of AST (Abstract Syntax Trees) from the realm of compiler principles into Merkle Trees. So, what is an AST? In simple terms, it’s a tree-like data structure that breaks down a complex command into a bunch of basic operation units through lexical analysis.

(An example of an AST tree would be breaking down simple calculations like “x=2, y=x*3” into underlying operation codes and data. )

The MAST tree, then, is the result of applying Merkleization to an AST tree, supporting Merkle Proofs. One advantage of Merkle trees is their ability to efficiently “compress” data. For instance, if you want to publish a segment of data from the Merkle tree on the BTC blockchain when necessary, while also making it credible that this data segment truly exists on the Merkle tree and is not arbitrarily chosen, what do you do?

You simply record the Merkle tree’s Root on the blockchain in advance. In the future, presenting a Merkle Proof that proves a piece of data exists on the Merkle tree corresponding to the Root will suffice.

(The relationship between Merkle Proof/Branch and Root)

Thus, there’s no need to store the complete MAST tree on the BTC blockchain; it’s enough to disclose its Root in advance as a Commitment. When necessary, presenting the data segment + Merkle Proof/Branch is adequate. This greatly reduces the amount of data on-chain while ensuring that the on-chain data genuinely exists on the MAST tree. Moreover, disclosing only a small part of the data segments + Merkle Proof on the BTC blockchain, instead of all data, can significantly enhance privacy protection.

References:Data Withholding and Fraud Proofing: Why Plasma Doesn’t Support Smart Contracts

(MAST tree example)

In BitVM’s solution, all logic gate circuits are expressed using Bitcoin scripts, organized into a massive MAST tree. The bottom leaves of this tree, indicated as Content in the diagram, correspond to the logic gate circuits implemented in Bitcoin script. Layer 2’s Proposer frequently publishes the MAST tree’s root on the BTC blockchain, with each MAST tree associated with a transaction involving all its input parameters/operation codes/logic gate circuits. This is somewhat similar to Arbitrum’s Proposer publishing Rollup Blocks on the Ethereum blockchain.

When a dispute arises, a challenger declares on the BTC blockchain which Root they wish to challenge, then asks the Proposer to reveal a specific data segment corresponding to the Root. Subsequently, the Proposer presents a Merkle Proof, continuously disclosing small segments of the MAST tree’s data on-chain until the disputed logic gate circuit is jointly located with the challenger. After that, a Slash can be executed.

(Source:https://medium.com/crypto-garage/deep-dive-into-bitvm-computing-paradigm-to-express-turing-complete-bitcoin-contracts-1c6cb05edfca）

1. Up to this point, the most crucial aspects of the BitVM solution have been largely covered. Although some details may still be somewhat obscure, it is believed that readers can grasp the essence and main points of BitVM. Regarding the “bit value commitment” mentioned in its whitepaper, it is designed to prevent a Proposer from assigning both 0 and 1 to the input values of a logic gate when challenged and forced to verify the logic gate circuit on-chain, thereby creating ambiguity and confusion.

In summary, the BitVM scheme starts by using Bitcoin script to express logic gate circuits, then uses these circuits to express the opcodes of the EVM/other VMs, which in turn express the processing flow of any given transaction instruction, and finally organizes these into a Merkle tree/MAST tree. If the transaction processing flow represented by such a tree is very complex, it can easily exceed 100 million leaves, so it’s crucial to minimize the block space occupied by commitments and the scope affected by fraud proofs.

Although a single-step fraud proof only requires a very small amount of data and a logic gate script on-chain, the complete Merkle Tree must be stored off-chain for a long time, so that it can be accessed on-chain at any time if someone challenges it. Each transaction in a Layer 2 generates a large Merkle Tree, and one can imagine the computational and storage pressure on nodes. Most people might not want to run nodes (however, such historical data can be phased out, and the B^2 network specifically introduces zk-storage proofs similar to Filecoin to incentivize storage nodes to preserve historical data long-term).

However, optimistic Rollups based on fraud proofs do not need too many nodes because their trust model is 1/N, meaning that as long as one of the N nodes is honest and can initiate a fraud proof at a critical moment, the Layer 2 network is secure.

Nevertheless, there are many challenges in the design of Layer 2 solutions based on BitVM, such as:

1) Theoretically, to further compress data, it is not necessary to verify opcodes directly on Layer 1. The processing flow of opcodes can be further compressed into a zk-proof, allowing challengers to challenge the verification steps of the zk-proof. This could significantly reduce the amount of data on-chain. However, the specific development details could be very complex.

2) Proposers and Challengers need to generate interactions off-chain repeatedly. How the protocol should be designed, and how the commitment and challenge process should be further optimized in the processing flow, will require a lot of intellectual effort.

Disclaimer：

1. This article is reprinted from [Geek Web3], Forward the Original Title “A minimalist interpretation of BitVM: How to verify fraud proof on the BTC chain (execute the operation code of EVM or other VM)”, the copyright belongs to the original author [Faust & Misty Moon]
   . If there are objections to this reprint, please contact the Gate Learn team, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute any investment advice.
3. Translations of the article into other languages are done by the Gate Learn team. Unless mentioned, copying, distributing, or plagiarizing the translated articles is prohibited.