Zero Knowledge Proof protocol allows you to convince me that you know something, or have done something, without revealing to me what your secret was.
Zero Knowledge Proof (ZKP), is a collection of tools that allow an item of information to be validated without the need to expose the data that demonstrates it. This is made feasible by a set of cryptographic algorithms that allow a “tester” to mathematically prove to a “verifier” that a computational assertion is valid without exposing any data.
ZKPs were initially described in a 1985 MIT work titled “The Knowledge Complexity of Interactive Proof-Systems” by Shafi Goldwasser and Silvio Micali. The findings demonstrated that it is feasible for a “prover” to convince a “verifier” that a specific claim about a data point is true without revealing any further information about the data.
ZKPs can either be
1. Interactive — where a prover convinces a specific verifier but needs to repeat this process for each individual verifier
2. Non-interactive — where a prover generates a proof that can be verified by anyone using the same proof.
1. Where is waldo?
I am sure that everyone is familiar with “Find Waldo”. In this game, the goal is to locate the infamous “Waldo” in a large picture.
Task: Prove you know where Waldo is, without sharing his location
Assume Alice and Bob are competing to see who can solve this trivial problem first. Bob hasn’t discovered Waldo yet, However Alice claims she found Waldo. An initial solution would be for Alice to tell Bob, “I spotted Waldo, he’s on the top left of the photo.”
However, by focusing just on the top left of the image, Bob will be able to quickly spot Waldo.
“You ruined the game for me, Alice.”
How can we ensure Bob that Alice found “Waldo” without ruing the game for Bob?
Alice devices two proofs to prove her knowledge of Waldo’s location.
Alice removes Waldo from her picture and just shows Bob a clip of Waldo. Bob can watermark the back of Alice’s scene page to verify that she didn’t merely print off a fresh photo of Waldo.
Alice cuts a hole in a large, opaque piece of cardboard. She lays the cardboard cut-out over the original scene. Only Waldo is shown in this solution. It is still uncertain what his coordinates are in relation to the rest of the scenario. Alice can later recreate the scenario underneath to demonstrate that she used the original problem.
Both solutions fulfil the three important properties of zero-knowledge proof systems: soundness, completeness, and zero-knowledge.
Alice is able to use the same proofs to verify that she has found Waldo many times per game, and across many games. In this sense, her proof systems achieve statistical:
a. Soundness — everything that is provable is true: Assuming Alice is unaware of Waldo’s whereabouts and submits random bits of the scene to her proof system, her cardboard holes will display random pictures without Waldo. Simply said, Alice’s proof methods are honest and do not allow her to cheat.
b. Completeness — everything that is true has a proof: In each round, as long as Alice discovers Waldo, she may consistently utilize her proofs to display Waldo. Alice’s evidence methods persuade Bob that she discovered Waldo.
c. Zero-Knowledge — only the statement being proven is revealed: As Alice demonstrates to Bob that she has discovered Waldo, the only information supplied to Bob is that “Alice has discovered Waldo.” The location of Waldo is never revealed. Simply said, Alice’s proof methods demonstrate her win to Bob without disclosing the location of waldo i.e., her knowledge.
1. Trail Check
Imagine a cave with a single entrance but two trails (A and B) that intersect at a common door locked by a pass. Alice wants to demonstrate to Bob that she knows the passcode to the door without disclosing the information to Bob. To do this, Bob stands outside the cave while Alice ventures inside along one of the two pathways (without Bob knowing which path was taken). Bob then instructs Alice to follow one of the two pathways back to the cave’s entrance (chosen at random).
If Alice took path A to the door and then Bob instructs her to take path B back, the only way to solve the problem is for Alice to know the passcode for the closed door. This method can be performed numerous times to demonstrate Alice has knowledge of the door’s passcode and did not, by stroke of luck, chose the correct path to take at the beginning.
After this procedure is done, Bob has a high level of confidence that Alice knows the passcode to the door without exposing the information to Bob. While this is simply a hypothetical example, ZKPs use cryptography to verify knowledge about a data point without exposing the data point.
Non-interactive Zero-Knowledge Proof does not require an interactive method, which eliminates the risk of collusion, but it may necessitate the use of additional devices and algorithms to establish the sequence of tests.
Let’s assume Alice wants to show Bob that she solved the Sudoku puzzle. Alice does this by creating a tamper-proof machine that delivers the proof to Bob. Alice’s software follows a specific, publicly verifiable protocol with the following logic.
First, Alice reproduces the original, unsolved puzzle in the machine. For each cell with an existing value, it automatically lays three face-up cards with the corresponding number, e.g. cell C2 has 3 number 4 cards.
Next, Alice encodes her solution by having the machine lay her answers face down on the grid. Of course, the machine prevents Bob from simply flipping over the cards in their cells.
Bob can now interact with the machine. Starting with each row, Bob randomly chooses one card in each cell, from the top, the middle, or the bottom. Bob assembles cards for row 1. The machine takes the chosen cards and makes a face down, 9-card-packet for each row.
This action is repeated for each column as well. Finally, the remaining cards are sorted into one packet for each 3×3 grid. In total, the machine makes 27 packets.
Machine randomizes and shuffles the cards in each packet, before giving the packets back to Bob.
Bob flips the cards over and verifies that each packet contains the numbers 1 through 9 without any numbers missing or duplicated.
A few verification rounds later, Bob is convinced that Alice has solved this puzzle. In this example, the proof is non-interactive. Anyone can use the machine to verify the claim. Alice doesn’t have to be present to be challenged.
Alice and Bob, post pandemic move back to New York and start hunting for an apartment, they come across Jill’s apartment who is looking for tenants. Both Alice and Bob loved the apartment and tell Jill that they are interested.
Jill asks them to fill out the PDF and email your bank statements and income verification and both of your Social Security Numbers so that Jill can run a credit check.
In today’s data driven world, sharing any type of personal data can have hazardous consequences, if the data is not stored or maintained properly.
Using Zero Knowledge Proof, Alice and Bob can showcase Jill that they are eligible to rent the apartment and the credit score and monthly salary is high enough to qualify them for the selection process without actually disclosing exact specifics of their income and personal details. One can create a mathematical model to solve for this using an iteration of the classic Yao’s Millionaires Problem.
But armed with our new understanding, we can explore how ZKPs might actually apply to areas where they’re desperately needed, like crypto, finance, and the cloud.
Until now, Bitcoin has enjoyed widespread acceptance. Decentralized money is particularly appealing to today’s age since it allows people to transfer wealth without the involvement of banks.
The first-generation cryptocurrency pioneered the decentralized economy. However, it did not address the question of privacy. This is where Zcash enters the picture. Zcash, unlike Bitcoin, does not use an open ledger. Your transactions will be totally concealed from other individuals using the blockchain if you utilize Zcash.
To ensure anonymity, Zcash uses zk-SNARK, a cryptographic proof that allows one party to prove it possesses certain information without revealing the information
The ING is a Netherlands based bank who has started their new zero knowledge blockchain. They launched a modified version of zero knowledge system is called zero knowledge range proof.
The buyer will be able to prove that they have the salary to get a mortgage without revealing the salary.
Using these ZKPs, cloud infrastructure, for example, might become far more secure (no cryptocurrency required). Users could leverage cloud computing without ever disclosing sensitive consumer data to cloud providers. When it comes to data security, this is especially critical for financial services, government, and other similarly risk-averse organisations. These industries have been notoriously slow to adopt hosted cloud infrastructure, much to the chagrin of forward-thinking CTOs, cost-conscious CFOs, and end-users desiring a more contemporary experience. If zero-knowledge enables these businesses to begin using cloud providers without entrusting those providers with critical data, then a revolution is on the horizon.
Zero knowledge proof can aid in the secure transmission of sensitive information such as authentication information. In this case, ZKP can keep a secure channel open for the user to utilize his or her authentication information without disclosing it. As a result, companies would be able to effectively avoid data leaks.
There are other use cases as well such as Storage Protection, File System Control, messaging, etc.
Zero-knowledge proofs are highly encouraging and exciting. Accessing an internet account without a password. Performing a bitcoin transaction without disclosing your balance. Verifying Covid-19 status without providing details about vaccinations, past illnesses, or test dates. Verifying your household income for a loan without divulging your earnings. The notion of allowing verification of a statement without revealing the actual information is central to zero-knowledge proof.
ZKP has the ability to preserve privacy in a variety of situations. Businesses and society may progress to “open data 2.0” by applying ZKP, where daily transactions in today’s digital economy are done without releasing superfluous sensitive information.
Although, There are difficult technological, economic, and social challenges to overcome, and let’s be real, nothing fuels hype like zero knowledge.