Two Men on an Island

Say there are two people, you and me. Both of us are sent on a treasure hunt in a remote island miles away from the nearest settlement, with no outside communication. We were each previous 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 to the treasure because you have it.

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 don’t trust the other’s words, how can one prove the existence of the map or the key? How can I prove it to you I have the map, without letting you peek into it to get the treasure on your own and vice verse?

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

To explain how the problem can be solved, the different ways by which it can be solved, and the application it has in the real and virtual world, we will be splitting the article into three parts so that it can be perceived easily.

Zero-Knowledge Proofs

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.”

Wikipedia

Zero-knowledge proofs are mechanisms that allow one to reveal the validity of a claim, without actually revealing any knowledge about the claim. In simple words, I must be able to prove it 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

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’ve been lucky or I coulee 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 device a test on similar lines until both of us are able to trust each other of the claim.

Its all About the Probability

To solve the problem of successfully verifying a zero-knowledge proof to a validator in a virtual scenario, cryptographic means have to 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 considered to be probabilistic rather that deterministic.

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

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 has to be 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.

In the articles that follow, we will be diving deeper into the application of Zero-knowledge proofs, (both physical and virtual), discussing the capabilities of some of the variants by which they are calculated, looking at real-world use cases and debating their use against other privacy mechanisms. Let us know what you would like us to include along with the other topics for discussion.

Do have a look at our articles from the previous month: ReverseAcid Monthly Recap - March 2019 (Volume 4)

ReverseAcid Monthly Recap

Crypto Analysis Series

About Reverse Acid

Be a part of our Discord community to engage in related topic conversation.

Follow our Instagram and Twitter page for timely market updates

Two Men on an Island - An Introduction to Zero-Knowledge Proofs and What Follows (Part - 1)