Blockchain Semantics Insights
Business Case | Deep Tech | Announcements | Blockchain Glossary |
What Is A Zero Knowledge Proof?By Abhishek Singh | July 14, 2018, 1:32 p.m. GMT
Two millionaires Piglet and Vignette, while behaving like millionaires, want to find out who is richer. But given they are millionaires and probably take sleeping pills after having evaded taxes for years, they do not want to reveal their net worth to each other or to anyone. The solution to this problem, famously known as Yao’s Millionaires’ Problem involves a sophisticated application of cryptography. This is the derivative behind Zero Knowledge Proof now being explored fervently by different Blockchain networks.
Zero Knowledge Proof (ZKP) is the method in which a prover Piglet can prove to a verifier Vignette that she knows a secret without revealing the secret. Using zero-knowledge proof the verifier Vignette will not get any information of the secret and thus won’t be able to prove to anyone that she knows the secret. Piglet remains the prover and Vignette remains the verifier. Zero Knowledge Proof requires iteration and interaction. The process of zero-knowledge proof should be repeated many times, such that the verifier is absolutely certain that the prover has the knowledge of the secret.
What happens if there is no iteration? If there is no iteration there are chances of Piglet cheating Vignette- Piglet does not know the secret but Vignette still ends up verifying it. Every such iteration is a challenge from Vignette to Piglet where Vignette has to enter an input so as to convince Vignette. These challenges could even repeat. But at no point in time during the verification process will Vignette ask the secret itself as a challenge or will learn about the secret in any other way.
Here’s an example to bring this to life.
There is a famous example for explaining ZKP called The Ali Baba cave.
Again, Piglet is the prover and Vignette is the verifier. There is a cave which is ring-shaped and there are two ways to traverse around the cave-A and B- as shown in the figure below. There is only one door in the cave. Remember that the door is inside the cave and not at the mouth. The door has a secret password. You need to know the password to get around the cave, that is, to enter via A and exit via B or enter via B and exit via A.
Now, Piglet says that she knows the secret password that will open the door in the cave. Verifier wants to verify this. The easy way to do it is that Piglet tells her the secret password, Vignette uses it to open the door of the cave and hence is able to verify the password. But of course, Piglet does not want to tell Vignette the secret password. Hence, they decide to use ZKP.
Piglet enters the cave from either A or B and this decision is hers. Vignette does not know which path Piglet took. Now, Vignette will ask Piglet to come out from either path A or path B. Say, Vignette asks her to return via path A.
To do this, Piglet will have to use her secret password to open the door if she entered via B. If she entered via A, then she won’t have to use her password- she can simply turn around and exit via A.
Hence, if Vignette decides to declare the secret verified if Piglet emerges from A (which is where she wanted Piglet to emerge from), there is a 50% chance she has got it wrong. To get around this, Vignette will use iteration and interaction. The above-mentioned process will repeat many times with Vignette picking the exit side A or B randomly each time. If Piglet emerges correctly every single time, then she does know the secret and Vignette can verify Piglet’s secret confidently. But how many times will the Verifier have to iterate this process?
If this process is repeated just twenty times, then the probability of Piglet cheating decreases to 1 in a million. Thus, if Piglet is returning from the desired path every time across 20 iterations, it means almost beyond doubt that she knows the secret password.
This is ZKP.
Now, several of you may be wondering Vignette could simply ask Piglet to enter via A and exit via B. Or enter via B and exit via A. If Piglet is able to do it, then Piglet knows the secret password. Piglet still does not need to share the password with Vignette. However, there is one more requirement to ZKP. That Vignette should not be able to prove beyond doubt to third-parties that Piglet, in fact, knows the password (or the secret). If Vignette could set Piglet a challenge as above “Enter via A and exit via B” and record this event, she could prove to others (and not just herself) that Piglet knows the secret. If however the process would have been done as specified then Vignette would not able to prove anyone that Piglet knows the secret. What is the difference? The difference is that in the detailed process as specified, Vignette does not know which side- A or B- Piglet entered from.
To conclude, a zero-knowledge proof must satisfy three properties:
- Completeness: If the statement of the prover is true and the protocol is followed properly then an honest verifier will be convinced that the prover is honest
- Soundness: If the statement of prover is false then there is no way an honest verifier will accept the statement or will be convinced that the prover is honest. (Note: This does not hold true always. But the probability of the protocol failing should be very low.)
- Zero-knowledge: If the statement of the prover is true, then verifier never learns about the secret. The verifier is also not able to prove to others beyond doubt that the prover, in fact, knows the secret.