The concept of zero-knowledge proof
Zero-Knowledge Proofs (ZKPs from here on) are a way to prove a statement is valid (i.e. knowledge is held about veracity of the statement) without sharing information about the statement itself. For instance, proving somebody is at least 18 years old without sharing their birth date, or that a transaction is valid (i.e. the account of origin has enough money available) without disclosing how much was transferred or the balance of the ordering account. In fewer words, I can prove to you that I’m not lying, without telling you how.
ZKPs have three characteristics/requirements:
- Completeness: if the ZKP says a statement is correct, that statement is actually correct.
- Soundness: if the statement is false, and I’m a sneaky sneaky liar, I can’t make the ZKP say that the statement is true
- Zero-knowledge: at the end of the process, you (as the verifier) know only whether the statement is true or false, nothing else.
In the literature, I am called the Prover, because I’m the one proving the statement, and you’re the Verifier. ZKPs work by allowing the Verifier to ask questions and find out if the Prover has the knowledge they say they have.
A good example can be found at https://www.sans.org/reading-room/whitepapers/vpns/identification-zero-knowledge-protocols-719 (lightly edited for clarity):
Let’s say I want to convince you that I am able to count the leaves of a big maple tree in a few seconds without revealing to you my method and without revealing to you the number of the leaves. We can test my knowledge by going in front of one such tree, and doing the following:
- While I close my eyes, you can do either of the following actions: pull off a leaf or donothing;
- Then I take a look at the tree, and you ask me to tell you what you did.
For you it’s very easy to see whether I answered correctly or not, but it might have been luck. We can therefore repeat the experiment until you are convinced that yes, I know my stuff when it comes to counting leaves.
Another oft-cited example is that of a colour-blind friend that is skeptical of the difference between a red ball and a green one:
Imagine your friend is colour-blind and you have two balls: one red and one green, but otherwise identical. To your friend they seem completely identical and he is skeptical that they are actually distinguishable. You want to prove to him they are in fact differently coloured, but nothing else, thus you do not reveal which one is the red and which is the green.You give the two balls to your friend and he puts them behind his back. Next, he takes one of the balls and brings it out from behind his back and displays it. This ball is then placed behind his back again and then he chooses to reveal just one of the two balls, switching to the other ball with probability 50%. He will ask you, “Did I switch the ball?” This whole procedure is then repeated as often as necessary. He knows if he switched the ball because he did it himself, and you know if he did (because you can see the colour) without revealing to him the actual colour of the ball.
Characteristics of ZKPs
The above exposes a very important characteristic of ZKPs, they are probabilistic – the more tests are conducted the slimmer my chances of successfully cheating, and you can adjust the number of tests depending on how sure you want to be. So with one true/false test I have a ½ chance of cheating successfully, with two tests ¼, with three ⅛, and so on until we’ve run one, ten, or a hundred thousand tests and you’re pretty sure I’m not cheating.
ZKPs have been around for a few decades now, but were not usable in blockchains because, surprise surprise, until recently it was very expensive to compute a ZKP enough times to prove a statement to a satisfactory degree. Through the effort of many researchers, however, there are now multiple algorithms with interesting names like “zk-snark”, “bulletproof”, “zk-stark”, and “set membership” that can be used fairly effectively. There are even cryptocurrencies based on ZKPs, such as ZCash (which uses zk-snarks, and because of that requires an initial trusted setup described as a “ceremony”).
We will not go into the specifics of each algorithm, as it’s early days even by blockchain standards, with improvements on existing types of proofs and entirely new types of proofs being published fairly often. An example of the first are zk-starks removing the requirement of the trusted setup of zk-snarks (described in https://blog.z.cash/the-design-of-the-ceremony/), a big improvement towards complete trustlessness; as for the latter, IBM last year introduced range proofs, which allow proving that a value is in a certain range, and just recently unveiled set membership, which allows to prove that a value is part of a set.
What can ZKPs be used for?
Widespread use of ZKPs is still some distance away; it is however one of the more interesting and promising areas of cryptographical research, both in the blockchain sphere and more generally in technology, and their potential cannot be understated. In the simplest sense, they can guarantee the validity of a transaction without leaking any information about the sender, the recipient, or the transaction itself. In banking for example, ZPKs could prove that somebody is earning enough to qualify for a loan without the need to disclose their income. In more complex systems, they could prove that a certain actor followed the rules of a protocol, thus discouraging malicious behaviour. In authentication systems, they can prove the identity of somebody without divulging personal information. Many projects (rightly) criticized for their dubious privacy practices might find a functional implementation by using ZKPs, for instance protecting the identity of minorities while still allowing them to prove that they do have access to a certain service.
Further reading (if you’re interested)
- On Zero-Knowledge Proofs in Blockchains: https://medium.com/@argongroup/on-zero-knowledge-proofs-in-blockchains-14c48cfd1dd1
- zkSNARKs in a nutshell: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
- MIT Review Acclaims zk-SNARKs, but zk-STARKs May Steal the Show: https://themerkle.com/mit-review-acclaims-zk-snarks-but-zk-starks-may-steal-the-show/
- STARKs, Part I – Proofs with Polynomials: https://vitalik.ca/general/2017/11/09/starks_part_1.html
- Zero Knowledge Proofs – An illustrated primer: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/
- Magical internet blockchain robots – ZK Snarks and Starks edition: https://medium.com/@cameronrout/magical-internet-blockchain-robots-zk-snarks-and-starks-edition-ea627252ab59
- Explain Like I’m 5 – Zero Knowledge Proof (Halloween Edition): https://hackernoon.com/eli5-zero-knowledge-proof-78a276db9eff
- A zero knowledge proof for Where’s Wally: https://medium.com/swlh/a-zero-knowledge-proof-for-wheres-wally-930c21e55399
- Banking Giant ING Is Quietly Becoming a Serious Blockchain Innovator: https://www.coindesk.com/banking-giant-ing-quietly-becoming-serious-blockchain-innovator/
- Aim, Fire – Bulletproofs Is a Crypto Privacy Breakthrough: https://www.coindesk.com/aim-fire-bulletproofs-breakthrough-privacy-blockchains/
- ING Plans To Introduce Zero-Knowledge Set Membership: https://bitrazzi.com/ing-plans-to-introduce-zero-knowledge-set-membership/
- What is zkSNARKs – Spooky Moon Math: https://blockgeeks.com/guides/what-is-zksnarks/
- Exploring Zero-Knowledge Proofs: https://manishearth.github.io/blog/2016/03/05/exploring-zero-knowledge-proofs/
- SANS Institute InfoSec Reading Room: https://www.sans.org/reading-room/whitepapers/vpns/identification-zero-knowledge-protocols-719
- The Design of the Ceremony: https://blog.z.cash/the-design-of-the-ceremony/