A tour of Bitcoin ecological expansion plans (2): BitVM - the art of etching

Author: Simon shieh, Source: MetaTrust Labs

Foreword Review

Previous article In "Bitcoin ecological expansion plan tour (1): Where to go with the inscription", we discussed The technical principles and possible security issues of the popular inscription ecology were discussed, and the possibility of using recursive inscriptions to implement smart contracts was mentioned. However, due to Luke's restrictions on Taproot scripts, recursive inscription seems to have some obstacles. So are there other possibilities for implementing smart contracts on the Bitcoin network?

Robin Linus, co-founder of blockchain developer ZeroSync, published an article on October 9, 2023 titled "BitVM: Compute Anything on Bitcoin" )" paper, which proposes a plan to bring smart contracts to the Bitcoin blockchain.

This paper puts forward a very interesting idea, which can be used to complete almost everything with taproot. arbitrary calculations and use those 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 Optimistic Rollups principle to achieve verification of off-chain calculation 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 circuits

Within your computer or cell phone, electricity carries out all functions of the computer by passing 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, which is either 1 or 0. After completing the operation, the result is passed to the next logic gate.

This system based on simple logical operations has inspired: even the most complex calculations and functions can be realized 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 be able 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< /h2>

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 satisfying the hash lock or satisfying hash lock B. This way, path A outputs 1 to the stack, while path B outputs 0 to 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 the 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.

OP_BOOLAND operates inversely to the 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 to the input. So by combining these two opcodes, you can take two inputs and do the inverse sum in the script stack. Finally, OP_EQUALVERIFY can be used along with 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" in the Bitcoin script, which actually forces the virtual NAND gate operation through the Bitcoin script.

How to etch large-scale circuits
< /h2>

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, thousands of NAND gate circuits are needed , so how to cover complex calculations in the limited Taproot script space of Bitcoin?

BitVM proposed 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 door, you can only reveal the original image of the other 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, and finally a taperoot script that can handle certain calculations is formed. A "contract-like" logic circuit for a task.

Fraud Challenge

Fraud challenge is the core of OP (Optimism Rollup) technology (although it has not been implemented so far~), and the idea is to implement it in a batch Before the transactions are submitted in batches, the challenger initiates a fraud challenge (pledge vs. bet) on the transaction that is believed to be wrong. The Verifier contract on the main network will judge whether the submitter has done evil based on the changes in the state root after execution, and then allocate the pledged funds of both parties. assets.

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 above picture shows a series of pre-signed transactions:

< p>• Challenge: Vicky (challenger/verifier) ​​releases a preimage in the script path (these preimages are only known to the challenger), used as a challenge to the proof;

• Response : 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 several rounds of queries. 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. A 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 that the contract can be 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.

Falling barriers and safety issues

This proposal involves processing and generating an extremely large amount 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 acts as a prover, proving the accuracy of its execution; the other acts as a verifier, challenging the former's statement. 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 calculation work must be performed off-chain, and off-chain calculations are There are 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 concern. For security risks, due to the unreadability of the circuit, more audit costs or formal verification costs are required.

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——< strong>Taproott Assets.