How to make Bitcoin ZK-enabled: From OP_CAT to state proofs and BitVM

Author: Janos Nick, Blockstream

Translator: Bai Ding & Faust, Geek Web3

Abstract: This article concisely but to the point 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 clear point of view:

It is an inevitable trend for the Bitcoin protocol to introduce ZK, and there are two routes for this:One is to allow Bitcoin scripts to 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 verifying historical data.

Text:In order to understand Bitcoin more deeply, we'd better treat 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 followed by a social system. The reason why the Bitcoin social system 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, which 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. It can process a limited number of transactions per unit time. If the number of pending transactions increases rapidly, users will start 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 after the block reward was halved in 2024. The handling 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. However, according to a paper published in 2016, the Lightning Network can only support tens of millions of users at most in practice, and cannot realize its vision of a global payment system.

In addition to the high transaction fees, there is another problem, that is, 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 the initiator of the transaction can be completely anonymous. However, although the initiator of the transaction does 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 developer of the Samourai CoinJoin wallet was arrested by the FBI in April 2024, and a week later, the developer of the Wasabi wallet shut down their CoinJoin coordination component. Obviously, these so-called privacy wallets are not completely trustworthy of users.

In summary, many of Bitcoin's concepts are still far from being realized today, 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 make improvements to Bitcoin. So, in what direction should Bitcoin be improved?

There are many proposals in the Bitcoin community to address the above issues, and the ones with 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 (such 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. Improve 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 EVM opcodes every year, the Bitcoin protocol has changed very little since its inception.

In fact, it is a good thing to some extent that the protocol is difficult to modify. If it is easy to modify the Bitcoin protocol, it will also be easy to maliciously change and attack it. This leads to a 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. The opcode stipulates that in order to spend/unlock a certain UTXO, a digital signature of the corresponding public key must be presented.

Recommended reading: "Approaching BTC: Background knowledge required to understand BitVM (1)"

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

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

• It can perform limited arithmetic operations on 32-bit numbers, namely addition and subtraction.

• Data can be hashed, and ECDSA and Schnorr signatures can be checked.

What can't Bitcoin script do?

• No loops, jumps, recursion, that is, non-Turing complete, programming capabilities are very limited.

• No bitwise operations.

• Lack of opcodes for multiplication and division.

• Cannot connect elements on the stack.

• Almost no ability to read and check on-chain transaction data. 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 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 Satoshi Nakamoto found vulnerabilities in these opcodes. For example, the opcode OP_CAT, which can merge two elements in the stack, can be used to remotely attack Bitcoin nodes and cause them to crash. Satoshi Nakamoto disabled OP_CAT out of caution, and some other opcodes were also disabled.

So, Can Bitcoin scripts verify SNARK? Although Bitcoin scripts are not Turing complete in theory, their basic operations are sufficient to verify any calculation, but in practice SNARK verification cannot be achieved 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 Bitcoin script size of nearly 8KB.

Moreover, it is also expensive to verify Merkle proofs without OP_CAT, because it 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, and any proposal to improve the Bitcoin script 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 an update will cause a chain fork. 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 the activation of 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, with each script 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 features 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 for most people to support a single scheme; second, if such a proposal is passed, all Bitcoin nodes will have to support this specific OP_SNARK scheme, 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 in comparison.

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 questions. Therefore, on the whole, the OP_SNARK upgrade will not happen in a short time.

However, there are other ways to verify SNARK 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 verification programs in the Bitcoin Script language.

Therefore, the Blockstream research team is developing Simplicity, a programming language designed to replace Bitcoin Script. Simplicity is designed 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 scripts more powerful, namely the OP_CAT opcode.As mentioned earlier, OP_CAT exists in the original version of Bitcoin, but this opcode can cause 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 scripts.

For example, Bitcoin script programs could not access 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 functions. Many people have proposed the effects that can be achieved by using OP_CAT.

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 Bitcoin blocks, but with OP_CAT, the program size can be compressed.

OP_CAT has been discussed for many years, 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 scripts 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 allow everyone to verify SNARKs in Bitcoin scripts by enabling simple opcodes such as OP_CAT. It is also worth mentioning that there is a recent proposal called "Great Script Restoration" that enables multiplication opcodes and allows 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 a Bitcoin node will not increase significantly, which will not harm the security and anti-censorship 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 version of 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 responds very quickly when signing Bitcoin transactions.

I did a small survey asking users what the longest delay they would accept for the signature device to generate a proof was. Many people can accept a longer wait 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.

We spent a lot of time discussing how to change the underlying design of Bitcoin, but there are actually many application scenarios that can be implemented 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. Currently, 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, while 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 generating 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 using my browser.

However, since it does not include the verification process of the transaction content in the block, the header chain proof can only assume that the blockchain with the most POW proofs is valid, and by default, the Bitcoin client synchronizes 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, doing so will be extremely expensive and will be directly exposed by the existing Bitcoin full node client.

However, despite the low success rate of this attack scenario, if it allows attackers to steal huge amounts of BTC, then the header chain proof cannot be considered 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's historical blocks each month can contain 30 million signatures, a total of 2.5 billion signature operations, and a large number of SHA-256 operations. In this way, 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 enables Bitcoin to verify any computing task and is the best path to implement SNARK verification without changing the protocol. BitVM uses two technologies to circumvent the Bitcoin block's limit on script size. First, it uses the Taproot MerkleTree script structure;

Second, 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 problematic KV storage, others can initiate a transaction on the Bitcoin chain to indicate that the Prover is misbehaving and take away its previously pledged assets.

To sum up, Bitcoin is facing major challenges, and people have proposed various solutions 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 safe.

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 R&D 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;

No matter 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: https://www.youtube.com/watch?v=GrSCZmFuy7U