On October 9, Robin Linus, a developer from ZeroSync, released the BitVM whitepaper, which attracted huge attention from the community. BitVM introduces a new computing paradigm capable of expressing Turing-complete Bitcoin contracts without requiring modifications to the network’s consensus rules.

Decentralized Smart Contracts: Limitations and Goals

Bitcoin’s Script, a stack-based language, provides fundamental control structures, such as conditional checks, for defining the validation logic of transactions. It demands valid digital signatures to spend bitcoins through a simple process of conditional validation. That said, the Script was designed to be non-Turing complete. Although it doesn’t support complex flow control features like loops, this design ensures simplicity and security of the language. Such limitations have made it challenging for Script to execute complex computations, including those involving smart contracts.

While some Layer 2 solutions designed for Bitcoin can achieve basic smart contract functions by locking up assets, they essentially rely on multi-signature addresses and cross-chain asset mappings, which require a certain level of centralized trust. This compromises Bitcoin’s commitment to decentralization. Prior to the introduction of BitVM, the Bitcoin community had been exploring methods that would be decentralized, trust-minimized, and capable of Turing-complete computations.

BitVM: Compute Anything on Bitcoin

At the core of its innovation, BitVM utilizes Bitcoin’s existing Script system to implement logic gates (this includes AND gates, OR gates, NOT gates, and XOR gates, enabling operations like AND, OR, NOT, and XOR) to build arbitrarily complex Boolean circuits. These circuits are used to perform logic operations on binary inputs and give binary outputs; Boolean computation can be implemented using logic gates to carry out operations like AND, OR, NOT, and XOR. Specifically, BitVM employs Hash Time Locked Contracts (HTLC) and Taproot (a soft fork for optimizing Script activated in November 2021) to represent fundamental logic gates, such as AND and OR gates. BitVM then combines these basic logic gates to construct circuits of any complexity, essentially simulating a programmable computer on the Bitcoin blockchain.

Finally, in the event of disputes between transacting parties, an elegant challenge-response protocol, similar to fraud proofs on Bitcoin, can be employed for validation. A prover makes a claim that a given function evaluates for some particular inputs to some specific output. If that claim is false, then the verifier can perform a fraud-proof and punish the prover. Using this mechanism, any computable function can be verified on Bitcoin.

BitVM’s Design

Bit Value Commitment

Bit Value Commitment, a Bitcoin script, employs if-else statements to implement a commitment scheme. This cryptographic primitive makes sure that the sender can confirm the message’s content before sending it, and the content cannot be altered once it’s publicly disclosed. This commitment scheme encompasses two hash values, hash0 and hash1. Whether the returned value will be 0 or 1 is determined by comparing the hash value of the input to these two hash values.

Figure 1: A concrete implementation for a 1-bit commitment

Source: https://bitvm.org/bitvm.pdf

Logic Gate Commitment

In the theory of computation, any computable function can be represented as a Boolean circuit. In particular, the NAND gate is a universal logic gate that can be used to build all other complex logic gates. BitVM incorporates two bit value commitments representing the two inputs and a third bit value commitment representing the output to implement the NAND gate.

BitVM ingeniously expresses the NAND gate through Bitcoin scripts. This allows it to build arbitrarily complex Boolean logic circuits, effectively simulating a programmable computer via Script.

Figure 2: Implementation of a NAND gate using bit value commitments

Source: https://biquanlibai.notion.site/BitVM-2b8557e0ea004d0cbc52951782bc9754

Figure 3: Logic gate commitment for a NAND operation

Source: https://bitvm.org/bitvm.pdf

The script computes the NAND value of the two inputs to ensure that it matches the committed output bit.

Binary Circuit Commitment

BitVM can express any circuit by composing gate commitments. Every step of the execution is committed to in a Tapleaf. They are all combined into the same Taproot address, such that the prover can execute any gate in the circuit. Executing a gate requires the prover to open the corresponding gate commitment and set values for its inputs and output bits. For instance, in Figure 4, A, B, C, and D are predefined bit value commitments, each representing a bit. Logic operations involving the eight NAND gates are then carried out. For example, if A NAND B yield E, and E is used as the input for the next NAND gate, the final output of the entire circuit will be TRUE. This design of Boolean circuits connects the NAND gates of bit value commitments and achieves complex logic operations, offering a compact representation for verifiable computation on the Bitcoin blockchain.

Figure 4: A circuit with eight different NAND gates

Source: https://bitvm.org/bitvm.pdf

Challenges and Responses

In BitVM, committing to one circuit is not enough, and a challenge-response mechanism is required to prove the correctness of computations. To achieve that, the prover and the verifier should pre-sign a sequence of transactions during setup. The transactions are linked in the order of “challenge - response - challenge - response”, creating multiple rounds of challenge-and-response interactions. If one of the parties stops engaging then, after timeout, the other party wins the challenge and can take both deposits. This mechanism is required only in case of fraud. As long as both parties are cooperative, they can jointly settle any contract with a 2-of-2 signature.

Let’s see how this mechanism works in a hypothetical case. Paul (prover) and Vicky (verifier) pre-signed a sequence of transactions. Vicky can then initiate a challenge (TX 2) by selecting a challenge (hash7) from one of the hashlocks in her Tapscript leaves. This unlocks for Paul a specific Tapscript and forces him to execute it, with open inputs and outputs. Any inconsistent claim can be disproven quickly by repeating this procedure for a few rounds of queries. If the prover stops collaborating, the verifier can unlock a hash preimage he holds to force the prover to respond on-chain. Each round of queries may validate or disprove a specific gate. Through binary search (an algorithm used to locate a specific element in a sorted array), the verifier can quickly identify the prover’s error after just a few rounds of challenge-and-response. Once the prover’s two commitments conflict, the verifier immediately wins the challenge and takes the deposit.

Figure 5: A pre-signed sequence of transactions to perform multiple rounds of challenge-and-response

Source: https://bitvm.org/bitvm.pdf

This meticulous design allows BitVM to perform on-chain verification of any complex computation, which ensures the efficiency of collaboration and imposes penalties in the event of fraud. It demonstrates the possibility of verifying Turing-complete interactive computation in the Bitcoin network.

Key Aspects of BitVM’s Design

Off-chain Computation & On-chain Verification

BitVM places the burden of complex computation off the blockchain, reserving the Bitcoin blockchain for the sole purpose of verifying results. This approach avoids running complex contracts directly on the blockchain, which mitigates blockchain bloat.

Logic Gates Expressed with Hashlocks and Bitcoin Scripts

BitVM leverages hashlocks and script opcodes supported by Bitcoin to represent basic logic gates, such as AND and NOT gates. Connecting these logic gates allows it to build circuits of arbitrary complexity, enabling Turing-complete computation.

A Game Theory Mechanism for the Prover and the Verifier

BitVM’s validation mechanism, which resembles Optimistic Rollup, involves interactive challenges and responses between the parties of the computation. Ultimately, the correct computation result is confirmed on-chain. If the prover cheated, the verifier could execute penalties on the Bitcoin blockchain. As such, BitVM and Optimistic Rollup employ similar interaction mechanisms for on-chain verification, and the only difference is that BitVM directly uses Bitcoin scripts to implement an interactive challenge-response process.

Minimal On-chain Impact

BitVM’s computation process has minimal impact on the Bitcoin blockchain, leaving only a small number of transactions on-chain when disputes arise. This preserves the efficiency and scalability of Bitcoin.

No Need for Soft Forks

As BitVM only utilizes existing Bitcoin script capabilities, it does not require any modifications to the Bitcoin protocol through soft forks. This makes it easier for BitVM to be integrated into the Bitcoin mainnet.

Conclusion

BitVM’s biggest innovation lies in its ability to implement Turing-complete verification without modifying the core Bitcoin protocol; it achieves this by making creative use of scripts, especially the ones optimized by Taproot. This ingenious design enables seamless integration with the Bitcoin mainnet without introducing new compatibility issues or making Bitcoin less decentralized.

BitVM’s innovative solution holds the potential to introduce smart contracts and decentralized applications to the Bitcoin ecosystem. For instance, it can be used to build minimal-trust cross-chain bridges to connect different blockchain assets, enhancing Bitcoin’s interoperability. Additionally, BitVM can also help build more efficient zkRollup expansion layers to make Bitcoin more scalable. In a nutshell, BitVM showcases the vast possibilities of driving the Bitcoin ecosystem into a new era only through the innovative utilization of existing features.

References:

https://bitvm.org/bitvm.pdf

https://github.com/supertestnet/tapleaf-circuits

https://biquanlibai.notion.site/BitVM-2b8557e0ea004d0cbc52951782bc9754

BitVM, the Potential of Smart Contracts on the Bitcoin Mainnet