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 , , and in their paper “The Knowledge Complexity of Interactive Proof-Systems”. Shafi Goldwasser Silvio Micali Charles Rackoff 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 and making s . ZCash ecure payment over Bitcoin Blockchain Example In the paper “ ”, the author provides an abstract illustration of how ZKPs work. How to Explain Zero-Knowledge Protocols to Your Children 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 ( rover) and Varun ( erifier) 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. p v 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. : She can return via the path specified even if it requires her to cross the gate, no problem. Priya knows the secret words Priya is able to return via the path specified Case 2. : 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. Priya doesn’t know the secret words 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 Zcash implements a modified version of ZKP called zk-SNARKS, with “zk” referring to and SNARK referring to “ ” https://z.cash/ “zero-knowledge” 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 https://manishearth.github.io/blog/2016/03/05/exploring-zero-knowledge-proofs/ https://en.wikipedia.org/wiki/Zero-knowledge_proof https://bitcoincore.org/en/2016/02/26/zero-knowledge-contingent-payments-announcement/ http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.html https://news.ycombinator.com/item?id=11190830 https://www.reddit.com/r/Bitcoin/comments/47rk85/first_successful_zeroknowledge_contingent_payment/d0f69ml https://people.seas.harvard.edu/~salil/research/complexityZK.pdf https://guyrothblum.files.wordpress.com/2014/11/gnpr07.pdf https://crypto.stackexchange.com/a/14366