An Overview of BitVM: Bringing Validity Proofs to Bitcoin

“Bitcoin Season 2” is well underway this cycle, and devs and users alike are excited by the prospect of building on Bitcoin and bringing new use cases and fresh approaches to the perennial challenge of building on Bitcoin.

Bitcoin isn’t scalable. By its very nature, block space is limited, and transaction fees can vary wildly as users pay higher fees in times of network congestion. Processing only 7 transactions per second, and with each block only containing ~1MB of data, if you want Bitcoin to be used by billions of users, Bitcoin alone isn’t enough. You need scaling solutions.

And a lot of work has been done on Bitcoin L2s (layer 2 blockchains) to bring better scalability and new functionality to Bitcoin. Today there are dozens of projects building on Bitcoin, and one of the most promising areas of research and innovation is around Bitcoin rollups. At a high level, Bitcoin rollups enable transactions to occur off-chain and then be “rolled up” into a single state change that is submitted to the blockchain, and there is a cryptographic proof system so that participants can verify whether that submitted state change is accurate or not.

However, there are challenges with bringing this proof system to Bitcoin, and that’s where BitVM comes in.

What Is BitVM?

BitVM is a protocol/set of rules that enables, among other things, fraud proofs on Bitcoin. This protocol can be used by devs today and enables a wide range of use cases on Bitcoin, including Bitcoin rollups, trust-minimized bridges, and more. The core design of BitVM takes computation off-chain and implements a fraud proving mechanism on the Bitcoin blockchain.

BitVM enables fraud proofs on Bitcoin.

The BitVM white paper was just published in October 2023 by Robin Linus (which is noteworthy because Robin is part of the ZeroSync team, a project working on zero knowledge proof systems for Bitcoin), and developers have begun experimenting with this protocol with increasing interest in the past few months.

You can think of BitVM as a distributed protocol/set of rules that participants agree to follow ahead of time instead of an actual virtual machine implemented by software (such as the Ethereum Virtual Machine). Similar to the way Bitcoin Ordinals works, there is a component of social consensus here, where participants opt in to the stated rules, and those rules aren’t fully enforced at the protocol layer.

The reason BitVM is so exciting is that it offers a challenge-response protocol for verifying arbitrary circuits on Bitcoin—you can make a claim off-chain (e.g. this proof is valid) and use the Bitcoin L1 to verify it. The “on Bitcoin” part is key because building on Bitcoin is very difficult, and if implemented, the BitVM protocol can then be used to build optimistic rollups, 2-way BTC pegs, and more that can benefit other projects building on Bitcoin.

What Problem Does BitVM Solve?

Any project building on Bitcoin knows how difficult it is to work with the chain (at Hiro, we know this pain firsthand). One of the challenges of building on Bitcoin is that Bitcoin doesn’t have the ability to process complex computation.

There are no smart contracts. There is no virtual machine. Programmability is limited to what developers can build via Opcodes (operation codes), and that functionality is limited. Introducing new Opcodes requires a BIP and a Bitcoin fork (which is very hard to do).

So without a fork and new Opcodes, we are left with limited programmability. In the case of scaling Bitcoin, this limitation appears primarily in two ways:

1. If you want to build a 2-way BTC peg, it is very difficult to remove trust from the equation. Most BTC pegs today involve custodians, whether a single institution or a federation controlling a multisig, to process deposits/withdrawals. This is sometimes described as “the write problem”. In the Stacks ecosystem, the upcoming Nakamoto upgrade includes designs for a trust-minimized bridge—more on that later.
2. If you want to push computation or transactions off-chain via a rollup, it is very difficult to authenticate and verify that off-chain data on Bitcoin itself. This is a verification issue.

For both of these issues, BitVM can unlock dramatic design improvements by implementing a challenge/response protocol on the Bitcoin L1.

How does BitVM work?

A good way to think of BitVM is that it is a protocol, or a set of rules. If two parties agree beforehand to follow these rules (which implies they need to cooperatively collaborate with each other), they can then play arbitrary challenge-response games. In theory, this can be used to validate / prove arbitrarily complex programs on Bitcoin (the actual execution of these programs happens off-chain).

Let’s take a concrete example.

Suppose Alice and Bob want to play a coin toss game. Both players put 0.5 BTC in the pot. Heads wins 1 BTC. Alice has the coin and will flip first. Bob would like to make sure Alice doesn’t cheat. Here’s how they can play this game using BitVM (omitting many details for simplicity):

1. Alice and Bob agree they will follow the BitVM protocol.
2. Let’s say heads is denoted by the value H0, and tails is denoted by the value H1. Alice generates H0 and H1, by picking two other values, say P0 and P1 and hashing them. Thus Hash(P0) = H0 and Hash(P1) = H1. P0 is called the “preimage” of H0, P1 the preimage of H1. 
3. Alice shares the values H0 and H1 with Bob (in reality, Alice irrevocably commits to these hash values, so she can’t claim to have had different values later). Bob does not know the pre-images P0 and P1 (and it’s prohibitively hard to “guess” them, so we can safely assume Bob won’t magically discover these values).
4. Alice and Bob pre-sign two transactions: one for the challenge, and the other for the response.some text
   1. In the challenge transaction, Bob will include a script that essentially checks whether a supplied input hashes to one of the known hash values H0 or H1 – if it hashes to H0, then Bob knows the value was heads; if H1, tails. Additionally, the script has a time lock that says if a response does not arrive by a deadline, then Bob gets the pot.
   2. In the response transaction, Alice gets to reveal the value of the coin toss by including the corresponding pre-image P0 or P1. If Alice includes no values, both values, or anything other than P0 or P1, Bob takes the pot. Otherwise, if the value is P0 (heads), Alice gets the pot.
5. We’re now ready to start the game. Alice flips the coin but does not reveal the value yet. Bob issues the challenge transaction and subsequently Alice broadcasts the response transaction. The logic for “fraud detection” is executed on chain via the scripts described earlier.

Obviously this is a trivial and contrived example, but it demonstrates the key ideas. For a slightly more complex example, consider a game of tic-tac-toe, as designed by a dev who goes by the name Super Testnet. You can view the GitHub repo here, and you can even play “bit tac toe” today. Super Testnet actually gave a presentation to Hiro on this game, which you can watch below:

Here are the high level components of the game:

• Tic-tac-toe is a 9 square grid. The first player Alice can make up to 5 moves, so there are 45 pre-images & hashes (9 per turn). The second player Bob can make up to 4 moves, so 36 hashes.
• There are 3 ways to “cheat” in tic-tac-toe: a player can place more than one X / O on their turn; a player can overwrite a square they previously used; a player overwrites a square the opponent previously used. So the challenge / response protocol is built around detecting these cases.
• A challenge transaction would force the other player to “reveal” which square they placed X or O in.
• A response transaction would have a script that would check against all 3 cases described above: if no fraud is detected, the game continues (or the game is over because someone wins). If fraud is detected, the challenger wins, the prover loses.

Note that in both these cases, the fraud proofs were hand-crafted, and designed specifically for that use-case: the fraud proofs for tic-tac-toe won’t work for coin-toss or anything else for that matter.

Stepping back to the big picture, the BitVM whitepaper describes a generalizable approach: given any program, it lays out one way of constructing validity proofs for that program. The key insight is as follows:

• From the coin toss example, we saw how to validate a single bit: let’s call this a “bit commitment” proof.
• With bit commitments in hand, we can construct a logical gate commitment: consider the boolean AND / OR operators – given any two inputs (each taking value 0 or 1), the operator defines a single output. So using 2 bit commitments for the input and 1 bit commitment for the output, we can create a validity proof for any logic gate. The BitVM paper works with a NAND logical gate.
• Finally, any arbitrary computation can be represented using a sequence of logic gates. The BitVM paper refers to this as a “binary circuit”. Such a circuit can be represented efficiently using Tapscript, such that each leaf in the tap tree represents a single gate commitment.
• Then, the challenge / response protocol basically involves validating the output of a specific gate commitment. In the worst case, you might have to validate the output of every single gate.

See this repo for one way of converting arbitrary programs into tapleaf circuits.

Where does Stacks fit in?

The two obvious and most relevant applications for BitVM in the Stacks ecosystem are:

1. Improving the trust assumptions for sBTC
2. Adding validity proofs for Stacks blocks on Bitcoin

Why these two applications? The current sBTC design is already one of the most secure, trust-minimized 2-way pegs for Bitcoin in development. Nevertheless, there’s room for improvement in the security model & trust assumptions. Rather than require at least 30% honest signers, or trust a group of high-reputation signers, a BitVM-based approach could, in theory, allow sBTC to require only a single honest participant in order to function.

Likewise, while each Stacks block settles on Bitcoin, the current design only lets you independently verify the Stacks data as long as you have one copy of the chainstate. If, using BitVM, Stacks blocks additionally include a validity proof, then you can not only check for integrity (the data in a given Stacks block is consistent with the hash for it stored on Bitcoin), but you can check for correctness as well (you can verify that transactions in a given Stacks block actually executed correctly by looking at the proof stored on Bitcoin). Put another way: this would allow Stacks to evolve into an optimistic rollup on Bitcoin.

Exactly how to leverage BitVM for each of these applications requires a lot more research & development. But we can try to sketch things out at a high-level.

BitVM & sBTC

Consider the sBTC example: pegging-in is pretty straightforward and can be done by simply broadcasting a Bitcoin transaction. However, the peg-out process in the current design relies on signers to process the request (on Stacks). This creates some constraints:

• The peg-out can take time, depending on how many signers are offline / honest.
• You need to trust this network of signers and more broadly trust Stacks as a whole.

If instead (or perhaps, in addition to), a peg-out request generated a validity proof on Bitcoin and used BitVM, then:

• Peg-outs could be processed optimistically (and thus, in the happy path, be processed faster).
• The peg only needs 1 honest participant to function; you don’t need to trust 30% of a signer network.

The trick is figuring out exactly how to construct the validity proof. The brute force approach described in the BitVM whitepaper can work, but will likely result in a very large tapleaf circuit (billions of nodes). That in turn means any challenge will take a very long time (likely weeks or longer), not to mention costs in attention and resources (transaction fees!). As we saw in the tic-tac-toe example, it’s possible to construct more succinct proofs that are customized for the use-case, and likely a similar approach would work better for this case.

BitVM & Stacks

As for validity proofs for entire Stacks blocks, there are lots of points in the design space worth exploring. For instance, are the proofs at the granularity of individual transactions or whole blocks or something in between (like transactions that make a causal dependency chain)? Is an incremental approach possible where say you start by generating proofs for simple token transfers and gradually add in Clarity contracts? Is this even a good use of Bitcoin blockspace, since Stacks miners and network participants are economically incentivized to maintain the full history of the Stacks chainstate already?

Conclusion

BitVM is an exciting topic that requires a lot more research, thought, and experimentation than can be done justice in a blog post, but I hope this helped shed some light on one of the more exciting recent developments in Bitcoin.

I’ll be following BitVM closely, and I’m excited to see what developers build with it.  If you find the space exciting and you’d like to work on projects related to the space, reach out to me on Twitter.