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 that the only way we both reach the treasure is if we mutually come to an agreement and give each other 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 map’s existence 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 prove to you that I know 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 convince the verifier.
  • No prior knowledge: by just knowing the claim’s verification status, the verifier should not derive any knowledge from the claim.

Advantages of ZPKs

  • As the name suggests, ZKPs give out zero information about the information contents, other than proving the ownership.
  • The 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 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 to 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 impossible for me to have been lucky every time.

Due to the repetitive iterations of the same test, I have now established that I have ownership of the map without giving out any information about the map’s contents. I ask you to devise a test on similar lines until we can trust each other’s claims.

It is all About the Probability

To solve successfully verifying a zero-knowledge proof to a validator in a virtual scenario, cryptographic means must be employed, using 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 than 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 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. The claimant must ensure that the probability is virtually impossible to falsify due to the claim’s actual ownership.

zkp explained

Disclaimer: It must be noted that the concept of proof in ZKP is different from traditional mathematical concepts. Mathematical proofs are strict, using either self-evident statements or statements obtained from proofs established beforehand. ZK proofs are more similar to humans’ dynamic process to establish a statement’s truth throughout the exchange of information. One must remember that ZKPs are not exact but rather probabilistic.

Classification of ZKPs

ZKPs, with their apparent need in the virtual world, are immensely useful in everyday application. When examined closely, we can think of dozens of places where ZKPs can be helpful. To understand how a practical form of Zero-Knowledge Proof can be used, we must first understand how the message is communicated, i.e., Interactive or Non-Interactive. The use of a particular iteration of ZKP depends on the number of participants involved in that particular circle.

Interactive ZKP

Being one of the most used forms of ZKP, interactive ZKPs are exactly what the name says. The parties involved in proof have to interact with each other. At periodic intervals, the participants have to communicate that they are satisfied with the proof received and can move ahead. Most interactive ZKP involves a small number of parties, as it is not feasible to constantly ask for affirmation from a large group of Participants. The example we used about two men on an Island falls under this category. To make sure I communicate the proof to You, I used an interactive method of probabilistically ensuring the ownership, taking trips around the island, and reaching the start point.

To quote the definition, “An interactive proof protocol is complete if, given an honest prover and an honest verifier, the protocol succeeds with overwhelming probability (i.e., the verifier accepts the prover’s claim). Of course, the definition of overwhelming depends on the application, but generally implies that the probability of failure is not of practical significance.”

Non-Interactive ZKP

Interaction among a small group of participants could be carried out without any hindrances. But when it comes to a large audience, let’s say shareholders of a company, the Zcash network users, etc. a simpler approach is required. A Non-Interactive ZKP is a special kind of proof that does not involve constant verification from all participants. In a non-interactive ZKP, it is advisable to have one-way communication; wherein one proclaims the ownership of the information without requiring any validation from the rest of the participants.

Possible Use-Cases for ZKPs

  • A Blockchain where privacy is of utmost value can use ZKPs to ensure the trestles flow of value without propagating any information other than the owner of the said value. Zcash and its predecessor, Zcoin, use zk-SNARKS to ensure the safety of privacy and the transmission of information and value. We will be talking about them in detail later on.
  • Peer to Peer communication is when two parties communicate with each other without any intermediary in between. Two participants might communicate P2P for several reasons; to stay away from prying eyes, to exchange sensitive information, to transfer value without much attention, and so on. ZKPs, in this scenario, can push boundaries by providing means for the participants to have a truly private mechanism to communicate and transact.
  • Voting is also an essential part of every democracy, from that of a country down to its shareholder participation. Hence, with nations moving towards digitization and with the proliferation of security tokens, the demand for secure and anonymous voting solutions is bound to increase. ZKPs are bound to make an appearance here sometime in the future.
  • Any area where data-integrity, data-verification, and data-privacy is of utmost importance can do well by inculcating ZKP. For instance, members of a particular platform can submit their private documents for KYC without revealing the documents. This increases privacy and, at the same time, saves data storage costs for the platform.

Innovations in Zero-Knowledge Proofs

ZKP, when looked at closely, is a deeply technical concept. The concept relies heavily on probability, and removing the mathematical part in exchange for a toned-down example was a huge task for us.

But now that we have come so far let us take the effort to gain deeper knowledge in Zero-Knowledge Proofs. Let us look at some of the highly technical innovations that have been seen in ZKPs and how they are used every day.

zk-SNARKs

Zero-Knowledge Succinct Non-Interactive Argument of Knowledge or zk-SNARKs is one of the most used jargons within any crypto-developer community. As the abbreviation suggests, SNARKs are probabilistic means of assessing and arguing about particular information’s validity. In simple words, zk-SNARKs present Proof-of-Knowledge in the form of a secret key that could only be generated if the person claiming ownership has the information in the first place. ZK-SNARSs ensure that the key has been generated only by the owner and no one else.

One of the simplest forms of zk-SNARK is the verification of a hash. Hash is a mathematical concept used to verify the information. If a person has to prove they have a certain number, they can “hash” that number using any hashing algorithms. Since that hash represents a particular set of information, it can be verified that the hash belongs to the pre-determined number when the number comes out.

Even though it wasn’t the first to use an iteration of zk-SNARKs, the cryptocurrency Zcash was responsible for popularizing the use. Ethereum followed up in 2017 when they forked the chain to allow using zk-SNARKs when creating smart contracts.

zk-STARKS

“zk-STARKs were created by Eli-Ben Sasson, a professor at the Technion-Israel Institute of Technology. As an alternative version of zk-SNARK proofs, zk-STARKs are, generally, considered the more efficient variant of the technology – potentially faster and cheaper, depending on the implementation. They are considered better because zk-STARKs do not require an initial trusted setup (hence, the “T” for transparent). – Binance Academy

zk-STARKs was created to fill the gaps of zk-SNARKs. It is quite tough to communicate how zk-STARKs improve zk-SNARKs without getting a bit technical, but I will try my best to tone it down.

zk-SNARKs are non-interactive proofs that give ownership information to a large group without interacting with the proof. To do this, the private keys of the proof have to be created and attached to the string of the proof to ensure it is true and fair. The private key is the only part of the SNARK proof that stays behind the public’s eyes. Even though zk-SNARKs are proven to be quite effective, a vested party with enough resources can manipulate the loophole by creating similar proofs, hiding the private key.

zk-STARKs fixes the loophole by using randomness instead of private keys to generate the proof. By this mechanism, all information regarding the proof is public, and thus, the resilience against the proof is increased. Another advantage is that zk-STARKs are known to be Quantum resistant. As there is no cryptographic asymmetry due to public/private keys, Quantum computers cannot be used to crack the protocol.

Although the proof is undergoing constant updates, zk-STARKs have a prospective future ahead.

“Right now, no public blockchain has integrated zk-STARKs. Though, it is likely that they will find themselves in Zcash or Monero over the coming years and possibly Ethereum, also.”Coincentral.

Bullet Proofs

One of the latest additions to the privacy based cryptographic protocols, Bulletproofs were proposed by Stanford’s Applied Cryptography Group (ACG) in December 2017 in an academic paper. Bulletproofs is “a new zero-knowledge argument of the knowledge system, to prove that a secret committed value lies in a given interval.” The bulletproof name is credited to Shashank Agrawal for describing them as “short like a bullet, with bulletproof security assumptions.”

The proofs of bulletproofs are much shorter than other range proofs. Bulletproofs also does not require a trusted setup. They are especially suited for the distributed and trustless nature of blockchains. They can create substantial long-term cost savings, enormous space savings, lower fees, and faster verification times than current-proof implementations. Monero states that they have reached an 80% reduction in transaction size utilizing bulletproofs, leading to an 80% reduction in fees.

Zk-SNARKS, zk-STARKs, and Bullet Proofs appeal to the growing concern regarding privacy. Within the cryptocurrency world, these protocols have great potential and maybe a groundbreaking avenue towards mainstream adoption.

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.