Introduction to Zero-Knowledge Proofs 🔏

Saurav
Saurav
Jan 3, 2019 · 5 min read
Image Credits Alex Martinez

A zero-knowledge proof (ZKP) is a cryptographic method which allows one person (the prover) to prove to another person (the verifier) that they have the possession of some information without revealing the information to the verifier.

In other words, ZKP allows conveying the assurance that the information is in hand without revealing the information itself.

Origins

The New York Times, February 17th, 1987 © The New York Times

Here’s a newspaper clipping of The New York Time’s issue from 1980’s which covers these proofs. Zero-Knowledge proofs have sprung back into relevance recently due to their use in cryptocurrency ZCash and making secure payment over Bitcoin Blockchain.

Example

Consider a cave similar to Alibaba cave, containing a magic door which requires a secret word to open it. The cave has two entrances A and B, both leading to the magic door.

© WikiCommons

Consider two persons, Priya (prover) and Varun (verifier) with the situation that Priya knows the secret words to open the magic door and Varun does not. Varun is curious to find out whether Priya really knows the secret words or not.

Hence, a scheme is devised which allows Priya to prove that she knows the secret words without actually revealing them to Varun.

Varun waits outside the cave as Priya goes into the cave. Priya takes either path A or B. Varun is not allowed to see which path she takes. Then, Varun enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen at random.

Varun chooses the exit path for Priya to return

Now two cases arise,

Case 1. Priya knows the secret words: She can return via the path specified even if it requires her to cross the gate, no problem.

Priya is able to return via the path specified

Case 2. Priya doesn’t know the secret words: In this case, she can only return via the path she came in, if this is the path Varun chose earlier, then it is good, if not she is caught lying. So there is a 50% chance that she still can successfully claim that she knows the secret words, even though she doesn’t due to sheer luck.

50% is not good enough, so Priya and Varun repeat this exercise. With each iteration the chances of Priya not knowing the secret words and being able to claim that she does, decreases. After 20 iterations they become very low (one in a million)

At this point, Priya has successfully proved to Varun that she really does possess the knowledge of secret words.

Definition

Completeness

Soundness

Zero-Knowledge

Applications

Private Blockchains

Private Purchases

Authentication Systems

Secure Bitcoin Transactions

Proof of Knowledge

This article was originally published on Chaintope BlogChain.

Coinmonks

Coinmonks is a non-profit Crypto educational publication.