Zero Knowledge Proof

This is a short introduction to zero knowledge proofs (ZKP), along with some motivating examples. The aim of this post is to generate curiosity among the readers for this upcoming new area of research. After giving the readers an intution of what zero knowledge proofs are, In the next posts I would then get into some technical deep dives to show how ZKP is used in the wild.

Introduction

Zero knowledge proofs are a way in which a prover P can convince the verifier V about some claim C without giving out any extra details besides the claim.

The above statement was intentionally kept a bit vague to highten your curiosity.

As per Wikipedia: > The essence of zero-knowledge proofs is that it is trivial to prove that one possesses knowledge of certain information by simply revealing it; the challenge is to prove such possession without revealing the information itself or any additional information.

To bring some clarity: all ZKP starts with a claim that a prover wants to prove to a verifier. However, the challenge here is that the prover does not want to reveal any extra information about the claim except for the claim itself. This will get clearer with the following examples.

But first, you should know that there are two different types of ZKP: * Non-Interactive ZKP * Interactive ZKP

I will give you an example of each to make the distinction very clear.

Examples

Non-Interactive ZKP

Let’s look at an example of Non-Interactive ZKP. This will give you give an idea of what Zero Knowledge means in the context of proving a claim.

Peggy makes a claim to Victor that she knows Charlie’s ATM pin. Here Peggy is the prover and Victor is the verifier.

The simplest way for Peggy to prove her claim without revealing Victor the pin would be to withdraw some pre specified amount of cash from Charlie’s account in the presence of Victor. This way Victor can verify the claim without any doubt and in this process Victor did not learn Charlie’s ATM pin.

Now there are couple of other ways to prove her claim and we will go through each one and show why they do not fall under ZKP: - Peggy can tell Victor the pin and Victor can try out the pin, but this would require Victor getting to know Charlie’s pin. - Peggy can pass on a chit, which contains the pin, to Charlie, without showing it to Victor and Charlie can verify if the pin written on the chit is valid or not. However, since Victor doesn’t know what is written on the chit, he can cast a doubt on the method itself.

Interactive ZKP

Now that you have an idea of what zero knowledge means, let’s look at an example of Inetractive ZKP, this should help you contrast with the Non-Interactive aspect of ZKP in the previous example.

For this example we need a prop. Imagine a large bag of candies. There are a lot of candies. There is unimaginable quantity of candies in the bag.

Now Peggy makes a claim to Victor that she can count the number of candies in the bag within a second.

Simplest way to prove this claim would be for Peggy to tell Victor the actual count of candies in the bag. But there are two issues with this method: - It would no longer be Zero Knowledge proof, since in the process of proving the claim, Victor now knows the total number of candies in the bag. - Even if Victor gets to know the count from Peggy, to actually verify the claim, he would have to sit down and count the candies himself, which would takes him years because he not very good at counting.

The Zero Knowledge way of proving the claim would require the following steps: - Victor removes some candies from the bag, without telling Peggy how many he is removing. - Victor then asks Peggy to recount the candies in the bag and tell him the difference between the original number and the current number in the bag. - Even if Peggy tells the right number, there is a chance that Peggy got lucky. To reduce the luck factor, Victor can repeat these steps sufficient number of times to convince him that Peggy’s claim is indeed true.

By using this method, Victor would never get to know the actual number of candies in the bag, no matter how many times he repeates the experiment, but eventually he would get convinced that Peggy’s claim is indeed true.

You might argue that Victor can remove all the candies from the bag and ask Peggy for the difference. This way Peggy will have to reveal the total number of candies that was in the bag. But, this means that Victor is no longer verfying Peggy’s claim and is simply trying to find out the count by believing in Peggy’s ability of counting candies.

Conclusion

By now you should have a decent idea of the following concepts: - What is a claim - What is Zero Knowledge Proof - How Non-Interactive proof differs from Interactive proof

In the next post I would like to summarize the zCash’s implementation of Zero Knowledge Proofs.

Stay tuned..

Abhijit Sinha avatar
About Abhijit Sinha, "Abhijit"
Member of blockchain team at Imaginea