Bitget App
Trade smarter
Buy cryptoMarketsTradeFuturesCopyBotsEarn

From OP_CAT to state proofs and BitVM, how to make Bitcoin support ZK?

BlockBeatsBlockBeats2024/08/11 06:00
By:BlockBeats

The Bitcoin protocol is difficult to modify, but the community is considering introducing zero-knowledge proof (ZK) technology to improve privacy and performance.

Original author: Janos Nick, Blockstream
Original translator: Bai Ding, Faust, Geek Web3


Abstract: This article concisely but pointedly points out how to make Bitcoin support ZK verification function. The specific topics involved include the functional defects of Bitcoin UTXO and scripts, Taproot and OP_CAT, and the general content of concepts such as BitVM and Chain State Proof. The article puts forward a relatively clear point of view:


It is an inevitable trend for the Bitcoin protocol to introduce ZK. There are two routes for this: one is to make Bitcoin scripts directly support SNARK verification, which requires the use of OP_CAT opcodes, and the probability of OP_CAT passing in the end is very high; the second route is based on BitVM, which requires the introduction of fraud proofs, and the ZeroSync team has also specifically proposed Chain State Proofs to reduce the cost of node clients to verify historical data.



Text: To better understand Bitcoin, we'd better view it as a social system. When Bitcoin was first launched, developers determined the software programs that Bitcoin nodes needed to run, just like determining a set of rules that a social system follows. The reason why the social system of Bitcoin can operate stably is that everyone has a certain consensus on key issues such as "what is the essence of Bitcoin" and "what it should be". Of course, it is not easy to reach a consensus, and people still have extensive and evolving differences when facing the above issues.



This can be traced back to the historical origin of Bitcoin. When Satoshi Nakamoto released the Bitcoin white paper, he said: "I am studying a new electronic payment system. This system is completely P2P and does not need to rely on any third party." This passage was published on the Cypherpunk mailing list (an email discussion group founded in 1992, composed of a group of cryptographers and technology enthusiasts who focus on privacy protection and cryptography technology).


However, Bitcoin limits data throughput at the product design level. The number of transactions that can be processed per unit time is limited. If the number of pending transactions increases rapidly, users will launch a price war in order to quickly complete the transaction, and quickly increase the handling fee. The single transaction with the highest handling fee in the Bitcoin network occurred in 2024 After the block reward was halved, the transaction fee for a medium-priority transaction on the chain reached $150. It can be said that the expensive transaction fees of the Bitcoin network have become a problem.


In order to solve the problem of transaction fees, people have invested a lot of resources in the development of the Lightning Network. But according to a paper published in 2016, the Lightning Network can only support tens of millions of users in practice, and cannot realize its vision of a global payment system.


In addition to the high transaction fees, there is another problem that Bitcoin has never been able to achieve the anonymity it wants to achieve in its vision. Satoshi Nakamoto pointed out in the cypherpunk mailing group that Bitcoin has privacy protection functions and transaction initiators can be completely anonymous. However, although transaction initiators do not need KYC, the transaction data on the Bitcoin chain leaks a lot of information, which largely exposes user privacy.


Although some wallet clients with privacy functions have solved the above problems to a certain extent, the developers of these wallet clients are facing threats of varying sizes. For example, the developers of the Samourai CoinJoin wallet were arrested by the FBI in April 2024, and a week later, the developers of the Wasabi wallet shut down their CoinJoin coordination component. Obviously, these so-called privacy wallets are not completely trustworthy.


To sum up, many of Bitcoin's ideas are still far from being realized, and related technologies are still under development. Even so, many people in the Bitcoin community still believe that Bitcoin's protocol design should remain unchanged, but there are also many people like me who are keen to improve Bitcoin. So, in what direction should Bitcoin be improved?



There are many proposals in the Bitcoin community to address the above issues, and the best theoretical effects should be related to ZK and SNARKs. With the help of ZK and SNARKs, the following features can be achieved:


1. Significantly improve privacy: Use homomorphic Peterson commitments to significantly improve user privacy for transaction amounts and Range Proof (as done in Blockstream's Element sidechain); hide transaction traces through linkable signatures (such as Monero); and achieve truly private transactions (such as Zcash).


2. Increase transaction throughput


In fact, there are many technical means to solve the problems of Bitcoin, but why have these technologies not been added to the Bitcoin protocol until today? This is because the Bitcoin protocol is difficult to modify. There is no organization similar to the Ethereum Foundation in the Bitcoin ecosystem. Any modification of the protocol requires a high degree of consensus in the community, which involves a lot of gaming and checks and balances. Therefore, unlike Ethereum, which has an update of the EVM opcode every year, the Bitcoin protocol has changed very little since its inception.


In fact, it is a good thing that the protocol is difficult to modify to some extent. If it is easy to modify the Bitcoin protocol, it will also be easy to maliciously change and attack it. This leads to the question: What means can be used to improve the performance of Bitcoin without changing the design of the Bitcoin protocol?



To answer this question, we need to review our knowledge about Bitcoin. If we want to transfer Bitcoin to someone else, we need to create a transaction and broadcast it to the Bitcoin network. The output data of the transaction will indicate the amount of BTC transferred, and the BTC recipient can create a new transaction to spend the received BTC. After that, this new transaction will generate new output data and send BTC to others.


It should be noted here that Bitcoin does not have a global state like Ethereum, especially there is no account state, only transaction output data. The output of each transaction has two states: it has been spent by the recipient or it has not been spent. The unspent transaction output is the UTXO we are familiar with.


Of course, in addition to the associated BTC amount, each transaction output has an additional program written in a language called Bitcoin Script. Whoever can show the correct proof Witness to this program can spend the transaction output (UTXO). Bitcoin Script itself is a stack-based programming language that contains a series of opcodes. The additional program of the aforementioned UTXO often consists of multiple opcodes, which complete the calculation based on the stack and put the result back on the stack.


There are many types of common Bitcoin scripts, which have existed since the beginning of Bitcoin. For example, the most common script program in Bitcoin consists of a public key + an opcode to check the digital signature. This opcode stipulates that in order to spend/unlock a certain UTXO, the digital signature of the corresponding public key must be presented.



Here we summarize the functions of Bitcoin Script. First of all, what can Bitcoin Script do?


· Can rearrange the stack, equality check (use equality check to verify whether specific conditions are met, thereby ensuring the security and validity of the transaction), can perform branch operations similar to if-else.


· Can perform limited arithmetic operations on 32-bit numbers, namely addition and subtraction.


· Can hash data, and can check ECDSA and Schnorr signatures.


What can't Bitcoin script do?


· No loops, jumps, or recursion, i.e., non-Turing complete, very limited programming capabilities.


· Cannot perform bitwise operations. Lacks opcodes for multiplication and division.


· Cannot connect elements on the stack.


· Almost no ability to read and check transaction data on the chain.


· Bitcoin scripts cannot directly access the amount of each transaction, nor can they pass status (UTXOs are all one-time use, and each transfer destroys the old one and generates a new one).


In the early versions of Bitcoin, some of the things that "cannot be done" in the above scripts can actually be done, but some functions were later disabled by Satoshi Nakamoto because he found vulnerabilities in these opcodes. For example, the opcode OP_CAT, which can merge 2 elements in the stack, can be used to remotely attack Bitcoin nodes and cause them to crash. Out of caution, Satoshi Nakamoto disabled OP_CAT, and some other opcodes were also disabled.


So, can Bitcoin scripts verify SNARK? In theory, although Bitcoin scripts are not Turing complete, their basic operations are sufficient to verify any calculation, but in practice SNARK verification is still impossible because the program size required for the verification step exceeds the maximum block limit of Bitcoin - 4MB.


Perhaps we can try to perform arithmetic operations in large finite fields, but the cost is very high. For example, the multiplication of two 254-bit integers implemented by BitVM has a related Bitcoin script size of nearly 8KB.


Moreover, in the absence of The cost of verifying Merkle proofs is also high in the case of OP_CAT, because this requires operations similar to for loops.



So back to the previous question: Why can't we simply change the Bitcoin protocol and add more powerful opcodes?


As mentioned before, it is very difficult to reach a majority consensus on new protocol rules because the Bitcoin ecosystem has no centralized decision-makers. Any proposal to improve Bitcoin scripts has many objections, and everyone has different positions and perspectives. In the Bitcoin network, there is no good way to measure whether the community has reached a majority consensus. In this case, forcing updates will cause chain forks.


Of course, Bitcoin is not completely immutable. The most recent updates are SegWit in 2017 and Taproot in 2021.



The Taproot upgrade changed many rules. It took three and a half years from theoretical release to actual activation. The key factor in enabling Taproot is that it does not change the existing security assumptions and makes significant improvements to the Bitcoin protocol. For example, it allows the use of Schnorr signatures instead of ECDSA. Both are based on the discrete logarithm assumption and use the same elliptic curve, but the former is more efficient and less computationally intensive than the latter.


Furthermore, Taproot's improvements to Bitcoin are mainly divided into the following three parts:


First, Taproot reduces the verification cost of scripts with a large number of selective branches, allowing Bitcoin to support more complex programs;


Second, Taproot reduces the script data that needs to be revealed on the chain. You can assemble multiple script programs into a Merkle tree, each script is located on a different leaf. If you want to trigger a script, you only need to reveal the leaf where it is located and the Merkle proof;


Third, Taproot also adds other mechanism designs.



Speaking of which, since Bitcoin has a precedent of adding more powerful functions like Tarpoot, why not add a dedicated opcode to verify SNARK? This is because adding a so-called OP_SNARK opcode is very different from the Taproot upgrade.


First, there are many design ideas for OP_SNARK, and it is difficult to get most people to support a single solution; second, if such a proposal is passed, all Bitcoin nodes must support this specific OP_SNARK solution, which will add a huge technical burden.


In addition, the complexity of OP_SNARK itself is also a challenge. If the test is not included, Taproot only adds about 1,600 lines of code, which is acceptable to people, while the code contained in OP_SNARK is much more complicated.


Furthermore, who will review whether the OP_SNARK opcode should be activated? How to get consensus in the Bitcoin ecosystem without a few people understanding its details? These are all problems. Therefore, on the whole, the OP_SNARK upgrade will not happen in a short time.



However, there are other ways to verify SNARKs in Bitcoin Script. We can add simpler opcodes to make Bitcoin Script more powerful, allowing people to implement SNARK verifier programs in the script. But in fact, it is very difficult to write SNARK verifiers in the Bitcoin Script language.


Therefore, the Blockstream research team is developing Simplicity, a programming language that aims to replace Bitcoin Script. Simplicity is designed specifically for blockchain consensus systems and is intentionally not Turing-complete, making it easy to statically analyze and formally verify.



Next, we are going to talk about a very simple but heavyweight proposal that can make Bitcoin Script more powerful, namely the OP_CAT opcode. As we mentioned earlier, OP_CAT exists in the original version of Bitcoin, but this opcode can allow Bitcoin nodes to be attacked by DOS under certain conditions, so it was disabled by Satoshi Nakamoto. Now some people in the Bitcoin community want to re-enable it.


The function of OP_CAT is to pop the top two elements of the stack, connect them, and then put them back on the stack. This sounds very simple, but it can bring huge functional improvements to Bitcoin Script.


For example, Bitcoin script programs originally could not access state information such as the amount of transactions on the chain, but with OP_CAT this will become possible; OP_CAT can also be used to verify Merkle proofs. In short, OP_CAT is an upgrade at the underlying opcode level, which will derive a lot of new features. Many people have proposed the effects that can be achieved by using OP_CAT.


And does OP_CAT help verify SNARKs in scripts? The answer is yes, because supporting the verification of Merkle proofs helps verify FRI-based SNARKs, and OP_CAT can support this. In the past, script programs involving SNARK verification may be too large to be included in the Bitcoin block, and with OP_CAT, the program size can be compressed.


OP_CAT has been discussed for many years in the past, and more and more people are aware of its role in transaction inspection (introspection). Compared with other proposals, the advantage of OP_CAT is that it has existed in Bitcoin script before, so it is easier to reach consensus in the community. However, the activation of OP_CAT may also cause some people's MEV benefits to be damaged, so the Bitcoin community has not yet reached a consensus on it.


In summary, Bitcoin may have a potential path to enable simple opcodes such as OP_CAT, allowing everyone to verify SNARK in Bitcoin script. It is also worth mentioning that there is a recent proposal called "Great Script Restoration" that enables multiplication opcodes, allowing all arithmetic opcodes to operate with arbitrary precision.



In addition, when we consider the impact of OP_CAT on the Bitcoin network, we can examine the impact on Bitcoin node operators after it is passed. In order to make Bitcoin censorship-resistant and decentralized, the Bitcoin community hopes that as many people as possible will run nodes to verify data. If Bitcoin supports SNARK verification operations, the cost of running Bitcoin nodes will not increase significantly, which is not much harmful to the security and censorship resistance of Bitcoin.


Currently, a Bitcoin block can contain up to 4MB of data. It is expected that one block will be mined every 10 minutes, and almost all blocks can be filled with Bitcoin scripts and Witness witnesses (similar to digital signatures). In other words, each block can currently contain up to 80K signature verifications, and each block supports an average of 7K to 10K signature verifications. My 2020 Intel CPU takes an average of 3.2 seconds to verify a Bitcoin block. Of course, it is not only the time-consuming signature verification that affects the speed of block verification.


In addition, if Bitcoin transactions support ZK in the future, it seems harmless even if the transaction generation time is extended. For hardware wallets used for long-term storage of assets, they often have screens and are not large in size. Their function is to store keys and generate signatures. The CPU of hardware wallets is generally weak, such as a 240MHz dual-core CPU with a certain amount of memory, and they respond very quickly when signing Bitcoin transactions.



I did a small survey asking users what the longest delay they can accept for the signature device to generate proof. Many people can accept a longer waiting time, especially when they can get significant benefits. So if we introduce ZK into Bitcoin transactions, it doesn't seem to be too much trouble.


Above, we spent a lot of time discussing how to change the underlying design of Bitcoin, but in fact, there are many application scenarios that can be realized without changing Bitcoin. Here I want to emphasize an application related to BitVM - Chain State Proofs, which combines ZK to prove the validity of block hashes.



What changes does this technology bring to Bitcoin? First of all, with Chain State Proofs, the synchronization and verification workload of Bitcoin history data can be compressed, greatly reducing the cost of running nodes. At present, it takes 5 hours and 30 minutes to synchronize and verify from the genesis block to the latest Bitcoin block on a device with good hardware, and it takes several days on a Raspberry Pi-level device. If state proofs are introduced, this time consumption can be greatly compressed. Secondly, chain state proofs are an important part that can be used with BitVM, which will promote the implementation of BitVM.


The ZeroSync team conducted in-depth research on Chain State Proofs and created a lighter "header chain Proofs". This scheme, combined with ZK, only proves the validity of the Bitcoin block header, thereby forming a "header chain" containing all 850,000 block headers in Bitcoin's history, and generates an 80-byte hash for each block header.


This scheme requires double SHA-256 calculations for each Bitcoin block header to verify the corresponding PoW proof. ZeroSync uses STARKs to generate Bitcoin's header chain Proof. The cost of generating the proof is about $4,000, and it only takes 3 seconds to verify the proof with my browser.



However, since it does not include the verification process of the transaction content in the block, the header chain proof can only be assumed to have the most POW The blockchain proved to be valid, and by default, the Bitcoin client is synchronized with the latest block on this chain. In this scenario, although the attacker can create a block containing invalid transactions, add more blocks after this block, and generate a header chain proof to deceive the Bitcoin client that synchronizes historical data, the cost of the attack is extremely expensive and will be directly exposed by the existing Bitcoin full node client.



However, although the success rate of this attack scenario is very low, if it allows the attacker to steal a huge amount of BTC, then the header chain proof cannot be regarded as a foolproof solution. If we want to prove the complete chain state, we need to directly prove that all the contents in the Bitcoin block are valid, including ECDSA and Schnorr signature verification based on the secp256k1 elliptic curve.


Bitcoin can contain 30 million signatures in each month's historical blocks, with a total of 2.5 billion signature operations in history, as well as a large number of SHA-256 Calculation. As a result, the Bitcoin network generates about 7GB of block data each month, and all historical data totals more than 650GB. In reality, this number may be 2 to 3 times.



Now let's look at BitVM. BitVM allows Bitcoin to verify any computing task and is the best way to implement SNARK verification without changing the protocol. BitVM uses two technologies to circumvent the Bitcoin block limit on script size. First, it uses the Taproot MerkleTree script structure;


Secondly, it enables a KV storage solution that can be accessed across a single script, allowing connections to a super large number of script programs. However, the Bitcoin protocol does not enforce the integrity of the above KV storage solution. BitVM needs to check malicious Prover through fraud proof. If the Prover publishes an invalid statement or a problematic KV storage, others can initiate a transaction on the Bitcoin chain to indicate that the Prover behaved improperly and take away the assets pledged in advance.



To summarize, Bitcoin is facing major challenges, and various solutions have been proposed to solve these problems. However, these proposals will not be adopted by the Bitcoin community soon, and changes to the protocol cannot be completed in the short term. This is both a good thing and a bad thing. It also means that Bitcoin is decentralized and relatively secure.


Many people in the Bitcoin community are excited about the potential of SNARK/STARK. The most feasible way to achieve SNARK verification in the medium and long term is most likely BitVM, but it requires more RD investment to work in practice;


Re-enabling the OP_CAT opcode is also an idea, but it needs to prove that the benefits of restarting the opcode far outweigh the risks, and investigate which simple opcodes can allow SNARK verification in Bitcoin scripts, or explore what scenarios can be achieved with functions similar to OP_CAT. Regardless of which solution is chosen, the ultimate goal of the Bitcoin community must be to make the product practical and support more landing scenarios.


Original link

0

Disclaimer: The content of this article solely reflects the author's opinion and does not represent the platform in any capacity. This article is not intended to serve as a reference for making investment decisions.

PoolX: Stake to earn
CEC, QTLX, GDV and other popular new coins are in hot progress!
Stake now!