BitVM Overview: Bringing Proofs of Validity to Bitcoin

BitVM is the newest hot protocol in the Bitcoin ecosystem, with the potential to benefit every project built on Bitcoin. Let’s talk about the design of BitVM and the new possibilities it opens up for Bitcoin.

“Bitcoin Season 2^[3]” is well underway, and developers and users alike are excited about building projects on Bitcoin and bringing new use cases and new approaches to solving the eternal challenges of building on Bitcoin.

Bitcoin does not scale. Due to limited block space, transaction fees can fluctuate wildly during times of network congestion. With only 7 transactions per second and each block containing only about 1MB of data, Bitcoin alone is not enough if you want to enable billions of users to use Bitcoin. You need a scaling solution^[4] .

A lot of work has been done on Bitcoin L2s^[5] (Layer2 blockchains) to improve Bitcoin's scalability and introduce new features. There are dozens of projects building on Bitcoin today^[6] , and one of the most promising areas of research and innovation is Bitcoin Rollups^[7]. 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, with a cryptographic proof system so that participants can verify that the submitted state change is accurate.

However, there are challenges in bringing this kind of proof system to Bitcoin, which is where BitVM comes in.

What is BitVM?

BitVM^[8] is a protocol/rule set that enables fraud proofs on Bitcoin and is immediately available to developers for a variety of use cases on Bitcoin, including Bitcoin Rollups, minimal trust bridges, and more. The core design of BitVM moves computation off-chain and implements the fraud proof mechanism on the Bitcoin blockchain.

BitVM enables fraud proofs on Bitcoin.

The BitVM whitepaper was published in October 2023 by Robin Linus (notably, Robin is part of the ZeroSync^[9] team working on a zero-knowledge proof system for Bitcoin), and developers have begun experimenting with the protocol over the past few months, with growing interest.

You can think of BitVM as a distributed protocol/set of rules that participants agree to follow in advance, rather than an actual virtual machine implemented in software (like the Ethereum Virtual Machine). Similar to how Bitcoin Ordinals^[10] work, there is a social consensus component, participants opt-in to the rules, and these rules are not fully enforced at the protocol level.

What makes BitVM so exciting is that it provides a challenge-response protocol for verifying arbitrary circuits on Bitcoin - you can make claims off-chain (e.g., this proof works) and use Bitcoin L1 to verify it. The "on Bitcoin" part is key here because building on Bitcoin is very difficult, and if implemented, the BitVM protocol could be used to build optimistic rollups, two-way BTC pegs, etc., which could benefit other projects building on Bitcoin.

What problem does BitVM solve?

Any project building on Bitcoin knows how difficult it is to interact with the chain (at Hiro, we’ve experienced this pain firsthand). One of the challenges of building on Bitcoin is that Bitcoin doesn’t have the power to handle complex computations.

There are no smart contracts. There is no virtual machine. Programmability is limited to what developers can build via opcodes^[11] (opcodes), and that functionality is limited. Introducing new opcodes requires a BIP and a Bitcoin fork (which is very difficult).

So, without forks and new opcodes, we’re left with limited programmability. In the case of scaling Bitcoin, this limitation manifests itself in two main ways:

1. If you want to build a two-way BTC peg, it’s difficult to remove trust from the equation. Most BTC pegs today involve a custodian, either a single institution or a consortium that controls a multi-signature, to process deposits/withdrawals. Sometimes described as the “write problem”. In the Stacks ecosystem, the upcoming Nakamoto upgrade^[12] includes designs for minimal trust bridges—more on this later.

2. If computation or transactions are to be moved off-chain via Rollup, it is difficult to verify and validate off-chain data on Bitcoin itself. This is a verification problem.

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

How does BitVM work?

A good way to think of BitVM is as a protocol or set of rules. If two parties agree in advance to follow these rules (which means they need to cooperate with each other), they can play arbitrary challenge-response games. In theory, this can be used to verify/prove arbitrarily complex programs on Bitcoin (where the actual execution of these programs happens off-chain).

Let's take a concrete example.

Suppose Alice and Bob want to play a coin tossing game. Both players put 0.5 BTC each in the prize pool. Heads wins 1 BTC. Alice has the coin and will toss it first. Bob wants to make sure Alice doesn't cheat. Here's how they play the game using BitVM (many details omitted for simplicity):

1. Alice and Bob agree to follow the BitVM protocol.

2. Suppose heads is represented by the value H0 and tails by the value H1. Alice generated H0 and H1 by choosing two other values, say P0 and P1, and hashing them. Therefore, Hash(P0) = H0 and Hash(P1) = H1. P0 is called the "preimage" of H0, and P1 is called the preimage of H1.

3. Alice shares the values ​​H0 and H1 with Bob (effectively, Alice irrevocably "commits" to these hash values, so she can't later claim to have different values). Bob does not know the preimages P0 and P1 (and "guessing" these values ​​is very difficult, so we can safely assume that Bob will not magically discover these values).

4. Alice and Bob pre-sign two transactions: one for the challenge, and one for the response.

1. In the challenge transaction, Bob will include a script that basically checks if the provided input hashes to one of the known hash values ​​H0 or H1 - if it hashes to H0, Bob knows the value is heads; if it is H1, it is tails. Additionally, the script has a time lock, and if no response is received before the deadline, Bob wins the prize.

2. In the response transaction, Alice can "reveal" the coin toss result by including the corresponding preimage P0 or P1. If Alice includes no value, both values, or any value other than P0 or P1, Bob wins the prize. Otherwise, if the value is P0 (heads), Alice wins the prize.

5. Now we are ready to start the game. Alice flips a coin but has not yet revealed the result. Bob issues a challenge transaction, and Alice subsequently broadcasts a response transaction. The logic of “fraud detection” is executed on-chain via the script described earlier. Obviously, this is a trivial and contrived example, but it demonstrates the key idea. For a slightly more complex example, consider the game of tic-tac-toe designed by a developer called Super Testnet. You can check out the GitHub repository here^[13], and you can even play “bit tac toe^[14]” today. Super Testnet actually demonstrated this game to Hiro, which you can watch below:

Bitvm Crash Course on Youtube ^[15]

Here are the high-level components of the game:

• Tic-tac-toe is a 9-square grid. The first player, Alice, can make at most 5 moves, so there are 45 pre-images and hashes (9 per turn). The second player, Bob, can make at most 4 moves, so there are 36 hashes.

• There are 3 ways to "cheat" in Tic-Tac-Toe: a player can place multiple X/Os on their turn; a player can overwrite a square they used previously; a player can overwrite a square their opponent used previously. Therefore, the challenge/response protocol is built around detecting these cases.

• The challenge transaction will force the other player to "reveal" which square they placed an X or O on.

• The response transaction will have a script that will check for all 3 of the above cases:

• If no cheating is detected, the game continues (or the game ends because someone won).

• If cheating is detected, the challenger wins and the prover loses.

Note that in both cases, the fraud proofs were handcrafted and designed specifically for that use case: a fraud proof for tic-tac-toe wouldn't work for a coin toss, or anything else.

Back to the big picture, the BitVM whitepaper describes a general approach: for any program, it provides a way to construct a validity proof of that program. The key insights are as follows:

• From the coin toss example, we saw how to verify a single bit: let's call this a "bit commitment" proof.

• With bit commitments, we can build logic gate commitments: consider the Boolean AND/OR operator - for any two inputs (each taking the value 0 or 1), this operator defines a single output. So, using 2 bit commitments as input and 1 bit commitment as output, we can create a validity proof for any logic gate. The BitVM whitepaper uses a NAND logic gate.

• Finally, any arbitrary computation can be represented using a series of logic gates. The BitVM whitepaper calls these "binary circuits". Such circuits can be efficiently represented using Tapscript, with each leaf in the tap tree representing a single gate commitment.

• Then, the challenge/response protocol essentially involves verifying the output of a specific gate commitment. In the worst case, you might need to verify the output of every single gate.

See this repository ^[16] for one way to convert arbitrary programs into tapleaf circuits.

How do Stacks fit in?

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

1. Improving trust assumptions for sBTC

2. Adding validity proofs for Stacks blocks on Bitcoin

Why these two applications? The current sBTC design^[17] is already one of the most secure, trust-minimized two-way pegs for Bitcoin under development. Nonetheless, there is still room for improvement in terms of security model and trust assumptions^[18]. Instead of requiring at least 30% honest signers or trusting a set of high-reputation signers, a BitVM-based approach could theoretically allow sBTC to operate with only a single honest actor.

Similarly, while each Stacks block settles on Bitcoin, the current design only allows you to independently verify Stacks data if you have a copy of the chain state. If using BitVM, Stacks blocks also include validity proofs, so you can check not only integrity (the data in a given Stacks block is consistent with the hash stored on Bitcoin), but also correctness (you can verify that the transactions in a given Stacks block were actually executed correctly by looking at the proofs stored on Bitcoin). In other words: this will enable Stacks to develop into an optimistic Rollup on Bitcoin.

The specifics of how to use BitVM to implement these applications require more research and development. But we can try to sketch out some ideas at a high level.

BitVM and sBTC

Consider the example of sBTC: the anchoring process is very simple and can be completed by broadcasting a Bitcoin transaction. However, in the current design, the anchor withdrawal process relies on signers to process the request (on Stacks). This imposes some constraints:

• Exits can take time, depending on how many signers are offline/honest.

• You need to trust the network of signers, and more broadly the entire Stacks.

If you instead (or perhaps also) generate a validity proof on Bitcoin and use BitVM^[19], then:

• Exits can be processed optimistically (and thus, on the happy path, faster).

• The anchor only needs one honest participant to run; you don’t need to trust 30% of the signer network.

The key is to figure out exactly how to construct the validity proof. The brute force approach described in the BitVM whitepaper would work, but would likely result in a very large tapleaf circuit (billions of nodes). This in turn means that any challenge would take a long time (perhaps weeks or more), not to mention the cost in terms of attention and resources (transaction fees!). As we saw with the tic-tac-toe example, more concise proofs can be constructed, tailored for specific use cases, and similar approaches may work better for this case.

BitVM and Stacks

As for the validity proof of the entire Stacks block, there is a lot of design space worth exploring. For example, is the proof at the granularity of a single transaction or the granularity of an entire block or something in between (such as transactions forming a causal dependency chain)? Is it possible to take an incremental approach, such as generating proofs for simple token transfers first, and then gradually adding Clarity contracts? Is this a good use of Bitcoin block space, since Stacks miners and network participants already have an economic incentive to maintain a complete history of the Stacks chain state?

Conclusion

BitVM is an exciting topic that will require more research, thought, and experimentation than a blog post can provide, but I hope this has helped shed light on one of the most exciting recent developments in Bitcoin.