BitVM principle analysis and optimization considerations

Mar 26, 09:00

Original title: "BitVM and its Optimization Thoughts"

Original author: lynndell, mutourend, Bitlayer

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 a white paper called "BitVM: Compute Anything On Bitcoin", which triggered everyone's concern about improving the Thoughts on Bitcoin programmability. 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 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 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 of Bitcoin and is committed to promoting Bitcoin contract functionality. 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 Lamport's one-time signature. For example, you can force x in script1 and script2 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 1MB 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 the Optimistic Rollup and MATT proposals (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 rule. 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.

BitVM key components are:

· Circuit Commitment: Prover and Verification The programmer compiles the program into a large binary circuit. 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.

· Challenge and Response: Prover and verifier pre-sign a series of transactions to implement a 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 claim, the validator can take away the prover's deposit after a successful challenge , thwart the prover’s evil behavior.

3.BitVM optimization

3.1 Reduce the number of OP interactions based on ZK

There are currently two 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 17GB. In the worst case, it takes about 40 rounds of challenge and response, about half a year, and the total script is about 150KB. 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 the efficiency of BitVM. 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 algorithm complexity 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 validity 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, 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 signature

In the Bitcoin network, consensus rules are followed The transaction is a valid transaction, but in addition to the consensus rules, additional standardness rules are 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 a legacy (non-Segwit) transaction is 1MB, which occupies the entire block. But the standardness limit for legacy transactions is 100kB. According to consensus rules, the maximum size of a Segwit transaction is 4MB, which is the weight limit. But the standardness of Segwit transactions is capped at 400kB.

Lamport signature is a basic component of BitVM. Reducing the signature and public key length helps reduce transaction data, thereby reducing 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 2v bits, and the signature length is also 2v 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 a special case of Winternitz's one-time signature scheme for 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, 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-shot signature scheme. However, the complexity of signature verification increases by 4 times. Using d=15, v=160, f=ripemd160(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 function

According to consensus rules, the maximum size of P2TR script The size is 10kB, and the maximum size of P2TR script witness is the same as the maximum Segwit transaction size, which is 4MB. However, the standradness limit of P2TR script witness is 400kB.

The current Bitcoin network does not support OP_CAT and cannot splice strings 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.

BLAKE3 is an optimized version of the BLAKE2 hash function and introduces the Bao tree mode. Compared with BLAKE2s-based, the number of rounds of its compression function is 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, 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 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 the single chunk. In the compression function of BLAKE3, 7 round functions and 6 permutation functions need to be run.

Basic operations such as XOR, modular addition, and bit right shift based on u32 values have been completed in BitVM. It is easy to assemble BLAKE3 implemented by Bitcoin scripts. Ha Hish function. Use 4 separate bytes in the stack to represent u32 words to implement u32 addition, u32 bitwise XOR and u32 bitwise rotations required by BLAKE3. The current BLAKE3 hash function Bitcoin script totals about 100kB, which is enough to build a toy version of BitVM.

Additionally, these BLAKE3 codes can be split so that Verifier and Prover can be significantly improved by splitting the execution in the challenge-response game in half instead of executing it completely Reduce required on-chain data. 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 is a type of script that uses Schnorr signatures on the chain. How to execute smart contracts. 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.

· Features: 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 a method of 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.

With the help of Scriptless Scripts, Schnorr multi-signature and adapter signature can be used, which no longer provides hash values and hash preimages like the BitVM solution, and BitVM can also be implemented The logic gates in the circuit promise to save BitVM script space and improve 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 Permission-free multi-party challenge

The reason why current BitVM challenges require permission by default is because: 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 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 BitVM's 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 that allow anyone to participate without a permissionlist. 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:

· Sybil 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. In the paper Permissionless Refereed Tournaments, a game-changing dispute resolution algorithm is proposed. The cost of winning a dispute by a single honest participant increases logarithmically with the number of opponents, rather than linearly.

· Delay attack: A malicious party or group of malicious parties follow a strategy to prevent or delay the correct outcome (such as withdrawing assets to L1) for confirmation on L1, and forces honest provers to spend L1 handling 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. The algorithm proposed in the paper BoLD: Bounded Liquidity Delay in a Rollup Challenge Protocol enables the worst-case attack to only cause a certain upper limit of delay, no matter how much pledge the attacker is willing to lose.

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

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