An Introduction to Zero-Knowledge Proofs – Two men on an Island

Beginner’s Guide / 01.08.2020

Two Men on an Island

Let’s say there are two people, you and me. Both of us are sent on a treasure hunt, on a remote island, miles away from the nearest settlement, with no outside communication. We were each previously handed one part of the means to reach the treasure that lays waiting. I was handed the map to navigate to the treasure and you were given a key to open the chest and lay hands on it. Now, I know that you do not have the map to the treasure hunt, because I have it, and you know that I do not have the key to the door that opens the treasure, because you have it.

two men on an island to explain zero knowledge proof or zero knowledge protocol (zkp)

There are three ways this can turn out:

  • We both mutually agree to share each other’s information and divide the treasure.
  • I trick you into giving me the key and run off with it to lay hands on the treasure alone. Or,
  • You can promise to share the key, but as soon as you get a glimpse of the map, you leave me stranded and go ahead to unlock the treasure and lay claim.

Hence, the difficulty is in the fact that the only way we both reach the treasure is if we mutually come to an agreement and give each other the access to what we have. But if neither of us wants to do that because we do not trust the other’s words, how can one prove the existence of the map or the key? How can I prove to you that I have the map, without letting you peek into it to get the treasure on your own and vice versa?

Believe it or not, with a little bit of math, we can actually solve the problem.

Zero-Knowledge Proofs

zpk explained

Zero-knowledge proofs or zero-knowledge protocols (ZKP) were first introduced in the mid-80s by a group of MIT researchers in their paper, “The Knowledge Complexity Of Interactive Proof Systems”. They essentially defined ZKP as a method by which one party can interact with another party and provide proof of knowledge without unveiling their confidential data.

“In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x. 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.” – Source: Wikipedia

Zero-knowledge proofs are mechanisms that allow one to reveal the validity of a claim, without revealing any knowledge about the claim. In simple words, I must be able to prove to you that I have knowledge about the map, without showing the map itself.

To hold a verifiable zero-knowledge proof, the claim must satisfy three conditions:

  • Complete: If the statement is true, the verifier will be able to verify it without question.
  • Sound: if the statement is false, no attempt by the claimer will be able to convince the verifier.
  • No prior knowledge: by just knowing the verification status of the claim, the verifier should not be able to derive any knowledge out of the claim.

Advantages of ZPKs

  • As the name suggests, ZKPs give out zero information about the contents of the information, other than proving the ownership.
  • Usage of ZKP mechanisms does not hinder the base protocol in any way. ZKP protocols can be included and excluded as per will
  • Most ZKP mechanisms are non-interactive, meaning the end-parties do not have to interact with each other in any way. All the claimant must do is ensure the solution is sufficient enough for the verifier
  • Adding ZKPs onto distributed technologies such as Blockchain or any other DLT increases the security, privacy, and appeal of the base layer protocol. Information propagation is much more secure and inherently peer-to-peer
  • Although it could be debated, in some ways, ZKPs are computationally efficient. In coming to the proof, all information is removed to help the data propagation. But the use of homomorphic encryption sort of negates the efficiency.

Coming back to the Treasure Hunt Scenario

To go ahead and establish trust between each other, you want to ensure I have actual ownership of the correct map. The task is on me to make sure I devise a ZKP without giving out information about the map, for which reason I come up with a small test. I ask you to take me to a random position from our current place so that I can lead us right back to where we started and prove that I have the actual map.

But doing it just once might mean that I could have been lucky, or I could have figured a way to come back without the map. To make sure you are satisfied, we do the test several times, until you know that it is probabilistically not possible for me to have been lucky every single time.

Due to the repetitive iterations of the same test, it has now been established that I have ownership of the map, without giving out any information about the contents of the map. I ask you to devise a test on similar lines until both of us can trust each other of the claim.

It is all About the Probability

To solve the problem of successfully verifying a zero-knowledge proof to a validator in a virtual scenario, cryptographic means must be employed, which use several computational assumptions. Due to the assumptions, it can be perceived that there can never be an absolute solution. Zero-knowledge proofs are probabilistic rather that deterministic. This ideally means that the more times I show you the correct path, the more trust you have that I indeed have the correct map.

Things to keep in mind while choosing a protocol for zero-knowledge proof:

  • The verifier must be receptive to the proof of ownership given
  • The proof must not give out any knowledge other than the authentication of ownership
  • The verifier should not be able to use the same proof to communicate to someone else about actually owning the claim
  • The verifier must be fully justified when looking at the zero-knowledge proof, without feeling the need to look at the claim itself
  • The claimant must neither falsify information nor should they be able to tweak the protocol in their favor
  • The probabilistic solution must be acceptable to the verifier and the claimant must make sure that the probability is virtually impossible to falsify due to the actual ownership of the claim

zkp explained

avatar
Sudarshan M is a long time crypto-enthusiast. Pulled in by bitcoin early on, it did not take long for Sudarshan to divert all of his academic attention from business studies to blockchain by doing his Masters and eventually pursuing his PhD in the subject.