A tour of BTC ecological expansion plans: BitVM, the art of etching

How are smart contracts implemented on the Bitcoin network?

Written by: Simon shieh

Preface review

In the previous article “Tour of BTC Ecological Expansion Plans: Where to Go for Inscriptions”, we discussed the technical principles and possible security issues of the popular inscription ecology, and mentioned the possibility of using recursive inscriptions to implement smart contracts. However, due to Luke’s restrictions on Taproot scripts, recursive inscription seems to have some obstacles. So are there other possibilities to implement smart contracts on the Bitcoin network?

Robin Linus, co-founder of blockchain developer ZeroSync, published a paper titled “BitVM: Compute Anything on Bitcoin” on October 9, 2023, in which he proposed has launched a plan to bring smart contracts to the Bitcoin blockchain.

The paper proposes a very interesting idea to use taproot to perform almost any arbitrary calculation and use these calculations to verify what is happening off the Bitcoin chain. The trick is to keep all the logic off-chain and challenge dishonest results on-chain with a few steps of computation when others assert them.

In other words, it is to put the logic of a Verifier in the Bitcoin network, use the strong consensus security of Bitcoin to become a trusted third party for any Turing-complete computing layer, and then use the principle of Optimistic Rollups to realize off-chain calculations Verification of results.

So how to put a piece of Verifier logic in the Bitcoin network? In order to echo the “engraving” in the previous section, I would like to call it the technology of “etching” circuits on the Bitcoin network.

Logic gate circuit

Inside your computer or cell phone, electricity carries out all of the computer’s functions by delivering a series of ones and zeros. This is accomplished through millions of tiny components called logic gates. These logic gates are the basic building blocks of computer chips.

Each logic gate receives one or two “bits” of information, and each bit is either a 1 or a 0. Then, the logic gate performs a simple logical operation according to the set rules, such as “AND”, “OR” or “NOT” operations. The result of these operations is also a bit, either a 1 or a 0. After completing the operation, the result is passed to the next logic gate.

This system based on simple logical operations has led to the revelation that even the most complex calculations and functions can be achieved by combining a large number of simple logical operations. This combination and collaboration of logic gates is the basis for modern computers and electronic devices to perform complex tasks. Through these basic logical operations, computers can handle complex arithmetic operations, data storage, image rendering and other functions.

The picture below is a very special logic gate called a “NAND gate”. It can construct any type of logic gate circuit. Of course, it cannot be as efficient as other specialized types of gates, but it can still be done. . The logic gate circuit of BitVM is composed of NAND gates.

How to Etch NAND Gate on Bitcoin

Constructing a NAND gate on top of existing Bitcoin scripts can be achieved by combining a hash lock with two opcodes that may not be well known: OP_BOOLAND and OP_NOT.

First, a hash lock can be used to create a branch script that can be spent in one of two ways: either to satisfy the hash lock or to satisfy hash lock B. Thus, path A puts a 1 on the stack, and path B puts a 0 on the stack.

By satisfying a specific hash lock, you can “unlock” a bit that serves as one of the inputs to the NAND gate we are going to construct. Since you can only satisfy the requirements of one of the paths, this approach only allows the user to submit one bit at a time.

The logic of a NAND gate is to receive two bits as input and output one bit. If both input bits are 1, the output is 0; if the inputs are other combinations, the output is 1. Using two hash lock tricks, you can submit these two inputs and verify that the output is correct, which is what OP_BOOLAND and OP_NOT are for.

The operation of OP_BOOLAND is the opposite of a NAND gate: if both inputs are 1, the output is 1; any other combination of inputs produces a 0. OP_NOT outputs the opposite value of the input. So by combining these two opcodes, you can take two inputs and do the inverse sum in the script stack. Finally, you can use OP_EQUALVERIFY and the hash lock trick to verify the output of the assertion. If the actual NAND operation results on the stack are inconsistent with the output asserted by the user, the script fails validation.

In this way, the NAND gate circuit is “etched” into the Bitcoin script, effectively forcing a virtual NAND gate operation through the Bitcoin script.

How to etch large scale circuits

Although the idea of using Taproot scripts to achieve circuit etching is cool, let alone ultra-large-scale circuits like PCs, even to implement any set of calculations requires thousands of NAND gate circuits, which is limited in Bitcoin. How to cover complex calculations in the Taproot script space?

BitVM proposes the Taproot script tree (Taproot Tree) method. In order to implement complex computational processes in Bitcoin scripts, one can build computational circuits by connecting logic gates in series. In this scheme, hash locks are used to bind individual doors to achieve sequential execution of logical operations. Specifically, if one gate’s script produces a different output result C1 or C2 based on different hash preimage (hash plaintext value) input, then the next gate will use the matching hash lock value as its input .

This method can implement a penalty mechanism, that is, if you try to lie about the result of the previous gate, you can only reveal the original image of another hash lock. This mechanism can be used for interactive computing between two users, where they agree in advance to participate in a specific computing task, and then decompose the computing process into circuits consisting only of NAND gates. They need to choose the appropriate hash lock for each gate in the circuit and encode it into the script tree that locks the UTXO.

Then multiple addresses are used to form a Taproot address matrix, and then the logic circuit is etched into the Taproot script of a series of UTXO transactions connected in a tree structure through the Taproot Tree method, finally forming a “contract-like” logic that can handle certain computing tasks. circuit.

Fraud Challenge

Fraud challenge is the core of OP (Optimism Rollup) technology (although it has not been implemented yet~). The idea is that before a batch of transactions is submitted in batches, the challenger launches a fraud challenge (pledge vs. bet) on the transactions that are considered to be wrong. , the Verifier contract on the mainnet will determine whether the submitter has done evil based on the changes in the state root after execution, and then allocate the assets pledged by both parties.

In bitVM, the script tree is designed into two circuits. In addition to allowing the prover to submit to one circuit, the challenger also needs to be able to challenge the prover’s statement. This can be achieved by pre-signing a series of transactions. These pre-signed transactions are connected through “Challenge->Response->Challenge->…”. If one party stops for a period of time, the other party will win the challenge and recover both parties’ deposits.

The image above shows a series of pre-signed transactions:

• Challenge: Vicky (challenger/verifier) releases a pre-image in the script path (these pre-images are only known to the challenger), which is used to challenge the proof;
• Answer: Paul (the prover) executes the corresponding logic gate and sends the funds back to the initial script;

Any inconsistent statement can be quickly refuted after a few rounds of inquiry. If the prover stops cooperating with the challenger off-chain, the challenger will force the prover to cooperate on the chain: each time the challenger unlocks a hash lock, the Taproot leaf node corresponding to each NAND gate in the prover’s UTXO will have only It can only be spent if the prover knows a preimage held by the challenger. The prover can prove that a given Taproot leaf node executes correctly by revealing its inputs and outputs. The premise is that the challenger unlocks the original image of the hash corresponding to Tapleaf by revealing it. Through binary search, the challenger can lock the prover’s error after a limited round (O(logn)) of challenges and responses.

The entire process involves multiple rounds of interactions to ensure the contract is settled correctly. The challenger can keep challenging the prover until the prover confirms the correct result for each gate, or the challenger can withdraw the funds after a certain time in the event that the prover fails to respond to the challenge. In an ideal world, all operations take place off-chain and both parties collaborate to complete the settlement, but if cooperation breaks down, both parties can ensure that the contract is resolved correctly through an on-chain challenge game.

Landing obstacles and safety issues

This proposal involves processing and generating extremely large amounts of data. The Taproot script tree used may contain billions of leaf nodes, and the processing time of the associated pre-signed transactions may take at least several hours to ensure accurate settlement. The execution of the preset unlocking conditions for each Taproot address requires a mining fee, so the more address combinations, the greater the cost.

A major limitation of this scheme is that it only works for interactions between two participants: one, as a prover, certifying the accuracy of its execution; and the other, as a verifier, challenging the former’s claims. While future studies may find ways to include more participants, at this time there does not appear to be a clear solution.

In a cooperative settlement scenario, all participants must be online, which poses certain restrictions on the practicality and convenience of the protocol.

In terms of security, there are mainly the following security risks:

1. Due to cost constraints, a large amount of computing work must be performed off-chain. Off-chain computing has some common security risks of centralized services.

2. A large amount of data is stored off-chain, and data availability and data security are also risk points that must be considered.

3. Whether there are logical loopholes in the etched circuit itself is also a security risk point. Due to the unreadability of the circuit, more audit costs or formal verification costs need to be paid.

Metatrust has assisted Uniswap in conducting comprehensive formal verification work, and has very rich experience in ZK circuit auditing and formal verification, which can provide guarantee for the safe implementation of the BitVM ecosystem.

The solutions in the previous two articles are technical solutions that have just become popular this year. In the next article, we will introduce an older and more “orthodox” solution, an upgraded version of the Lightning Network - Taproott Assets.