BitVM Principle Analysis and Optimization Thoughts

Original Title: BitVM And Its Optimization Considerations

Original Authors: lynndell, mutourend.

1. Introduction

Bitcoin is a decentralized, secure, and trustworthy digital asset. However, it has significant limitations that prevent it from becoming a scalable network for payments and other applications. The scalability issue of Bitcoin has been a major concern since its inception. The Bitcoin UTXO model treats each transaction as an independent event, resulting in a stateless system that lacks the capability to execute complex, state-dependent computations. Therefore, while Bitcoin can execute simple scripts and multi-signature transactions, it struggles to facilitate the complex and dynamic contract interactions that are common on stateful blockchain platforms. This issue significantly limits the scope of decentralized applications (dApps) and complex financial instruments built on Bitcoin, while state model platforms provide a more diverse environment for deploying and executing feature-rich smart contracts.

For Bitcoin scalability, there are mainly technologies such as state channels, sidechains, and client validation. Among them, state channels provide secure and diverse payment solutions, but they have limitations in verifying arbitrarily complex computations. This limitation reduces their applicability in various scenarios that require complex, conditional logic and interactions. Sidechains, while supporting a wide range of applications and offering diversity beyond Bitcoin's capabilities, have lower security. This security difference arises from the independent consensus mechanisms used by sidechains, which are far less robust than Bitcoin's consensus mechanism. Client validation, which uses the Bitcoin UTXO model, can handle more complex transactions, but lacks the bidirectional verification and constraint capabilities of Bitcoin, resulting in lower security. The off-chain design of client validation protocols relies on servers or cloud infrastructure, which may lead to centralization or potential censorship through compromised servers. Additionally, the off-chain design of client validation introduces more complexity to the blockchain infrastructure, potentially leading to scalability issues.

In December 2023, Robin Linus, the head of the ZeroSync project, published a white paper titled “BitVM: Compute Anything On Bitcoin,” sparking discussions about enhancing Bitcoin's programmability. The paper proposes a Turing-complete Bitcoin contract solution that can be realized without changing the consensus of the Bitcoin network, allowing any complex computation to be verified on Bitcoin without altering its fundamental rules. BitVM leverages Bitcoin scripts and Taproot to implement optimistic rollups. Based on Lamport signatures (also known as bit commitments), it establishes a connection between two Bitcoin UTXOs, enabling stateful Bitcoin scripts. A large program is committed in a Taproot address, where the operator and verifier engage in extensive off-chain interactions, leaving a minimal footprint on-chain. If both parties cooperate, they can execute any complex, stateful off-chain computation without leaving any trace on-chain. If the parties do not cooperate, on-chain execution is required in case of disputes. Thus, BitVM significantly broadens the potential use cases for Bitcoin, allowing it to serve not only as a currency but also as a verification platform for various decentralized applications and complex computational tasks.

However, despite the significant advantages of BitVM technology for Bitcoin scalability, it is still in its early stages and faces some challenges in efficiency and security. For example: (1) Challenges and responses require multiple interactions, leading to high fees and long challenge cycles; (2) The length of Lamport one-time signature data is considerable, necessitating a reduction in data length; (3) The complexity of hash functions is high, requiring Bitcoin-friendly hash functions to reduce costs; (4) The existing BitVM contracts are large, and Bitcoin block capacity is limited; utilizing scriptless scripts can achieve Scriptless Scripts BitVM, saving Bitcoin block space while improving BitVM efficiency; (5) The current BitVM operates on a permissioned model, allowing only consortium members to initiate challenges, limited to two parties; it should be expanded to a permissionless multi-party challenge model to further reduce trust assumptions. To address this, this paper proposes some optimization ideas to enhance the efficiency and security of BitVM.

2. BitVM Principles

BitVM is positioned as an off-chain contract for Bitcoin, aimed at advancing Bitcoin's contract functionality. Currently, Bitcoin scripts are completely stateless, meaning that the execution environment resets after each script execution. There is no native way for scripts 1 and 2 to share the same x value, as Bitcoin scripts do not natively support this. However, it is still possible to leverage existing opcodes to make Bitcoin scripts stateful through Lamport one-time signatures, such as enforcing that x in script 1 and script 2 has the same value. If the participants sign conflicting x values, they can be penalized. BitVM program computations occur off-chain, while the verification of computation results happens on-chain. Currently, Bitcoin blocks have a 1 MB limit, and when the verification of computations becomes too complex, OP technology can be utilized, employing a challenge-response model to support higher complexity computation verification.

Similar to Optimistic Rollup and the MATT proposal (Merkelize All The Things), the BitVM system is based on fraud proofs and a challenge-response protocol, but does not require modifications to Bitcoin's consensus rules. The underlying primitives of BitVM are simple, mainly based on hash locks, time locks, and large Taproot trees.

The prover commits byte by byte, but verifying all computations on-chain would be too costly. Therefore, the verifier executes a series of carefully designed challenges to succinctly refute the prover's false claims. The prover and verifier jointly pre-sign a series of challenge and response transactions to resolve disputes, thus allowing for general computation verification on Bitcoin.

Key components of BitVM include:

• Circuit Commitment: The prover and verifier compile the program into a large binary circuit. The prover commits this circuit in a Taproot address, where each leaf script corresponds to each logic gate in the circuit. The core is based on bit commitment to achieve logic gate commitment, thus realizing circuit commitment.
• Challenge and Response: The prover and verifier pre-sign a series of transactions to implement the challenge-response game. Ideally, this interaction occurs off-chain, but can also be executed on-chain if the prover does not cooperate.
• Ambiguous Penalty: If the prover makes any incorrect claims, the verifier can take the prover's deposit after successfully challenging, thwarting the prover's malicious actions.

3. BitVM Optimization

3.1 Reducing OP Interaction Count Based on ZK

Currently, there are two major types of Rollups: ZK Rollups and OP Rollups. ZK Rollups rely on the validity of ZK Proofs, which are cryptographic proofs of correct execution, with their security depending on computational complexity assumptions; OP Rollups rely on Fraud Proofs, assuming that the submitted states are correct, with a typical challenge period of 7 days, and their security assumes that at least one honest party in the system can detect incorrect states and submit fraud proofs. Assuming the maximum number of steps for the BitVM challenge program is 2^{32}, it requires memory of 2^{32} * 4 bytes, approximately 17GB. In the worst case, about 40 rounds of challenges and responses may be needed, taking about six months, with a total script size of about 150KB. In this case, incentives are severely lacking, but in practice, such situations rarely occur.

Consider using zero-knowledge proofs to reduce the number of challenges in BitVM, thereby improving its efficiency. According to zero-knowledge proof theory, if data Data satisfies algorithm F, then the proof proof satisfies the verification algorithm Verify, meaning the verification algorithm outputs True; if data Data does not satisfy algorithm F, then the proof proof also does not satisfy the verification algorithm Verify, meaning the verification algorithm outputs False. In the BitVM system, if the challenger does not accept the data submitted by the prover, a challenge is initiated.

For algorithm F, using binary search, suppose it requires 2^n times, then an error point can be found; if the algorithm's complexity is too high, n will be large, taking a long time to complete. However, the complexity of the verification algorithm Verify for zero-knowledge proofs is fixed, and the entire process of public proof proof and verification algorithm Verify can reveal an output of False. The advantage of zero-knowledge proofs lies in the lower computational complexity required to open the verification algorithm Verify compared to opening the original algorithm F using binary search. Therefore, by leveraging zero-knowledge proofs, the challenge in BitVM is no longer the original algorithm F, but the verification algorithm Verify, reducing the number of challenges and shortening the challenge period.

Finally, although the validity of zero-knowledge proofs and fraud proofs relies on different security assumptions, they can be combined to construct ZK Fraud Proofs, achieving On-Demand ZK Proofs. Unlike full ZK Rollups, there is no need to generate ZK proofs for each individual state change; the On-Demand model allows for ZK Proofs to be generated only when there is a challenge, while the entire Rollup design remains optimistic. Thus, it is still assumed that the generated states are valid until someone challenges that state. If a state has no challenges, no ZK Proof needs to be generated. However, if a participant initiates a challenge, ZK Proofs must be generated for the correctness of all transactions within the challenge block. In the future, exploring the generation of ZK Fraud Proofs for individual disputed instructions can help avoid the computational costs of continuously generating ZK Proofs.

3.2 Bitcoin-Friendly One-Time Signatures

In the Bitcoin network, transactions that follow consensus rules are valid transactions, but in addition to consensus rules, there are also standardness rules. Bitcoin nodes only forward broadcast standard transactions, and the only way to package valid but non-standard transactions is to collaborate directly with miners.

According to consensus rules, the maximum size of legacy (i.e., non-Segwit) transactions is 1MB, filling the entire block. However, the standardness limit for legacy transactions is 100kB. According to consensus rules, the maximum size of Segwit transactions is 4MB, which is the weight limit. However, the standardness limit for Segwit transactions is 400kB.

Lamport signatures are a fundamental component of BitVM, reducing the length of signatures and public keys, which helps lower transaction data and thus reduce fees. Lamport one-time signatures require the use of hash functions (such as one-way permutation function f). In the Lamport one-time signature scheme, the message length is v bits, the public key length is 2v bits, and the signature length is also 2v bits. The long signatures and public keys consume a significant amount of storage gas. Therefore, it is necessary to find a signature scheme with similar functionality to reduce the lengths of signatures and public keys. Compared to Lamport one-time signatures, Winternitz one-time signatures significantly reduce the lengths of signatures and public keys but increase the computational complexity of signing and verification.

In the Winternitz one-time signature scheme, a special function P maps a v-bit message into a vector s of length n. Each element in s takes values from {0,…, d}. The Lamport one-time signature scheme is a special case of the Winternitz one-time signature scheme where d = 1. In the Winternitz one-time signature scheme, the relationship between n, d, and v satisfies: n ≈ v / log2(d + 1). When d = 15, n ≈ (v / 4) + 1. For a Winternitz signature containing n elements, the public key length and signature length are 4 times shorter than those in the Lamport one-time signature scheme. However, the complexity of verification increases by 4 times. Using d = 15, v = 160, and f = ripemd160(x) to implement Winternitz one-time signatures in BitVM can reduce the bit commitment size by 50%, thus lowering BitVM's transaction fees by at least 50%. In the future, while optimizing the existing Winternitz Bitcoin script implementation, exploring more compact one-time signature schemes expressed in Bitcoin scripts can be pursued.

3.3 Bitcoin-Friendly Hash Functions

According to consensus rules, the maximum size of P2TR scripts is 10kB, and the maximum size of P2TR script witnesses is the same as the maximum Segwit transaction size, which is 4MB. However, the standardness limit for P2TR script witnesses is 400kB.

Currently, the Bitcoin network does not support OP_CAT, making it impossible to concatenate strings for Merkle path verification. Therefore, it is necessary to implement a Bitcoin-friendly hash function using existing Bitcoin scripts in an optimal way regarding script size and script witness size, thereby supporting Merkle inclusion proof verification functionality.

BLAKE3 is an optimized version of the BLAKE2 hash function and introduces the Bao tree mode. Compared to BLAKE2s-based, its compression function rounds are reduced from 10 to 7. The BLAKE3 hash function splits its input into contiguous chunks of 1024 bytes, with the last chunk possibly being shorter but not empty. When there is only one chunk, that chunk is the root node and the only node of the tree. These chunks are arranged as leaf nodes of a binary tree, and each chunk is compressed independently.

When using BitVM for verifying Merkle inclusion proof scenarios, the input for the hash operation is composed of two 256-bit hash values, meaning the input for the hash operation is 64 bytes. When using the BLAKE3 hash function, these 64 bytes can be allocated within a single chunk, and the entire BLAKE3 hash operation only requires applying the compression function once to a single chunk. In the BLAKE3 compression function, 7 rounds of round functions and 6 permutations need to be executed.

Currently, basic operations based on u32 values such as XOR, modular addition, and bitwise right shifts have been completed in BitVM, making it easy to assemble a BLAKE3 hash function implemented in Bitcoin scripts. Using 4 separate bytes in the stack to represent u32 words allows for the implementation of the u32 addition, u32 bitwise XOR, and u32 bitwise rotations required by BLAKE3. The current BLAKE3 hash function in Bitcoin scripts is approximately 100kB, sufficient for building a toy version of BitVM.

Additionally, these BLAKE3 codes can be split, allowing the Verifier and Prover to significantly reduce the required on-chain data by dividing the execution of the challenge-response game rather than executing it completely. Finally, implementing hash functions such as Keccak-256 and Groestl in Bitcoin scripts can help identify the most Bitcoin-friendly hash function and explore other new Bitcoin-friendly hash functions.

3.4 Scriptless Scripts BitVM

Scriptless Scripts is a method for executing smart contracts off-chain using Schnorr signatures. The concept of Scriptless Scripts originated from Mimblewimble, which does not store permanent data aside from the kernel and its signature.

The advantages of Scriptless Scripts include functionality, privacy, and efficiency.

• Functionality: Scriptless Scripts can increase the range and complexity of smart contracts. The capabilities of Bitcoin scripts are limited by the number of OP_CODES enabled in the network, while Scriptless Scripts shift the specification and execution of smart contracts off-chain to discussions among the contract participants, eliminating the need to wait for a Bitcoin network fork to enable new opcodes.
• Privacy: Moving the specification and execution of smart contracts off-chain enhances privacy. On-chain, many details of the contract are shared across the entire network, including the number of participants, addresses, and transfer amounts. By moving smart contracts off-chain, the network only knows that the participants agree that the contract terms have been met and that the related transactions are valid.
• Efficiency: Scriptless Scripts minimize the amount of data required for on-chain verification and storage. By moving smart contracts off-chain, the management costs for full nodes decrease, and users' transaction fees are lowered.

Scriptless Scripts is a method for designing cryptographic protocols on Bitcoin that avoids executing explicit smart contracts. The core idea is to use cryptographic algorithms to achieve the desired functionality instead of using scripts. Adapter signatures and multi-signatures are the foundational building blocks of Scriptless Scripts. Using Scriptless Scripts allows for smaller transactions than conventional transactions, reducing transaction fees.

With Scriptless Scripts, using Schnorr multi-signatures and adapter signatures, it is no longer necessary to provide hash values and hash preimages as in the BitVM scheme; it can also achieve logic gate commitments in the BitVM circuit, thereby saving BitVM script space and improving BitVM efficiency. Although existing Scriptless Scripts solutions can reduce BitVM script space, they require significant interaction between the prover and challenger to combine public keys. Future improvements will be made to this solution while attempting to integrate Scriptless Scripts into specific BitVM functional modules.

3.5 Permissionless Multi-Party Challenges

The current default requirement for permission in BitVM challenges arises from the fact that Bitcoin's UTXO can only be spent once, allowing malicious verifiers to "waste" the contract by challenging honest provers. The current BitVM is limited to a two-party challenge model. A malicious prover can simultaneously initiate a challenge with a verifier they control, thereby "wasting" the contract and succeeding in their malicious actions, while other verifiers cannot prevent this behavior. Therefore, it is necessary to research a permissionless multi-party OP challenge protocol based on Bitcoin, which can extend BitVM's existing 1-of-n trust model to 1-of-N, where N is much larger than n. Additionally, it is necessary to study solutions to the issues of collusion between challengers and provers or malicious challenges that "waste" contracts. Ultimately, this aims to achieve a BitVM protocol with reduced trust assumptions.

Permissionless multi-party challenges allow anyone to participate without a whitelist. This means that users can withdraw from L2 without any trusted third-party involvement. Furthermore, any user wishing to participate in the OP challenge protocol can question and invalidate invalid withdrawals.

Expanding BitVM into a permissionless multi-party challenge model requires addressing the following attacks:

• Witch Attack: Even if an attacker forges multiple identities to participate in a dispute challenge, a single honest participant can still win the dispute. If the cost for the honest participant to defend the correct outcome is linearly related to the number of attackers, then when a large number of attackers are involved, the cost for the honest participant to win the dispute becomes impractical and is vulnerable to witch attacks. The paper Permissionless Refereed Tournaments proposes a dispute resolution algorithm that changes the rules of the game, where the cost for a single honest participant to win the dispute grows logarithmically with the number of opponents, rather than linearly.
• Delay Attack: A malicious party or group of parties follows a strategy to prevent or delay the confirmation of the correct outcome (such as withdrawing assets to L1) on L1, forcing the honest prover to incur L1 fees. It can be required that challengers must stake in advance to mitigate this issue. If a challenger initiates a delay attack, their stake can be forfeited. However, if an attacker is willing to sacrifice their stake to pursue a delay attack within certain limits, there should be counter-strategies to reduce the impact of delay attacks. The algorithm proposed in the paper BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol ensures that regardless of how much stake the attacker is willing to lose, the worst-case attack can only lead to a bounded delay.

In the future, a BitVM permissionless multi-party challenge model that is resistant to the above attack issues will be explored, tailored to Bitcoin's characteristics.

4. Conclusion

The exploration of BitVM technology has just begun, and in the future, more optimization directions will be explored and practiced to achieve scalability for Bitcoin and to prosper the Bitcoin ecosystem.

References

1. BitVM: Compute Anything on Bitcoin
2. BitVM: Off-chain Bitcoin Contracts
3. Robin Linus on BitVM
4. [bitcoin-dev] BitVM: Compute Anything on Bitcoin
5. The Odd Couple: ZK and Optimistic Rollups on a Scalability Date
6. What are Bitcoin's transaction and script limits?
7. BIP-342: Validation of Taproot Scripts
8. https://twitter.com/robin_linus/status/1765337186222686347
9. A Graduate Course in Applied Cryptography
10. BLAKE3: one function, fast everywhere
11. [bitcoin-dev] Implementing Blake3 in Bitcoin Script
12. https://github.com/BlockstreamResearch/scriptless-scripts
13. Introduction to Scriptless Scripts
14. BitVM using Scriptless Scripts
15. Solutions to Delay Attacks on Rollups
16. Introducing DAVE. Cartesi's Permissionless Fault-Proof System.
17. Delay Attacks on Rollups
18. Solutions to Delay Attacks on Rollups - Arbitrum Research
19. Multiplayer Interactive Computation Games Notes
20. BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol
21. Permissionless Refereed Tournaments