Preface Review
In the previous article "A Tour of Bitcoin Ecosystem Expansion Plans (1): Where is Inscription Going?", we discussed the technical principles and possible security issues of the popular inscription ecosystem, and mentioned the possibility of using recursive inscriptions to implement smart contracts. However, due to Luke's restrictions on Taproot scripts, recursive inscriptions seem 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 a paper titled "BitVM: Compute Anything on Bitcoin" on October 9, 2023, which proposed a plan to introduce smart contracts to the Bitcoin blockchain.
The paper proposes a very interesting idea that you can use taproot to complete almost any arbitrary computation and use it to verify what happened off-chain in Bitcoin. The trick is to put all the logic off-chain and challenge those results with a few steps of computation on-chain when others assert dishonest results.
In other words, it is to place the logic of a Verifier in the Bitcoin network, use Bitcoin's strong consensus security to become a trusted third party for any Turing-complete computing layer, and then use the principle of Optimistic Rollups to verify off-chain computing results.
So how do we put a Verifier logic into the Bitcoin network? 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
Constructing a NAND gate on top of an existing Bitcoin script can be accomplished by combining a hash lock with two perhaps less well-known opcodes: OP_BOOLAND and OP_NOT.
First, the hash lock can be used to create a branching 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, which is used 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 method only allows users 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 input is any other combination, the output is 1. Using two hash lock tricks, you can submit these two inputs and verify whether the output is correct, which is the purpose of OP_BOOLAND and OP_NOT.
OP_BOOLAND operates in the opposite way to the NAND gate: if both inputs are 1, the output is 1; any other input combination produces 0. OP_NOT outputs the opposite of the input. Therefore, by combining these two opcodes, two inputs can be taken and inverted in the script stack. Finally, OP_EQUALVERIFY can be used along with the hash lock trick to verify the asserted output. If the actual NAND result in the stack is inconsistent with the output asserted by the user, the script will fail verification.
In this way, a NAND gate circuit is “etched” into the Bitcoin script, effectively forcing a virtual NAND gate operation to be executed via the Bitcoin script.
How to Etch a NAND Gate on Bitcoin
Constructing a NAND gate on top of an existing Bitcoin script can be accomplished by combining a hash lock with two perhaps less well-known opcodes: OP_BOOLAND and OP_NOT.
First, the hash lock can be used to create a branching 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, which is used 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 method only allows users 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 input is any other combination, the output is 1. Using two hash lock tricks, you can submit these two inputs and verify whether the output is correct, which is the purpose of OP_BOOLAND and OP_NOT.
OP_BOOLAND operates in the opposite way to the NAND gate: if both inputs are 1, the output is 1; any other input combination produces 0. OP_NOT outputs the opposite of the input. Therefore, by combining these two opcodes, two inputs can be taken and inverted in the script stack. Finally, OP_EQUALVERIFY can be used along with the hash lock trick to verify the asserted output. If the actual NAND result in the stack is inconsistent with the output asserted by the user, the script will fail verification.
In this way, a NAND gate circuit is “etched” into the Bitcoin script, effectively forcing a virtual NAND gate operation to be executed via the Bitcoin script.
How to Etch Large Scale Circuits
Although the idea of using Taproot scripts to implement 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 required. How can complex calculations be covered in the limited Taproot script space of Bitcoin?
BitVM proposed the Taproot Tree method. In order to implement complex calculation processes in Bitcoin scripts, people can build calculation circuits by connecting logic gates in series. In this scheme, hash locks are used to bind various gates to achieve sequential logical operations. Specifically, if a gate's script produces different output results C1 or C2 based on different hash original images (hash plaintext values) inputs, the next gate will use the matching hash lock value as its input.
This approach allows for a penalty mechanism whereby only the original image of another hash lock can be revealed if one attempts to lie about the result of the previous gate. This mechanism can be used for interactive computations between two users, where they agree in advance to participate in a specific computational task and then decompose the computational process into a circuit consisting only of NAND gates. They need to choose a suitable hash lock for each gate in the circuit and encode it into the script tree that locks the UTXO.
Then, a Taproot address matrix is formed through multiple addresses, and the logic circuit is etched into the Taproot script of a series of UTXO transactions connected in a tree structure through the Taproot Tree, finally forming a "quasi-contract" logic circuit that can handle certain computing tasks.
Fraud Challenges
Fraud challenge is the core of OP (Optimism Rollup) technology (although it has not been really implemented so far~). The idea is that before a batch of transactions is submitted in batches, the challenger initiates a fraud challenge (pledge bet) against the transactions that he believes to be wrong. The Verifier contract on the main network will determine whether the submitter has committed a malicious act based on the changes in the state root after execution, and then distribute the assets pledged by both parties.
In bitVM, the script tree is designed as two circuits. In addition to allowing the prover to submit to a circuit, the challenger is also required 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 in the form of "challenge -> response -> challenge ->...". If one party stops for a period of time, the other party will win the challenge and recover the deposits of both parties.
The above image shows a series of pre-signed transactions:
• Challenge: Vicky (Challenger/Verifier) releases a preimage in a script path (these preimages are only known to the challenger) to serve 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 a few rounds of queries. If the prover stops cooperating with the challenger off-chain, the challenger will force the prover to cooperate on-chain: each time the challenger unlocks a hash lock, the Taproot leaf node corresponding to each NAND gate in the prover's UTXO can only be spent when the prover knows a preimage held by the challenger. The prover can prove that a given Taproot leaf node is executed correctly by revealing its input and output. The premise is that the challenger unlocks it by revealing the preimage of the hash of the corresponding Tapleaf. Through binary search, the challenger can lock the prover's error after a finite round (O(logn)) of challenges and responses.
The whole process involves multiple rounds of interaction to ensure that the contract can be settled correctly. The challenger can continue to challenge the prover until the prover confirms the correct result of each door, or if the prover fails to respond to the challenge, the challenger can withdraw the funds after a certain time. Ideally, all operations are carried out off-chain and both parties cooperate to complete the settlement, but if the cooperation breaks down, both parties can use the challenge game on the chain to ensure that the contract is correctly resolved.
Landing obstacles and safety issues
The amount of data that this proposal involves processing and generating is extremely large. The Taproot script tree used may contain billions of leaf nodes, and the processing time of the related pre-signed transactions may take at least several hours to ensure accurate settlement. Mining fees are required to execute the preset unlocking conditions of each Taproot address, so the more address combinations, the greater the cost.
A major limitation of this scheme is that it only works for interactions between two parties: one as a prover, attesting to the accuracy of its execution, and the other as a verifier, challenging the former's claims. While future research may find ways to allow more participants to join, there does not seem to be a clear solution at this point.
In the scenario of cooperative settlement, all participants must be online, which imposes certain limitations 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 done off-chain, and 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 difficulty in reading the circuit, more audit costs or formal verification costs are required.
Metatrust has assisted Uniswap in conducting comprehensive formal verification work and has extensive experience in ZK circuit auditing and formal verification, which can provide guarantees 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.
