In this post we will take a high level look at how we went from having bit commitments using lamport signatures to having BitVM.
I'm not an expert in cryptography (or lamport signatures), some of what I'm saying might be slightly (or very) wrong. Feel free to email me with any corrections.
I'm not the first to write about this, obviously and you can read more at these places:
Bitcoin uses the UTXO transaction model (vs for instance the account model on Ethereum), they are unspent transactions output. Usually created from another transaction or the coinbase transaction itself. They have spending conditions, P2PKH is one example of that.
The locking script for P2PKH would be the following
OP_DUP OP_HASH160 <Public key hash> OP_EQUALVERIFY OP_CHECKSIG
The unlock script to spend that UTXO would be
<Signature> <Public key>
The user will in other words put a signature and the associated public key on the stack.
When the script interpreter runs, it will run those scripts combined like this:
<Signature> <Public key>OP_DUP OP_HASH160 <Public key hash> OP_EQUALVERIFY OP_CHECKSIG
This script will validate that the associated public key matches the hash and that the signature is valid for that public key. Only if it succeeds the UTXO can be spent. You can see a list of all the opcodes here and read more on learnmeabitcoin about script itself.
One important thing to highlight is that Bitcoin script is stateless and is not Turing complete, but as we soon will see BitVM challenges this in a unique way.
Related to this, most users don't ever see these scripts as they get encoded part of the address which serves as an abstraction for these scripts.
The seed was planted when Jeremy Rubin posted a blog post in 2021 on how one can commit to bits using Lamport signatures with the existing Bitcoin script.
Short version is that Lamport signatures are a onetime use signature scheme, meaning (as the name suggests) it can only be securely used to sign a single message.
The longer version of how key generation and signature verification works is probably best described by Matthew Green's blog post. The Wikipedia article also has a step by step example.
Jeremy wrote up the following script which could be used to sign a bit commitment (I added the comments).
// Verify the public key
<pk> checksigverify
// Counter starts at 0
0x0
// First bit
SWAP sha256 DUP <H(K_0_1)> EQUAL IF // Preimage for 1-bit
DROP <1> ADD // Stack alignment and bit shifting
ELSE <H(K_0_0)> // Preimage for 0-bit
EQUALVERIFY // Stack alignment
ENDIF
// Second bit
SWAP sha256 DUP <H(K_1_1)> EQUAL IF
DROP <1<<1> ADD
ELSE <H(K_1_0)>
EQUALVERIFY
ENDIF
// Third bit
SWAP sha256 DUP <H(K_2_1)> EQUAL IF
DROP <1<<2> ADD
ELSE <H(K_2_0)>
EQUALVERIFY
ENDIF
// Same pattern repeated for each bit up to 16
...
// Final 16th bit
SWAP sha256 DUP <H(K_15_1)> EQUAL IF
DROP <1<<15> ADD
ELSE <H(K_15_0)>
EQUALVERIFY
ENDIF
// Verify the time commitment
CHECKSEQUENCEVERIFY
So what is happening here?
<pk> checksigverify
(this is
unrelated to the
lamport
signature part)
CHECKSEQUENCEVERIFYCool, so preimages are used to commit to bits. Bitwise operators are used to construct the final number.
BitVM takes this to the next level. Instead of committing to a counter, we are committing to the output of a NAND gate.
This is done by creating a hypothetical opcode OP BITCOMMITMENT which based on a preimage outputs a zero or a one:
// (this is slightly rewritten version of Figure 1 from the
// BitVM whitepaper)
// Definition of OP_BITCOMMITMENT
OP_IF
OP_HASH160 <0xf592e757267b7f3073241fe78b34472f8b6f46f3> // Preimage 1
OP_EQUALVERIFY
0x1
OP_ELSE
OP_HASH160
<0xb157bee96d62f6855392b9920385a834c3113d9a> // Preimage 0
OP_EQUALVERIFY
0x0
OP_ENDIF
Based on that, you can construct a NAND gate
// (this is slightly rewritten version of Figure 1 from the
// BitVM whitepaper)
// Reveal preimage of hash C1 or hash C0
OP_BITCOMMITMENT
// Now the bit value of "C" is on the stack
// ... we put it to the altstack for now
OP_TOALTSTACK
// Reveal preimage of hash B1 or hash B0
OP_BITCOMMITMENT
// Now there's the bit value of "B" on the stack
// ... we put it to the altstack for now
OP_TOALTSTACK
// Reveal preimage of hash A0 or hash A1
OP_BITCOMMITMENT
// Now the bit value of "A" is on the stack
//
// Verify that "A NAND B == C"
// Read "B" from altstack
OP_FROMALTSTACK
// Compute "A NAND B"
OP_BOOLAND
OP_NOT
// Read "C" from altstack
OP_FROMALTSTACK
// ... and check that it is correct
OP_EQUALVERIFY
Great, so now we are able to construct NAND gates which are universal building blocks and we can build program executions based on them. These NAND gates won't be executed on Bitcoin though, at least in most cases, but they might be used to challenge incorrect executions. This is similar to an optimistic rollup. By utilizing Taproot the full script doesn't even need to be onchain, just the hash of the script paths. This minimizes the footprint on chain.
Both the provider and verifier will also pre-sign a set of challenges-and-response transactions that they later can use in a challenge response game. It's easy to see when people are cheating because of either inconsistency in the NAND gates. This is also the way we get state transitions, as the signature check between transactions can enforce consistency.
In other words, the combination of pre-signed transactions and one-time signatures ensures that only the correct state transitions can be taken. If not, it will be detected and can be penalized.
BitVMX is based on the original idea from Robin Linus, but takes a different architectural approach to the problem. They have done a larger write-up on the differences, but I think the key part is that BitVMX has been focusing on allowing arbitrary computation while BitVM has been focusing more on having a stark verifier. They handle disputes a bit differently also.
ColliderVM is interesting as it doesn't really on the need for fraud proofs. It also doesn't need any new opcodes to function. This is still in a more research phase compared to BitVM.
Like in BitVM, there is a pre-signing phase that will sign a series of program to represent the logic of the program. Since there will be multiple transactions each with subfunctions that needs to have a consistent input to function as expected there is a hash-commitment mechanism.
The hash commitment is a bit involved, first we pre-sign a $2^L$ transaction flows for each possible input ($D$). To execute the program, the operator needs to find a nonce such that a hash based on the user input $\mathcal{X}$ the $Hash(x,r)$ matches an element from $D$ and then uses that to run the computation. This puzzle is similar to the one used to the Proof Of Work (POW) protecting Bitcoin where miners need to do a certain amount of work for submitting an block.
The reason this it's secure is, similar to the POW for Bitcoin, the operator would need to find a "hash collision" (read: a hash with at least the equivalent amount of work) with $D$ to to cheat and that is exponentially more expensive than just doing the honest work.
Delbrag is a proposal from the original legend himself, Jeremy Rubin. It's mean to BitVM like, but moves the computation off-chain and only have the final computation be published on-chain by utilizing Garbled Circuits (CG).
This blogpost will do a better job than I would do at explaining GG, but the TLDR is that it's a way for two parties to evaluate an arbitrary function with secret inputs without revealing the inputs.
citrea.xyz does use it for their clementine v2 bridge . Where they took a Groth16 verifier and made it into a CG. This made their disproving mechanism $\approx 100 000$ times more efficient over using the standard BitVM disproving mechanism.
Hopefully this gave a bit more context into BitVM(X). To summarize
If you want to read more on the topic: