ZK-proof on Bitcoin

[OmegaStarScream]

So in the last week, two companies released the first-ever (mainnet) Zero-knowledge solutions to help scale Ethereum (L2s).

Today, one of these companies announced that they will be using that technology for bitcoin as well so I'd like like to get your thoughts on this:

“It's very much in the prototype stage,” ZeroSync co-founder Robin Linus told CoinDesk. “But the grand vision is that you download that one megabyte of proof and that is as good as if you had downloaded the 500 gigabytes.”
.....
Light clients or simple payment verification (SPV) nodes have always existed on the Bitcoin blockchain. In fact, Satoshi Nakamoto mentioned the concept in his original whitepaper. They are critical for small devices like mobile phones that can’t download the entire blockchain.
“It is possible to verify payments without running a full network node,” Satoshi wrote. "Verification is reliable as long as honest nodes control the network, but is more vulnerable if the network is overpowered by an attacker.”

ZeroSync goes a step further by verifying transactions via cryptographic proof rather than merely trusting honest nodes as suggested by Satoshi.

This should also help with other use cases:

A fully functioning zk-proof mechanism can be used to enable a wide range of applications outside of the flagship node syncing use case. ZeroSync has created a developer tool kit to enable applications like proof-of-reserves on exchanges and transaction history compression on second layer protocols like Lightning Labs’ Taro.

[Pmalek]

I am not sure how the Bitcoin community and pro full-node proponents will accept the idea of not being the ones that perform the full verification process themselves. If the idea has always been to verify and not trust, I don't see that changing. I guess it's also going to depend on how ZeroSync exactly verifies those transactions. An increase in centralization will surely not be something hardcore-bitcoiners will approve of.  

[baro77]

I am not sure how the Bitcoin community and pro full-node proponents will accept the idea of not being the ones that perform the full verification process themselves. If the idea has always been to verify and not trust, I don't see that changing. I guess it's also going to depend on how ZeroSync exactly verifies those transactions. An increase in centralization will surely not be something hardcore-bitcoiners will approve of.  

I don't know ZeroSync actual tech, but from what I read my educated guess is they are going to use recursive or folded SNARKs, in the path of an "old" idea called UTREEXO... so not possible to judge just from that simple article, but tech to do something good exist... and StarkWare funding seems reassuring

[sha420hashcollision]

I am not sure how the Bitcoin community and pro full-node proponents will accept the idea of not being the ones that perform the full verification process themselves. If the idea has always been to verify and not trust, I don't see that changing. I guess it's also going to depend on how ZeroSync exactly verifies those transactions. An increase in centralization will surely not be something hardcore-bitcoiners will approve of.  

Yea UNFORTUNATELY the implementations of these "Zero Knowledge" proofs on EVM chains mainly seems to completely throw away the purpose of using ZK systems in the first place which is privacy and they instead institute some sort of consortium of trusted keys to validate AND verify these proofs and use them for scaling( even though they are much larger than the underlying data inherently)? Seems dumb to me.

ZK proofs for privacy purposes on the other hand is a wonderful application, ZKSTARK implementation seems very promising in a quantum resistance sense and also is acceptably scalable.

But using these things to verify something that is not going to be private ever? That makes no sense, why even use zero knowledge for that application.

There needs to be a legitimate use case for the proofs and one that is reasonably weighted for the Bitcoin network so that it can scale properly.

I am positive a "Full Knowledge" system would be more suitable for public blockchain verification, there is no sense in wrapping stuff in ZK for the hell of it.

These things are not going to be any better than SPV at network security, might they offer a trusted solution that is scalable? Hopefully. But other than that no one will replace a full node with zero knowledge unless they dont care about what code they are running and in that case why even run a node?

[baro77]

ll Knowledge" system would be more suitable for public blockchain verification, there is no sense in wrapping stuff in ZK for the hell of it.
[...]
These things are not going to be any better than SPV at network security, might they offer a trusted solution that is scalable? Hopefully. But other than that no one will replace a full node with zero knowledge unless they dont care about what code they are running and in that case why even run a node?

I'm not ZeroSync evangelist nor I have any interest with them.

That said, I think you are thinking to zkSNARKs, but SNARKs can be also non-ZK. Their use is justified by being "Succinct", short proof (and quickly verifiable). Also ZK-Rollups, despite the name, are not zero knowledge, they use SNARKs because of succinctness.

So, I don't know if ZeroSync idea is good for blockchain size reduction (because any serious evaluation of schemes of that complexity should require a careful study of the proposed solution) , or if it will be accepted (I don't think so to be honest), but the usage of SNARKs to have succinct and fast checkable proof is brand new but well established.. confusing it with ZK flavours is not a good service to the OP imho

[sha420hashcollision]

non ZK proofs can just be merkle proofs, they are extremely small and easy to verify. Such there is no reason to use zk proofs where the zero knowledge factor is not being leveraged, this is a waste of ones time.

[RobinLinus]

Hi, I am the project lead at ZeroSync. Happy to see our work discussed on bitcointalk. Would like to clarify a few points mentioned here:  

- We are using STARKs, which is a form of zero-knowledge proof that requires no trusted setup. It is a *transparent* ZKP.
- "Zero-knowledge" is indeed misleading in a way. This technology was invented for privacy reasons but it turned out to be also very useful to compress a computation. To be precise, actually it doesn't even use the zero-knowledge property really. Nevertheless it became an industry standard to call this tech ZKPs. We use it just because it is a *succinct* proof.
- Using ZeroSync requires no global consensus. Every user can decide individually if they want to sync using a proof or the conventional way. You can even zerosync Bitcoin Core without any code modifications: Use an external tool to verify a UTXO set and then copy it into your chainstate folder.
- ZeroSync is not a company but a Swiss nonprofit creating FOSS software.
- ZeroSync is not just a chain proof but creates a toolkit for Bitcoin developers to apply ZKPs to their own products and services.

On our project website https://zerosync.org you can find more details.


Happy to answer any questions you have.

[baro77]

Hi, I am the project lead at ZeroSync. Happy to see our work discussed on bitcointalk. Would like to clarify a few points mentioned here:  

thanks your notes

Just to have an high level idea in a quick/lazy way ;-) , any diagram/note/schema about who plays the role of public STATEMENT & private WITNESS (in the SNARK meaning of those keywords) in each of the 3 stages of your chainproof (header/assumedvalid/full)?

[RobinLinus]

Just to have an high level idea in a quick/lazy way ;-) , any diagram/note/schema about who plays the role of public STATEMENT & private WITNESS (in the SNARK meaning of those keywords) in each of the 3 stages of your chainproof (header/assumedvalid/full)?

The statement is the bitcoin consensus rules, basically expressing "I know a chain of blocks that is valid and results in chain state X". The (private) witness is the chain of blocks.
The chain state contains data like the block height, the total work, etc, but also a UTXO set commitment. To get a feeling for it, see our demo https://zerosync.org/headers-chain.html

[sha420hashcollision]

Hi, I am the project lead at ZeroSync. Happy to see our work discussed on bitcointalk. Would like to clarify a few points mentioned here:  

- We are using STARKs, which is a form of zero-knowledge proof that requires no trusted setup. It is a *transparent* ZKP.
- "Zero-knowledge" is indeed misleading in a way. This technology was invented for privacy reasons but it turned out to be also very useful to compress a computation. To be precise, actually it doesn't even use the zero-knowledge property really. Nevertheless it became an industry standard to call this tech ZKPs. We use it just because it is a *succinct* proof.
- Using ZeroSync requires no global consensus. Every user can decide individually if they want to sync using a proof or the conventional way. You can even zerosync Bitcoin Core without any code modifications: Use an external tool to verify a UTXO set and then copy it into your chainstate folder.
- ZeroSync is not a company but a Swiss nonprofit creating FOSS software.
- ZeroSync is not just a chain proof but creates a toolkit for Bitcoin developers to apply ZKPs to their own products and services.

On our project website https://zerosync.org you can find more details.


Happy to answer any questions you have.

A ZKP that represents chain state effectively shunts the usefulness of a full node entirely. Why not just concatenate the entire chain into a merkle proof? They are small, succinct, speedy to verify, and are completely transparent. ZKSTARK for verifying a block requires that I trust a consortium of keys that have approved ZKPs of chain state. This goes against not just Bitcoin fundamentals but basic cryptographic assumptions.

[RobinLinus]

requires that I trust a consortium of keys that have approved ZKPs of chain state.

That is a fundamental misunderstanding. STARKs are transparent which means there is no trusted setup. What you mean is SNARKs and not wanting to trust a 'consortium' is exactly why STARKs were invented.

[sha420hashcollision]

If I have to trust a chain-state built from an alternative proof system that is practically like not running a full node whatsoever. I am just trusting that someone whether that be your organization or whoever else ran the prover built the proof correctly. If they did not they can easily spoof the important parts of transaction data and relay something that the end user is completely unaware of. The matter of it being part of an alternative proof system does not strengthen any of the underlying assumptions it does not even preserve them.

[RobinLinus]

That is also a misunderstanding. It all depends on the verifier. If the verifier implementation is correct then the prover cannot fool the verifier even the slightest bit. That is the magic of proof systems. The invention is that there is no trust required. The prover can only ever prove a valid chainstate. Otherwise, it isn't a valid proof.

Of course, you can doubt our implementation. And we openly state ourselves that this is all still prototype-grade. It's still a long way to get it production-ready, but the underlying math is sound and well-established in the research community. STARKs don't even require any novel cryptographic assumptions like many other ZKP systems. They rely only on collision-resistant hash functions*.



* In theory. Actually, we're using a STARK-friendly hash function for proof recursion, e.g. Pedersen hash. However, this also relies on nothing more fancy than assuming that dlogs are hard.

[sha420hashcollision]

That is also a misunderstanding. It all depends on the verifier. If the verifier implementation is correct then the prover cannot fool the verifier even the slightest bit. That is the magic of proof systems. The invention is that there is no trust required. The prover can only ever prove a valid chainstate. Otherwise, it isn't a valid proof.

Of course, you can doubt our implementation. And we openly state ourselves that this is all still prototype-grade. It's still a long way to get it production-ready, but the underlying math is sound and well-established in the research community. STARKs don't even require any novel cryptographic assumptions like many other ZKP systems. They rely only on collision-resistant hash functions*.



* In theory. Actually, we're using a STARK-friendly hash function for proof recursion, e.g. Pedersen hash. However, this also relies on nothing more fancy than assuming that dlogs are hard.

What does it mean for the verifier implementation to be "correct"?

If I have an incorrect verifier I can be fooled, therefore I trade off the ability to verify a completely valid blockchain for the assumption that your organization built a proper prover and verifier.

[sha420hashcollision]

Also it will be commonly misunderstood that the ZK properties of a ZK proof are not even being utilized all the time.
A hash function itself is a scalable transparent proof, and if you aren't aware collisions for sha256 are only possible when employing terrible cryptographic assumptions such as hashing raw strings. I can verify a sha256 faster than any ZKSTARK prover for obvious reasons. The only thing left is the security assumption trade offs which are serious.

[RobinLinus]

What does it mean for the verifier implementation to be "correct"?

I meant that there could be implementation bugs as in any cryptographic software. And it will take a lot of work to harden it.

I trade off the ability to verify a completely valid blockchain for the assumption that your organization built a proper prover and verifier.

We have not really build a new verifier, but only apply existing open source tools. We use the Giza verifier, which is mostly the Winterfell STARK library. What we have added is a translation of that verifier to Cairo.


The best of it all is that you don't have to use it. It is fully optional. It can get rolled out for low value use cases first and grow over time into a hardened library that makes sense for high-value use cases.

[sha420hashcollision]

What does it mean for the verifier implementation to be "correct"?

I meant that there could be implementation bugs as in any cryptographic software. And it will take a lot of work to harden it.

I trade off the ability to verify a completely valid blockchain for the assumption that your organization built a proper prover and verifier.

We have not really build a new verifier, but only apply existing open source tools. We use the Giza verifier, which is mostly the Winterfell STARK library. What we have added is a translation of that verifier to Cairo.


The best of it all is that you don't have to use it. It is fully optional. It can get rolled out for low value use cases first and grow over time into a hardened library that makes sense for high-value use cases.

I dont think the extent of my concern is getting across.
I can build a prover and verifier for generic data for example:
I want to prove I know x where x * secp256k1.G = (xX, xY) and I give you (xX, xY) as the zkproof.

I can only prove I know this by revealing x.

If now x is encoded bitcoin consensus data, the coordinates may very well look like any other coordinates in the proof (xX, xY) but if you then reveal that x is invalid consensus data now it is revealed that every block that is based on x is now invalid. So then if there were to be an attack coordinated against nodes not checking consensus data, they would need to constantly reveal x which breaks the ZK assumption which leaves a fully un-encrypted homomorphic proof which bitcoin already has. If all of this is understood how is it possibly optimized in any way to use external provers on top of the underlying full node proof system?

[IShishkin]

The whole this situation is very similar to the one with Theranos. Theranos' succinct blood test analysis machine was producing zero-knowledge proofs that it works as intended.

As we know, Theranos' devices were capable to execute only a fraction of analysis with a high error rate. However, Theranos team was claiming that analysis is full and accurate. Is it possible that we have the same story with zero-knowledge proofs applied to blockchain verification?

When you describe your ZK-proof system, do you describe "how you want it to work" or "how it actually works"?

[sha420hashcollision]

The whole this situation is very similar to the one with Theranos. Theranos' succinct blood test analysis machine was producing zero-knowledge proofs that it works as intended.

As we know, Theranos' devices were capable to execute only a fraction of analysis with a high error rate. However, Theranos team was claiming that analysis is full and accurate. Is it possible that we have the same story with zero-knowledge proofs applied to blockchain verification?

When you describe your ZK-proof system, do you describe "how you want it to work" or "how it actually works"?

I was trying to make some honest challenges with my claims, but do you also agree there is not much being said as for how these proofs are being used and how they are secure within the Bitcoin framework?

[IShishkin]

The whole this situation is very similar to the one with Theranos. Theranos' succinct blood test analysis machine was producing zero-knowledge proofs that it works as intended.

As we know, Theranos' devices were capable to execute only a fraction of analysis with a high error rate. However, Theranos team was claiming that analysis is full and accurate. Is it possible that we have the same story with zero-knowledge proofs applied to blockchain verification?

When you describe your ZK-proof system, do you describe "how you want it to work" or "how it actually works"?

I was trying to make some honest challenges with my claims, but do you also agree there is not much being said as for how these proofs are being used and how they are secure within the Bitcoin framework?

Yes, I completely agree with you. They don't provide us much information about how these proofs are being used and how they are secure within the Bitcoin framework. They want us to believe their product works as intended without disclosing the full data. It's kind of ZK-proof in real life.

Anyways, I guess ZeroSync exists only as a prototype, as RobinLinus writes. I doubt this prototype is working as described in the real-life test scenario and within a reasonable time limit. I doubt the team has a clear picture of how to finalise the product. It's not clear whether we talk about a working product or about a vision of how it should look like in the future.

Second, there are many proposals which try to utilise ZK-proof system in blockchain networks. It's very common that their developers do not understand what "the complete verification" actually means. The complete list of verifications performed within "a complete verification" might not be as complete as it sounds.

Last but not least. According to RobinLinus, Zerosync relies on the third party ZK-proof library and on math which is "sound and well-established in the research community".

[sha420hashcollision]

The whole this situation is very similar to the one with Theranos. Theranos' succinct blood test analysis machine was producing zero-knowledge proofs that it works as intended.

As we know, Theranos' devices were capable to execute only a fraction of analysis with a high error rate. However, Theranos team was claiming that analysis is full and accurate. Is it possible that we have the same story with zero-knowledge proofs applied to blockchain verification?

When you describe your ZK-proof system, do you describe "how you want it to work" or "how it actually works"?

I was trying to make some honest challenges with my claims, but do you also agree there is not much being said as for how these proofs are being used and how they are secure within the Bitcoin framework?

Yes, I completely agree with you. They don't provide us much information about how these proofs are being used and how they are secure within the Bitcoin framework. They want us to believe their product works as intended without disclosing the full data. It's kind of ZK-proof in real life.

Anyways, I guess ZeroSync exists only as a prototype, as RobinLinus writes. I doubt this prototype is working as described in the real-life test scenario and within a reasonable time limit. I doubt the team has a clear picture of how to finalise the product. It's not clear whether we talk about a working product or about a vision of how it should look like in the future.

Second, there are many proposals which try to utilise ZK-proof system in blockchain networks. It's very common that their developers do not understand what "the complete verification" actually means. The complete list of verifications performed within "a complete verification" might not be as complete as it sounds.

Last but not least. According to RobinLinus, Zerosync relies on the third party ZK-proof library and on math which is "sound and well-established in the research community".

Cairo and ZKSTARK is very sound stuff in my own opinion, I went through some workshops on it myself. But the idea that the ZK part is thrown out makes me entirely confused, the whole point of the ZKSTARK prover is to have an efficient ZK proof. These are also transparent proofs as they require no trusted setup. But the offered STARK non-ZK proofs don't seem to offer much value, this in my opinion needs to be elaborated on heavily.

 For example if I want to prove I know  5+5=10 I can just write that out in clear text. There is no secret information, and thus why wrap the data in a non-standard prover and verification scheme? I was proposing just use a merkle tree for such a thing, for example lets say I want to prove a tx to send bob 50 sats and alice 25 sats. I can do:
sign(sha256(50 | bob))  sign(sha256(25 | alice)) and hand you these signed merkle branches, then you could use them in an extended tree of fully signed commitments that would match hashes when the input data is reproduced perfectly. Such you have a fully transparent proof of knowledge that is to be revealed eventually and you do not need some archaic verification scheme.  

[IShishkin]

But the idea that the ZK part is thrown out makes me entirely confused, the whole point of the ZKSTARK prover is to have an efficient ZK proof.

My personal opinion is that we shouldn't try to guess what is going on there, behind fancy user interfaces. In the trustless system we don't trust.

[Wind_FURY]

I am not sure how the Bitcoin community and pro full-node proponents will accept the idea of not being the ones that perform the full verification process themselves. If the idea has always been to verify and not trust, I don't see that changing. I guess it's also going to depend on how ZeroSync exactly verifies those transactions. An increase in centralization will surely not be something hardcore-bitcoiners will approve of.  

Besides the technical side, in essence, what would be the difference between a ZeroSync client and an SPV wallet/light-client? SPV wallets have existed since the early days of Bitcoin, I believe full-node proponents wouldn't mind another implementation of another kind of light-client.

[sha420hashcollision]

I am not sure how the Bitcoin community and pro full-node proponents will accept the idea of not being the ones that perform the full verification process themselves. If the idea has always been to verify and not trust, I don't see that changing. I guess it's also going to depend on how ZeroSync exactly verifies those transactions. An increase in centralization will surely not be something hardcore-bitcoiners will approve of.  

Besides the technical side, in essence, what would be the difference between a ZeroSync client and an SPV wallet/light-client? SPV wallets have existed since the early days of Bitcoin, I believe full-node proponents wouldn't mind another implementation of another kind of light-client.

SPV clients inherently trust other nodes for block contents. Another implementation of it does not seem to solve this.

[Pmalek]

SPV wallets have existed since the early days of Bitcoin, I believe full-node proponents wouldn't mind another implementation of another kind of light-client.

They wouldn't mind that others use them if they want to, sure, but I don't see why they would. Think about it, if you are using a full-node client, it means you want to have your own copy of the history that your client has verified and ticked as correct. Why would you go from there to trusting my version or a different one, as mentioned in the OP?

It could surely be an attractive option for those of us used to light-clients, but I wasn't thinking about that user base when I wrote that post you quoted. 

[baro77]

The statement is the bitcoin consensus rules, basically expressing "I know a chain of blocks that is valid and results in chain state X". The (private) witness is the chain of blocks.
The chain state contains data like the block height, the total work, etc, but also a UTXO set commitment. To get a feeling for it, see our demo https://zerosync.org/headers-chain.html

So, is it correct to say that when you'll have The Full Chain Proof, your proof will prove that you known a set of ordered blocks (the witness) which starts from the Genesis one and produce -following all BTC consensus rules- the current UTXO set you advertise (and the additional data you have mentioned - height, total work,...)?

If so  I think it's important -without of course forgetting the non-easy need for Full Chain Proof- to underline explicitly the result I have summarized above, because it would mean that, with publicly and widely audited scheme proved sound, the only way to cheat "for you" (aka for anyone advertising a current state by means of your tech) would be to be able to reconstruct a valid blockchain from the beginning, which should reassure many doubts.

Wish you to make fast progresses toward Full-Chain-Proof

[Wind_FURY]

SPV wallets have existed since the early days of Bitcoin, I believe full-node proponents wouldn't mind another implementation of another kind of light-client.

They wouldn't mind that others use them if they want to, sure, but I don't see why they would. Think about it, if you are using a full-node client, it means you want to have your own copy of the history that your client has verified and ticked as correct. Why would you go from there to trusting my version or a different one, as mentioned in the OP?

It could surely be an attractive option for those of us used to light-clients, but I wasn't thinking about that user base when I wrote that post you quoted.  

From my personal opinion, it would be because of for the sake of convenience unless the user wants to be a hardcore, power-user and run full-nodes in all of his/her computers. But I would also encourage that all users should run their own nodes, or have the experience of running one.

But to give you the context of my post, I don't think most full-node proponents would mind if a user runs a Light Client, although they would always suggest that everyone should run one to validate their own transactions, and enforce the consensus rules.

[sha420hashcollision]

That's fair, I think the issue is mainly that SPV is a faulty model that often gives end users incorrect warnings and stuff like that. For example here is a problem I ran into yesterday with Blockstream official software: https://www.reddit.com/r/BitcoinBeginners/comments/za8vqz/invalid_merkle_proof_between_two_blockstream/

Tons of other people experiencing too, and it's safe to say it is not the specific implementation causing the error given that this is developed by one of the leading development groups known to Bitcoin.

[OmegaStarScream]

Update: So apparently there has been some progress in the last few months. You can read these articles[1][2] that came out a couple of days ago.

@RobinLinus Any GitHub links we can look into? and I'm also interested in knowing the ETA of this.

Bitcoin light clients are now able to sync to the tip of the blockchain nearly instantly, thanks to a new development enabled by bitcoin startup ZeroSync and their work in zero-knowledge (ZK) proofs. Ultimately, ZeroSync seeks to enable full nodes to do the same.
--snip--

[1] https://bitcoinmagazine.com/technical/bitcoin-nodes-now-one-step-closer-to-instant-sync
[2] https://blockworks.co/news/zerosync-starkware-zero-knowledge-proofs-bitcoin

[NotATether]

Update: So apparently there has been some progress in the last few months. You can read these articles[1][2] that came out a couple of days ago.

Are there any designs on how the zero knowledge proof will be calculated? I imagine this can be eventually be added into Bitcoin Core cli and graphical with a command to generate the proof of the blockchain up to a certain height, after which the proof can be included in future Bitcoin Core builds to skip the first N (thousand) blocks.

[sha420hashcollision]

Hello! I want to say I'm very impressed with your work and I would like to lighten up the suspicion that I casted on this project a while back.
I look forward to the immense potential of these tools. Also the BitVM paper is very cool!

[OmegaStarScream]

Are there any designs on how the zero knowledge proof will be calculated? I imagine this can be eventually be added into Bitcoin Core cli and graphical with a command to generate the proof of the blockchain up to a certain height, after which the proof can be included in future Bitcoin Core builds to skip the first N (thousand) blocks.

Not as far as I know, I couldn't really find much about it but maybe BitVM whitepaper (made by Robin linus too) as mentioned above might give you an idea of what to expect (just went through it quickly so not sure)[1][2].

[1] https://www.coindesk.com/tech/2023/10/11/bitcoin-might-get-ethereum-style-smart-contracts-under-bitvm-plan/
[2] https://www.bitvm.org/