A Primer on Zero-Knowledge Proofs 🔏

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

Zero-knowledge proofs were first conceived in 1985 by Shafi Goldwasser, Silvio Micali, and Charles Rackoff in their paper “The Knowledge Complexity of Interactive Proof-Systems”.

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

In the paper “How to Explain Zero-Knowledge Protocols to Your Children”, the author provides an abstract illustration of how ZKPs work.

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 falsely claim that she knows the secret words, 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 (prover) has successfully proved to Varun(verifier) that she really does possess the knowledge of secret words.

Properties

A ZKP must satisfy the following properties:

Completeness

If the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.

Soundness

If the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability. Linking back to our example, even after 20 iterations there is still a one in a million chance that Priya (prover) has fooled Varun (honest verifier)

Zero-Knowledge

If the statement is true, no verifier learns anything other than the fact that the statement is true. In our example, Varun does not get the knowledge of the secret words to open the magic door in the verification process.

Classifications

Interactive ZKPs

This is the normal kind of ZKP which requires that prover and verifier interact with each other during the verification process. The prover issues a bunch of commitments which are then verified by the verifier by issuing respective challenges to those commitments. Our example of Priya and Varun falls into this category.

Non-Interactive ZKPs

A non-interactive proof is a special kind of proof which requires no interacting between the prover and verifier. A common reference string is shared between the prover and the verifier and is enough to achieve computational zero-knowledge without requiring interaction.

Applications

Private Blockchains

ZKPs can be used to guarantee that transactions are valid despite the fact that information about the sender, the recipient, and other transaction details remain hidden. Example https://z.cash/ Zcash implements a modified version of ZKP called zk-SNARKS, with “zk” referring to “zero-knowledge” and SNARK referring to “Succinct Non-interactive ARgument of Knowledge”

Private Purchases

Imagine going to the supermarket and purchasing goods with your credit card without revealing your card information to the merchant. A smart card using zero-knowledge proof could identify the cardholder to a merchant without giving the merchant the knowledge, i.e the card number, that would let him make illicit purchases or forge a new card.

Authentication Systems

ZKPs can be used to make passwordless logins a reality using Zero-Knowledge password proof.

Secure Bitcoin Transactions

Bitcoin has a way for you to send money to someone contingent on them producing the preimage of a SHA256 hash, with the condition that should they fail to produce the preimage, you get your money back. ZKPs can be used to enforce that the preimage of the hash is a key which unlocks some data you want, this becomes a powerful tool for building exotic protocols or performing risky transactions. Bitcoin core developer Gregory Maxwell demonstrated this by making the first successful Zero-Knowledge Contingent Payment.

Proof of Knowledge

Other applications include situations like proving that you have the solution to a sudoku puzzle without revealing the solutions. This can be extended to Treasure Hunt Games, Sealed Bid Auctions etc (to any problem as long as it is of class NP)

References

1. https://manishearth.github.io/blog/2016/03/05/exploring-zero-knowledge-proofs/
2. https://en.wikipedia.org/wiki/Zero-knowledge_proof
3. https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/
4. http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.html
5. https://news.ycombinator.com/item?id=11190830
6. https://www.reddit.com/r/Bitcoin/comments/47rk85/first_successful_zeroknowledge_contingent_payment/d0f69ml
7. https://people.seas.harvard.edu/~salil/research/complexityZK.pdf
8. https://guyrothblum.files.wordpress.com/2014/11/gnpr07.pdf
9. https://crypto.stackexchange.com/a/14366