Zero-Knowledge Proofs
(Redirected from Zero-knowledge proof)
Basics
- In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.
- Used in zk-SNARKS, zk-STARKs and zk-Rollups
- This is being used to create 100% anonymous transactions.
- Also used for anonymous login, anonymous DAOs, anonymous voting etc by Semaphore on Ethereum.
- A ELI5 can be found here
- From a transcript (Summer 2019) by Andrew Poelstra (Blockstream) and David Vorick (Sia):
"In confidential transactions, we have a rangeproof attached to every output. This is an example of a zero-knowledge proof, specifically one to prove a range. The purpose of this is to make sure that ranges aren't going to overflow, that the values aren't going to be negative numbers and won't overflow.
But in general, it's possible to prove anything you want in zero knowledge. This has been generally known since the 1980s. Since the early 90s, it was known to be possible to be done and within the bounds of the known universe. More recently in 2013 there's been a tremendous amount of development in really practical general zero-knowledge proof systems.
STARKs are developed by Eli Ben-Sasson's and others here in Tel Aviv. STARKs are very fast to verify. They are asymptotically very small- they grow with the logarithm of the size of your program execution. Unfortunately, they have large constants like 10s or 100s of kilobytes. Practical STARK programs end up being 50 to 100 kilobytes. They are quantum secure, and they are fast to verify. They scale really well.
One application of STARKs if they were to be much smaller would be a quantum resistant rangeproof which would be interesting, which could lead to a confidential transaction proposal for bitcoin. But they are much more general than this. In theory, you could prove script conditions. You could hide your amount but also your spending conditions. You get something like taproot without all the tricks and the interaction and all these caveats about how sometimes you still need to reveal your scripts.
STARKs can also be used to basically do batch validation. You can produce a STARK proof of the validation of every single signature in the bitcoin blockchain for example. This is a little bit outside of feasibility but with special purpose ASICs you could probably produce such a proof. Now validation of every single signature comes down to validating this small STARK proof which is a few hundred kilobytes of size, rather than dealing with the 100s of gigabytes of data you presently need to do EC operations on. You could compress the whole blockchain signature validation workload into a single proof. We're stretching what's practical to encode; you would have to implement an entire script interpreter into a single zero-knowledge proof system which is very far away from our current ability to design programs.
It's promising tech, and it's practical for a lot of purposes even right now. It's mindblowing and surprising that we can even do this. There's lots of ways in the immediate future that these types of things could be used to improve the scalability of the current system, and also they interact pretty well with the other proposals. Utreexo proofs could be replaced with STARK proofs. The utreexo proofs are small, but STARKs could do aggregation of those. Also, you can do it piecemeal and you don't need to get everyone to do that."
Team
- Silvio Micali; co-inventor of zero-knowledge proofs
