IOSG ｜BitVM: The dawn of Bitcoin programmability

Acknowledgements: Thanks to Momir, Xinshu for their valuable revisions

TL;DR:

• Changes to Bitcoin Core are often resisted for reasons including: a) People prefer Bitcoin as a store of value over a currency. b) Value stability and predictability over rapid innovation. c) It is difficult to reach consensus within a diverse community.

• Many projects claim to have solutions to Bitcoin’s scalability issues without requiring changes to the Bitcoin chain itself. Recently we have witnessed hyperinflation with Bitcoin’s “L2s”.

• While many of the claims are simply misleading marketing, we also recognize a new paradigm of computing that can bring programmability to Bitcoin - BitVM.

• The best scaling solutions that BitVM can support are close to OP-Rollup type security assumptions (although with some additional caveats).

• The success of BitVM and similar initiatives depends on technical viability, community support, and differentiation from other "over-marketed" projects.

Bitcoin was built as a transaction blockchain with a scripting language that is intentionally constrained to be stateless to minimize the attack surface and ensure network security. Due to the lack of Turing-completeness, it is not possible to introduce smart contracts directly on the blockchain, except by forking and upgrading Bitcoin Core.

The traditional Bitcoin community is resistant to change for the following reasons:

• Narrative focus on value storage rather than currency: The Bitcoin community intentionally focuses on maintaining the network as a peer-to-peer payment system, prioritizing security and decentralization over rapid development. As Michael Saylor, a famous Bitcoin holder, said: "No one is trying to buy a cup of coffee with a small portion of their building on Fifth Avenue." This statement reflects the community's preference for using Bitcoin as a store of value tool rather than an everyday currency.

• System stability over innovation: For an asset to be considered a good store of value, predictability is essential. For example, even if the network has only had 10 major upgrades, and each has a 90% success rate, the probability of one failure occurring is about 65%! According to the Normal Accident Theory: "In complex systems, we should expect small factors that can usually be ignored to occasionally cause major events by chance", so the goal of the Bitcoin community has always been to reduce the number of potential errors.

• Diverse Community: Many Bitcoin holders understand Bitcoin from different perspectives and value it for different reasons. Reaching consensus in a diverse and decentralized community is inherently challenging, which further slows the pace of innovation. To illustrate the diversity of the Bitcoin community, one can observe the community's reaction to Inscriptions and Ordinals. While one part of the Bitcoin community celebrated the success of Ordinals as Bitcoin's CryptoKitties moment, another part saw it as a vulnerability that should be fixed.

1. The rapid expansion of Bitcoin scaling solutions

Given the above, why are there suddenly so many new Bitcoin "L2" solutions?

Recently, we have observed a surge in Bitcoin "L2" solutions (according to https://l2.watch/, there are already more than 50!), however, the community has been exploring different scalability approaches for years:

1. Sidechains like Stacks offer smart contract capabilities and a wide range of applications, although they have independent consensus mechanisms that have struggled to gain widespread acceptance.

2. Client verification projects like RGB use the mainnet's UTXO model to conduct more complex transactions off-chain, but their interaction with the Bitcoin mainnet lacks stability.

3. State channels like the Lightning Network, which are closely associated with core Bitcoin developers, are seen as a more orthodox approach to scaling.

First Generation BTC Scaling Solutions

What novelties do recent scaling methods bring compared to existing solutions? In our opinion, the most exciting innovation comes from coding programs on Bitcoin (via BitVM) and trustlessly staking BTC (e.g. Babylon). This article will focus primarily on the former.

2. BitVM - Overview

To explain what BitVM is, we should first introduce the primitive that enabled and inspired it - the Bitcoin Taproot upgrade.

Taproot is a major upgrade to the Bitcoin protocol that was activated in November 2021. With Taproot, the script’s hash needs to be submitted on-chain by default. When a certain path of the script is executed, only the script on that path needs to be submitted on-chain. This not only improves efficiency (the size of the transaction does not grow with the size of the script) but also enhances privacy (only the path that is a transaction is revealed, not the entire script).

Recognizing the huge opportunities unlocked by the Taproot upgrade, Robin Linus pioneered BitVM, a breakthrough innovation in the Bitcoin ecosystem.

BitVM is a computational paradigm that leverages the Taproot upgrade to facilitate Turing-complete contracts on Bitcoin without changing the network’s consensus rules. It allows computations to be verified (not executed), similar to Optimistic Rollups.

BitVM minimizes the on-chain footprint by submitting programs to Taproot addresses while enabling complex off-chain computations that only need to be executed on-chain when disputes arise.

This process involves submitting the binary circuit of the program in the Taproot address and verifying it using a challenge-response mechanism. In a nutshell, BitVM implements Turing-complete Bitcoin contracts, and most importantly:

• BitVM does not require forks or any changes to the Bitcoin protocol.

• BitVM will not congest the Bitcoin blockchain because the computation is not performed on Bitcoin, but only uses the Bitcoin network for verification when a dispute arises.

• 

Building Binary Circuits on Bitcoin

Building binary circuits is a way of representing calculations or programs using binary logic gates (such as AND, OR, NOT), capable of performing any computable function.

BitVM is like a complex simulation of the flow of electricity through the logic gates of a computer chip (these tiny structures decide whether a signal passes through, i.e., on or off, depending on the presence or absence of electricity), translated into the language of Bitcoin.

Essentially, any computer program, from a game to a complete Linux operating system, is the result of a complex arrangement of these logic gates, and all digital things are fundamentally based on binary digits - 0 and 1. By combining these binary digits with logic gates, such as AND and NOT gates, we create a variety of circuits, including arithmetic logic units (ALUs) and memory systems. This foundational technology allows us to write and execute programs to perform a wide range of tasks.

 Source: Stepping Through Logic Gates; Basic logic gates (F for 0, T for 1)

The premise of BitVM is to use Bitcoin Script to make commitments to off-chain computations (submit a computational hash to the Taproot address), by deconstructing any program into a combination of binary circuits and enabling execution verification, which includes Bitcoin Script, but the script itself does not execute the entire computational logic.

Bitcoin Script enables bit-value commitments, which are essential for being able to demonstrate and punish equivocation. It achieves immutability because it allows individuals to commit to values ​​that cannot be modified by others.

This approach involves using two hashes to represent each input bit: one for the number 0 and the other for the number 1. When someone wishes to execute the program, they reveal a pre-image to indicate the input. Whether the value will be converted to 0 or 1 is determined by comparing the hash of the pre-image to the two hashes representing 0 and 1.

If the input and output do not match, the verifier has the power to punish the provider by confiscating the provider's funds.

Challenge-Response Mechanism

Verification is usually done off-chain, optimistically assuming that the prover is honest. In case of a dispute, the process moves on-chain and a round of challenge-response is initiated. This mechanism ensures that in most cases, computation and verification can be performed efficiently and cheaply, while only in case of disagreement does the final ruling need to be made using the immutability and transparency of the blockchain. The dynamics of the challenge-response mechanism in BitVM involves a system where participants (such as Vicky and Paul) undergo a verification process through the execution of programs on the blockchain. When a dispute arises, Vicky challenges Paul to prove the correctness of his program execution. Vicky selects a logic gate from a binary circuit and Paul opens this gate by revealing the input and output. This process is repeated until an equivocation is confirmed or Vicky exhausts the possibility of further challenges. An equivocation means that Paul claims that a certain input X is 0 when one logic gate is opened, but 1 when another logic gate is opened. Paul needs to secure the proof of his claim by depositing funds to the response address using a pre-signed transaction. These transactions create a chain that allows funds to swing between the challenge and response addresses based on ongoing interactions.

The funds in the response address can flow along multiple paths depending on the outcome of the challenge:

• If Vicky stops the challenge, indicating acceptance of Paul's proof, Paul eventually regains access to the funds after a certain amount of time.

• If Vicky proves that Paul was inconsistent in his execution (ambiguity occurred), she can claim the funds.

• If Vicky suspects that another part of the execution is wrong, she can initiate another challenge to move the funds to the next response address. To do this, she must reveal a preimage of the specific tapeleaf, which Paul then needs to use to unlock the funds and prove his correctness within a limited time.

This system provides a solid and transparent framework for resolving disputes and verifying program execution on the blockchain. By combining financial incentives, it promotes completeness and accuracy in the recording of execution and program results. Initially, the design supported a two-party challenge-response mechanism. However, as we will show later, BitVM contributors have found solutions that allow many participants to participate as challengers.

Bisection: Improving Efficiency in Dispute Resolution

To improve the efficiency of on-chain verification, validators can utilize bisection, a method for efficient search on pre-committed logic gates to find the logic gates that should be challenged, which is a significant improvement over the random challenge process. By splitting the problem space into two, the bisection method allows validators to quickly narrow down the scope of potential errors, thereby reducing the steps and time required to resolve disputes. This method provides a more efficient and direct path when dealing with complex verification processes, especially when the precise location of the error needs to be determined.

Below, we use a simplified example to illustrate how the segmentation method works:

Paul and Vicky are doing a math problem, and the question is to calculate ((1+2)+(3+4))+((5+6)+(7+8)).

The correct way to complete this calculation is ((1+2)+(3+4))+((5+6)+(7+8)) = (3+7)+(11+15) = 10+26 = 36.

And the answer given by Paul is 35, because the way he calculated is ((1+2)+(3+4))+((5+6)+(7+8)) = (2+7)+(11+15) = 9+26 = 35.

When Vicky challenges Paul, she only needs to challenge the computation involving the first part of the computation (i.e., opening the logic gate) because they agree that the second part of the computation is exactly ((5+6)+(7+8)) = 26.

3. Build a Trust-Minimized Bridge with BitVM

The first practical implementation of BitVM will most likely be a program that represents a Trust-Minimized Bitcoin Bridge. By analyzing the implementation details of the bridge, we can better understand the additional complexity of implementing a BitVM program. Below, we summarize the proposal by BoB co-founder Alexei Zamyatin.

First, a method needs to be created for a Bitcoin full node to operate a sidechain bridge program using only Bitcoin script, including a sidechain light client.

Then, a federation/multi-sig network needs to be established to facilitate the transfer of BTC and run the challenge-response game. The federation must commit to running the bridge program as part of the BitVM setup.

The complexity of the initial setup of the federation grows quadratically with the number of members, because each member of the federation must interact with every other member, so there is a certain upper limit to the size of the federation, and researchers speculate that N=100 is feasible.

Unlike OP Rollup, which has no limit on the size of N, this scheme provides weaker security guarantees. However, this proposed working solution will most likely include a rotation of federation members so that N is much larger than 100 over a longer timeframe. As long as one of these 100 members is honest at any time, deposits remain safe. Assuming there are malicious actors, they can be challenged on-chain at any time, and if proven to be cheating, they can be banned by the federation.

At all times the federation has a single Operator who is responsible for managing deposits and withdrawals and validating the state of the sidechain. Both Operators and Watchtowers are required to post collateral to incentivize correct behavior and discourage false challenges.

Another reason this scheme does not meet the strictest definition of convolution is that users cannot unilaterally exit the sidechain, but must request a withdrawal from the federation which operates on the 1/N security assumption.

4. BitVM v2: Can BitVM support permissionless verification?

On March 25, Robin Linus introduced BitVM v2. The key change in the BitVM v2 proposal is that the prover needs to submit the output state and all intermediate results at once, instead of opening the logic gates one by one during the challenge-verification process as in v1. With this change, BitVM ensures that any challenge to these commitments must be supported by cryptographic evidence. This mechanism filters out unfounded junk challenges because the challenger must provide specific cryptographic proofs to dispute the prover.

By allowing unlimited participation in the verification and challenge process, BitVM 2 extends its security guarantees beyond the limitations of multi-signature alliances and brings BitVM closer to the security assumptions of optimistic convolution.

However, the construction of the bridge still requires federation multi-signatures to facilitate it, which means that members of the federation may cause liveness issues, and in the worst case, they try to extort ransom from users to unfreeze their funds. This is an additional security assumption that does not exist for optimistic convolution, because in optimistic convolution, users can exit to L1 without obtaining any intermediary approval.

Additional security assumptions on the base chain

5. Limitations of BitVM

As we discussed above, the best solution BitVM can provide is a security assumption close to optimistic convolution. In addition to the complexity of managing a federation responsible for insurance deposits and its liveness problem, some additional complexities specific to BitVM include:

• While BitVM is theoretically capable of executing complex off-chain programs, in practice the costs associated with executing fraud proofs on Bitcoin increase rapidly as the complexity of those off-chain programs increases. Excessively large programs may require multiple blocks to execute, further complicating the process.

• Mining pools with a majority of hashrate can steal from BitVM (similar to issues with the Lightning Network) because they can collude to censor challengers’ proofs, or malicious actors can bribe them to ignore challengers.

• Due to the interactive nature of BitVM proofs, malicious provers can potentially manipulate the system to steal from validators. The attack can be constructed based on the following assumptions:

• The prover begins the verification sequence by launching a transaction

• The verifier, doubting the validity of the prover's actions, launches a challenge, which includes a response fee paid to the prover

• The prover chooses to collect the fee and ignores the challenge, not fulfilling their part of the verification process

• Finally, BitVM is currently a conceptual framework and a virtual computer concept that can hardly perform any operations. BitVM's "convolution" is still far from the application level, and the optimistic estimate is that we may see some BitVM programs put into use as early as 2025. The technical risks of implementing BitVM should not be underestimated.

6. Conclusion

Given the valuation of Ethereum scaling solutions, which currently account for approximately 15-20% of Ethereum’s market cap – the potential market cap for Bitcoin’s second layer solutions could be huge.

Although BitVM is still in its early stages – essentially an unrealized virtual computer concept – it has already inspired a lot of interest and announcements from various projects eager to capitalize on its potential. Many projects not affiliated with the BitVM team are rushing to make grand announcements, hoping to carve out a place in what they see as a promising new area for Bitcoin. However, closer scrutiny reveals a more sobering reality: BitVM’s GitHub account has only a handful of contributors, and only a handful of Bitcoin ‘L2’ projects are actually participating in the BitVM Builders Telegram group.

A key principle that any scalability solution for Bitcoin must adhere to is that the core architecture of Bitcoin should remain unchanged (per the predictability principle). BitVM adheres to this principle and has become the first pioneering solution to provide a programmable layer on top of Bitcoin without changing its core.

This article is written at a very early stage of BitVM's development, and given its rapid development, the information here may quickly become outdated. For example, until recently, the idea of ​​implementing ZK convolutions on Bitcoin seemed like a pie in the sky, as the required underlying capabilities - such as Bitcoin's ability to verify ZK proofs - did not exist. However, recently BitVM researchers shared progress in Bitcoin Script that could lead to the implementation of STARK validators on Bitcoin.

The implementation of Bitcoin scaling solutions goes beyond purely technical challenges; it encompasses factors such as community support, user experience, and timing. While the current moment provides a unique window of opportunity for these innovations, the rapid inflation of the number of projects and the significant risk of misleading claims and marketing may undermine the prospects of more legitimate projects.

As the ecosystem stands at this crossroads, the question of whether Bitcoin’s scaling solutions can replicate Ethereum’s success is not only technical, but also deeply rooted in the broader dynamics of the blockchain community. After all, the core Ethereum community has already chosen L2 as a key part of Ethereum’s scaling roadmap, while the Bitcoin community cannot yet say the same.

Reference

• “Bitcoin Audible.” Accessed February 26, 2024.https://pod.link/1359544516/episode/413027f0bdb982a8593d50f4466930f5.

• “BitVM.” Accessed February 26, 2024.https://www.bitcoinrollups.io/bitvm.

• “BitVM: Uma Ferramenta Para Contratos Ainda Mais Inteligentes - Super Testnet - Satsconf 2023 - YouTube.” Accessed February 26, 2024. https://www.youtube.com/watch?v=iEM_txmJYxA.

• Linus, Robin. “BitVM: Compute Anything on Bitcoin,” n.d.

• “What Is BitVM? With Robin Linus and Super Testnet (SLP520) - YouTube.” Accessed February 26, 2024. https://www.youtube.com/watch?v=XxqQU6j6jI8.

• Deep dive into BitVM -Computing paradigm to express Turing-complete Bitcoin contracts. https://medium.com/crypto-garage/deep-dive-into-bitvm-computing-paradigm-to-express-turing-complete-bitcoin-contracts-1c6cb05edfca CoinEx Institution: BitVM, the Potential of Smart Contracts on the Bitcoin Mainnet https://www.business-standard.com/content/press-releases-ani/coinex-institution-bitvm-the-potential-of-smart-contracts-on-the-bitcoin-mainnet-123122500619_1.html