Last updated
Original: https://medium.com/@Bitlayer/bitvm-and-its-optimization-considerations-007da599d8ac
Written by Lynndell and Mutourend, Bitlayer Research Group
Mail: lynndell2010@gmail.com , zouyudi@gmail.com
Bitcoin is a decentralized, secure, and trustworthy digital asset. However, it faces significant limitations that prevent it from becoming a scalable network for payments and other applications. The scaling issue of Bitcoin has been a concern since its inception. Bitcoin’s UTXO (Unspent Transaction Output) model treats each transaction as an independent event, leading to a stateless system that lacks the ability to execute complex, state-dependent computations. As a result, while Bitcoin can perform simple scripts and multi-signature transactions, it struggles to facilitate the complex and dynamic contract interactions common on stateful blockchain platforms. This limitation significantly restricts the range of decentralized applications (dApps) and complex financial instruments that can be built on Bitcoin, whereas stateful platform models offer a more diverse environment for deploying and executing feature-rich smart contracts.
For Bitcoin scaling, the main technologies include state channels, sidechains, and client-side validation. State channels provide a secure and diverse payment solution but have limited capacity to verify arbitrarily complex computations. This limitation reduces their applicability in various scenarios requiring complex, conditional logic and interactions. Sidechains support a broad range of applications and offer diversity beyond Bitcoin’s capabilities, but they have lower security. This security difference stems from sidechains using independent consensus mechanisms, which are far less robust than Bitcoin’s consensus mechanism. Client-side validation, using the Bitcoin UTXO model, can handle more complex transactions, but it lacks bidirectional checking and constraints with Bitcoin, leading to lower security. The off-chain design of client-side validation protocols relies on servers or cloud infrastructure, which could lead to centralization or potential censorship through compromised servers. The off-chain design of client-side validation also introduces more complexity into blockchain infrastructure, possibly leading to scalability issues.
In December 2023, Robin Linus, the project leader of ZeroSync, published a white paper titled “BitVM：Compute Anything On Bitcoin”, which sparked considerable thought on enhancing Bitcoin’s programmability. The paper proposes a Turing-complete Bitcoin contract solution that can execute any complex computation on Bitcoin without changing the network’s consensus rules or altering Bitcoin’s fundamental principles. BitVM leverages Bitcoin scripts and Taproot to implement optimistic Rollups. It uses Lamport signatures (also known as bit commitment) to establish connections between two Bitcoin UTXOs, enabling stateful Bitcoin scripts. A large program is committed within a Taproot address, and operators and validators engage in extensive off-chain interactions, leaving a minimal footprint on the blockchain. If both parties cooperate, any complex, stateful off-chain computation can be executed without leaving any trace on the blockchain. However, if the parties do not cooperate, on-chain execution is required in the event of a dispute. Therefore, BitVM significantly expands Bitcoin’s potential use cases, 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 advantages of BitVM technology in Bitcoin scaling, it is still in the early stages and faces some efficiency and security issues, such as: (1) Challenges and responses require multiple interactions, leading to high transaction fees and lengthy challenge periods; (2) Lamport one-time signatures have long data lengths, necessitating a reduction in data size; (3) High hash function complexity requires Bitcoin-friendly hash functions to reduce costs; (4) Existing BitVM contracts are large, and Bitcoin block capacity is limited, so using scriptless scripts could help achieve Scriptless Scripts BitVM, saving Bitcoin block space and enhancing BitVM efficiency; (5) Current BitVM operates on a permission model, with challenges initiated only by consortium members and limited to two parties, which should be expanded to a permissionless multi-party challenge model to further reduce trust assumptions. To address these issues, the paper suggests several optimization ideas to improve BitVM’s efficiency and security.
BitVM is positioned as an off-chain contract system for Bitcoin, aimed at advancing the contract functionality of Bitcoin. Currently, Bitcoin scripts are entirely stateless, meaning the execution environment resets after each script. There is no native way in the Bitcoin scripting to ensure that scripts 1 and 2 have the same value of x. However, it’s possible to make Bitcoin scripts stateful using existing opcodes and Lamport one-time signatures, enforcing that x in script1 and script2 are the same. If participants sign conflicting values of x, they can be penalized.
BitVM computations occur off-chain, while the verification of these computations takes place on-chain. Given the 1MB limit of Bitcoin blocks, when verification of complex computations is needed, the OP technology can be used in a challenge-response mode 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 challenge-response protocols but does not require changes to Bitcoin’s consensus rules. BitVM’s underlying primitives are simple, primarily based on hash locks, time locks, and large Taproot trees.
Provers commit to the program byte-by-byte, but verifying all computations on-chain would be prohibitively expensive. Therefore, verifiers conduct a series of carefully designed challenges to succinctly refute the prover’s false claims. Provers and verifiers co-sign a series of challenge and response transactions to resolve disputes, allowing for general computation verification on Bitcoin.
Key components of BitVM include:
Circuit commitment: Provers and verifiers compile the program into a large binary circuit. The prover commits to this circuit in a Taproot address, with each leaf script under that address corresponding to each logic gate in the circuit. The core is to achieve logic gate commitment based on bit commitment.
Challenge and response: Provers and verifiers pre-sign a series of transactions to implement the challenge-response game. Ideally, this interaction occurs off-chain, but it can also be executed on-chain if the prover is uncooperative.
Ambiguous penalty: If the prover makes any incorrect claims, the verifier can take the prover’s deposit after successfully challenging, and thwarting the prover’s malicious actions.
There are two main types of Rollups: ZK Rollups and Optimistic Rollups (OP Rollups). ZK Rollups rely on the validity verification of Zero-Knowledge (ZK) Proofs, which are cryptographic proofs of correct execution. Their security depends on computational complexity assumptions. Optimistic Rollups rely on Fraud Proofs, assuming that all submitted states are correct and usually setting a challenge period of about seven days. Their security presupposes that at least one honest party in the system can detect the incorrect state and submit fraud-proof.
Assuming the maximum step count for BitVM’s challenge program is 2^{32}, it would need approximately 17GB of memory (2^{32}×4 bytes). In the worst-case scenario, around 40 rounds of challenges and responses might take about six months, with a total script size of around 150KB. Such a scenario would provide insufficient incentives, but it rarely occurs in practice.
Using Zero-Knowledge Proofs to reduce the number of challenges in BitVM could enhance its efficiency. According to Zero-Knowledge Proof theory, if data Data satisfies an algorithm F, then the proof satisfies the verification algorithm Verify, outputting True. Conversely, if Data does not satisfy F, then proof will not satisfy Verify, outputting False. In the BitVM system, if the challenger does not accept the prover’s data, a challenge is initiated.
For algorithm F, using a binary search approach, assuming 2^n iterations are needed to find the error point. If the algorithm’s complexity is too high, n is large, and it takes a long time to complete. However, the complexity of the Zero-Knowledge Proof verification algorithm Verify is fixed. By publicly revealing the proof and the verification process Verify, it is possible to see 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. Thus, with Zero-Knowledge Proofs, BitVM no longer challenges the original algorithm F, but rather the verification algorithm Verify, reducing the number of challenge rounds and shortening the challenge period.
Although the validity of Zero-Knowledge Proofs and Fraud Proofs relies on different security assumptions, they can be combined to construct a ZK Fraud Proof and implement On-Demand ZK Proof. Unlike a full ZK Rollup, the On-Demand model requires a ZK Proof only when a challenge is made, maintaining an optimistic design where the generated state is assumed valid until challenged. If a state is not challenged, no ZK Proof is needed. However, if a challenge is made, a ZK Proof must be generated for the correctness of all transactions within the challenged block. In the future, it could be possible to generate ZK Fraud Proofs for individual disputed instructions, avoiding the computational cost of continuously generating ZK Proofs.
In the Bitcoin network, transactions that follow the consensus rules are considered valid, but beyond these rules, there is an additional concept of standardness. Bitcoin nodes only propagate and broadcast standard transactions, and the only way for valid but non-standard transactions to be included in a block is through direct collaboration with miners.
According to the consensus rules, the maximum size for legacy (non-Segwit) transactions is 1MB, which could fill an entire block. However, the standardness limit for legacy transactions is set at 100kB. For Segwit transactions, the maximum size allowed by consensus rules is 4MB, known as the weight limit, but their standardness limit is 400kB.
Lamport signatures are a foundational component of BitVM, and reducing the length of signatures and public keys helps decrease transaction data size, thus reducing transaction fees. Lamport one-time signatures require a hash function (like a one-way permutation function f). In a Lamport one-time signature scheme, the message length is v bits, and both the public key and the signature lengths are 2v bits. These long signatures and public keys consume a significant amount of storage gas. Therefore, it’s necessary to explore signature schemes that can reduce the length of signatures and public keys. Compared to Lamport one-time signatures, Winternitz one-time signatures greatly reduce the lengths of signatures and public keys, but they increase the computational complexity of signing and verifying.
In the Winternitz one-time signature scheme, a special function P maps a v-bit message to a vector s of length n, with each element of s taking a value in {0,…,d}. The Lamport one-time signature scheme is a special case of the Winternitz scheme, where d=1. In the Winternitz scheme, the relationship between n, d, and v is approximately n≈v/log2(d+1). When d=15, n≈(v/4)+1. For a Winternitz signature with n elements, the public key and signature lengths are four times shorter than those in the Lamport one-time signature scheme, but the complexity of verification is four times higher. Using d=15,v=160,f=ripemd160(x) in BitVM for Winternitz one-time signatures can reduce the bit commitment size by 50%, thereby reducing BitVM’s transaction fees by at least 50%. In the future, while optimizing the existing Winternitz Bitcoin script implementation, exploration of more compact one-time signature schemes expressible in the Bitcoin script could be pursued.
According to the consensus rules, the maximum size for a P2TR script is 10kB, and the maximum size for a P2TR script witness is the same as the maximum Segwit transaction size, which is 4MB. However, the standardness limit for a P2TR script witness is 400kB.
Currently, the Bitcoin network does not support OP_CAT, making it impossible to concatenate strings for Merkle path verification. Therefore, there is a need to implement a Bitcoin-friendly hash function using the existing Bitcoin script, in the most size-efficient manner for both script size and script witness size, to support Merkle inclusion proof verification.
BLAKE3 is an optimized version of the BLAKE2 hash function and introduces a Bao tree mode. Compared to BLAKE2s-based, its compression function’s round count has been reduced from 10 to 7. The BLAKE3 hash function splits its input into chunks of 1024 bytes, with the last chunk being possibly shorter but not empty. When there is only one chunk, it serves as the root node and the tree’s sole node. These chunks are arranged as leaf nodes of a binary tree, and each chunk is compressed independently.
When BitVM is used for verifying Merkle inclusion proofs, the input for the hash operation consists of two concatenated 256-bit hash values, totaling 64 bytes. With the BLAKE3 hash function, these 64 bytes can fit within a single chunk, meaning the BLAKE3 hash operation only needs to apply the compression function once to this single chunk. In the compression function of BLAKE3, seven round functions and six permutation functions are required.
BitVM has already implemented basic operations such as XOR, modular addition, and right-bit shift based on u32 values, making it straightforward to assemble a BLAKE3 hash function using Bitcoin script. The stack uses four separate bytes to represent u32 words, facilitating the u32 addition, u32 bitwise XOR, and u32 bitwise rotations required by BLAKE3. The BLAKE3 hash function in the Bitcoin script is currently about 100kB, sufficient for constructing a toy version of BitVM.
Furthermore, by splitting these BLAKE3 codes, the Verifier and Prover can significantly reduce the on-chain data requirements by dividing the execution into the challenge-response game instead of performing it entirely. Finally, implementing hash functions like Keccak-256 and Grøstl in the Bitcoin script will identify the most Bitcoin-friendly hash function and explore other new Bitcoin-friendly hash functions.
Scriptless Scripts is a method of executing smart contracts off-chain using Schnorr signatures. The concept of Scriptless Scripts originated from Mimblewimble, where no permanent data is stored other than the kernel and its signature.
The advantages of Scriptless Scripts include functionality, privacy, and efficiency:
Functionality: Scriptless Scripts can expand the scope and complexity of smart contracts. The capabilities of Bitcoin script are limited by the number of OP_CODES enabled on the network. In contrast, Scriptless Scripts move the specification and execution of smart contracts off-chain to discussions among the contract parties alone, without waiting for the Bitcoin network to fork to enable new opcodes.
Privacy: Moving the specification and execution of smart contracts from on-chain to off-chain enhances privacy. On-chain, many details of the contract are shared with the entire network, including the number of participants, addresses, and the amount transferred. Moving smart contracts off-chain means the network only knows that the participants have agreed that the terms of the contract are satisfied and the related transactions are valid.
Efficiency: Scriptless Scripts minimize the amount of data that needs to be verified and stored on-chain. By moving smart contracts off-chain, the administrative costs for full nodes are reduced, and transaction fees for users are also lowered.
Scriptless scripts represent a way to design 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. Adaptor signatures and multi-signatures are foundational building blocks of Scriptless Scripts. With Scriptless Scripts, transactions can be smaller than conventional transactions, thus reducing transaction fees.
Scriptless Scripts can be used to implement logic gate commitments in the BitVM circuit, saving BitVM script space and enhancing BitVM efficiency, using Schnorr multi-signature and Adaptor signatures instead of providing hash values and pre-images like the BitVM solution. Although current Scriptless Scripts schemes can reduce BitVM script space, they require extensive interaction between the prover and challenger to combine public keys. Future improvements will aim to integrate Scriptless Scripts into specific BitVM functional modules.
The current BitVM challenge requires permission because a Bitcoin UTXO can only be executed once, leading to a situation where a malicious verifier could “waste” the contract by challenging an honest prover. BitVM is currently restricted to a two-party challenge model. A malicious prover could use a verifier under his control to initiate a challenge and “waste” the contract, thus ensuring his malicious action succeeds while other verifiers cannot prevent this behavior. Therefore, on top of Bitcoin, it is necessary to research a permissionless multi-party OP challenge protocol that could expand BitVM’s existing 1-of-n trust model to 1-of-N, where N is much larger than n. Additionally, it’s important to address issues of collusion between challengers and provers or malicious challenges that “waste” contracts to achieve a more trust-minimized BitVM protocol.
A permissionless multi-party challenge allows anyone to participate without a whitelist, meaning users can withdraw from L2 without the involvement of any trusted third party. Moreover, any user wanting to engage in the OP challenge protocol can question and remove invalid withdrawals.
Expanding BitVM into a permissionless multi-party challenge model involves addressing the following attacks:
Sybil attacks: Even if an attacker creates multiple identities to participate in the dispute challenge, a single honest participant should still be able to win the dispute. If the cost for an honest participant to defend the correct result grows linearly with the number of attackers, the cost for the honest participant to win the dispute becomes impractical and vulnerable to Sybil attacks when involving a large number of attackers. The paper “Permissionless Refereed Tournaments” proposes a dispute resolution algorithm that changes the game rules, where the cost for a single honest participant to win the dispute grows logarithmically, not linearly, with the number of opponents.
Delay attacks: An individual or group of malicious actors follow a strategy to prevent or delay the confirmation of the correct result (like withdrawing assets to L1) on L1, forcing the honest prover to spend L1 transaction fees. To mitigate this issue, challengers could be required to make an upfront stake. If a challenger launches a delay attack, their stake would be forfeited. However, if attackers are willing to sacrifice their stake to some extent to pursue delay attacks, there should be strategies to reduce the impact of these attacks. The algorithm proposed in the paper “BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol” ensures that the worst-case delay caused by the attacker is capped, regardless of how much stake the attacker is willing to lose.
In the future, there will be an exploration of a BitVM permissionless multi-party challenge model that is resistant to these attacks and suitable for the characteristics of Bitcoin.
The exploration of BitVM technology is just beginning, and in the future, more optimizations will be explored and practiced to achieve scaling for Bitcoin and enrich the Bitcoin ecosystem.
References
