Zero Knowledge Proof - How it works and The Alibaba Cave Experiment
This blog will introduce the mathematical concept of Zero Knowledge Proofs in a readable format. We will visually demonstrate how it works and show examples of its application in real life and blockchain technology.
ByVitali Bestolkauand Ignas Apšega — Explainers
7 min read
Introduction to the series
This blog is the first in a complete series about Zero Knowledge Proofs. Over the following few articles, we will fully detail the mathematical concept behind them, how different variants work, and how to implement ZPK to improve existing blockchain protocols.
What is Zero-Knowledge Proof?
Zero-Knowledge Proof (from now on: ”ZKP”) is a mathematical concept initially proposed by MIT researchers Shafi Goldwasser, Silvio Micali, and Charles Rackoff in the 1980s. A clear definition of the concept is:
💡
Zero-Knowledge Proof is a technique to define whether the provided data is true without revealing it.
Three criteria must be satisfied for a method called a ZKP. These criteria are also called the properties of ZKP:
-
Completeness
At the end of the method execution, the method should tell that the provided information is accurate if it is accurate.
-
Soundness
The method must not state that the provided information is accurate in case it is not.
-
Zero Knowledge
The method must not reveal (to the verifier) anything about the information it is trying to verify.
The concept of ZKP leads to the idea that we can theoretically create proofs of all types of sensitive data. For example, we can use it to protect credentials, money in a bank account, and personal identity. Given the public nature of transactions on Ethereum, the concept is becoming increasingly prominent in solving its privacy issues. Vitalik Buterin wrote about this exact use case using ZK-Snarks.
How do Zero Knowledge Proofs work?
ZKP resolves around two main parties: a prover and a verifier. A prover is a party trying to prove that the information they deliver is accurate without revealing it. A verifier is a party that verifies whether the information is accurate. In other words, a ZKP can also be defined as a way for a prover to convince a verifier that the data is accurate without telling any underlying information.
However, a verifier can never access the underlying data, as that would violate the 3rd ZKP Property (Zero Knowledge). Instead, a verifier has to perform a specific action repeatedly to gain enough confidence that the data the prover delivers is accurate. Only when a verifier is convinced that data is accurate, the ZKP method can be called complete.
We explain what that means below using the common Alibaba cave example.
The Alibaba cave example
This is a story about Peggy and Victor, who found a ring-shaped cave with the entrance on one side and the magic door blocking the opposite side. Peggy claims to have uncovered a secret word that opens the magic door, but she doesn't want to say this word to Victor. At the same time, Victor wants to learn whether Peggy, in fact, knows the secret word.
So, Peggy and Victor agree on naming both paths (let's call them paths A and B). Then Peggy takes a random path without Victor seeing which path Peggy chooses. After that, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen randomly.
If Peggy knows the secret word, she has no problem returning to Victor using the correct path. But if Victor calls her only once, Peggy has a 50% chance of being lucky if Victor calls here to return the way she entered the cave initially.
That's why Peggy and Victor repeat this activity multiple times. After each repetition, Victor becomes more confident that Peggy knows the secret word. Victor's confidence will rise towards, but never precisely, 100% since there is always a (negligible) chance that Peggy was lucky in all repetitions.
As soon as Peggy returns using the wrong path, we prove she didn't know the secret word. Interestingly, we can confirm that Peggy doesn't know the secret word, but we can never 100% verify that she does, only that it's improbable that she doesn't.
For clarity, the activity that Peggy and Victor repeat is:
- Peggy enters the cave.
- Peggy takes a random path.
- Victor enters the cave.
- Victor shouts a name of a random path.
- Peggy returns using the path Victor shouted (in case she didn't know the secret word and got unlucky, she returns the same way she came in).
We've created an interactive example for the Alibaba Cave on CodeSandbox, which you can check out here:
Use-cases of Zero-Knowledge Proofs
Real-life examples
There are many real-life use cases of ZKPs. These are the most straightforward cases we can think of:
-
Online voting
ZKP technology allows voters to vote anonymously and verify that their vote was included in the final tally.
-
Covidpass
Most countries had or still have the Covidpass. For example, Danish authorities and private businesses universally accept Denmark's "Coronapas" to verify that someone is vaccinated, tested, or immune through the previous infection without revealing specific information. The digital version is a phone app linked to the Danish electronic ID system. When checking in at the airport or entering a restaurant or another facility, a checker scans the QR code and sees whether the passport is valid. Notably, the passport does not disclose why it is valid; there is no information about vaccine status, dates of tests, or previous infections.
-
License and Insurance of a car
ZKP can be used to track a car's license and insurance. The car owner's ID, with a ZKP, could be contained in an app that keeps personal information hidden. A police officer would scan the digital license to verify that the holder can drive, doesn't have outstanding warrants or tickets, and that the car meets all requirements.
Blockchain examples
Zero-knowledge Proofs mainly improve the privacy, security, and scalability of the blockchains:
-
Confidential transactions on blockchains
Transaction data is encrypted, and the proof is posted to prove it was computed correctly. For example, ZCash uses ZKPs to confirm transactions without revealing sensitive data, such as how much money was sent or the identity of the final recipient.
-
Performance optimizations for distributed applications on blockchains
I.e., Ethereum smart contracts - application code is executed off-chain or by a single node on the blockchain network. Only the proof of its correct execution is posted to the blockchain so other parties can verify its correctness.
-
Self Sovereign Identity
Verifiable credentials of self-sovereign identity can be verified using ZKP. As a result, a person would have better control over her privacy.
-
Data security
Organizations that control sensitive data, such as banks and hospitals, must keep them free from third-party access. ZKPs and blockchain together can make accessing data impossible.
Recollection
Let's briefly go through the main facts mentioned about Zero-Knowledge Proof:
💡
Zero-Knowledge Proof is a technique to define whether the provided information is accurate without revealing it.
💡
The three main ZKP properties are Completeness, Soundness, and Zero-Knowledge. If one of these criteria is not met, then the method/technique used to verify the data can not be called a Zero-Knowledge Proof.
💡
Two main parties usually participate in ZKP: a prover and a verifier. A prover is trying to prove the information is accurate without revealing it. A verifier verifies if the information is accurate or not.
💡
In ZKPs, a set of actions is repeated multiple times to maximize the likelihood of the provided data being true.
💡
When using ZKP, a verifier can never be 100% confident that the received information is true.
💡
ZKP can bring privacy, confidentiality, and performance improvements to the blockchain and real life.
Conclusion
In this article, we explained the concept of ZKPs and how they protect sensitive data in real life and for blockchain applications. To eventually understand how that works, we will continue our series in the upcoming article about their types, different protocols, and tooling used in blockchain. So stay tuned for that by following us on Twitter and LinkedIn.