[DRAFT] Scuffed Intro to BitVM

Medium says I last updated this October 27th, 2023. It was a blog post I planned to finish but never did. I’m going to publish this as a draft with hopes that having this publicly incomplete will motivate me to finish.

— — — —

//Note that I’ll use Paul and Vicky for Prover and verifier

//Add a high-level intro

Bitvm is a new scheme in bitcoin that allows a wide range of arbitrary programs to be verified on-chain. The aim is to execute the programs off-chain and settle on-chain in case of a dispute, similar to the lightning model.

The BitVM paper focuses on the construction of programs using NAND gates, as will I, but active research in this space has yielded more expressive primitives. This guide won’t explore any of that.

To demonstrate the concept, I’m going to make an example bitvm program that uses 1 NAND gate. The goal is for the 1 NAND gate program to evaluate to true. In this example we’ll be given the role of “prover” and labeled “Paul” (yay for alliteration), which means we’ll construct the program and be responsible for providing inputs to it. The counterparty running our program will be the “verifier” labeled “Vicky”. Before entering the contract, both parties must enter a setup phase.

We’ll go more into detail later, but at a high level the setup phase involves making the program as the prover, sharing the program with the verifier, allowing the verifier to construct 2 taptrees, and making a series of presigned transactions that will help with fraud proofs later on. After all this is done, we broadcast the first transaction (the funding transaction) in our series of presigned transactions.

{image with the states of nand gates}

So how do we represent a NAND gate locking script that allows the nand inputs to be specified during spend time? Here’s some pseudocode written in an imperative style showing what’s happening (the locking script is the function and the witness will be the inputs on invocation):

function nandGate(a, b, c) {

let x;

if(sha256(a) == HASH_A_ZERO) {

x = 1;

}

else if (sha256(a) == HASH_A_ONE) {

x = 0;

}

else {

return new Error();

}

let y;

if(sha256(b) == HASH_B_ZERO) {

y = 1;

}

else if (sha256(b) == HASH_B_ONE) {

y = 0;

}

else {

return new Error();

}

let z;

if(sha256(c) == HASH_Z_ZERO) {

z = 1;

}

else if (sha256(c) == HASH_Z_ONE) {

z = 0;

}

else {

return new Error();

}

if(nand(x, y) != z) {

throw new Error();

};

}

Let’s say we locked a utxo using a script functionally similar to the above. To satisfy this gate, x, y, and z must be values that cause the value to return true. As the prover, I would give the verifier this program comprised of ’n=1’ logic gates and ask them to create 2*n challenge-response transactions. In our case this will be 2 transactions (a challenge and a response), and neither will be signed yet. We also need a final transaction for if/when the prover Paul verifies the last gate. The funding transaction is separate and must be signed last.

Message passing flow:

Paul -> Vicky: The program

Vicky -> Paul: a series of challenge-response transactions that he’ll have to sign the multisig inputs of (using sighash all to cover the other input).

/*

-Makes more sense to use input since I can say Vicky published teh challenge tx

*/

/*

Show image for visualization:

https://github.com/BitVM/bitcoin-scripts/blob/main/presigned-tx-sequence.png

*/

================

THE FUNDING / RESPONSE TX

================

The verifier then makes a multisig transaction that will serve as our first tx. It will reference one utxo given by the verifier, and one utxo given by the prover when the program was transferred, as the inputs. The outputs are designed to always be spent together.

It has the same output structure as the response transaction which is why I grouped them together. The response tx differs in that the input UTXOs have to be the outputs of the challenge tx.

The output of this transaction has 2 outputs:

-a 0-valued output that is locked with a taptree of hashlocks numbering the number of gates in the program guarded by a check verifying the Verifier’s signature

-imperative example of a hashlock:

-(x, s) => hash(x) == PREDEFINED_HASH_VALUE && checksig(s)

-an output containing the funds, locked with a taptree.

-The taptree contains leaves for a:

-2 of 2

-equivocation slashing for the verifier to take the prover’s money (what supertestnet calls anti-contradiction)

-a timelock for the prover to take the money

================

THE CHALLENGE TX

================

The verifier is also responsible for making a response tx for the prover to use. The response transaction will take both outputs of the challenge tx as inputs. This transaction is intended for the Verifier to spend to, and the Prover to spend from.

The output of this transaction also has 2 outputs:

-a 0-valued output that is locked with a taptree, using the same hashlocks the output of the challenge transaction had, except with each leaf containing one gate’s logic converted to script. Note the trees for the challenge and response txs are different.*

-imperative example of leaf script:

-(x, a, b, c, m, s, k) => hash(x) == PREDEFINED_HASH_VALUE && nand(a,b,c) && checksig(m, s, k)

-an output containing the funds, locked with a taptree.

-The taptree contains leaves for a:

-2 of 2

-equivocation slashing for the verifier to take the prover’s money (what supertestnet calls anti-contradiction)

-a timelock for the verifier to take the money (assuming the prover can’t successfully solve the gate without contradicting themselves or failing the script)

================

Author’s Note

================

If the hashes in the hashlock don’t also include a checksig, on a second round of a challenge-response, the prover can force the first output to be spent without the money from the second output (since they already know one of the hashes). To prevent this, a signature check should be added. This isn’t explicitly said in the paper but it’s somewhat mentioned in the telegram. (telegram screenshot ref: A hashlock’s technical definition…)

-Mention how the multisig is sighash all and why that’s important

-Mention that we need one more transaction in case we end on the last leaf

-Mention that the prover can prove the same gate over and over whenver the verifier challenges. To prevent this, a verifier signature should be used instead

— — DONE AUTHORS NOTE — —

These are how the transactions will look for our case:

{Add some more images maybe? Link to Robin’s GH image may be enough}

—

Now that Vicky has made the txs for us, she signs all the inputs she can for each transaction except the first one.

She gives them to Paul, us, and we sign all the multisig inputs, including the first one. We then send it back to Vicky. When Vicky receives this she can sign the first input and broadcast the first challenge on-chain.

— — -

Now as the prover, there are 2 things I can do after the first transaction is published. I can give the inputs for the successful execution of the program encoded in this scheme (as hash preimages), I can lie and give faulty inputs, or I can choose to give no inputs at all.

/*

Show images of series of txs for each case

*/

====

Successful inputs

===

if we give Vicky the successful inputs, she can still spend the first output in the funding utxo even if she knows we’re right. There’s nothing we can do to stop her from challenging our gate. Because we have the correct inputs it’s annoying but not the end of the world. Maybe redeemable collateral requirements for Vicky can minimize this impact.

====

Unsuccessful inputs

===

If we give Vicky bad inputs, she’ll spend the funding tx into the challenge transaction. In this case it’s trivial to find the correct inputs since our challenge is a simple nand gate, but there are consequences for giving bad inputs. If she challenges us on-chain, and we provide the good inputs on-chain after giving her the bad inputs off-chain, she can use our bad inputs to take our money using the anti-contradictory script (link to super’s repo and just point to the script there).

====

No inputs

===

In this case we don’t give Vicky inputs because we refuse to or can’t. In this scenario Vicky can spend from the funding/response transaction to initiate the challenge. This forces Paul to reveal his inputs and if he knows it then he can spend into the final response tx. Otherwise he’d just be waiting it out until Vicky can take the funds.