Four First-Ever ZKP Verifications on Bitcoin

17 July 2024, Starkware claims that the first-ever Zero-Knowledge proof is verified on the Bitcoin testnet, Signet.

19 July 2024, nChain claims that the first-ever Zero-Knowledge proof is verified on a Bitcoin mainnet.

23 July 2024, BitcoinOS claims that the first-ever Zero-Knowledge Proof is verified on the Bitcoin mainnet.

24 July 2024, BitVMX claims that the first-ever Zero-Knowledge Proof is verified interactively on a Bitcoin testnet.

What was going on there?

StarkWare used STARK, a hash-function-based proof system that requires OP_CAT to implement proof verification in-script. They tested their implementation on a BTC testnet called Signnet, which is the only one that has OP_CAT enabled. In their example, the verification script verifies that the prover knows or has computed correctly the 32nd number in the Fibonacci squared sequence. More technically speaking, the circuit underlying the computation that is verified on-chain consists of tens of additions and one multiplication, which probably resulted in less than 100 constraints. A series of 11 TapRoot transactions were created to verify the proof, with a total size of roughly 4MB. While the implementation is a toy example and the transactions are testnet transactions, it does not undermine the efforts and talents behind the success. The StarkWare team has certainly demonstrated their incredible capability to build complex Bitcoin scripts. The future of STARKs on BTC mainnet is still uncertain. The main bottleneck is likely to come from the proof size. STARK is designed to significantly improve the proof generation time. As a result, it loses succinctness in proof size. When 128-bit security is needed, the proof size and transaction size may become economically or even computationally unviable for many real-world use cases. They also have to wait for OP_CAT to be enabled on BTC mainnet, which cannot be guaranteed to happen.

nChain zkScript team used Groth16, a proof system that enjoys the smallest proof size and efficient verification time. They tested their implementation on a Bitcoin mainnet called BSV, which has all the original Bitcoin arithmetic opcodes available including OP_MUL and OP_MOD on large integers. These opcodes make implementing cryptographic schemes much more feasible on BSV than on BTC. In their example, the verification script verifies that the prover has computed SHA256 correctly on an input of 5 bytes. The circuit consists of 40875 constraints. However, Groth16 has a constant proof size with respect to the number of constraints. Using existing libraries such as arkworks, nChain has subsequently verified a circuit consisting of over 700,000 constraints on BSV mainnet to demonstrate, with a toy example, verifiability in machine learning. In both cases, the transaction is less than 500KB and to spend the output requires another transaction of around 40KB. The implementation is on BLS12–381 curve which leads to 128-bits of security. While using Groth16 creates no problem in terms of proof size or verification efficiency, it has a bottleneck in proof generation. nChain zkScipt team also implemented MNT4–753 curve to enable recursive Groth16, in which case, the bottleneck in proof generation would be hit more easily. The team is exploring other proof systems and a composition of different proof systems to expand the scope for applicable use cases.

In fact, the first one to experiment Groth16 verification in Bitcoin script was sCrypt. Their implementation resulted in a transaction of 11MB on BSV mainnet as early as 2022. Strictly speaking, nChain zkScript team can only claim that they are the first to do it practically (compliant to network policy of 500KB limit on the locking script) on the BSV mainnet.

BitcoinOS has a different approach. They do not require any changes to BTC. They use something called Merkle Mesh, which is to handle many decentralised verifications at scale off chain (not on Bitcoin). As the proof is not directly verified in Bitcoin script, the challenge of using Bitcoin opcodes to implement complex algorithms is avoided instead of being tackled. What we can say is that StarkWare and nChain are trying to achieve something that seems impossible while Bitcoin OS focuses on delivering a solution that could work on BTC today.

BitVMX’s approach is an interesting blend of what has been mentioned so far. They use Groth16 as a proof system to show that a STARK proof has been verified correctly. This hybrid approach addresses both the bottleneck of proof generation in Groth16 and the bottleneck of proof size in STARK. STARK is first used to efficiently generate a proof that a specific computation is done correctly, resulting a non-succinct proof. Groth16 is then used to generate a succinct proof that the non-succinct STARK proof is verified correctly. Assuming that generating a Groth16 proof on the computation for verifying a STARK proof is significantly more efficient than on the computation of the specific computation, the hybrid approach is better-off. Like BitcoinOS’s approach, the Groth16 proof is verified off-chain (not on Bitcoin). BitVMX then implemented a One-Time-Signature scheme in Bitcoin script to attest to the Groth16 proof. The attestation transaction is then published on a Bitcoin testnet. Their solution also allows others to challenge the attestation. It seems that they have a great solution, but imagine their Groth16 proofs being verified on Bitcoin directly. Isn’t that even better?

It is great to see many teams are trying to bring more functionalities and utilities to Bitcoin by leveraging ZKPs. I hope this gives a clear and objective picture of the current state of zkp verification on Bitcoin. Of course, given that I am part of the nChain zkScript team, I cannot deny my unintentional bias😊. If there is anything inaccurate in the text above, please do not hesitate to contact me.

research.enquiries@nchain.com