Blogs & Articles: The Big Deal with BitVM: Arbitrary Computation Now Possible on Bitcoin Without a Fork 🔗 29 weeks ago

​​Fear the wizards. Not those wizards, real wizards.

Announced today by developer Robin Linus of ZeroSync, an association founded to help scale Bitcoin by using zero-knowledge proofs, BitVM is a proposal that opens very interesting doors for Bitcoin application development going forward. It can enable pretty much any arbitrary computation, and use that computation to enforce what happens to bitcoin on-chain.

It requires no consensus changes to Bitcoin at all. The trick is lifting all of that logic off-chain and being able to challenge a few steps of the computation on-chain if the other party asserts a dishonest outcome. In short, BitVM will bring arbitrary Turing-complete computation, in an enforceable way, to bitcoin itself – today.

The Basics Of Logic Gates

To really grasp the mechanisms behind the proposal, we need to understand a little bit about the physical and logical basis of computation.

Everyone knows that under the hood your computer is just passing around individual 1s and 0s to do everything it does, but how does that work? What does it mean? Every single chip in your computer at its core is composed of millions or billions of individual things called logic gates.

These little devices take either one or two "bits" of information, a 1 or a 0, and perform a simple logical operation on them to produce either a 1 or a 0 as an output, which then feeds into the next logic gate.

There are many different types of logic gates, some that just take a single bit and put out the same number fed into it (the buffer gate). Others take a single bit and output the opposite value it receives (the NOT gate, or an inverter). Some take two bits, and output a 1 if both input bits are 1, with any other combination outputting a 0 (the AND gate). Lastly, at least here today in this list of examples, is a gate that takes two bits and outputs 0 if both inputs are 1s, and outputs 1 for all other bit combinations (the NAND gate).

The NAND truth table from 

The interesting thing about a NAND gate is you can build any other type of logic gate from just NAND gates. It definitely won't be as efficient as just making a special purpose version of the other gate, but it will get the job done. So, given that you can build any logic gate out of NAND gates, you can build circuits for any arbitrary computation out of NAND gates.

Building NAND on Bitcoin

Now how do you build a NAND gate with existing Bitcoin script? Hashlocks and two other op codes you are probably unfamiliar with: OP_BOOLAND and OP_NOT.

First, let's look at the hashlocks. You create a branching script that can be spent one of two ways, revealing the preimage to hashlock A, or revealing the preimage to hashlock B. Path A would put the number 1 on the stack, and Path B would put the number 0.

This allows you to "unlock" a bit to be used as an input to the NAND gate we are building by providing the preimage to the hashlock. You can only fulfill the script with one or the other, not both, and there are reasons we will get into shortly for this. This simple primitive is just there to allow users to commit to single bits at a time for use in a NAND gate script.

Now think back to what a NAND gate is, it takes two bits and outputs one. If the input bits are both 1s, then the output has to be a zero. If the input bits are any other combination the output is a 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 the output is correct. This is where OP_BOOLAND and OP_NOT come in.

After you have picked which values to assign as inputs, and which output value to verify it against, you can take advantage of a neat trick. OP_BOOLAND does the exact opposite that NAND does, if both inputs are 1s, the output is 1. Everything else outputs 0. OP_NOT takes whatever value is input and reverses it, a 1 becomes a zero and vice versa. This allows you to take the two input values and actually do a NAND operation on them on the scripting stack. You can then verify the output of that against the asserted output committed to with the hashlock trick using OP_EQUALVERIFY. The script will not pass evaluation if the actual NAND operation output created on the stack doesn't match the output the user claims it will produce.

You now have a NAND gate implemented in Bitcoin script, in a way that actually enforces with Bitcoin script the virtual NAND gate operates correctly.

Where the Arbitrary Computation Comes In

So what can you do now that you can make a single NAND gate in Bitcoin script? You can create an entire tapleaf tree that covers every single step of any arbitrary computation, just like actual logic gates do to make computer processors.

To accomplish complex computation, people put logic gates together in series, so that once you feed the initial inputs into the first gates, the output of each of them feeds right into another gate as input. The same thing is accomplished here by tying hashlocks together appropriately between gates. I.e. if one gate script has a choice between the preimages for value C1 or C2 as an output, the next gate in the series uses those same hashlock values in the matching input. This way the only way for someone to lie about the result from the previous gate is to reveal the other C hashlock. We can use this for a penalty mechanism.

Both users take whatever computation they want to engage in, and break it down into a circuit of only NAND gates doing the computation gate by gate. They then take and encode every individual gate in the circuit, with the appropriate hashlock choices for each circuit step, and encode it into a tapleaf tree that a single UTXO can be locked to. There is one version of the tree for the user trying to prove they are executing the program correctly, and one version for the person verifying it is executed correctly. Now what they do is pre-sign a series of transactions for a challenge and response game that can be executed on-chain. Ideally the entire computation is run through and verified off-chain, and users cooperatively settle it by spending the funds together to the appropriate person based on the computations outcome. If the prover stops cooperating however, the verifier can challenge them on-chain.

Step one is loading money into the scheme. One script path will let the prover just claim the money unilaterally after a timelock. The next script path will let the verifier instantly claim the money if they can show the preimages to both the possible values for any input or output of the current gate. The next script path will allow the verifier to force the prover to execute any specific gate contract on-chain (i.e. the one right after they stopped cooperating with off-chain). This path requires the verifier to release another hashlock preimage that only they have, functioning as a lock for each gate challenge to the prover. This guarantees the prover can only execute that specific gate. The verifier's pre-signed transaction for that path will spend it to a script with the following script paths: the verifier takes the coins after a timelock, or the prover executes the gate and spends the coin back into a script like the first one, the prover can claim the money after a timelock, the verifier can claim it instantly if showing both preimages to any single hashlock pair, or the verifier can challenge the prover again.

Only a few rounds of this scheme will guarantee the contract settles correctly. Either the verifier runs out of pre-signed transactions to keep challenging the prover, because the prover keeps demonstrating correct execution of each gate, and the prover claims the fund; or, the prover does not respond to a challenge because it would allow them to be penalized, and the verifier claims the funds after a timelock; or the prover actually does execute a gate incorrectly on-chain and the verifier claims the funds immediately. Ideally everything happens off-chain and is settled cooperatively, but if cooperation fails there literally is no other outcome after just a few rounds on-chain than the contract settling correctly.

Where to Go From Here

Certainly, a proposal of this magnitude will be discussed for some weeks going forward.

The amount of data needed to be processed and generated is enormous. We are talking taptrees with leaves numbered in the billions, and pre-signed transactions to go with them all at least a few hops long to ensure accurate settlement.

The off-chain data management cost is absolutely massive.

The other big limitation is this scheme will only work with two parties, one playing the role of proving correct execution, and the second playing the role of verifying it.

While it is possible future research finds a way to generalize this to more participants, I at least see no clear path to accomplishing that. Also, even addressing that particular problem, I see no way to get around that this is an interactive protocol requiring participation at all times by all participants in the cooperative case.

Nonetheless, this is a very interesting demonstration of 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 what can be done with different op codes to make the entire scheme more efficient. Simple deconstruction to the basic operations and game theoretic balances can enforce any arbitrary computation using Bitcoin.

Truly the creation of wizards.