OP_ZKP Proposal: One Year Milestone

Eventual Turing-completeness, and Bitcoin as The Worldwide Linker

By Weiji , Founder of Lightec, Updated Apr 28, 2024

On April 28, 2023, the same day last year, I sent an email [1] to the Bitcoin developer mailing list proposing that we add a new opcode to Bitcoin Script to verify ZKP proofs. This new opcode, OP_ZKP, would enable Bitcoin to verify off-chain computation as spending conditions for UTXOs. OP_ZKP will equip Bitcoin Script with eventual Turing completeness and capabilities to support many new applications.

Now that a year has passed let’s discuss this proposal further. I will provide further technical background, then explain what has happened in the past year, and finally, what is yet to come.

The BIP

Every proposal must accompany one or multiple BIPs to specify all the technical details and the rationales behind the proposal. However, we understand that ZKP is still fast-growing, with many ZKP schemes. It takes efforts to explore the right combinations of technology and to implement them verifiably correctly (meaning the community could verify the correctness of the implementation rigorously; see [6] for general materials, [7] and [8] for formal verifications in zero-knowledge proof). Meanwhile, the technology stack must remain secure and stable for a long time.

None is easy. And every requirement demands lots of effort.

Meanwhile, it remains a question whether this new opcode is useful in some serious scenarios instead of being just a fancy toy that only tech geeks love.

So, we have adopted a different approach. We spent the past year developing an application that we call zkBTC. It is not just a random sample application that we fabricated to showcase how OP_ZKP could work. It is so tightly coupled with our vision and our roadmap. Let me expand on this a bit.

Bitcoin as Programmable Money, yet only Limited Programmability

Bitcoin is considered programmable money by many. Bitcoin carries a stack language called (just) Script, to express the conditions under which the selected UTXOs could be spent. When one tries to spend some UTXOs, Bitcoin nodes evaluate a piece of Script codes to determine if the spending conditions have been met.

Being programmable is tremendous or even historical. For the first time in humanity, people could enter contracts with each other without the need to trust the counterparty. Instead of a trusted third party or police-backed arbiter, the program determines the final settlement of the contract (along with consensus protocol, of course).

People may have noticed and wondered why there are not as many applications in Bitcoin as in other blockchains. If Bitcoin is the first secure cryptocurrency and is programmable, why are people programming more in other blockchains? What is holding Bitcoin back?

The answer is that the Script, Bitcoin’s native programming language, is not Turing-complete. Being Turing-incomplete means that, in theory, there are many computations that you cannot compute, no matter how smart the programmers are. It is like one cannot punch a hole through a thick steel panel with his bare fist, no matter how strong he is. Only in Bitcoin’s case is the limitation mathematical, not physical or physiological.

So why Turing-incompleteness? Why not just fix it straightforwardly, adding back some opcodes to make the Script Turing-complete? Then, we can express all computable payment conditions with the Bitcoin Script, right?

Lack of Turing-completeness is a deliberate security choice, as otherwise, it is infeasible to tell whether the evaluation of any given script will terminate or not. Then, Bitcoin nodes might be exposed to attacks, causing them to loop forever, and the Bitcoin network would be seriously sabotaged. In theoretical computer science, this is called the halting problem. Interested readers might refer to [2] for further literature. Also, [3] or [4] provides video illustrations that are much more digestible.

Unlocking the Programming Capabilities And (eventual) Turing Completeness

Can we circumvent the limitation? A well-known example is Ethereum, which introduces gas to guarantee the termination of any solidity program execution, as it costs gas to run the program, and gas might run out. For Bitcoin, note that the Script consists of many opcodes, which could do either simple computations or very complex ones. So, eventual Turing-completeness could arise by delegating risky computations off-chain employing some opcode.

And that is our proposal — a new opcode to verify the off-chain computation of arbitrary spending conditions instead of evaluating them directly on-chain. The verification procedure is fully deterministic and presents no risk of undecidability. Bitcoin remains a programmable money with more programming capabilities.

We call this eventual Turing-completeness. The Script is still Turing-incomplete for security reasons. By being eventual, we mean that potentially risky arbitrary spending conditions could be evaluated off-chain, and the evaluation is eventually verified on-chain.

Bitcoin as The Worldwide Linker

What could we achieve should Bitcoin come to carry eventual Turing-completeness? We envision The Worldwide Linker which can link everything computable in the world, both on-chain and off-chain. The linking hub must be decentralized and trustless so that people can collaborate with each other without having to rely on corruptible agencies or intermediaries. And it should be extremely secure to carry the whole world. As the largest cryptocurrency and perhaps also the largest autonomous economy, Bitcoin naturally fits this role, as then the collaboration is protected by Bitcoin’s unparalleled security.

To link is to compute, which will be verified in Bitcoin (or layer 2s on top of Bitcoin). A contract, club membership, a payment receipt, one’s identity, career experiences, asset ownership, digital driver licenses, delivery of goods, and reputations accumulated in some Web2 services are just some concrete examples.

We will not expand or enumerate more on what could be linked now. For the vision to fully unfold, we must build many infra-structure-level applications on top of OP_ZKP. Just remember: everything computable could be linked.

Enough Turing-completeness. Now, let’s turn to the practical parts.

The zkBTC Project and The Chainwide Linker as Phase 1 Roadmap

Project zkBTC started as I tried to build a fully decentralized bridge between the world’s two most significant and prominent cryptocurrency systems. After I had developed a recursive proof of Bitcoin’s chain structure from the genesis block to the deposit transaction at a certain confirmation depth, I realized that I have to manage the private key for Bitcoin when users redeem their $zkBTC. There are some practical and powerful techniques dealing with private keys to prevent a single point of failure, lost key, collusion, etc. I eventually came up with a cryptographically secure solution, and its economic security is strong enough, too.

Still, I don’t like the very existence of private keys for essentially a smart contract that is supposedly open to general public. What if we remove private keys from the equation? Can this be done? Then, the email [1].

We consider project zkBTC an essential part of the opZKP proposal for two reasons beyond its inspiring the latter. First, it is a serious application bridging Bitcoin and Ethereum in a fully decentralized way. Crypto assets in billions of dollars value will flow over the bridge. Second, it makes up the phase 1 roadmap of the Worldwide Linker vision after we further bridge $zkBTC (as ERC-20 token) to all other major blockchains and even L2s.

We name this phase 1 roadmap as the Chainwide Linker vision. The completion of phase 1 would mean that Bitcoin is effectively available in the whole crypto-ecosystem. Pervasive and ubiquitous.

During the past year, I have built a small team to develop project zkBTC towards this phase 1 vision.

Here are what we have accomplished:

a) chainark [5], an open-source ZKP library to prove chain-like structure with a single proof. It is developed on top of gnark but could also be ported to other proving libraries. We use chainark to prove the deposit transaction when the user deposits some Bitcoin to our designated address to mint $zkBTC in Ethereum. With chainark we could prove whole bitcoin history from the genesis block, over and including the block where the deposit happens, to some blocks further to ensure confirmation depth. Other security designs are in play, but let’s discuss them later.

b) reLight, a library to recursively prove the Ethereum Light Client Protocol. It will be open to partners before we open-source it later. reLight is also built on top of chainark and provides one single proof to prove the entire chain from the genesis sync committee to the latest one. The sync committee has a central role in Ethereum Light Client, signing off block information so that (light) clients can verify. With reLight, it is much easier for development teams to prove what happens in Ethereum in ZKP.

c) An interim security solution before OP_ZKP activation. The objective is to launch the zkBTC project before OP_ZKP activation without compromising cryptographic security. The key security architecture is to place the Bitcoin assets under a multi-sig address, keep the private keys confidential to everyone, even including us, and then only sign the fund-release transactions after verifying some proper zero-knowledge proof (the same as OP_ZKP would have done).

d) A test-net. We are still wrapping up the development. But it will be available soon.

Join Us

We need partners to join us. The efforts are enormous. So are the opportunities.

For the Chainwide Linker vision, we leave partners the job of bridging $zkBTC further to other major blockchains and L2s in a fully decentralized way. And we provide support. Suppose the solution is to bridge in ZKP. In that case, we stress that with the project reLight, one can easily prove any Ethereum transaction to any other blockchain or L2s — just one proof. Alternatively, if there are already some different solutions to bridge between Ethereum and other EVM blockchains, feel free to build on top of it. It is permission-less.

For the Worldwide Linker vision, we also welcome people around the world, academic or industrial, to talk with us regarding what and how we could build on top of the proposed ZKP opcode, and which ZKP schemes should be supported, how to ensure correct implementation, etc. We will be sharing related information from time to time. Thanks for reading, and stay tuned.