Blockchain privacy technologies serie: Introduction to zero knowledge proofs
February 23, 2020•750 words
In most of the situtations where you (Prover) make a statement and have to prove its authenticity to someone (Verifier), you'll actually have to disclose the actual value of the statement's argument.
Examples
| Situation | Statement | Argument | What is disclosed as a practical proof |
|---|---|---|---|
| Voting, Driving, Buying alcohol... | I am over 18 yo | Age | ID card: actual age, birthdate, name |
| Execute a bank transfer or card transaction | I have enough funds on my account | Account balance | Actual account value |
| Mathematical problem | I know the solution | Mathematical solution | How to solve the problem |
| Private Key | I am the owner of the private key | Private key | Actual private key value |
Having to disclose the value of my account to anyone I want to buy something from, as a proof that I can actually pay him, is very problematic with regards to privacy and security.
Zero Knowledge Proofs
Zero knowledge proofs are precisely a mechanism to assert knowledge without divulging it.
It is a probabilistic-based verification (verification of the equality of 2 polynomial products by randomly selecting several checkpoints). The verifier asks the prover based on certain randomness. If the correct answer is given, the prover has a high probability of possessing what he claims to be “knowledge.”
Example: How to explain zk Proofs to your children - The Strange Alibaba Cave
As illustrated by the Binance Academy, imagine a ring-shaped cave with a single entry and a magic doorway that separates the two side paths apart. In order to go through the magic doorway, one needs to whisper the correct secret words. So consider that Alice (yellow) wants to prove to Bob (blue) that she knows what the secret words are - while still keeping them in secret.
- Bob waits outside. Alice enters the cave and walks until the end of one of the two possible paths.
- Bob walks by the entrance and shout which side he wants Alice to appear from.
- If Alice truly knows the secret, she will reliably show up from the path Bob names.
Bob could think that Alice doesn't really know the secret words and was just lucky. (50% chance to choose the right side of the cave). To convince him they could repeat the operation. After n repetitions, the probability for Alice to luckily choose the right side has decreased to (1/2)^n. The bigger n, the more reliable the proof.
Hence the description of zero knowledge proofs as a probabilistic-based verification mechanism. zk Proofs aren't proofs in the mathematical sense because there is always a small probability (converging to 0) that a cheating prover may convince a verifier that a false statement is true.
Another famous example is the 3-colarability puzzle.
Properties
The combination of the 3 following properties defines more formally a zero-knowledge proof:
Soundness: cheaters get caught
A dishonest prover can't convince a verifier that a false statement is true.
Completeness: true statements get accepted
Following the protocol, an honest prover will naturally convince the verifier that a true statement is true.
Zero knowledgeness: true statements don't teach the verifier anything else except it being true
Applications
zk-SNARK
zk-SNARKs are a particular type of zk Proof
Zero Knowledge
Succinct
Proofs are smaller in size and quick to perform.
Non interactive
The basic of Zero-Knowledge Proof protocol is interactive. It requires the verifier to constantly ask a series of questions about the “knowledge” the prover possess. zk-SNARKs are non interactive in the sense that there is little to no interaction required between the Prover and the Verifier. The Prover can publish their proof in advance, and a verifier can ensure its correctness.
ARgument of Knowledge
= considered computationally sound (see soundness property).
Limitations
zk-SNARKs have limitations though. They are dependent on a trusted setup between the prover and the verifier. A set of public parameters is required to construct zero-knowledge proofs. This creates a potential centralization issue because the parameters are often formulated by a very small group. The initial setup phase is critical in preventing counterfeit spending because if someone had access to the randomness that generated the parameters, they could create false proofs that seemed valid to the verifier.
zk-STARKs were invented as an alternative zk proof mechanism to zk-SNARKs. One that doesn't require such an inital trusted setup.
zk-STARK: succinct-Transparent- ARgument of Knowlege
Transparent
zk-STARK proofs present a simpler structure in terms of cryptographic assumptions. However, this novel technology comes with the disadvantage of generating bigger proofs compared to zk-SNARKs.