# BitVM: Compute Anything on Bitcoin

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/bitvm-compute-anything-on-bitcoin

- **Authors:** Robin Linus
- **Published:** 2023
- **Topic:** Computer Science
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1741059582330-utf9p75zf2h-65bbdf7d79533da79ea3211653a1c349%2Fbitvm.pdf
- **Pages:** 8
- **Annotations:** 10 comments in 10 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/bitvm-compute-anything-on-bitcoin

## Annotations

### Annotation 1 (page 1)

Beside the passage: “Abstract BitVM is a computing paradigm to express Turing-complete Bitcoin contracts. This requires no changes to the network’s consensus rules. Rather than executing computations on Bitcoin, they are merely veriﬁed, similarly to optimistic rollups. A prover makes a claim that a given function evaluates for some …”

**Annotation** by João Batalha (2025-03-04):

> You’ll often hear the term "Turing complete" in discussions about blockchains and smart contracts. At its heart, Turing completeness means that a programming language can theoretically compute anything that a traditional computer can, given enough time and memory.
>
> Bitcoin’s built-in scripting language is intentionally not Turing complete - it’s simple, stack-based, and designed with limited functionality. A stack-based language operates by pushing and popping values onto a stack, rather than accessing variables directly. Bitcoin scripts intentionally lack loops and recursion, meaning they cannot run indefinitely—this is deliberate, because it guarantees scripts always terminate, ensuring predictable behavior and security.
>
> Ethereum, by contrast, uses a Turing-complete language, meaning Ethereum smart contracts can, in theory, perform arbitrarily complex computations, loops, and conditional logic directly on-chain. This makes Ethereum powerful for programming complex contracts but introduces complexity and potential vulnerabilities.
>
> BitVM shows that although Bitcoin itself is not Turing complete, we can cleverly achieve Turing-complete contracts off-chain, only using Bitcoin’s limited on-chain scripting language to verify (rather than execute) computations.

### Annotation 2 (page 1)

Beside the passage: “Abstract BitVM is a computing paradigm to express Turing-complete Bitcoin contracts. This requires no changes to the network’s consensus rules. Rather than executing computations on Bitcoin, they are merely veriﬁed, similarly to optimistic rollups. A prover makes a claim that a given function evaluates for some …”

**Annotation** by João Batalha (2025-03-04):

> ### Optimistic Rollups
>
> Optimistic Rollups are a blockchain scaling technique designed to handle large numbers of transactions off-chain. The name "optimistic" comes from the assumption that most computations or transactions are honest and don't need immediate verification. Instead of checking every action on-chain (which is slow and costly), transactions are executed off-chain, and only a summary or "rollup" is recorded on-chain.
>
> These rollups work by assuming honesty first - transactions are optimistically accepted without immediate verification. If nobody disputes them within a given timeframe, they're finalized. But if someone suspects wrongdoing, they can submit a fraud proof, prompting the blockchain to verify the challenged transaction. If fraud is found, the dishonest actor loses a deposit.
>
> Optimistic rollups are primarily used on Ethereum to address scalability limitations. Introduced around 2019–2020 by Ethereum community researchers, these rollups help Ethereum process more transactions efficiently without sacrificing its robust security guarantees.

### Annotation 3 (page 1)

Beside the passage: “Abstract BitVM is a computing paradigm to express Turing-complete Bitcoin contracts. This requires no changes to the network’s consensus rules. Rather than executing computations on Bitcoin, they are merely veriﬁed, similarly to optimistic rollups. A prover makes a claim that a given function evaluates for some …”

**Annotation** by João Batalha (2025-03-04):

> ### Taproot
>  Taproot addresses, introduced to Bitcoin in 2021, significantly enhanced privacy and efficiency by allowing complex scripts to appear indistinguishable from simple transactions. Developed by Pieter Wuille and other Bitcoin contributors, Taproot solved the issue of limited privacy and scalability for complex scripts by combining them into a compact, cryptographic structure.
>
> Internally, Taproot uses a Merkelized Abstract Syntax Tree (MAST) - think of it as a cryptographic "tree" structure where only the specific branch that's executed is revealed, keeping all other conditions hidden and private. This makes even highly complex Bitcoin contracts look just like ordinary transactions, unless explicitly revealed.

### Annotation 4 (page 1)

Beside the passage: “By design, the smart contract capabilities of Bitcoin are reduced to basic operations, such as signatures, timelocks, and hashlocks. The BitVM creates a novel design space for more expressive Bitcoin contracts and also oﬀ-chain computation. Potential applications include games like Chess, Go, or Poker, and …”

**Annotation** by João Batalha (2025-03-04):

> By design, Bitcoin supports only very simple smart contracts using basic operations. The main building blocks are:
>
> - **Signatures (`OP_CHECKSIG`):** Verify that a transaction was authorized by the rightful owner.
> - **Timelocks (`OP_CHECKLOCKTIMEVERIFY` / `OP_CHECKSEQUENCEVERIFY`):** Restrict spending funds until a specific block height or time has passed.
> - **Hashlocks (`OP_HASH160`, `OP_EQUALVERIFY`):** Lock coins until someone reveals a secret preimage matching a previously committed hash.
>
> These intentionally limited operations ensure Bitcoin remains secure and predictable, at the expense of complex programmability.

### Annotation 5 (page 2)

Beside the passage: “Similar to Optimistic Rollups[1] and the MATT proposal (Merkelize All The Things)[2], our system is based on fraud proofs and a challenge-response protocol. However, BitVM requires no changes to Bitcoin’s consensus rules. The underlying primitives are relatively simple. It’s mostly based on hashlocks, timelocks, and …”

**Annotation** by João Batalha (2025-03-04):

> ### MATT
> "MATT," short for "Merkelize All The Things," is a proposal to enhance Bitcoin’s contract capabilities without changing its fundamental rules. It suggests encoding complex contract logic and conditions using Merkle trees - a cryptographic structure that hides detailed logic behind simple hashes. Complex conditions remain hidden until explicitly executed, significantly improving privacy and efficiency.
>
> MATT is similar in spirit to Optimistic Rollups (popularized around 2019, mostly in Ethereum), which execute transactions off-chain and periodically post transaction summaries on-chain, assuming correctness unless disputed. In contrast, MATT commits logic directly on-chain from the beginning but keeps details hidden until executed. MATT emerged shortly after optimistic rollups (~2021), applying similar concepts but specifically adapted to Bitcoin's architecture.

### Annotation 6 (page 2)

Beside the passage: “The bit value commitment is the most elementary component of the system. It allows the prover to set the value of a particular bit to either “0” or “1”. Especially, it allows the prover to set the value of a variable across diﬀerent Scripts and UTXOs. This is key, as it extends the execution runtime of Bitcoin’s VM by …”

**Annotation** by João Batalha (2025-03-04):

> In BitVM, the basic building block is the **bit value commitment**, where the prover securely commits to setting a specific bit (either 0 or 1). To understand this clearly, recall two important Bitcoin concepts:
>
> - **UTXO (Unspent Transaction Output):**
>   A UTXO is essentially a "coin" locked by conditions defined in scripts. You can only spend the coin if you satisfy those conditions.
>
> - **Scripts:**
>   Small pieces of logic attached to UTXOs that determine under which conditions they can be spent.
>
> BitVM leverages bit commitments to chain multiple transactions together, like so:
>
> 1. Transaction #1 creates a UTXO with a script containing a committed bit (0 or 1).
> 2. Transaction #2 spends this UTXO by running its script, checking the previously set bit, and possibly committing a new bit.
> 3. This process repeats through multiple transactions, each validating previous bits and setting new conditions.

### Annotation 7 (page 2)

Beside the passage: “The bit value commitment is the most elementary component of the system. It allows the prover to set the value of a particular bit to either “0” or “1”. Especially, it allows the prover to set the value of a variable across diﬀerent Scripts and UTXOs. This is key, as it extends the execution runtime of Bitcoin’s VM by …”

**Annotation** by João Batalha (2025-03-04):

> When the prover and verifier first set up the circuit, the prover commits to a single bit ("0" or "1") by publishing two hashes (**hash0** and **hash1**), each corresponding secretly to **preimage0** and **preimage1** respectively. Initially, only the prover knows both preimages.
>
> Later, the prover chooses one bit value by revealing exactly one preimage (for example, **preimage1**, meaning "bit = 1"). If at any point the prover reveals both preimages (**preimage0** and **preimage1**), that's called **equivocation**, because the prover has tried to commit to both values.
>
> In this scenario, the verifier can now prove fraud by using these two preimages to satisfy a hashlock condition set previously in the Bitcoin script, unlocking and claiming the prover's deposit as punishment.

### Annotation 8 (page 3)

Beside the passage: “Any computable function can be represented as a Boolean circuit. The NAND gate is a universal logic gate, so any Boolean function can be composed from them. To keep our model simple, we show that our method works for simple NAND gates. Additionally, we show how to compose gates arbitrarily. Together this demonstrates …”

**Annotation** by João Batalha (2025-03-04):

> The fact that any computable function can be represented as a Boolean circuit comes from foundational work in computational complexity, especially related to the Cook-Levin theorem, proven independently by Stephen Cook in 1971 and Leonid Levin in 1973.
>
> This theorem essentially showed that any computational task solvable by a Turing machine (the abstract mathematical model for computation) can also be represented by a Boolean circuit composed of logic gates. In other words, Boolean circuits are universal and capable of expressing any computational problem, given sufficient size and complexity.

### Annotation 9 (page 4)

Beside the passage: “In the previous section we deﬁned NAND gate commitments. We can express any circuit by composing gate commitments. Every step of the execution is committed to in a Tapleaf. They’re are all combined into the same Taproot address, such that the prover could execute any gate in the circuit. Executing a gate requires the …”

**Annotation** by João Batalha (2025-03-05):

> In BitVM, each computational step (logic gate execution) is encoded into its own separate script, called a Tapleaf. These scripts are hidden together within a single Taproot address. To execute a particular gate, the prover creates an on-chain transaction that reveals the specific Tapleaf corresponding to that gate.
>
> Revealing a Tapleaf means the prover provides the blockchain with:
> * The script for that specific logic gate,
> * The necessary input and output values to satisfy the gate’s logic,
> * Proof linking the revealed script back to the original Taproot address.
>
> This allows verification of any chosen gate's correctness directly on-chain, while keeping all other gates hidden.

### Annotation 10 (page 5)

Beside the passage: “Committing to a circuit is not enough. To disprove an incorrect claim, the veriﬁer has to be able to challenge the prover’s statement. This is possible by them pre-signing a sequence of transactions during setup. The transactions are linked like challenge → response → challenge → response → . . .. If one of the …”

**Annotation** by João Batalha (2025-03-05):

> In this context, pre-signing a sequence of transactions means that before execution begins, the prover and verifier collaboratively create and sign a series of Bitcoin transactions off-chain. These transactions aren’t immediately broadcasted; instead, they're privately stored. The Taproot address acts as a cryptographic anchor for these commitments, ensuring that neither party can alter the terms later. If disputes arise, either party can broadcast these pre-signed transactions to enforce the challenge-response mechanism on-chain, resolving disputes efficiently.

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

BitVM: Compute Anything on Bitcoin

Robin Linus robin@zerosync.org

December 12, 2023

Abstract BitVM is a computing paradigm to express Turing-complete Bitcoin contracts. This [Annotation 1] requires no changes to the network’s consensus rules. Rather than executing computations on Bitcoin, they are merely veriﬁed, similarly to optimistic rollups. A [Annotation 2] prover makes a claim that a given function evaluates for some particular inputs to some speciﬁc output. If that claim is false, then the veriﬁer can perform a succinct fraud proof and punish the prover. Using this mechanism, any computable function can be veriﬁed on Bitcoin. Committing to a large program in a Taproot address requires signiﬁcant amounts [Annotation 3] of oﬀ-chain computation and communication, however the resulting on-chain footprint is minimal. As long as both parties collaborate, they can perform arbitrarily complex, stateful oﬀ-chain computation, without leaving any trace in the chain. On-chain execution is required only in case of a dispute.

1 Introduction

By design, the smart contract capabilities of Bitcoin are reduced to basic operations, [Annotation 4] such as signatures, timelocks, and hashlocks. The BitVM creates a novel design space for more expressive Bitcoin contracts and also oﬀ-chain computation. Potential applications include games like Chess, Go, or Poker, and particularly, veriﬁcation of validity proofs in Bitcoin contracts. Additionally, it might be possible to bridge BTC to foreign chains, build a prediction market, or emulate novel opcodes. The main drawback of the model proposed here is that it is limited to the two-party setting with a prover and a veriﬁer. Another limitation is that, for both the prover and the veriﬁer, signiﬁcant amounts of oﬀ-chain computation and communication is required to execute programs. However, these issues seem likely to be solved by further research. In this work, we focus solely on the key components of the two-party BitVM.

1

#### Page 2

2 Architecture

Similar to Optimistic Rollups[1] and the MATT proposal (Merkelize All The Things)[2], our system is based on fraud proofs and a challenge-response protocol. However, BitVM [Annotation 5] requires no changes to Bitcoin’s consensus rules. The underlying primitives are relatively simple. It’s mostly based on hashlocks, timelocks, and large Taproot trees. The prover commits to the program literally bit-by-bit, however verifying all of that on-chain would be too computationally expensive, so the veriﬁer performs a sequence of carefully crafted challenges to succinctly disprove a false claim of the prover. Prover and veriﬁer jointly pre-sign a sequence of challenge-and-response transactions, which they can later use to resolve any dispute. The model is designed to simply illustrate that this approach allows for universal computations on Bitcoin. For practical applications we should consider more eﬃcient models.

The protocol is simple: Firstly, prover and veriﬁer compile the program into a huge binary circuit. The prover commits to that circuit in a Taproot address which has a leaf script for every logic gate in the circuit. Additionally, they pre-sign a sequence of transactions, enabling a challenge-response game between the prover and the veriﬁer. Now they have exchanged all of the required data, so they can make their on-chain deposits to the resulting Taproot address. This activates the contract and they can start exchanging oﬀ-chain data to trigger state changes in the circuit. If the prover makes any incorrect claim, the veriﬁer can take their deposit. This guarantees attackers always lose their deposits.

3 Bit Value Commitment

The bit value commitment is the most elementary component of the system. It allows the prover to set the value of a particular bit to either “0” or “1”. Especially, it allows the prover to set the value of a variable across diﬀerent Scripts and UTXOs. This is key, as it extends the execution runtime of Bitcoin’s VM by splitting it across multiple [Annotation 6] transactions. Similar to Lamport signatures[3], the commitment contains two hashes, hash0 and hash1. At some later point, the prover sets the bit’s value either to “0” by revealing preimage0, the preimage of hash0 – or the prover sets the bit’s value to “1” by revealing preimage1, the preimage of hash1. If, at some point, they reveal both preimages preimage0 and preimage1, then the veriﬁer can use them as a fraud proof, and take the prover’s deposit. That is called equivocation. Being able to punish equivocation is what makes the commitment binding – it is an “incentive-based commitment”. [Annotation 7] Combining bit value commitments with timelocks allows the veriﬁer to force the prover

2

#### Page 3

to decide the value of a particular bit within some given time frame.

Figure 1: A concrete implementation for a 1-bit commitment. To unlock this script, the prover has to reveal either the preimage of hash0 or of hash1. In this example execution, the prover reveals hash1, and sets the bit’s value to “1”. We can have copies of this commitment to enforce a speciﬁc value across diﬀerent scripts.

For simplicity, from here on, we assume there’s an opcode OP BITCOMMITMENT, which is shorthand for the script above. The opcode consumes two hashes and a preimage of one of the hashes. It puts a bit value on the stack, according to which hash is matched by the preimage.

4 Logic Gate Commitment

Any computable function can be represented as a Boolean circuit. The NAND gate is a universal logic gate, so any Boolean function can be composed from them. To keep our [Annotation 8] model simple, we show that our method works for simple NAND gates. Additionally, we show how to compose gates arbitrarily. Together this demonstrates BitVM can express any circuit. The implementation of a NAND gate commitment is simple. It contains two bit commitments representing the two inputs and a third bit commitment representing the output. The Script computes the NAND value of the two inputs to ensure that it matches the committed output bit.

3

#### Page 4

Figure 2: Logic gate commitment for a NAND operation. Executing this script requires to reveal values for the bit commitments A, B, and C, such that A NAND B = C holds.

(Here, we assume for simplicity, that an opcode for OP NAND exists. Actually it does not exist, however, it can be easily implemented using OP BOOLAND and OP NOT.)

5 Binary Circuit Commitment

In the previous section we deﬁned NAND gate commitments. We can express any circuit by composing gate commitments. Every step of the execution is committed to in a Tapleaf. They’re are all combined into the same Taproot address, such that the prover could execute any gate in the circuit. Executing a gate requires the prover to open the [Annotation 9] corresponding gate commitment and set values for its inputs and output bits.

4

#### Page 5

The Taptree might become huge and have a billion Tapleaf Scripts, but its on-chain footprint is minimal.

Figure 3: A random example circuit which has 8 diﬀerent NAND gates, and 4 inputs A,B,C, and D. Using billions of gates would allow us to deﬁne basically any function.

Figure 4: For each gate, the prover’s Taproot address contains a leaf script with a corresponding gate commitment. This allows the prover to set the values of the circuit’s inputs, (here, A,B,C, and D), at any point later in time.

6 Challenges and Responses

Committing to a circuit is not enough. To disprove an incorrect claim, the veriﬁer has to be able to challenge the prover’s statement. This is possible by them pre-signing a sequence of transactions during setup. The transactions are linked like challenge → response → challenge → response → . . .. If one of the parties stops engaging then, after [Annotation 10]

5

#### Page 6

some timeout, the other party wins the challenge and can take both deposits. As long as both parties are cooperative, they can jointly settle any contract with a 2-of-2 signature. The following mechanism is required only in case of fraud.

Figure 5: A pre-signed sequence of transactions to perform multiple rounds of challengeand-response. This sequence is generated during setup. Vicky chooses a challenge by opening one of the hashlocks in her Tapscript leaves. This unlocks for Paul a speciﬁc Tapscript and forces him to execute it. The script forces Paul to reveal the gate commitment challenged by Vicky. Any inconsistent claim can be disproven quickly by repeating this procedure for a few rounds of queries.

If the prover stops collaborating with the veriﬁer oﬀ-chain, the veriﬁer needs a way to force his hand on-chain. The veriﬁer does this by unlocking a hashlock: each of the NAND Tapleaves in the prover’s UTXO can only be spent if the prover knows a preimage held by the veriﬁer. Therefore, the prover can prove that a given Tapleaf executes correctly by revealing its inputs and outputs, but only if the veriﬁer “unlocks” it for him by revealing the preimage to the hash that guards that Tapleaf. Applying binary search, the veriﬁer can quickly identify the prover’s error after just a few rounds of challenge-and-response.

6

#### Page 7

Figure 6: After each response, Vicky can punish equivocation. If Paul ever reveals two conﬂicting values for a variable, then Vicky immediately wins the challenge and is allowed to take his deposit. Vicky proves Paul’s equivocation by revealing for any of his bit commitments both of the preimages.

7 Inputs and Outputs

The prover can set inputs by revealing the corresponding bit commitments. Ideally, they reveal the commitments oﬀ-chain to minimize their on-chain footprint. In the noncooperative case the veriﬁer can force the prover to reveal their inputs on-chain. It is possible to process large amounts of data by exchanging it upfront, but encrypted. This way the prover can reveal the decryption key at a later point in time. Multi-party inputs are also possible. Gates can have bit commitments from both parties.

8 Limitations and Outlook

It is ineﬃcient to express functions in simple NAND circuits. Programs can be expressed more eﬃciently by using more high-level opcodes. E.g., Bitcoin script supports adding 32-bit numbers, so we need no binary circuit for that. We could also have larger bit commitments, e.g. it is possible to commit to 32 bits in a single hash. Additionally, scripts can be up to about 4 MB in size. Thus, we can implement substantially more than a single NAND instruction per leaf script.

The model proposed here is limited to two parties. However, it might be possible to have

7

#### Page 8

two-way channels, and chain them to form a network similar to Lightning. Exploring the two-party setting might yield interesting possibilities for generalization. For example, we can explore a 1-to-n star topology for the network. Another research question is if we can apply our model to the n-of-n setting and create more sophisticated channel factories. Furthermore, we could combine our system with diﬀerent oﬀ-chain protocols, e.g., the Lightning Network or rollups. Other directions of research include cross-application memory, how to make statements about arbitrary data inscribed into the chain, or oﬀ-chain programmable circuits, i.e. an oﬀ-chain VM. It also might be possible to apply more sophisticated sampling techniques, similar to STARKs, to check a circuit in a single round. The next major milestone is to complete a design and an implementation of a concrete BitVM and also of Tree++, a high-level language to write and debug Bitcoin contracts.

9 Conclusion

Bitcoin is Turing-complete in the sense that encoding fraud proofs in large Taptrees allows to verify the execution of any program. A major constraint of the model outlined here is that it is limited to the two-party setting. Hopefully, this can be generalized in further works.

Acknowledgments

Special thanks to Super Testnet and Sam Parker, who always kept refusing to believe that Bitcoin would not be Turing-complete.

References

[1] Ethereum Research. Optimistic rollups. https://ethereum.org/en/developers/

docs/scaling/optimistic-rollups/, 2022.

[2] Salvatore Ingala. Merkleize all the things. https://lists.linuxfoundation.org/

pipermail/bitcoin-dev/2022-November/021182.html, 2022.

[3] Jeremy Rubin. CheckSigFromStack for 5 Byte Values. https://rubin.io/blog/

2021/07/02/signing-5-bytes, 2021.

Sponsor BitVM developers: bc1qf5g6z0py2t3t49gupeqrlewga0qz2etalu4xf9

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/bitvm-compute-anything-on-bitcoin. More annotated papers: https://fermatslibrary.com/llms.txt
