Fear magicians. Not those magicians, the real magicians.
Announced today by developer Robin Linus of ZeroSync, a partnership founded to help scale bitcoin through the use of zero-knowledge proofs, BitVM It is a proposal that opens very interesting doors for the development of bitcoin applications in the future. You can allow virtually any arbitrary calculation and use that calculation to enforce what happens to bitcoin on-chain.
It does not require any consensus changes in bitcoin. The trick is to take all that logic off-chain and be able to challenge some steps of the calculation on the chain if the other party claims a dishonest result. In short, BitVM will bring the arbitrary Turing-complete computation, in executable form, to bitcoin itself, today.
The Basics of Logic Gates
To really understand the mechanisms behind the proposal, we need to understand a little about the physical and logical bases of computing.
Everyone knows that under the hood, your computer just passes around individual ones and zeros to do everything it does, but how does that work? What does it mean? Each chip in your computer is made up at its core of millions or billions of individual elements called logic gates.
These small devices take one or two “bits” of information, a 1 or a 0, and perform a simple logic operation on them to produce a 1 or a 0 as output, which is then passed to the next logic gate.
There are many different types of logic gates, some that simply take a bit and output the same number (the buffer gate). Others take a single bit and generate the opposite value it receives (the NOT gate or an inverter). Some take two bits and generate a 1 if both input bits are 1, and any other combination generates a 0 (the AND gate). Finally, at least here today in this list of examples, there is a gate that takes two bits and outputs 0 if both inputs are 1, and outputs 1 for all other combinations of bits (the NAND gate).
The interesting thing about a NAND gate is that you can build any other type of logic gate just from NAND gates. It definitely won’t be as efficient and will only make a special version of the other door, but it will get the job done. So since you can build any logic gate from NAND gates, you can build circuits for any arbitrary calculation from NAND gates.
Building NAND in bitcoin
Now, how do you build a NAND gate with an existing bitcoin script? Hashlocks and two other opcodes you’re probably not familiar with: OP_BOOLAND and OP_NOT.
First, let’s look at hashlocks. You create a branch script that can be spent in two ways: revealing the preimage to hashlock A or revealing the preimage to hashlock B. Path A would push the number 1 onto the stack and path B would push the number 0.
This allows you to “unlock” a bit to use as input to the NAND gate we are building by providing the pre-image to the hashlock. You can only fulfill the script with one or the other, not both, and there are reasons that we will see shortly for this. This simple primitive is there to allow users to commit to individual bits at a time for use in a NAND gate script.
Now think about what a NAND gate is: it takes two bits and outputs one. If the input bits are both ones, then the output has to be zero. If the input bits are any other combination, the output is 1. You can use the two-path hashlock trick above to commit to both inputs as well as the output, you just need a way to verify that the output is correct. This is where OP_BOOLAND and OP_NOT come in.
Once you’ve chosen which values to assign as inputs and which output value to check them with, you can take advantage of a neat trick. OP_BOOLAND does the exact opposite of NAND, if both inputs are 1, the output is 1. Everything else outputs 0. OP_NOT takes any value entered and inverts it, a 1 becomes zero and vice versa. This allows you to take the two input values and perform a NAND operation on them. on the script stack. You can then verify the result of that with the asserted result committed to the hashlock hack using OP_EQUALVERIFY. The script will fail evaluation if the actual NAND operation result created on the stack does not match the result the user claims it will produce.
Now you have a NAND gate implemented in a bitcoin script, in a way that actually applies with the bitcoin script that the virtual NAND gate works correctly.
Where arbitrary computing comes into play
So what can you do now that you can create a single NAND gate in a bitcoin script? You can create a complete tapleaf tree that covers every step of any arbitrary calculation, just like real logic gates do for making computer processors.
To achieve complex calculations, people put logic gates together in series, so that once the initial inputs are entered into the first gates, the output of each of them is fed directly into another gate as input. The same is achieved here by tying the hashlocks appropriately between the doors. That is, if a gate script can choose between preimages for value C1 or C2 as output, the next gate in the series uses those same hashlock values on the matching input. This way, the only way for someone to lie about the result of the previous gate is to reveal the other hashlock C. We can use this as a penalty mechanism.
Both users take whatever calculation they want to perform and split it into a circuit of just NAND gates that perform the calculation gate by gate. They then take and encrypt each individual gate in the circuit, with the appropriate hashlock options for each step of the circuit, and encode them into a tapleaf tree to which a single UTXO can be locked. There is a version of the tree for the user who is trying to prove that they are running the program correctly and a version for the person who is verifying that it is running correctly. Now what they do is pre-sign a series of transactions for a challenge and response game that can be run on chain. Ideally, the entire calculation is executed and verified off-chain, and users solve it cooperatively by spending the funds together to the appropriate person based on the result of the calculation. However, if the prover stops cooperating, the verifier can challenge him up the chain.
The first step is to load money into the plan. A script route will allow the tester to claim the money unilaterally after a time lock. The following script path will allow the verifier to instantly claim the money if it can display preview images of the possible values for any input or output of the current door. The following script path will allow the verifier to force the prover to execute any specific gate contract within the chain (i.e. the one that occurred just after they stopped cooperating off-chain). This route requires the verifier to release another hashlock preimage that only it has, which functions as a lock for each door challenge to the prover. This ensures that the tester can only run that specific gate. The verifier’s pre-signed transaction for that path will be passed to a script with the following script paths: the verifier takes the coins after a time lock, or the prover executes the gate and spends the coin again in a script like the first one, The prover can claim the money after a time lock, the verifier can claim it instantly by showing both preimages to any hashlock pair, or the verifier can challenge the prover again.
Only a few rounds of this scheme will ensure that the contract is settled correctly. Or the verifier runs out of pre-signed transactions to continue challenging the prover, because the prover keeps proving the correct execution of each gate and the prover claims the fund; or the tester does not respond to a challenge because it would allow him or her to be penalized and the verifier claims the funds after a time block; or the tester actually executes a gate incorrectly in the chain and the verifier claims the funds immediately. Ideally everything happens off-chain and is resolved cooperatively, but if cooperation fails there is literally no other outcome after a few rounds on-chain than the contract being resolved correctly.
Where to go from here
No doubt a proposal of this magnitude will be discussed for a few weeks in the future.
The amount of data required to be processed and generated is enormous. We are talking about taptrees with sheets numbered in the billions and pre-signed transactions that will accompany them for at least a few hops to ensure accurate settlement.
The cost of off-chain data management is absolutely enormous.
The other major limitation is that this scheme will only work with two parts, one that plays the role of demonstrating correct execution and the second that plays the role of verifying it.
While future research may find a way to generalize this to more participants, at least I don’t see a clear path to achieve this. Furthermore, even addressing that particular issue, I see no way around the fact that this is an interactive protocol that requires the participation at all times of all participants in the cooperative case.
Nevertheless, this is a very interesting demonstration of how complex programs can be used to impose conditional control over bitcoin. There is definitely room for optimization in terms of how much logic can be packed into a single sheet script, or what can be done with different opcodes to make the entire scheme more efficient. A simple deconstruction of the basic operations and equilibria of game theory can impose any arbitrary calculation using bitcoin.
Truly the creation of magicians.
