A zero-knowledge proof, also known as the ZKP protocol, attempts to establish a fact between the parties with minimal exchange of information. In cryptography, it is intended to limit the transfer of information during authentication activities. The creators of ZKP explicitly studied the movement of information, or knowledge, in computational evidence. The zero-knowledge proof was a significant step forward in introducing a new field of study at the time. Its implications are being explored again today in the context of web3 and blockchains.
Knowledge complexity in proof systems
A more accurate name for zero-knowledge proofs might be conscious evidence of knowledge. The first paper to propose the idea appeared in a few variations in the late 1980s. The paper, which referred to the complexity of knowledge versus proof systems, posed the following question: When a party attempts to prove one assertion to another, what is the minimum information that must be transmitted?
The conceptual North Star to keep in mind is that we are trying to understand and control the flow of information while supporting effective verification.
Zero-Knowledge Proof vs Asymmetric Encryption
The idea of zero-knowledge proof comes from the 70s and 80s era of exploring new conceptual territory in cryptography. It’s the same medium that brought us asymmetric encryption. Some ZKP protocols use prime factorization as one-way (or trap) functions modeled on the Diffie-Hellman key exchange or RSA encryption algorithm.
With asymmetric encryption, the primary goal is for both parties to come to a shared secret. In ZKP, the goal is to make statements without revealing superfluous information. In asymmetric encryption, the parties share a secret number; in ZKP, the prover demonstrates its possession of a secret number without disclosing this number.
It’s no surprise that ZKP is finding greater use in blockchain.
ZKP in blockchain and web3
The ability to prove statements or assertions without disclosing the underlying evidence data has a range of exciting uses. For one thing, it’s entirely possible to use ZKP in conjunction with existing authentication apps. If you can demonstrate that you are in possession of your password without revealing the actual plain text of the password, you have just swept a whole set of attack vectors off the table.
Using ZKP for password authentication is a small step forward, however; it doesn’t really change the fundamental pattern we know today. For this authentication mechanism to work, you would still need to transmit your password to the central servers of the service you are interacting with and store it there. For a more revolutionary approach, consider what would happen if we integrated ZKP into the design of application security systems. In this case, we are starting to see alternatives to existing authentication. If governments and banks were to take on the role of issuing cryptographic keys to authenticate material claims, users could use ZKP protocols to authenticate claims.
As a high-level example, if government agencies issued a key as part of a passport, then the ZKP could be used to demonstrate an application for citizenship without revealing the passport number or the citizen’s name. With a little more hashing, the citizen could use ZKP to demonstrate specific claims like age.
This kind of functionality dovetails powerfully with web3 because blockchain users already hold cryptographic keys and know how to use them. Additionally, ZKP could enable authentication of identity and other data in the context of decentralized blockchain identity, either together or independently of existing web2 applications. Empowering users to show zero-knowledge proof of their bank statement or credit score via private keys would enable new types of on-chain financial functionality.
The bottom line is that ZKP seeks to minimize the drawbacks associated with current authentication models: loss of control of user data, exposure of user data to hacking, and non-consensual monetization of user data.
How ZKP Works
In a zero-knowledge proof system, one party (the prover) demonstrates to another (the verifier) that the prover is in possession of information, ideally without revealing anything other than that fact. The authors of the original ZKP article used the example of a Hamiltonian graph, which is a type of graph that visits every node of a connected graph.
A naïve approach to establishing that a demonstrator was in possession of such a graph would be to hand over the graph itself. But this approach misses a lot of information beyond the fact that the demonstrator owns the graph. In the words of the creators of ZKP, it “contains[s] more knowledge than the Hamiltonian/non-Hamiltonian bit.
We can imagine a scenario where the verifier instead repeatedly requests information about specific lines and points on the graph and the prover responds. If the demonstrator provides enough valid answers, it becomes likely that they do, in fact, hold the Hamiltonian graph. The graph itself is never transmitted.
A ZKP thought experiment
In public key encryption, the actors are traditionally called Alice, Bob, and Eve. In ZKP, the prover is called Peggy and the verifier is called Victor.
Let’s say Peggy has created a room furnished with two buttons. She invites Victor to confirm her claim that the buttons work. The proof is that she can tell when either button is pressed. To prove the claim in a “zero-knowledge” way, Peggy must be in a different room from Victor. She can’t see what he’s doing, but she can tell when different buttons are pressed, and she can communicate what she sees to Victor. Maybe Peggy can see lights that light up different colors depending on which button is pressed. Figure 1 shows the layout in comic book form.
The first time Victor presses a button, Peggy notifies Victor that a button has been pressed. At this point, Victor can assume that Peggy made a good guess or that she really is able to see an effect. Either possibility is equally true.
To increase the chances that Peggy doesn’t cheat, the two can take multiple turns. Victor can either press the same button or a different button each time. If she guesses, Peggy’s deception will be revealed quickly. The probability of guessing correctly decreases with each round. The process can be repeated for as many rounds as they wish to achieve an acceptable probability.
This scenario proves to Victor that Peggy knows when a button has been pressed and the effect of that button is all Victor needs to know. The experiment does not reveal the pimple’s effects or how Peggy is able to monitor them. This demonstrates to Victor that the buttons have different effects, but he doesn’t need to know what they are.
Evidence and Probability
The key here is that Victor controls which button to press, but he doesn’t know the effect of the button. He depends on Peggy to complete the feedback loop. At the same time, he retains the ability to tell with a high degree of probability whether Peggy is legitimately able to see which button was pressed. This is why we say that the zero-knowledge proof is a probabilistic proof rather than determinist a.
Another thing to note about the Peggy and Victor storyline is that it’s called a interactive proof. In this model, the verifier is able to interrogate the demonstrator at will. It opposes non-interactive proofs, where the prover conducts the verification process alone and transmits the proof without interacting with the verifier. Either style can be applied using ZKP.
Go further with ZPK
Zero-knowledge proof is a growing field, making it an exciting and uncertain area to explore. The most common generic protocol is zk-SNARK, or Zero Knowledge Succinct Non-Interactive Argument of Knowledge. Check out the z-Cash project to learn more about zk-SNARK.
Here are some additional tips for further study:
- For a practical application of ZKP in blockchains, take a look at the Mina project.
- ZKP also plays an important role in Ethereum level 2, where performance optimization is central. For a specific project in space, consider Polygon’s Project Nightfall.
- For working code and a library, see the Zilch project.
- For how a mainstream company is working in this space, see Auth0’s work with the MATTR project.
The best place to learn about zero-knowledge proof protocols is still the original ZKP whitepaper. This gives you access to the actual mental wrangling going on to design how the computational time factor can be introduced into proof systems to limit the ability of attackers to spoof NP-time proofs. Everything stems from that. Implementing the code and infrastructure to realize the promise of those ideas is where we are today.
Copyright © 2022 IDG Communications, Inc.