This article aims to give you a solid intuitive understanding of what the technical term "zero knowledge" actually means, without going into all the complex mathematics you’d need for the full formal definition. Our goal is to explain the core definition and its rationale in a way that's accessible to everyone, without requiring any mathematical background.
We think understanding the actual meaning of "zero knowledge" is important and being under-emphasized. This term, along with many related terms, is often misused in our industry, leading to unclear communication. Speaking imprecisely about trust and privacy matters can hinder the adoption of these emerging innovative and powerful technologies.
We’ll start with defining proof systems, which are what the term “zero knowledge” applies to.
Proof systems are message exchange protocols with the goal of allowing a prover to convince a verifier of something. A given proof system will be specialized for proving statements of a specific form.
For example, we could have a proof system for proving statements like “The $n$th digit of $\pi$ is $d$”. Here, the prover would provide both $n$ and $d$, and the goal of the protocol is to convince the verifier that the $n$th digit of $\pi$ really is $d$. Ideally, the protocol allows the verifier to be convinced with less effort than it would take them to calculate the digit themselves (otherwise, the protocol is not very useful).
Let's look at a simple but powerful example of a proof system: password verification. When you create a password for a website, you want to be able to prove you know the password later without the website ever storing your actual password. This is done using hash functions - special mathematical functions that convert your password into a unique "fingerprint."
The website stores only this fingerprint (the hash). When you try to log in, you prove you know the password by showing that your input creates the same fingerprint - without ever sending the actual password. This perfectly demonstrates how proof systems can verify knowledge without revealing sensitive information.
The next step towards the term “zero knowledge” is to formalize the sorts of things our proof system is made for proving, which we do with the concept of a relation.
A relation is a set of ordered $(x,y)$ pairs where the $x$ values come from some set $X$, and the $y$ values come from some set $Y$ (and $X$ and $Y$ can be the same). Usually, the relation is defined as a descriptive rule instead of a list of actual pairs.
Let’s look at a couple examples.
Set $X$ and $Y$ to be the integers (i.e: $...,-2,-1,0,1,2,...$). We can define a relation $R_=$ based on the equals sign. In other words, $(x,y)$ is in $R_=$ whenever $x=y$. The list of pairs looks like this:
$$ R_= = \{...,(-2,-2),(-1,-1),(0,0),(1,1),(2,2),...\} $$
Set $X$ and $Y$ to be the integers again. We can define a relation $R_>$ based on the greater than sign. So $(x,y)$ is in $R_>$ whenever $x>y$. Some example pairs would be $(2,1),(2,0),(1,0),(1,-1),(0,-1)$.
Now we’ll revisit our digits of $\pi$ example from above. Set $X$ to be the positive integers and $Y$ to be the digits 0-9. Define $R_\pi$ to contain pairs $(n,d)$ where $d$ is the $n$th digit of $\pi$.
Since $\pi \approx 3.14159...$, the following would be pairs in this relation:
$$ (1,3), (2,1), (3,4), (4,1), (5,5) $$
because the first digit is $3$, then the second digit is $1$, and so on.
When we build a proof system, it’s always for a relation.
For example, we could build a proof system for proving whether a given pair $(n,d)$ is in the relation $R_\pi$ that we discussed above. (Note that, since the verifier can fairly easy check for themselves whether a given value $d$ is in fact the $n$th digit of $\pi$, this isn’t a very useful relation to build a proof system for.)
Let's revisit our password example using hash functions. Hash functions are particularly useful for proving knowledge because of three key properties:
These properties allow us to create a relation where:
This gives us a way to prove we know a password without revealing it - exactly what we want in a zero-knowledge proof system.
“Zero knowledge” is a property of proof systems. In other words, a
In a proof system, there’s two actors:
When we say "prove," we mean "convince beyond reasonable doubt." We do not mean providing a mathematical proof that someone could read and verify line by line.
Unlike traditional mathematical proofs where you verify a static document step-by-step, interactive proof systems rely on dynamic back-and-forth exchanges with random challenges. The system is cleverly designed (by mathematicians) such that the verifier’s random challenges give the prover an opportunity to “prove” something without revealing underlying information.
The mathematics ensures that an honest prover will always succeed in proving valid claims, while a dishonest prover trying to prove a false statement will almost certainly fail, no matter what strategy they take for responding to the challenges.
The combination of randomness and interaction is powerful:
What makes this system powerful is that we can design this interaction in a way that proves something about a secret while revealing nothing about the secret itself (other than what we proved). In other words, the verifier gains zero knowledge beyond the statement to be proved.
<aside> <img src="/icons/view_blue.svg" alt="/icons/view_blue.svg" width="40px" />
Reminder that the word "proof" is used in two distinct ways:
When people talk about “zero knowledge proofs”, they’re talking about the first kind.
</aside>
At the start, $\mathcal{P}$ and $\mathcal{V}$ know a value $x$ which is called the “instance” (i.e.). The goal is to give $\mathcal{V}$ convincing evidence that there exists a “witness” $w$ such that $(x,w)\in R$ (and usually also that $\mathcal{P}$ knows this witness).
We assume that if $\mathcal{V}$ were handed a potential witness $w$, they could quickly check whether $(x,w) \in R$. More precisely, we assume there is a “polynomial-time” algorithm which takes in $(x,w)$ and outputs $\mathsf{YES}$ or $\mathsf{NO}$ according to whether $(x,w) \in R$.
<aside> <img src="/icons/light-bulb_blue.svg" alt="/icons/light-bulb_blue.svg" width="40px" />
Interestingly, proof systems are often designed such that $\mathcal{V}$ never actually does a check of whether any pair is in the relation. Instead, the process looks more like $\mathcal{V}$ using random challenges to confirm that $\mathcal{P}$’s execution of the algorithm is correct and outputs $\mathsf{YES}$.
</aside>
There are two common types of things that $\mathcal{P}$ is trying to convince $\mathcal{V}$ of:
In both cases, $\mathcal{P}$ often wants to convince $\mathcal{V}$ without actually revealing $w$.
You might be asking, what does it mean for $\mathcal{P}$ to “know” $w$? And how could they possibly prove they know $w$ without revealing anything about it?
Our proof system consists of a back-and-forth exchange between $\mathcal{P}$ and $\mathcal{V}$, where $\mathcal{P}$ responds to unpredictable random challenges from the verifier. This live interaction and true randomness prevent the prover from pre-computing responses that could trick the verifier into accepting a false instance.
Interestingly, after a successful interaction between $\mathcal{P}$ and $\mathcal{V}$, anyone who observed the interaction would be convinced of what $\mathcal{P}$ was proving. In other words, if the verifier is satisfied, then everyone else should be too, even without participating in the verification themselves.
On the other hand, if someone simply receives a transcript of the interaction but doesn’t watch it actually happen, they should not be satisfied. This is because anyone could have fabricated a transcript after the fact, including choosing the challenges to whatever they like—which also means the challenges are no longer actually random. A bad actor can make what appears like the output of a valid procedure, when in reality no actual interaction took place.
Think of it like watching a magic trick live versus watching a recorded video. In a live performance, you can verify there are no camera tricks or editing—you're seeing it happen in real-time. But with a recorded video, special effects and editing could have been used to create the illusion.
Let’s pause to point out a subtle distinction: there is the prover $\mathcal{P}$ which is an entity that can know a valid witness $w$ “in its head”, and then there is the prover’s algorithm, which is what actually interacts with the verifier. By definition, the algorithm needs to be given a value of $w$ (valid witness or not) in order to perform the interaction with $\mathcal{V}$.
We write $P(w)$ to represent “the prover’s algorithm instantiated with $w$ as the claimed witness”. The prover’s algorithm instantiated with a valid witness will convince the verifier of the desired statement about $x$. And, on the other hand, when the algorithm is instantiated with an invalid witness $w$ (i.e. $(x,w) \not\in R$), the verifier will reject the claim about $x$.
Our goal with the proof system is to convince $\mathcal{V}$ that $\mathcal{P}$ knows a witness $w$ for a given instance $x$, ideally without revealing anything about $w$. So, we need to formalize this idea where $\mathcal{V}$ can be convinced that $\mathcal{P}$ knows that witness, even though $\mathcal{V}$ never sees the witness itself.
In the actual interaction, $\mathcal{P}$’s algorithm is instantiated with some value for the witness, which we write as $P(w)$. At the end of the back and forth exchange, the verifier algorithm decides whether to accept the claim.
Now recall, the interaction involves randomness. So, it’s possible that one run of the protocol using $P(w)$ could produce a different verifier result than another run. If $w$ is a valid witness for $x$, then the prover algorithm’s job is to maximize the chances of $\mathcal{V}$ accepting the interaction.
This is where the notion of an extractor algorithm comes in: its job is to extract the witness from the prover algorithm. An extractor algorithm $\mathcal{E}$ takes in an instance $x$ as well as an instantiated prover algorithm $P(w)$.
The existence of an extractor is a theoretical tool - we don't actually need to extract the witness in practice. We just need to prove that it would be possible to do so if we wanted to. So, when a researcher presents a system and claims it offers “proof of knowledge”, they prove this by proving the existence of an extractor algorithm.
Now that we’ve learned what it means for a proof system to have “proof of knowledge”, we can turn to what it means for the verifier to gain "zero knowledge” from the interaction.
Just like we needed a formal way to define "knowing" $w$, we need a precise definition of what it means for $\mathcal{V}$ to learn "nothing" about $w$.
Here's the key insight: if $\mathcal{V}$ could generate a transcript that looks exactly like a real interaction with $\mathcal{P}$ without having access to $w$, then $\mathcal{V}$ couldn't have learned anything about $w$ from the real interaction.
This is where the simulator comes in. The simulator $\mathcal{S}$ is an algorithm that takes as input only the statement $x$ (not the witness $w$). Its job is to generate transcripts that look identical to real interactions between $\mathcal{P}$ and $\mathcal{V}$.
The simulator demonstrates that if you could "cheat" by controlling the randomness and message timing, you could create convincing-looking transcripts without knowing $w$. This means that the actual interactive proof process, where the verifier controls the randomness and timing, cannot be revealing anything meaningful about $w$ - because if it did reveal something about $w$, the simulator (which doesn't know $w$) wouldn't be able to create indistinguishable transcripts.
The key is that in a real proof, the verifier's random challenges force the prover to demonstrate knowledge in real-time, while the simulator can "cheat" by constructing its transcript in any order. The fact that these are indistinguishable proves that the actual interaction, despite being convincing about $x$ having a witness, doesn't leak information about what that witness is.
Like the extractor, the simulator is a theoretical tool. We don't need to actually simulate interactions in practice - we just need to prove that such simulation would be possible.
So the essence of zero knowledge comes down to this: could anyone tell the difference between responses from a real prover versus responses generated by our simulator? If not, we've achieved "zero knowledge". In other words, the verifier is convinced that the prover knows the answer but gains no additional knowledge about it.
<aside> 🐦
If you want updates about new content in the book, be sure to follow the book on X: https://x.com/thebookofzk
</aside>