Анализ технологии масштабирования Bitcoin Layer 2: доказательство действительности и доказательство мошенничества

28 0 0

Original title: Analysis of Bitcoin Layer 2 Scaling Techniques: Validity Proofs and Fraud Proofs

Original author: mutourend lynndell, Bitlayer Labs

1 Introduction

For an algorithm f, two mutually distrusting parties, Alice and Bob, can establish trust in the following way:

Alice inputs x, runs algorithm f, and obtains result y. Bob also runs algorithm f based on the same input x, and the result is y′. If y = y′, then Bob approves the input x and output y provided by Alice. This is a A special validity proof mechanism, commonly used in blockchain consensus. Alice is the node that packages the block, and Bob is the node that participates in the consensus.
Alice inputs x and runs the zk.prove program on algorithm f to obtain the result y and proof. Bob runs the zk.verify program based on f, y and proof. If the result is true, Bob approves Alices result y; if the result is false, Bob approves Alices result y. If false, Bob does not recognize Alices result y. This is a proof of validity. Among them, Bob can be an on-chain contract.
Alice inputs x, runs algorithm f, and obtains result y. Bob also runs algorithm f based on the same input x, and the result is y′. If y = y′, then do nothing; if y ≠ y′, then Bob Alice is challenged with a program f. Alice and Bob can interact once or multiple times. Arbitration is achieved based on the challenge response process. This is a fraud proof. Bob is the challenger, listening off-chain. Challenge on the chain.
Alice inputs x, runs zk.prove program on algorithm f, and obtains result y and proof. Bob runs zk.verify program based on f, y and proof. If the result is true, do nothing; if the result is false, Then Bob challenges Alice, and the challenged program is zk.verify. Alice and Bob can interact once or more times. Alice and Bob can interact once or more times. Arbitration is achieved according to the challenge response process. This is a fraud proof, in which Bob is the challenger, listening off-chain and challenging on-chain.

For 2, 3, and 4 above, let x be the Layer 2 transaction and the starting state, f be the Layer 2 consensus program, and y be the transaction end state, then the corresponding blockchain Layer 2 expansion plan is as follows:

Validity Proof: Based on the pessimistic assumption, it must be proven to be valid before it is accepted, and it takes effect immediately. In the validity proof, it is necessary to provide evidence that the L2 state transition is correct, reflecting the pessimistic view of the world – if and only if A state is accepted only when it is proven to be correct.
Fraud Proof: Based on optimistic assumptions, it is accepted by default and rejected unless someone proves it is wrong. It has a challenge window period and will only take effect after the challenge window period. In the fraud proof, it is necessary to provide evidence that the L2 state transition is incorrect, reflecting This creates an optimistic view of the world – a state transition is correct by default unless proven incorrect.

Table 1: Trust building methods

In addition, please note that:

The key to distinguishing fraud proofs from validity proofs is not whether a ZK proof system such as SNARK/STARK is used. The ZK proof system expresses the proof method used, while fraud or validity represents the content of the proof. This is why Scenario 1 in Table 1 is said to be proof of effectiveness.
The validity proof has better timeliness, but the on-chain verification complexity is relatively high; the fraud proof has lower on-chain verification complexity, but relatively poor timeliness.
For cases 2 and 4 in Table 1, with the help of ZK recursion and combination technology, multiple f can be calculated and compressed, greatly alleviating and reducing the verification cost of off-chain calculations on the chain.

Currently, benefiting from Solidity Turing-complete smart contracts, fraud proof and validity proof technologies are widely used in Ethereum Layer 2 expansion. However, under the Bitcoin paradigm, limited by Bitcoins limited opcode functions and 1,000 stack elements, This article summarizes the limitations and breakthrough technologies under the Bitcoin paradigm in the context of Bitcoin Layer 2 expansion, studies the validity proof and fraud proof technologies, and sorts out the Unique script segmentation technology.

2 Limitations and Breakthroughs under the Bitcoin Paradigm

There are many limitations under the Bitcoin paradigm, but various clever methods or technologies can be used to break through these limitations. For example, Bit Commitment can break through the UTXO stateless limitation, taproot can break through the script space limitation, connector output can break through the UTXO spending method limitation, and contract Can break through the pre-signing restrictions.

2.1 UTXO Model and Script Restrictions

Bitcoin uses the UTXO model, where each UTXO is locked in a locking script that defines the conditions that must be met to spend the UTXO. Bitcoin scripts have the following limitations:

Bitcoin Script is stateless;
Для P2TR output type, the total number of opcodes that can be accommodated in a single transaction is up to about 4 million, which will fill the entire block, while for other output types it is only 10,000 opcodes;
The spending methods of a single UTXO are limited, and there is a lack of exploration of combined spending methods;
Does not support flexible contract functions;
The stack size is limited to 1000 elements (altstack + stack), and the maximum size of a single element is 520 bytes;
Arithmetic operations (such as addition and subtraction) are limited to 4-byte elements. They cannot be modified to longer elements, such as 20 bytes or larger, which is required for cryptographic operations;
Opcodes such as OP_MUL и OP_CAT have been disabled. If existing opcodes are used for simulation, the cost is extremely high. For example, to simulate a one-round BLAKE 3 hash, the script size is about 75K.

2.2 Bit Commitment: Breaking through the UTXO stateless limitation

Currently, Bitcoin Script is completely stateless. When executing Bitcoin Script, its execution environment is reset after each script. This makes Bitcoin Script unable to natively support constraining script 1 and script 2 to have the same x value. However, there are some ways to circumvent this problem. The core idea is to sign a value in some way. If a value can be signed, then a stateful Bitcoin script can be implemented. By checking the signature of the value of x in script 1 and script 2, we can enforce that the same value of x is used in script 1 and script 2. If there are conflicting signatures, that is, signing 2 different values for the same variable x, they can be penalized. The solution is bit commitment.

The principle of bit commitment is relatively simple. The so-called bit means that for each bit in the signature message, two different hash values are set, namely hash 0 and hash 1. If the bit value to be signed is 0, then hash 0 is revealed. The preimage of hash 1 is preimage 1. If the bit value required to be signed is 1, the preimage of hash 1 is revealed.

Taking a single bit message m ∈ {0, 1} as an example, the corresponding bit commitment unlocking script is just some preimages: if the bit value is 0, the corresponding unlocking script is preimage 0 ——0xfa7fa5b1dea37d71a0b841967f6a3b119dbea140; if the bit value is is 1, then the corresponding unlocking script is preimage 1 — “0x47c31e611a3bd2f3a7a42207613046703fa27496”. Therefore, with the help of bit commitment, the UTXO stateless limitation can be broken and the stateful Bitcoin script can be realized, making various interesting new features possible.

OP_HASH 160

OP_DUP

// This is hash 1

OP_EQUAL

OP_DUP

OP_ROT

// This is hash 0

OP_EQUAL

OP_BOOLOR

OP_VERIFY

// Now the value of the bit commitment is on the stack. Either ” 0 ” or ” 1 ”.

There are currently two ways to implement Bit Commitment:

Lamport one-time signature : The principle is relatively simple and only requires the use of hash functions, so it is Bitcoin-friendly. For each bit in the message, two hash values need to be committed, resulting in a relatively large signature data. In other words, for A message of length v bits, a public key of length 2v bits, and a signature of length v bits.
Winternitz one-time signature : Compared with Lamport signature, it can significantly reduce the length of signature and public key, but increase the complexity of signing and verifying signature. This scheme can flexibly set different hash chain length d values, thus For example, when d = 15, the length of the public key and the length of the signature are both about 4 times shorter, but the complexity of signature verification will increase by 4 times. This is essentially a trade-off between Bitcoin stack space and script size. The Lamport signature can be viewed as a special case of the Winternitz signature when d = 1.

Currently, the BitVM 2 library implements Winternitz signatures based on Blake 3 hash functions. The signature length corresponding to a single bit is about 26 bytes. It can be seen that the cost of introducing states through bit commitment is expensive. In the BitVM 2 project implementation, the message is first hashed to obtain a 256-bit hash value, and then the hash value is bit committed, thereby saving overhead, instead of directly committing to each bit of the original longer message. .

2.3 Taproot: Breaking through the script space limitation

The Bitcoin Taproot soft fork upgrade activated in November 2021 includes 3 proposals: Schnorr signature (BIP 340) , Taproot (BIP 341) and TapScript (BIP 342). A new transaction type, Pay -to-Taproot (P2TR) transactions. P2TR transactions combine the advantages of Taproot, MAST (Merkle Abstract Syntax Tree), and Schnorr signatures to create a more private, flexible, and scalable transaction format.

P2TR supports two spending methods: spending based on key path or script path.

According to the provisions of Taproot (BIP 341) , when spending by script path, the maximum length of the corresponding Merkle path does not exceed 128. This means that the number of tapleafs in the taptree does not exceed 2128. Since the segwit upgrade in 2017, the Bitcoin network has The block size is measured in weight units, with a maximum support of 4 million weight units (about 4 MB). When a P2TR output is spent through a script path, it actually only needs to reveal a single tapeaf script, that is, the block is packaged as a single tapleaf script. This means that for P2TR transactions, the maximum script size for each tapleaf is about 4 MB. However, in the default Bitcoin policy, many nodes only forward transactions smaller than 400K. If larger transactions are to be forwarded, For packaging, you need to cooperate with the miners.

The script space premium brought by Taproot makes it more valuable to use existing opcodes to simulate cryptographic operations such as multiplication and hashing.

When building verifiable computation based on P2TR, the corresponding script size is no longer limited to 4 MB. Instead, the computation can be divided into multiple sub-functions and distributed on multiple tapeafs, thus breaking through the 4 MB limit. 4 MB script space limit. In fact, the current Groth 16 verifier algorithm implemented in BitVM 2 is up to 2 GB in size. However, it can be split and distributed in about 1000 tapelets, and combined with bit commitment , the integrity and correctness of the entire calculation can be constrained by constraining the consistency between the input and output of each sub-function.

2.4 Connector output: Breaking through the UTXO spending restrictions

Bitcoin currently provides two native spending methods for a single UTXO: spending by script or spending by public key. Therefore, as long as the corresponding correct public key signature is provided or the script conditions are met, the UTXO can be spent. The two UTXOs can be spent independently. For spending, no restrictions can be added to constrain the two UTXOs so that they can be spent only if some additional conditions are met.

However, Burak, the founder of the Ark protocol, cleverly used the SIGHASH flag to implement connector output. Specifically, Alice can create a signature to send her BTC to Bob. However, since the signature can commit to multiple inputs, Alice The signature can be set to be conditional: the signature is valid for the Take_tx transaction if and only if the transaction consumes the second input. The second input is called the connector, which connects UTXO A and UTXO B. In other words, The Take_tx transaction is valid if and only if UTXO B is not spent by Challenge_tx. Therefore, by destroying the connector output, the Take_tx transaction can be blocked from taking effect.

Figure 1: Schematic diagram of connector output

In the BitVM 2 protocol, the connector output acts as an if…else function. Once a connector output is spent by a transaction, it cannot be spent by another transaction to ensure its exclusivity. In actual deployment, the challenge response is reserved. In addition, the corresponding connector output can also set different spending policies as needed, such as setting the challenge transaction to be spendable by anyone, and setting the response transaction to be spendable by only the operator or Anyone can spend it after the expiration date.

2.5 Contract: Breaking through the pre-signing restrictions

Currently, Bitcoin scripts mainly restrict the conditions for unlocking, but do not restrict how the UTXO can be further spent. The reason is that Bitcoin scripts cannot read the content of the transaction itself, that is, they cannot achieve transaction introspection. If Bitcoin scripts can check any part of the transaction, The content (including output) can realize the contract function.

The current contract implementation methods can be divided into two categories:

Pre-signature: Based on the existing Bitcoin script capabilities, a pre-signature is used to build a predetermined contract with limited functionality. That is, all possible future transactions are designed and signed in advance, locking the participants into a specific private key and rate. Some solutions It even requires the parties to generate short-term private keys for all pre-signed transactions. Once the pre-signing is completed, these short-term private keys are securely deleted, making it impossible for attackers to obtain the short-term private keys and steal funds. When adding participants or updating operations, the above process needs to be repeated, resulting in heavy maintenance costs. For example, the Lightning Network implements 2-party contracts through pre-signing, and uses hash time lock (HTLC) technology to achieve multiple 2-party The routing function of the contract can achieve a trust-minimizing expansion strategy. However, the Lightning Network requires multiple pre-signed transactions and is limited to two parties, which is a bit cumbersome. In BitVM 1, hundreds of pre-signed In the optimized BitVM 2, the number of transactions that need to be pre-signed during each initialization also reaches dozens. Whether it is BitVM 1 or BitVM 2, only the operator who participated in the pre-signing is eligible for reimbursement. If there are n participants participating in the pre-signing, and each participant needs to pre-sign m transactions, then the pre-signing of each participant is The complexity will be n ∗ m.
Introducing contract opcodes: Introducing new contract function opcodes can significantly reduce the communication complexity and maintenance costs between contract participants, thereby introducing a more flexible contract implementation method for Bitcoin. For example, OP_CAT: used to splice bytes String. Although its function is very simple, it is very powerful and can greatly reduce the complexity of BitVM; OP_TXHASH: can control the actions within the contract with finer granularity. If used in BitVM, it can support a larger set of operators, This greatly improves BitVMs security assumptions and minimizes its trust. In addition, the pre-signing method means that in the BitVM design, the operator can only use the advance payment reimbursement process, which is inefficient in terms of capital utilization. However, through the new contract operation code, it is possible to achieve Direct payments to depositors from the peg-in fund pool further improve fund efficiency. Therefore, the flexible contract model will effectively break through the traditional pre-signing restrictions.

3 Bitcoin Layer 2 Scaling: Proof of Validity and Proof of Fraud

Both validity proof and fraud proof can be used for Bitcoin L2 expansion. The main differences between the two are shown in Table 2.

Table 2: Validity Proof and Fraud Proof

Based on bit commitment, taproot, pre-signature and connector output, a fraud proof based on Bitcoin can be constructed. Based on taproot, by introducing contract operation codes such as OP_CAT, a validity proof based on Bitcoin can be constructed. In addition, depending on whether Bob has Access system, fraud proofs can be divided into permissioned fraud proofs and permissionless fraud proofs. Among them, in the permissioned fraud proof, only a specific group can initiate a challenge as Bob, while in the permissionless fraud proof, any third party can Initiate a challenge as Bob. The security of permissionless is better than permissioned, which can reduce the risk of malicious collusion among the permissioned parties.

According to the number of challenge-response interactions between Alice and Bob, fraud proofs can be divided into one-round fraud proofs and multi-round fraud proofs, as shown in Figure 2.

Figure 2: One-round fraud proof vs. multi-round fraud proof

As shown in Table 3, fraud proof can be implemented through different interaction models, including one-round interaction model and multi-round interaction model.

Table 3: One-round interaction and multiple-round interaction

In the Bitcoin Layer 2 expansion paradigm, BitVM 1 uses a multi-round fraud proof mechanism, BitVM 2 uses a single-round fraud proof mechanism, and bitcoincircle stark uses validity proof. Among them, BitVM 1 and BitVM 2 can be used without making any changes to the Bitcoin protocol. , while bitcoin-circle stark needs to introduce a new opcode OP_CAT.

For most computing tasks, Bitcoin signet, testnet and mainnet cannot be fully represented by a 4 MB script, so the script split technology is needed, which is to split the script that expresses the complete calculation into chunks smaller than 4 MB and distribute them to various nodes. tapleaf.

3.1 Multi-round Fraud Proofs on Bitcoin

As shown in Table 3, multi-round fraud proofs are suitable for scenarios where you want to reduce the amount of on-chain arbitration computation and/or cannot locate the problematic computation fragment in one step. As the name suggests, multi-round fraud proofs involve a series of rounds of negotiation between the prover and the verifier. Multiple rounds of interaction are required to locate problematic computation fragments, and then arbitration is performed based on the located computation fragments.

Robin Linuss early BitVM white paper (often referred to as BitVM 1) used multiple rounds of fraud proofs. Assuming that each round of challenge period is one week, and the binary search method is used to locate the problematic computation fragment, the on-chain challenge response cycle for the Groth 16 Verifier will be As high as 30 weeks, the timeliness is extremely poor. Although there are teams currently studying n-ary search methods that are more efficient than binary search , their timeliness is still much lower than the 2-week cycle in a round of fraud proof.

At present, the multi-round fraud proofs under the Bitcoin paradigm all use permissioned challenges, while the one-round fraud proofs implement a permissionless challenge method, which reduces the risk of collusion among participants and thus provides higher security. Taking advantage of taproot, BitVM 1 is optimized. Not only does it reduce the number of interaction rounds to 1, but it also expands the challenge method to a permissionless one, but at the cost of increasing the amount of on-chain arbitration computation.

3.2 A round of fraud proofs on Bitcoin

The fraud proof can be verified with only one interaction between the prover and the verifier. In this model, the verifier only needs to issue a challenge once, and the prover only needs to respond once. In this response, the prover needs to provide a piece of evidence. , claiming that its calculation is correct. If the verifier can find inconsistencies from the proof, the challenge succeeds, otherwise the challenge fails. The characteristics of a round of interactive fraud proof are shown in Table 3.

Figure 3: One round of fraud proofs

In the technical white paper BitVM 2: Bridging Bitcoin to Second Layers released by Robin Linus on August 15, 2024, a method similar to Figure 3 was used to implement the BitVM 2 cross-chain bridge using a round of fraud proof.

3.3 Bitcoin + OP_CAT to achieve validity proof

OP_CAT was part of the scripting language when Bitcoin was first released, but was disabled in 2010 due to security vulnerabilities. However, the Bitcoin community has been discussing activating it for several years. Currently, OP_CAT has been assigned the number 347 and has been registered in the Bitcoin signet. on.

The main function of OP_CAT is to combine two elements in the stack and push the combined result back to the stack. This feature opens up contracts and STARK Verifier on Bitcoin:

Contract: Andrew Poelstra proposed CAT and Schnorr Tricks I , using OP_CAT and Schnorr tricks to implement contracts on Bitcoin. Among them, the Schnorr algorithm is a digital signature of the P 2 TR output type; for other output types, similar ECDSA tricks can be used, see Covenants with CAT and ECDSA . With the help of OP_CAT contract, it can help split the STARK Verifier algorithm into multiple transactions and gradually verify the entire STARK proof.
STARK Verifier: STARK Verifier essentially concatenates data together and hashes it. Unlike algebraic operations, hashing is a native Bitcoin script operation, which can save a lot of overhead. Taking OP_SHA 256 as an example, native The OP_CAT method only requires one opcode, while the analog method requires hundreds of K. The main hash operations in STARK are the verification of Merkle paths and the Fiat-Shamir transformation. Therefore, OP_CAT is very friendly to the STARK Verifier algorithm.

3.4 Bitcoin Script Split Technology

Although the computation required to run the corresponding verifier algorithm to verify the proof after SNARK/STARK proof is much less than the computation required to directly run the original calculation f. However, when converting it to the verifier algorithm implemented in Bitcoin script, the computation required is much less than that required to run the original calculation f directly. The script size is still huge. Currently, based on the existing Bitcoin opcodes, after optimization, the implemented Groth 16 verifier script size and Fflonk verifier script size are still larger than 2 GB. However, the size of a single Bitcoin block is only 4 MB, it is impossible to run the entire verifier script in a single block. However, after Bitcoin was upgraded to taproot, it supports executing scripts by tapleaf, which can split the verifier script into multiple chunks, and then build a taptree with each chunk as a tapleaf. Between each chunk, bit commitment is used to ensure the consistency of values between chunks.

With the OP_CAT contract, the STARK Verifier can be split into multiple standard transactions of less than 400 KB, so that the entire STARK validity proof can be verified without the need to collaborate with miners.

This section focuses on the relevant Split technology of Bitcoin Script in the existing case without introducing or activating any new opcodes.

When splitting scripts, the following dimension information needs to be balanced:

The size of a single chunk script shall not exceed 4 MB and must include space for input bit commitment scripts, transaction signatures, etc.
The maximum size of a single chunk stack is no more than 1000. Therefore, only the required elements should be kept on each chunk stack, so as to reserve enough stack space to serve the script size optimization. Because the Bitcoin transaction fee does not depend on the stack size used.
Bit commitment on Bitcoin is expensive. So currently 1 bit corresponds to 26 bytes, and the number of input and output bits between 2 adjacent chunks should be minimized.
To facilitate auditing, the function of each chunk should be as clear as possible.

Currently, script segmentation methods are mainly divided into the following three categories:

Automatic segmentation: Based on the stack size and script size, find a segmentation method that minimizes the stack size while keeping the script size around 3 MB. The advantage of this method is that it is independent of the specific verifier algorithm and can be extended to any script segmentation. The disadvantages are: (1) the entire block of logic needs to be marked separately, for example, the OP_IF code block cannot be split, otherwise the script execution result after splitting will be incorrect; (2) the chunk execution result may correspond to multiple elements on the stack, The number of stack elements that need to apply bit commitment needs to be marked according to the actual calculation logic; (3) The logical functions implemented by each chunk script are poorly readable, which is not conducive to auditing; (4) The stack may contain data that will not be used by the next chunk. Elements, wasting stack space.
Functional segmentation: segmentation is based on the functional sub-functions in the calculation. The input and output values of the sub-functions are clear. While segmenting the script, the bit commitment script required by each chunk is also implemented, making the final chunk total script The size is less than 4 MB, and the stack size is less than 1000. Advantages: clear functions, clear logic of a single chunk, good readability, and easy auditing. Disadvantages: the expression of the original calculation logic does not match the expression of the script-level logic. The original calculation sub-function may be optimal, but it does not mean that it is optimal at the script level.
Manual segmentation: The script segmentation point is not in the functional sub-function, but is manually set. It is especially suitable for the case where the size of a single sub-function is greater than 4 MB. The advantage is that it can be used for heavy script size sub-functions, such as F q1 2 The related calculation sub-functions are manually split; the logic of a single chunk is clear, readable, and easy to audit. The disadvantage is that due to the limitation of manual tuning capabilities, when the overall script is optimized, the previously set manual split points may Not optimal, needs readjustment.

For example, after multiple rounds of optimization, the script size of the Groth 16 verifier has been reduced from about 7 GB to about 1.26 GB. In addition to this overall computational optimization, each chunk can also be optimized separately to make full use of the stack space. For example, by introducing A better algorithm based on the lookup table and dynamic loading and unloading of the lookup table can further reduce the script size of each chunk.

The computational cost and operating environment of the web2 programming language are completely different from those of Bitcoin scripts, so for Bitcoin scripts of various algorithms, simply translating existing implementations is not feasible. The following optimizations:

Finding an algorithm with optimal memory locality, even at the expense of some computational effort, can reduce the number of input and output bits between chunks, thereby reducing the amount of data required to commit to assertTx transactions in the BitVM 2 design.
By taking advantage of the commutativity of related operations (such as logical operations), xy = yx, almost half of the lookup table is saved.
Currently, the amount of scripts corresponding to the F q1 2 operation is very large. We can consider using Fiat-Shamir, Schwartz-Zipple and polynomial commitment schemes to significantly reduce the computational complexity of the F q1 2 extended domain operation.

4 Summary

This article first introduces the Bitcoin script restrictions, and introduces how to use Bitcoin commitments to break through the UTXO stateless restrictions, use Taproot to break through the script space restrictions, use connector output to break through the UTXO spending restrictions, and use contracts to break through the pre-signing restrictions. Then, fraud proofs and valid The characteristics of fraud proofs, the characteristics of permissioned fraud proofs and permissionless fraud proofs, the characteristics of one-round fraud proofs and multi-round fraud proofs, and Bitcoin script splitting technology are comprehensively sorted out and summarized.