Bitlayer: BitVM and its optimization thoughts

Author: lynndell, mutourend; Source: Bitlayer Research Group

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, resulting in its security being 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 an article titled "BitVM: Compute Anything On Bitcoin" white paper has triggered everyone's 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 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. Therefore, BitVM greatly broadens the potential use cases of Bitcoin, allowing Bitcoin to not only serve as a currency, but also as a verification platform for various 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 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 Bitcoin scripts stateful through Lamport 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 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:

• Circuit commitment: the prover and the verifier will Programs are compiled into large binary circuits. The prover commits to the circuit in a Taproot address, and each leaf script under that address corresponds to each logic gate in the circuit. The core is to implement logic gate commitment based on bit commitment and realize circuit commitment.

• Challenge and response: The prover and verifier 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 statement, the verifier can take away the prover's deposit after a successful challenge to thwart the prover's evil behavior.

3.BitVM optimization

3.1 Reduce the number of OP interactions based on ZK

Currently there are 2 Major 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 proof 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. Assuming that it takes 2^n times, the error point can be found; if the complexity of the algorithm is too high, n is larger and it is necessary to It takes 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 implement On-Demand ZK Proof. Unlike full ZK Rollup, which no longer needs 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 1MB, which occupies the entire block. But the standardness limit of 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 length of signature and public key helps reduce transaction data, thereby reducing handling fees. Lamport 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 the v-bit message into a vector s of length n. The value of each element in s is {0,...,d}. The Lamport 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, 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-time 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's 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 is 10kB, and the maximum size of P2TR script witness is the same as the maximum Segwit transaction size, which is 4MB. However, the upper limit of standradness of P2TR script witness is 400kB.

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.

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 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 BLAKE3 hash function, these 64 bytes can be allocated within a single chunk, and the entire BLAKE3 hash operation only needs to apply the compression function once to a single chunk. In the compression function of BLAKE3, it is necessary to run the round function 7 times and the displacement function 6 times.

Currently, BitVM has completed basic operations such as XOR, modular addition, and bit right shift based on u32 values. It is easy to assemble the BLAKE3 hash function implemented by Bitcoin scripts. 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, allowing Verifier and Prover to significantly reduce the cost of execution by splitting the execution in the challenge-response game in half instead of executing it completely. 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 method of executing smart contracts off-chain by using Schnorr signatures. The concept of Scripless Scripts was born from Mimblewimble and does not store permanent data except the kernel and its signature.

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

• Function: Scriptless Scripts can 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 move the specification and execution of smart contracts from the chain to discussions only among design contract participants, without waiting for a 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 can increase 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 the 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 can also realize the logic gate commitment in the BitVM circuit, thus saving money. BitVM script space improves BitVM efficiency. Although the existing Scriptless Scripts solution 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 Scripts 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, causing malicious verifiers to "waste" by challenging honest provers. "The contract. BitVM is currently limited to two-party challenge mode. A prover who tries to do evil can challenge the contract with a verifier it controls at the same time, thereby "wasting" the contract and making the evil act successful, while other verifiers cannot 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, it is necessary to study and solve the problem of challengers colluding with provers or maliciously challenging "wasted" contracts. Finally implement the BitVM protocol with less trust.

Permissionless multi-party challenges, allowing anyone to participate without a permissionlist. 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:

• Sybil 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 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  Propose a game-changing dispute resolution algorithm in which the cost for a single honest party to win a dispute grows logarithmically with the number of opponents, rather than linearly.

• Delay attack: A malicious party or group of malicious parties follow a certain strategy to prevent or delay the confirmation of the correct result (such as withdrawing assets to L1) on L1, and force An honest prover costs L1 handling fee. This problem can be alleviated by requiring challengers to stake in advance. If a challenger launches a delay 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 Protocol The algorithm proposed makes it so that no matter how much pledge the attacker is willing to lose, the worst-case attack can only lead to a certain upper limit. 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 practiced to achieve the expansion of Bitcoin and prosper the Bitcoin ecosystem.

References

1. BitVM: Compute Anything on Bitcoin

2. BitVM: Off-chain Bitcoin Contracts

3. Robin Linus on BitVM< /span>

4. [bitcoin-dev] BitVM: Compute Anything on Bitcoin

   < /li>

5. The Odd Couple: ZK and Optimistic Rollups on a Scalability Date

6. < p>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. < span style="font-size: 18px;">[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< /span>

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