Unless you live off the grid, you use apps that capture, and likely resell, your personal data (like your contact information, interests and preferences). Even if you don’t use apps, your network provider and your phone operating system collect your data. Companies benefit from this data in two ways: by using it to optimize their services to better appeal to you, and to re-sell it to other companies.
How can we put people back in control of their data? The issue is that some services genuinely require your data to serve you. For example, it would be difficult to get health insurance without sharing health information with your insurer, or to get a loan without disclosing your credit score.
What if there was a way to show that you were in the healthy range on all metrics without sharing your actual health information, or to prove that your credit score was good enough, without disclosing the actual credit score?
Zero-Knowledge Proofs (ZKPs) allow data to be verified without revealing that data. They therefore have the potential to revolutionize the way data is collected, used and transacted with.
Each transaction has a ‘verifier’ and a ‘prover’. In a transaction using ZKPs, the prover attempts to prove something to the verifier without telling the verifier anything else about that thing.
By providing the final output, the prover proves that they are able to compute something without revealing the input or the computational process. Meanwhile, the verifier only learns about the output.
A true ZKP needs to prove 3 criteria:
1. Completeness: it should convince the verifier that the prover knows what they say they know
2. Soundness: if the information is false, it cannot convince the verifier that the prover’s information is true
3. Zero-knowledge-ness: it should reveal nothing else to the verifier
Example: Where’s Waldo
In a talk given last year Elad Verbin explained zero-knowledge proofs very well with an example using “Where’s Waldo”.
In the “Where’s Waldo” kids’ books, the reader is asked to find Waldo (wearing glasses, red-and-white sweater, blue jeans and a beanie cap) in an illustrated crowd of people doing various things.
Assume that I (the writer) am the prover and you (the reader) are the verifier. I claim to have an algorithm that can find Waldo easily, but I’ll only let you use in exchange for a fee. You want the algorithm, but don’t want to pay before I can prove that it works.
So, like many transactions, we want to collaborate, but we don’t fully trust each other.
To prove that I have a working algorithm, I put an illustration on the floor showing a large crowd of people. After asking you to cover your eyes, I cover the illustration with a large, flat piece of black cardboard (which covers far more area than the illustration itself) with a tiny cutout in it. The tiny cutout allows us to see Waldo, but where he is located in the image or where the puzzle begins and ends. Then, I ask you to close your eyes again, and I take the board off the Where’s Waldo puzzle.
I have proven that I can find Waldo in the puzzle quickly, without telling you where Waldo is in that image, how I found him so fast or anything else about that illustration. The more times we repeat this exercise, the more probable it is that I have an effective, fast algorithm.
Interactive and Non-Interactive ZKPs
There are two types of ZKPs: interactive and non-interactive.
Interactive: The Where’s Waldo example above is an interactive proof since I, the prover, performed a series of actions to convince you, the verifier, of a certain fact. The problem with interactive proofs is their limited transferability: to prove my ability to find Waldo to someone else, or to the verifier several times, I will have to repeat the entire process.
Non-interactive: In a non-interactive proof, I can deliver a proof that anyone can verify for themselves. This relies on the verifier picking a random challenge for the prover to solve. Cryptographers Fiat and Shamir found that an interactive protocol can be converted into a non-interactive one using a hash function to pick the challenge (without any interaction with the verifier). Repeated interaction between the prover and verifier becomes unnecessary, since the proof exists in a single message sent from prover to verifier.
Zero-Knowledge Succinct Non-interactive ARguments of Knowledge (Zk-SNARKs, a type of non-interactive ZKP) are Zero-Knowledge because they don’t reveal any knowledge to the verifier, succinct because the proof can be verified quickly, non interactive because repeated interaction is not required between prover and verifier and arguments of knowledge because they present sound proof
Use Cases of ZKPs
ZKPs can be used to preserve data privacy in areas such as health care, communications, finance and civic tech.
An interesting use case in finance is a proposal from ING to prove that a number is within a specific range without revealing that number. So, an applicant for a loan could prove that their salary is within a certain range to qualify for a loan, without giving away the exact amount of their salary.
The most prominent use of ZKPs thus far is Z-Cash, a cryptocurrency that allows for private transactions.
The AdEx Network allows for decentralized, ZKP advertisement auctions in which a user can bid for the price of placing an ad without revealing what that price is to other users.
Zero-Knowledge Proofs have immense potential to put people back in control of their data, by allowing others to verify certain attributes of that data without revealing the data itself. This will have enormous impact in finance, health care and other industries, by enabling transactions while safeguarding data privacy.