Author: Shinpbo, Bitcoin Magazine; Translation: LianGuaicryptonaitive
Fear the wizards (note: humans with magical abilities). Not those wizards, these are the real wizards.
ZeroSync is an association that extends Bitcoin using zero-knowledge proofs. Recently, ZeroSync developer Robin Linus released a new Bitcoin proposal called BitVM, which opens up very interesting possibilities for future Bitcoin application development. BitVM enables almost any computation and uses that computation to enforce operations on the Bitcoin blockchain.
BitVM does not require any consensus changes to Bitcoin. The trick is to move all of this logic off-chain and have the ability to challenge some steps of the computation on-chain if the other party claims dishonest results. In short, BitVM brings arbitrary Turing-complete computation into Bitcoin in an executable way.
- Inventory of 16 Israeli concept coins worth paying attention to, with infrastructure and DeFi as the main force.
- Is Grayscale’s September report too optimistic? A study of Bitcoin’s on-chain performance in September.
- New Organizational Paradigm An In-depth Analysis of All Aspects of DAO
Logic Gate Basics
In order to truly understand the mechanics behind this proposal, we need to understand some basic physical and logical principles about computation.
Everyone knows that inside a computer, everything is done by passing around ones and zeros, but how does that work? What does it mean? Each chip core in a computer consists of millions or billions of logic gates.
These little devices take one or two bits of information (1 or 0) as input and perform simple logical operations on them to produce an output of 1 or 0, which is then fed into the next logic gate.
There are many different types of logic gates, some simply take one bit and output the same number (buffer gate). Others take one bit and output the opposite value of what they received (NOT gate). Some take two bits and output 1 only when both input bits are 1, and output 0 for any other combination (AND gate). Finally, at least in the example list below, there is one gate that takes two bits and outputs 0 when both inputs are 1, and outputs 1 for all other combinations (NAND gate).
NAND Gate Truth Table
The interesting thing about NAND gates is that you can build any other type of logic gate using just NAND gates. It’s certainly not as efficient as making specialized versions of the other gates, but it gets the job done. So, given that you can build any logic gate using NAND gates, you can build arbitrary circuits for any computation using NAND gates.
Building a NAND Gate on Bitcoin
Now, how do you build a NAND gate using existing Bitcoin scripts? With hash locks and two additional opcodes you might not be familiar with: OP_BOOLAND and OP_NOT.
First, let’s look at the hash lock. Create a branching script that can be spent in one of two ways, revealing the preimage of hash lock A or revealing the preimage of hash lock B. Path A will place the number 1 on the stack, while path B will place the number 0.
This allows you to “unlock” a bit by providing the preimage of the hash lock to use as an input for the NAND gate we are building. You can only complete the script with one of them, not both, and we will discuss the reasons for this shortly. This simple primitive is just to allow a user to commit to using one bit in a NAND gate script at a time.
Now let’s think back to what a NAND gate is. It takes two inputs and outputs one. If both inputs are 1, then the output must be 0. If the inputs are any other combination, the output is 1. You can use the two-path hash lock trick mentioned above to commit to the two inputs as well as the output, with only one way to verify if the output is correct. This is where OP_BOOLAND and OP_NOT come into play.
After choosing the values to assign as inputs and the output value to verify, you can leverage a clever trick. OP_BOOLAND performs the opposite operation to NAND— if both inputs are 1, the output is 1. In all other cases, the output is 0. OP_NOT takes any input value and flips it— 1 becomes 0 and vice versa. This allows you to perform the NAND operation on the two input values on the script stack. Then, use OP_EQUALVERIFY to verify that the actual output of the NAND operation matches the output promised by the hash lock trick. If the script’s actual NAND operation output on the stack does not match what the user claims it will produce, the script will fail to evaluate.
Now, you have implemented a NAND gate in Bitcoin script, effectively enforcing a virtual NAND gate.
Introducing Arbitrary Computation
So, now that you can create a standalone NAND gate in Bitcoin script, what can you do? You can create a complete taproot tree, covering every step of an arbitrary computation, just like actual logic gates for manufacturing computer processors.
To accomplish complex computations, people put logic gates together in succession, so that once the initial inputs are fed into the first gate, the output of each gate becomes the input of another gate directly. We achieve the same thing here by properly binding hash locks between gates. That is, if a gate script has a choice between outputs C1 or C2, the next gate in the series will use the same hash lock value in the matching input. This way, the only way someone can deceive about the result of the previous gate is by revealing another C hash lock. We can use this for punishment mechanisms.
Two users choose any computation they want to participate in and break it down into circuits that are calculated one by one using only NAND gates. Then, they adopt and encode each individual gate in the circuit, with the proper hash lock choice for each circuit step, and encode it into a taproot tree that can lock a single UTXO. There is one version of the tree for users trying to prove they correctly executed the program, and another version for people trying to verify if the program was correctly executed. Now, what they need to do is pre-sign a series of transactions for the challenge and response game to be executed on-chain. Ideally, the entire computation runs off-chain and gets verified, settling it to the appropriate party based on the computation result by jointly spending the funds. However, if the prover stops cooperating, the verifier can challenge them on-chain.
The first step is to load funds into the scheme. One script path allows the prover to unilaterally claim the funds after a time lock. The next script path allows the verifier to immediately claim the funds in the case they can show two preimages for any possible value of the current gate’s input or output. The next script path allows the verifier to force the prover to execute any specific gate contract on-chain (i.e., after ceasing cooperation off-chain). This path requires the verifier to reveal another hash lock preimage that only they possess, as a lock for each gate challenge to the prover. This ensures that the prover can only execute that specific gate. The verifier’s pre-signed transaction for this path spends it into a script that has the following script paths: the verifier takes the coin after a time lock, or the prover executes the gate and spends the coin back into a script similar to the first one, the prover can claim the funds after a time lock, the verifier can immediately claim the funds if two preimages are shown to any single hash lock, or the verifier can challenge the prover again.
This scheme only requires a few rounds to ensure the correct settlement of the contract. Either the validator uses up the pre-signed transactions to continue challenging the prover, because the prover has been demonstrating the correct execution of each gate and the prover will claim the funds; or the prover does not respond to the challenge, as it would result in punishment for them, and the validator can claim the funds after the time lock; or the prover incorrectly executes a gate on-chain, and the validator can immediately claim the funds. Ideally, everything happens off-chain and is resolved through cooperation, but if cooperation fails, then after a few rounds on-chain, there is no other outcome other than the correct settlement of the contract.
The Road Ahead
There is no doubt that such a proposal will be discussed in the coming weeks.
The amount of data to be processed and generated is enormous. We are discussing tapleaf trees with leaf numbers reaching billions, and there are at least a few hops of pre-signed transactions to ensure accurate settlement.
The cost of off-chain data management is absolutely huge.
Another important limitation is that this scheme can only be used with two parties involved, one playing the role of proving correct execution and the other playing the role of verifying correct execution.
Although future research may find ways to extend it to more participants, I cannot see a clear path to accomplish this at least. And even if this specific problem is solved, I do not see a way to escape the fact that it is an interactive protocol that requires all participants to always participate in cooperation.
Nevertheless, this is indeed a very interesting demonstration, showcasing how complex programs can be used to enforce conditional control over Bitcoin. There is definitely room for optimization in terms of how much logic can be packed into a single leaf script, or using different opcodes to make the whole scheme more efficient. By breaking down the basic operations and balancing game theory, arbitrary computations can be enforced using Bitcoin.
The real wizard has arrived.
Like what you're reading? Subscribe to our top stories.
We will continue to update Gambling Chain; if you have any questions or suggestions, please contact us!
