BitVM 2: Opening Up The Playing Field

Last October Robin Linus from Zerosync dropped a bit of a bomb in the form of BitVM. One of the longest running criticisms of Bitcoin is that it is not possible to make arbitrary programs to control how money is spent or locked. Bitcoin only has a very limited amount of programmability in its scripting language, and the primitives available are extremely constrained. You can check a signature, you can add a timelock to something, you can manipulate data in a few simple ways, but that’s it.

You can program a Bitcoin UTXO to require a signature check, a timelock verification, etc. But you cannot program it to unlock based on any arbitrary conditions. Robin’s insight with BitVM was that one single primitive in the field of computing could be enforced in Bitcoin script: a NAND gate, one of the basic primitives of computing at the physical/electrical level. Every computation that is possible can be constructed out of NAND gates.

Script can actually verify a NAND gate due to a neat trick using OP_BOOLAND and OP_NOT. OP_BOOLAND is an AND operation, the opposite of NAND. OP_NOT takes a binary 1 or 0 value and inverts it. This together allows you to actually enforce a single NAND operation in script directly. In combination with hashlocks, a NAND gate script can be made where each input and output field has two possible hashlocks to “unlock” that spending path, each one pushing a 1 or 0 to the stack to perform the NAND operation. Each script also has a path where if you can reveal both preimages to a single bit value, you can immediately claim the funds. This is so that once someone decides what to input to the NAND gate, they cannot change their mind without losing money.

A massive amount of NAND gate scripts can all be compacted into a taproot tree, and once someone commits to the bit values off-chain to input to that computation, the other party can challenge them on any individual step in the computation to prove it is being executed correctly on chain. Each “challenge” allows the challenged party to prove that the individual gate was computed correctly, otherwise the other party can claim the funds after a timelock. Going back and forth like this if a computation is contested, it is guaranteed that the cheating party will eventually be caught and lose funds.

The limitations

The main limitation of BitVM is that only the people involved in creating a BitVM contract can participate, and the roles are very limited. There is the prover, the person asserting how the computation happened off-chain, and the verifier, the person who can challenge the computation and force it to be proven on-chain if the prover does not complete the computation off-chain or tries to lie about the results.

One of the reasons for designing BitVM was to establish two way pegs to sidechains or other systems. The scheme offers a very powerful primitive in that use case, the ability to actually enforce funds be given to one party or the other based on the correctness of an arbitrary computation, i.e. a validity check on whether a pegout is valid according to a sidechains rules. The problem is, only the people who hold keys to that BitVM UTXO can actually go “Hey, you’re cheating!” when someone is, and engage in the challenge protocol. This ultimately makes the system still trusted.

Another limitation is that the challenge response protocol can be very long. If someone realizes the outcome of the computation is going to result in them losing money and they stop responding, the verifier has to essentially guess where the individual NAND gate is in the computation that the prover would have to lie at and reveal both preimages to a bit that would give the verifier the funds. Until that specific gate is challenged on-chain, the prover can still respond correctly to a challenge and drag it out. This can be very time consuming and inefficient.

Some improvements to this design have been made since the original proposal to allow for multiple verifiers to exist in the system with the prover, to create a 1-of-n trust model where only a single verifier is required to challenge a dishonest prover. However, this requires the instantiation of multiple BitVM instances in parallel to accomplish, and therefore increases the inefficiencies with the original two party design.

BitVM 2

Robin recently proposed a design scheme for BitVM 2. This scheme seeks to make a few trade offs in comparison to the original design for the benefit of mitigating its two major shortcomings. BitVM 2 shortens the challenge/response protocol length from an indeterminate series of transactions that could be upwards of dozens in the worst case scenario, to two rounds in the challenge/response. In addition to this, with the use of connector outputs it allows anyone to act as a verifier. It does not require someone to be a member involved in establishing the BitVM to challenge a dishonest prover.

The fundamental shift here is moving away from directly using script NAND gates to implement the raw computational trace directly, and moving to using them to implement a general SNARK zero knowledge proof verifier (one of the core primitives Robin intended from the start to implement using BitVM). Instead of putting the raw input into the raw computational trace, and running it gate by gate in their own tapleaf scripts, the input of the BitVM 2 instance would simply be a zero knowledge proof input in combination with an asserted output of the computation.

In addition to abstracting away the computation implementation with a ZKP, the tapleaf scripts are being massively expanded from a single NAND gate per leaf to an entire sub-function of the ZKP verifier. Instead of the challenge response protocol being based around the verifier guessing at which NAND gate the prover attempted to cheat at, selectively challenging at a single gate, the verifier can prove an entire sub-function’s output is invalid according to the input.

Just like BitVM 1, the contract is pre-negotiated using pre-signed transactions and branching scripts. Funds pegged into the BitVM are sent to an n-of-n multisig which signs two possible execution transactions, one in which no challenge occurs, and one in which a challenge occurs. To start the process of executing the contract, the prover initiates a kick off transaction. This kick off transaction commits to the output value ‘y’ they claim the computation produces, and includes three outputs: a timelocked output that is included in the no challenge execution transaction, a connector output A, and a connector output B, both of which also are spent in the no challenge transaction.

Here is where the design allows for anyone to participate as a verifier. Connector output A has a second pre-signed transaction that can spend it, the challenge transaction. This is a pre-signed transaction that pays the prover a bond in bitcoin, but the connector output A is not enough to fund it. Literally anyone can add their own inputs to fund the transaction and spend connector output A, which invalidates the no challenge withdrawal transaction for the prover (one of the inputs it needs no challenge exists).

This forces the challenge path. Connector output B is also spendable using a pre-signed transaction, the assert transaction, to the output of every sub-function in the entire BitVM 2 contract. This requires a large transaction with a lot of data, but remember, the ultimate output ‘y’ the prover is claiming the computation produced was already committed to in the kick off transaction. This creates two outputs. One is a timelocked output, the other is a connector output C. Both of these outputs, in addition to the original pegged in funds, are all spent in the second successful withdrawal transaction for the prover after the timelock.

Connector output C is also spendable by anyone who can prove that any sub-function output in the BitVM 2 contract produces an invalid output. This requires a very large transaction, because the script necessary to prove an entire section of the BitVM computation is incorrect is massive, but in this single transaction a verifier can claim the coins in the connector output with a valid proof. This invalidates the second withdrawal transaction for the prover and effectively burns the coins. The only way to recover them at this point is if the prover and all of the verifiers in the original n-of-n funding multisig all cooperate to recover them. Connector output B in the kick off transaction can also be spent after a much longer timeout than no challenge withdrawal to invalidate both the no challenge and the assert transaction, burning the pegged coins.

This reduces what could be a ridiculous chain of transactions in the original BitVM proposal to enforce the correct contract outcome, to at most four transactions (although admittedly very massive ones), while in the process making the set of verifiers for the BitVM 2 instance literally anyone with bitcoin who will fund the challenge transaction.

BitVM 2 could wind up being a significant breakthrough in regards to the wave of rollups and other layer 2s aiming to use BitVM as a two way peg. The operator of a rollup (the prover in the BitVM) can use their own funds to cover withdrawals of users who have pegged into the system, and periodically withdraw those funds from the BitVM to compensate themselves. Any user or interested party would then be able to penalize them by burning their funds if they could produce proof the operator was not processing all withdrawals correctly.

It is important to note that ultimately the security of a BitVM 2 instance is backstopped by the n-of-n keyholder, even though people not participating in it can still challenge the prover as a verifier. But because the prover has an efficient exit in the case of no challengers, and anyone can fund the challenge transaction to act as a verifier, the n-of-n funding multisig could follow a setup and key deletion ceremony similar to the Zcash launch to improve its security.

BitVM 2 will probably wind up being a significant breakthrough in terms of improving the flexibility and trust model of two way pegs that make use of BitVM. Once again, Robin has proven himself a real wizard.