Analysis of BitVM principles and its optimization considerations
Original source: Bitlayer Research Group
Original author: 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 scaling issue of Bitcoin has been a concern since its inception. The Bitcoin UTXO model treats each transaction as an independent event, resulting in a stateless system that lacks the ability to perform complex, state-dependent computations. Therefore, while Bitcoin can perform simple scripts and multi-signature transactions, it has difficulty facilitating the complex and dynamic contract interactions common on stateful blockchain platforms. This issue significantly limits the scope of decentralized applications (dApps) and complex financial instruments that can be built on Bitcoin, whereas state model platforms provide a more diverse environment for deploying and executing feature-rich smart contracts.
For Bitcoin expansion, there are mainly technologies such as state channels, side chains, and client verification. Among them, state channels provide secure and diverse payment solutions, but they are limited in their ability to verify arbitrarily complex calculations. This limitation reduces its use in a variety of scenarios that require complex, conditional logic and interactions. Sidechains, while supporting a wide range of applications and providing a diversity of functionality beyond Bitcoin, have lower security. This difference in security stems from the fact that sidechains use independent consensus mechanisms, which are far less robust than the Bitcoin consensus mechanism. Client-side verification, using the Bitcoin UTXO model, can handle more complex transactions, but does not have the bidirectional checksum constraint capabilities of Bitcoin, resulting in lower security than Bitcoin. The off-chain design of client verification protocols relies on server or cloud infrastructure, which can lead to centralization or potential censorship through compromised servers. The off-chain design of client-side validation also introduces more complexity into the blockchain infrastructure, potentially leading to scalability issues.
In December 2023, ZeroSync project leader Robin Linus published an article titled BitVM：Compute Anything On BitcoinThe white paper has triggered everyones thinking on improving the programmability of Bitcoin. This paper proposes a Bitcoin contract solution that can achieve Turing completeness without changing the consensus of the Bitcoin network, so that any complex calculation can be verified on Bitcoin without changing the basic rules of Bitcoin. BitVM leverages Bitcoin Script and Taproot to implement optimistic rollups. Based on Lamport signature (also known as bit commitment), a connection is established between two Bitcoin UTXOs to implement stateful Bitcoin scripts. By committing to a large program in a Taproot address, operators and validators engage in extensive off-chain interactions, resulting in a small on-chain footprint. If both parties cooperate, arbitrarily complex, stateful off-chain computations can be performed without leaving any trace on the chain. If both parties do not cooperate, when a dispute occurs, on-chain execution is required. As a result, BitVM greatly broadens Bitcoins potential use cases, allowing Bitcoin to serve not only as a currency but also as a verification platform for a variety of decentralized applications and complex computing tasks.
However, although BitVM technology has great advantages in Bitcoin expansion, it is still in its early stages and there are still some problems in terms of efficiency and security. For example: (1) Challenges and responses require multiple interactions, resulting in expensive handling fees and long challenge cycles; (2) Lamports one-time signature data is long and the data length needs to be reduced; (3) The hash function is complex and requires Bitcoin friendly hash function reduces costs; (4) The existing BitVM contract is huge and the Bitcoin block capacity is limited, scriptless scripts can be used to implement Scriptless Scripts BitVM, saving Bitcoin block space while improving BitVM efficiency; (5) The existing BitVM adopts a permission model. Only alliance members can initiate challenges, and it is limited to only two parties. It should be extended to a permissionless multi-party challenge model to further reduce the trust assumption. To this end, this article proposes some optimization ideas to further improve the efficiency and security of BitVM.
2.BitVM principle
BitVM is positioned as an off-chain contract for Bitcoin and is committed to promoting Bitcoin contract functions. Currently Bitcoin scripts are completely stateless, so when a Bitcoin script is executed, its execution environment is reset after each script. There is no native way to have script 1 and script 2 have the same x value, it is not natively supported by Bitcoin scripts. However, you can still use existing opcodes to make Bitcoin scripts stateful through Lamports one-time signature. For example, you can force x in script 1 and script 2 to be the same value. Participants can be penalized if they sign conflicting x-values. BitVM program calculations occur off-chain, while calculation result verification occurs on-chain. The current Bitcoin block has a 1 MB limit. When the verification calculation is too complex, OP technology can be used to adopt the challenge response mode to support higher complexity calculation verification.
Similar to Optimistic Rollup and the MATT proposal (Merkelize All The Things), the BitVM system is based on fraud proof and challenge-response protocols, 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 expensive. So, the verifier performs a series of carefully designed challenges to succinctly refute the provers false claims. Provers and validators jointly pre-sign a series of challenge and response transactions that are used to resolve disputes, allowing universal computational verification on Bitcoin.
The key components of BitVM are:
Circuit Commitment:Provers and verifiers compile programs into large binary circuits. The prover commits to the circuit at a Taproot address, for each leaf script under that address, corresponding to each logic gate in the circuit. The core is based on bit commitment to implement logic gate commitment and circuit commitment.
Challenges and responses:Provers and verifiers pre-sign a series of transactions to implement the challenge-response game. Ideally, this interaction is performed off-chain, but can also be performed on-chain when the prover is uncooperative.
Ambiguity penalty:If the prover makes any incorrect claims, the verifier can take away the provers deposit after a successful challenge to thwart the provers evil behavior.
3.BitVM optimization
3.1 Reduce the number of OP interactions based on ZK
There are currently 2 mainstream Rollups: ZK Rollups and OP Rollups. Among them, ZK Rollups relies on the validity verification of ZK Proof, that is, the cryptographic proof of correct execution, and its security relies on the computational complexity assumption; OP Rollups relies on Fraud Proof, assuming that the submitted states are correct, setting The challenge period is usually 7 days, and its security assumes that at least one honest party in the system can detect the incorrect state and submit a fraud proof. Assume that the maximum number of steps of the BitVM challenge program is 2 ^{ 32 }, and the required memory is 2 ^{ 32 }* 4 bytes, which is about 17 GB. In the worst case, it takes about 40 rounds of challenge and response, about half a year, and the total script is about 150 KB. There is a serious lack of incentives in this situation, but it almost never happens in practice.
Consider using zero-knowledge proofs to reduce the number of BitVM challenges, thereby improving BitVMs efficiency. According to zero-knowledge proof theory, if the dataDataSatisfy algorithmF, it proves that proof satisfies the verification algorithmVerify, that is, the verification algorithm outputs True; if the dataDatadoes not satisfy the algorithmF, it proves that proof also does not satisfy the verification algorithmVerify, that is, the verification algorithm outputs False. In the BitVM system, if the challenger does not recognize the data submitted by the prover, a challenge is initiated.
For algorithmF, split using the dichotomy method, assuming that it is necessary2 ^ntimes, the error point can be found; if the algorithm complexity is too high, n will be large and it will take a long time to complete. However, the verification algorithm of zero-knowledge proofVerifyThe complexity is fixed, and the proof and verification algorithms are publicVerifyThroughout the process, the output was found to be False. The advantage of zero-knowledge proof is that it opens up the verification algorithmVerifyRequired computational complexity, compared to bisection open original algorithmF, much lower. Therefore, with zero-knowledge proofs, BitVM is no longer challenging the original algorithmF, but the verification algorithmVerify, reduce the number of challenge rounds and shorten the challenge period.
Finally, although zero-knowledge proof validity and fraud proof rely on different security assumptions, they can be combined to build ZK Fraud Proof and implement On-Demand ZK Proof. Unlike full ZK Rollup, which no longer needs to generate ZK proof for each individual state transition, the On-Demand model makes ZK Proof required only when there are challenges, while the entire Rollup design remains optimistic. Therefore, the resulting state is still valid by default until someone challenges it. If a state is unchallenged, there is no need to generate any ZK Proof. However, if a participant initiates a challenge, ZK Proof needs to be generated for the correctness of all transactions within the challenge block. In the future, we can explore generating ZK Fraud Proof for a single controversial instruction to avoid the computational cost of generating ZK Proof all the time.
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, standardness rules are also introduced. Bitcoin nodes only forward broadcast standard transactions, the only way for valid but non-standard transactions to be packaged is directly by working with miners.
According to consensus rules, the maximum size of legacy (non-Segwit) transactions is 1 MB, which occupies the entire block. But the standardness of legacy transactions is capped at 100 kB. According to consensus rules, the maximum size of a Segwit transaction is 4 MB, which is the weight limit. But the standardness of Segwit transactions is capped at 400 kB.
Lamport signature is a basic component of BitVM. It reduces the length of signature and public key, which helps to reduce transaction data and thereby reduce handling fees. Lamports one-time signature requires the use of a hash function (such as one way permutation function f). In Lamports one-time signature scheme, the message length is v bits, the public key length is 2 v bits, and the signature length is also 2 v bits. The signature and public key are long and require a large amount of storage gas. Therefore, there is a need to find signature schemes with similar functions to reduce signature and public key lengths. Compared with Lamport one-time signature, Winternitz one-time signature has significantly reduced signature and public key lengths, but increases the computational complexity of signature and signature verification.
In the Winternitz one-time signature scheme, use special functionsPWillvA message of bits is mapped to a length ofnvector ofs。sThe value of each element in is { 0,...,d}. Lamport one-time signature scheme isd= 1 Special case of Winternitz one-time signature scheme. In the Winternitz one-time signature scheme,n, d, vThe relationship between satisfies:n≈v/log 2(d+ 1). When d= 15, there isn≈(v/4)+ 1 . For containsnThe Winternitz signature of elements is 4 times shorter than the public key length and signature length in Lamports one-time signature scheme. However, the complexity of signature verification increases by 4 times. Used in BitVMd= 15, v= 160, f=ripemd 160(x) implements Winternitz one-time signature, which can reduce the bit commitment size by 50%, thus reducing BitVM’s transaction fees by at least 50%. In the future, while optimizing the existing Winternitz Bitcoin Script implementation, more compact one-time signature schemes expressed in Bitcoin Script can be explored.
3.3 Bitcoin-friendly hash functions
According to the consensus rules, the maximum size of P 2 TR script is 10 kB, and the maximum size of P 2 TR script witness is the same as the maximum Segwit transaction size, which is 4 MB. However, the standradness limit of P 2 TR script witness is 400 kB.
The current Bitcoin network does not support OP_CAT, and strings cannot be spliced for Merkle path verification. Therefore, it is necessary to use existing Bitcoin scripts to implement a Bitcoin-friendly hash function with optimal script size and script witness size to support the merkle inclusion proof verification function.
BLAKE 3 is an optimized version of the BLAKE 2 hash function and introduces the Bao tree mode. Compared with BLAKE 2 s-based, the number of rounds of its compression function is reduced from 10 to 7. The BLAKE 3 hash function will split its input into contiguous chunks of 1024 bytes in size, the last chunk may be shorter but not empty. When there is only one chunk, the chunk is the root node and the only node of the tree. Arrange these chunks as leaf nodes of a binary tree, and then compress each chunk independently.
When BitVM is used to verify the Merkle inclusion proof scenario, the input of the hash operation is composed of two 256-bit hash values, that is, the input of the hash operation is 64 bytes. When using the BLAKE 3 hash function, these 64 bytes can be allocated within a single chunk, and the entire BLAKE 3 hash operation only requires the compression function to be applied once to the single chunk. In the compression function of BLAKE 3, 7 round functions and 6 permutation functions need to be run.
At present, basic operations such as XOR, modular addition, and bit right shift based on u 32 values have been completed in BitVM, and the BLAKE 3 hash function implemented by Bitcoin script can be easily assembled. Use 4 separate bytes in the stack to represent u 32 words to implement u 32 addition, u 32 bitwise XOR and u 32 bitwise rotations required by BLAKE 3. The current BLAKE 3 hash function Bitcoin script totals about 100 kB, which is enough to build a toy version of BitVM.
Additionally, these BLAKE 3 codes can be split, allowing Verifier and Prover to significantly reduce the required on-chain data by splitting the execution in a challenge-response game in half instead of executing it entirely. Finally, use Bitcoin script to implement hash functions such as Keccak-256 and Grøstl, select the most Bitcoin-friendly hash function, and explore other new Bitcoin-friendly hash functions.
3.4 Scriptless Scripts BitVM
Scriptless Scripts are a way to execute smart contracts off-chain by using Schnorr signatures. The Scripless Scripts concept was born from Mimblewimble and stores no permanent data except the kernel and its signature.
The advantages of Scriptless Scripts are functionality, privacy, and efficiency.
Function:Scriptless Scripts increase the scope and complexity of smart contracts. Bitcoin scripting capabilities are limited by the number of enabled OP_CODES in the network, and Scriptless Scripts transfer the specification and execution of smart contracts from the chain to discussions only among design contract participants, without waiting for the fork of the Bitcoin network to enable new ones. opcode.
privacy:Moving the specification and execution of smart contracts from on-chain to off-chain increases privacy. On the chain, many details of the contract will be shared to the entire network. These details include the number and addresses of participants and the transfer amount. By moving smart contracts off-chain, the network only knows that participants agree that the terms of their contracts have been met and the underlying transactions are valid.
efficiency:Scriptless Scripts minimize the amount of data verified and stored on-chain. By moving smart contracts off-chain, management fees for full nodes will be reduced and transaction fees for users will also be reduced.
Scriptless scripts are an approach to designing cryptographic protocols on Bitcoin that avoid executing explicit smart contracts. The core idea is to use cryptographic algorithms to achieve the desired functionality rather than using scripts to achieve the functionality. Adapter signatures and multi-signatures are the original building blocks of Scriptless scripts. Using Scriptless scripts, you can achieve smaller transactions than regular transactions and reduce transaction fees.
Scriptless Scripts can be used to use Schnorr multi-signatures and adapter signatures, which no longer provide hash values and hash preimages like the BitVM solution, and can also realize the logic gate commitment in the BitVM circuit, thus saving BitVM script space and improving BitVM efficiency. . Although the existing Scriptless Scripts scheme can reduce the BitVM script space, it requires a lot of interaction between the prover and the challenger to combine the public key. In the future, we will improve this solution and try to introduce Scripless Scripts into specific BitVM function modules.
3.5 Permissionless multi-party challenges
The reason why BitVM challenges currently require permission by default is that Bitcoins UTXO can only be executed once, allowing a malicious verifier to waste the contract by challenging an honest prover. BitVM is currently limited to two-party challenge mode. A prover that attempts to do evil can simultaneously challenge with a verifier it controls, thereby wasting the contract, making the evil act successful, and other verifiers unable to prevent the behavior. Therefore, based on Bitcoin, it is necessary to study a permissionless multi-party OP challenge protocol that can extend BitVMs existing 1-of-n trust model to 1-of-N. Among them, N is much larger than n. In addition, research is needed to address the issue of challengers colluding with provers or maliciously challenging “wasted” contracts. Ultimately implementing a less trustworthy BitVM protocol.
Permissionless multi-party challenges, allowing anyone to participate without a permission list. This means that users can withdraw coins from L2 without the involvement of any trusted third party. Additionally, invalid withdrawals can be challenged and deleted by any user who wishes to participate in the OP Challenge Protocol.
Extending BitVM to a permissionless multi-party challenge model requires solving the following attacks:
Witch attack:Even if an attacker forges multiple identities to participate in a dispute challenge, a single honest party can still win the dispute. If the cost to an honest party of defending the correct outcome is linearly related to the number of attackers, then when a large number of attackers are involved, the cost of winning a dispute becomes unrealistic and vulnerable to Witch attack. paper Permissionless Refereed Tournaments, proposes a game-changing dispute resolution algorithm in which the cost of a single honest party winning a dispute grows logarithmically with the number of opponents, rather than linearly.
Delayed attack:A malicious party, or group of malicious parties, follows a strategy to prevent or delay the confirmation of correct results (such as withdrawing assets to L1) on L1, and forces honest provers to spend L1 fees. This problem can be alleviated by requiring challengers to stake in advance. If a challenger launches a delayed attack, their stake is forfeited. However, if an attacker is willing to sacrifice staking within certain limits to pursue a delay attack, there should be countermeasures to reduce the impact of the delay attack. paper BoLD: Bounded Liquidity Delay in a Rollup Challenge ProtocolThe proposed algorithm makes it so that no matter how much pledge the attacker is willing to lose, the worst-case attack can only cause a certain upper limit of delay.
In the future, we will explore the BitVM permissionless multi-party challenge model that is suitable for the characteristics of Bitcoin and can resist the above attack problems.
4 Conclusion
The exploration of BitVM technology has just begun. In the future, more optimization directions will be explored and implemented to achieve the expansion of Bitcoin and prosper the Bitcoin ecosystem.
references
