🔥 Gate Post Ambassador Exclusive Posting Reward Task Round 4 Is Live!
Not yet a Gate Post Ambassador? Apply now 👉 https://www.gate.com/questionnaire/4937
Join the Ambassador Task and post daily from June 9 to June 15, get your posts rated, and share a $300 prize pool based on your ratings!
🎁 Reward Details:
S-Level Weekly Ranking Reward
Post every day for 7 days with an overall quality score above 90 to qualify for S-Level.
2 outstanding ambassadors will each receive a $50 trading fee rebate voucher.
A/B-Level Tiered Rewards
Based on the number of posts and their quality, ambassadors will
BitVM principle analysis and 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 calculations. 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, while 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 it does not have the two-way checksum constraint capability with Bitcoin, making its security lower 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 a white paper called "BitVM: Compute Anything On Bitcoin", which triggered everyone's thinking about 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 makes full use of Bitcoin Script and Taproot to achieve optimistic rollup. 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 Bitcoin's 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) Lamport's 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 to reduce costs; (4) The existing BitVM contract is huge and the Bitcoin block capacity is limited. Less s can be used to implement less s BitVM, saving Bitcoin block space and 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 of 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 for script 1 and script 2 to have the same x value, and Bitcoin Script does not support this natively. However, you can still use existing opcodes to make the Bitcoin script stateful through Lamport's one-time signature. For example, you can force x in 1 and 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 modification of 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 prover's 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:
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 BitVM's efficiency. According to the zero-knowledge proof theory, if the data Data satisfies the algorithm F, it is proved that the proof satisfies the verification algorithm Verify, that is, the verification algorithm outputs True; if the data Data does not satisfy the algorithm F, it is proved that the proof does not satisfy the verification algorithm Verify, 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 algorithm F, use the dichotomy method to split it. Assume that it takes 2^n times to find the error point; if the complexity of the algorithm is too high, n will be large and it will take a long time to complete. However, the complexity of the verification algorithm Verify of zero-knowledge proof is fixed. The entire process of proof and verification algorithm Verify is public, and the output is found to be False. The advantage of zero-knowledge proof is that the computational complexity required to open the verification algorithm Verify is much lower than the binary method to open the original algorithm F. Therefore, with the help of zero-knowledge proof, BitVM is no longer challenging the original algorithm F, but the verification algorithm Verify, reducing the number of challenge rounds and shortening the challenge cycle.
Finally, although the effectiveness of zero-knowledge proof and fraud proof depend on different security assumptions, they can be combined to build ZK Fraud Proof and realize On-Demand ZK Proof. Unlike full ZK Rollup, it is no longer necessary to generate ZK proof for each single state transition. The On-Demand model makes ZK Proof only required when there are challenges, while the entire Rollup design is still optimistic. Therefore, the resulting state is still valid by default until someone challenges it. If there is no challenge in a certain state, 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 in 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 signature
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 limit for legacy transactions is 100 kB. According to consensus rules, the maximum size of a Segwit transaction is 4 MB, which is the weight limit. However, the standardness limit of Segwit transactions is 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. Lamport's one-time signature requires the use of a hash function (such as one way permutation function f). In Lamport's 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, a special function P is used to map a v-bit message into a vector s of length n. The value of each element in s is {0,..., d}. Lamport's one-time signature scheme is the Winternitz one-time signature scheme in the special case of d= 1. In the Winternitz one-time signature scheme, the relationship between n, d, v satisfies: n≈v/log 2(d+ 1). When d= 15, there is n≈(v/4)+ 1. For a Winternitz signature containing n elements, the public key length and signature length are 4 times shorter than in Lamport's one-time signature scheme. However, the complexity of signature verification increases by 4 times. Using d= 15, v= 160, f=ripemd 160(x) in BitVM to implement Winternitz one-time signature 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, 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 is 10 kB, and the maximum size of P 2 TR witness is the same as the maximum Segwit transaction size, which is 4 MB. However, the upper limit of standradness of P 2 TR witness is 400 kB.
Currently, the Bitcoin network does not support OP_CAT, and string 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 size and 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 consecutive 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 needs to apply the compression function once to the single chunk. In the compression function of BLAKE 3, it is necessary to run the round function 7 times and the permutation function 6 times.
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 on-chain data required by splitting the execution in the 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 less s BitVM
less s is a method of executing smart contracts off-chain by using Schnorr signatures. The concept of Scripless s was born from Mimblewimble, which does not store permanent data except the kernel and its signature.
The advantages of less s are functionality, privacy and efficiency.
less s is an approach to designing cryptographic protocols on Bitcoin that avoids the need to execute 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 less s. Using less s, you can achieve smaller transactions than regular transactions and reduce transaction fees.
With the help of less s, Schnorr multi-signature and adapter signature can be used, which no longer provides hash values and hash preimages like the BitVM solution, and can also realize the logic gate commitment in the BitVM circuit, thereby saving BitVM script space and improving BitVM efficiency. . Although the existing less s scheme can reduce the BitVM script space, it requires a large amount 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 s into specific BitVM function modules.
3.5 Permissionless multi-party challenge
The reason why current BitVM challenges require permission by default is that Bitcoin's 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 who tries to do evil can simultaneously launch a challenge with a verifier he controls, thereby "wasting" the contract, making the evil act successful, and other verifiers cannot prevent the behavior. Therefore, based on Bitcoin, a permissionless multi-party OP challenge protocol needs to be studied, which can extend BitVM's existing 1-of-n trust model to 1-of-N. Among them, N is much larger than n. In addition, there is a need to study and solve the problem of challengers colluding with provers or maliciously challenging "wasted" contracts. Ultimately implementing the BitVM protocol with less trust.
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. In addition, any user who wants to participate in the OP challenge protocol can challenge and delete invalid withdrawals.
Extending BitVM to a permissionless multi-party challenge model requires solving the following attacks:
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
Original link