An Introduction To Zero-Knowledge Proofs (the Cryptographic Version of: Talks so Much but Says so Little)

My desk on a typical day (not as neat…and not my real desk, obviously)

Dear Theorists/Cryptographers,

This is a simple introduction to the basics of ZKPs in order to prepare you for the more complicated and “useful”[citation needed] concepts like zk-SNARKs and zk-STARKs (which I will also be discussing, soon enough…hopefully)

As its name suggests, a Zero-Knowledge Proof has three components: Zero, Knowledge and Proof. The main purpose of a ZKP is to prove a statement while not revealing any useful internal details of how the proof for that statement was achieved. So let’s start at the beginning and get into the Proof part before we tackle the Zero-Knowledge part. Its complicated. But I will try to keep this as simple as possible. End of the day, the main idea is to not scare people away from this beautiful work. 😛

Standard Proof

The standard mathematical proof is the first thing that comes to your mind when you think about a proof. Basic high school algebra where you were given a problem statement by a teacher, with a single well-defined end goal (like proving a theorem). Your job was to prove to the teacher that you know the steps in order to successfully reach that goal.

This was achieved rather easily (or not, if you hated algebra…we have all been there), by writing the entire proof down on paper and then submitting it to your teacher to be checked line-by-line. If any relevant step in your proof was wrong, the entire proof was considered wrong/false. Therefore, the teacher had to go through each and every step to ensure that the proof works as you claim.

This is what the idea of a proof it. Now lets get into the technical jargon. (see Fig.1)

In the aforementioned case, the teacher is the Verifier (since they verify the proof) and you the student are the Prover (since it is your (Prover’s) job to convince the teacher (Verifier) that the proof you have supplied is correct. And that is all there is to the standard mathematical proof: A Prover, a Verifier and a logical sequence of steps that constitute the proof.

Fig:1 An example of standard proof

But this proof is deterministic (remember the part about a single well-defined end goal we mentioned earlier?) Deterministic proof is just a fancy way of saying: reading the proof will make it absolutely certain whether the proof is correct or not. Which is great for everyone, except in those cases where the proof is lets say a 100 or a 1000 lines long. Yikes!! I feel sorry for those teachers already!

Interactive Proof

In life, not all proofs work like our standard deterministic proofs. And alternatives to this are much more common that you think. Surprised? Here is an example:

Your friend, lets call her Peggy, says she has a program that can predict the score in the next match. You don’t believe her of course (I mean, come on! Peggy makes stuff up all the time!). She shows you the code she has written to predict it. Its like a million lines of code. Surely you don’t have time or energy to verify each line…so what now? But you are smart. So you ask her what the score is going to be in the next match. If the result is as she claims it is, you are convinced…. Or are you?? Well it could have been a fluke. So you ask her again. A prediction for another totally random day (who knows your friend has some understanding with bookies for next couple of days…Peggy is shady as hell!) And if that’s true, then another…and so on. If she gets even one prediction wrong, her entire claim is judged to be false. If she gets every single one of them correct, after several rounds, you are convinced with a high probability that her program does indeed work as she says. (Well good for Peggy!)

Fig.2: Interactive Proof (when correct…hence the dance!)

Now lets break this example down into the technical jargon.

Your friend is the Prover since she is the one with the claim that needs proving.You are the Verifier since its you who needs to be convinced. Property of convincing you that she is correct is called Correctness (of the proof). Property of her getting caught if proof is false is called Soundness (of the proof). Your unpredictability in choosing the match to be predicted is Randomness. And that folks, is a simple example of an Interactive Proof: no actual lines of the proof were exchanged, but instead the proof was verified via an interactive discourse.

An interactive Proof between a Prover and Verifier has the following properties:

• The Verifier has randomness
• The conclusion is probabilistic
• The proof is interactive in nature
• If the Prover is correct, Verifier accepts with 100% probability (called correctness of the proof)
• if the Prover is false, Verifier rejects with a high probability (called soundness of the proof)

So that is an Interactive Proof. But what if there is a secret involved? That is, the Prover doesn’t want you to know the actual solution or even get any hint of it to use to your advantage?

For example, lets say the Prover shows the Verifier her solution to one of the Millennium Problems. The Verifier memorizes it, goes home, writes it down and somehow publishes it ahead of the Prover and gets all the glory (plus a cool $1 million and tenure at Harvard!) That wont be good for our poor Prover! If only there was a way to stop the Verifier. But how can someone prove something without revealing anything more about it?

Zero Knowledge (Being Jon Snow is fun!)

Zero Knowledge (ZK) property states that the Verifier shouldn’t gain any knowledge from the interaction. Sounds simple enough. But its a tricky business. To understand it first we need to define what Knowledge means.

Information is any data you receive. Knowledge is more subtle then that. We define knowledge as useful information that the receiving party can’t compute easily on its own. Here are some examples:

• The number “83741873403740170” (useless without a context — hence not knowledge)
• Multiplying 2*3 (can be easily computed on own — hence not knowledge)
• Factorization of two large primes of an RSA cryptosystem (useful and can’t be computed on own — hence can be considered knowledge)
• Good quality password (useful and can’t be computed easily on own — hence knowledge)

If you can find the time, do read the original 1985 paper by Shafi Goldwasser, Silvio Micali, and Charles Rackoff: “The Knowledge Complexity of Interactive Proof-Systems” (PDF). It is — for the lack of a better phrase — pretty dope.

Now that the intro to our intro (yeah, i know!) is taken care of, we finally arrive at Zero-Knowledge Proofs.

ZKPs are interactive proofs that reveal nothing other than validity of the assertion being proven. And boy, are ZKPs important! The Blockchain revolution has lead to their mass adoption given their usefulness in a trust-less system.

Let’s understand ZKP through a proper example: The graph coloring problem (lets call it 3-C for short): Given a planar Graph G, is it possible to color its vertices using just 3 colors such that no two vertices sharing the same edge have the same color?

Fig.3: Example of a 3-coloring problem

Some of you from a computer-science background might be thinking ,”Hey, I’ve heard of this?! Whats this NP-complete problem got to do with ZKPs?”. As it turns out — a lot! Given 3-C is a known NP-complete problem, representing input size with k where k is the size of the input (here number of vertices), it is not possible (so far) to find a solution for it in deterministic polynomial time (in input size k). At the same time, though, what can be done is, assuming the solution is already known by some powerful entity, a verifier can verify it deterministically very efficiently, i.e., in polynomial time in k. (For more details or a quick refresh, on NP-complete problems, please refer to this Wikipedia link)

This is all fine and dandy, except when the pesky Prover doesn’t want the Verifier to know her coloring of the graph. This is knowledge (useful and can’t be efficiently calculated by the Verifier) and to ensure that it remains hidden, The Prover will need to utilize the property of Zero Knowledge.

The new protocol is as follows:

1. The Prover selects a random permutation of 3 colors (lets say RGB) and colors the vertices
2. She now locks the vertices in individual boxes and sends them to the Verifier
3. The Verifier picks an edge randomly and demands the keys pertaining to the vertices for that edge. The Prover sends the corresponding keys.
4. Verifier unlocks the boxes and verifies that the vertices are of different colors.
5. If not, then Verifier rejects immediately and the protocol aborts (soundness).
6. If step 4 is correct, then Prover and Verifier start another round from step 1
7. After several rounds, if all the instances are accepted, the Verifier accepts with a high probability (correctness)

Note how the only thing the Verifier learns in each round is whether any two adjacent vertices selected by him are of different colors. Since anyone (including he himself) can color the chosen vertices with two different colors, the verifier has gained zero knowledge from the interaction. Hence, a Zero-Knowledge Proof.

Hope you have understood how ZKP came about. Now we will formalize the various parts of the protocol. This might be slightly theoretical but should be easier to follow now that you understand the intuition.

My favorite Simulator game (only if I knew how to play Kerbel Space Program :,( )

Let P, V and S be Turing machines. An interactive proof system with (P,V) for a language

is zero-knowledge if for every (honest) probabilistic polynomial time (PPT) verifier V there exists a PPT simulator S which when given only the statement to be proved (but no access to the Prover P), can produce a transcript that is indistinguishable from a real interaction between an honest Prover P and the Verifier V.

Why so? Well, the Simulator doesn’t have any knowledge of the actual proof. But it is still able to conduct the interaction with the Verifier without being caught, then its protocol is the same as the one with the actual Prover. This implies that if we can prove that such a Simulator exists, the Verifier can not learn anything new from the real interaction either, since the two interactions (with a knowledgeable Prover and un-knowledgeable Simulator) are indistinguishable from each other. Hence preserving the property of Zero Knowledge.

But how does the Simulator know the secret without knowing it? This is done via a small trick. We give it the power of rewinding. (Yeah, I know, crypto proofs can be hilarious!) Now assuming the Simulator can rewind the protocol, it colors the vertices as good as it can and during the interaction, every time it is caught with same colored vertices, it will rewind the protocol to the first step. The steps where it isn’t caught are left untouched. This way, the Simulator is able to act like a Prover without actually knowing the coloring of the graph. Since the Simulator doesn’t know the coloring, any strategy the Verifier applies to extract the knowledge through this interaction will fail. Since the simulated protocol is zero-knowledge and indistinguishable from the real protocol, it concludes that the Verifier can not learn anything from the real protocol either. Please note that the rewinding property doesn’t affect the core functionality of the ZKP because the simulator is not a real entity but a theoretical methodology to show that no knowledge is leaked during the interactions.

But..where Cryptography?

At this very late point, the smartest ones among you will ask, “Hey Mr Cryptography guy, this is all fancy, but where does Cryptography come in all this??” Well how do you think those boxes were locked and unlocked in our 3-C example (see step 2). Locking digital boxes has been one of the core jobs of cryptography. We call this particular procedure a Commitment scheme.

A commitment scheme has two phases — Commit and Reveal. Lets say a sender wants to commit a single bit b to the receiver.

Commit Phase:

• Sender chooses a random input K
• Sender chooses an injective (one-to-one) function f(.) and a hardcore predicate h(.) for f(.) (hardcore predicate h(.) can be thought of as another one-way function which has a unique relationship with f(.) such that you can easily compute h(K) from K but not just from f(K) ).
• Sender sends f(K) and (h(K) ⨁b) to the Receiver

Reveal Phase:

• Sender sends K to the Receiver
• The Receiver calculates f(K). If it doesn’t match with the value of f(K) obtained during the commit phase, he aborts.
• If it matches, Receiver calculates h(K) and then XOR it to (h(K) ⨁b) to get b.

The final protocol resembles Fig.4 below:

Fig.4: One round of our 3-C ZKP

Since 3C is a NP-complete problem, this also implies that any problem in NP-complete can have a ZKP (PDF).

So is this how this really works in real life? Well…yes and no.

Can this work? Absolutely, as this is a totally legit way of using ZKPs.

Should this be used: Nope.

This is an extremely inefficient way of incorporating ZKPs in regular protocols:

• Convert given problem to the corresponding boolean circuit taking care of all input and outputs
• Convert the boolean circuit to 3-C graph problem
• Generate a multiple-round ZKP for the 3C

Instead we use more efficient methods to make ZKPs more practical. We talk about them in the next post.

Worth mentioning:

Q. Wait, did you sneakily put “honest” in front of Verifier in the definition of ZKP? What about a dishonest Verifier?

It does complicate matters. A way around this problem is to make the Verifier commit his random coins before using them to ensure that his choices are independent of the Prover’s responses

Q. What about Non-Interactive Zero-Knowledge (NIZK) proofs? Doesn’t the N in zkSNARKs stand for non-interactive?

Smart observation. NIZK implies that the choices of the Verifier need to be replaced with suitable randomness (since that’s his main contribution to the validity of the protocol). This is achieved by using a good cryptographic hash function (so good that its a random oracle!). We will discuss this in detail at a later time.

There are so many things to talk about, but that will all be in my next post. Till then, take care and trust the Maths.

Yours Cryptographically