A zero-knowledge proof, also known as the ZKP protocol, attempts to establish a fact between parties with a minimum of information exchange. In cryptography, it is intended to limit the transmission of information during authentication activities. ZKP’s originators explicitly studied the movement of information, or knowledge, in computer evidence. The zero-knowledge certificate 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 evidence systems
A more accurate name for zero-knowledge certificate might be knowledge-conscious evidence. The first paper proposing the idea appeared in a few variations in the late 1980s. The paper, which referred to knowledge complexity in relation to proof systems, asked the question: When one party attempts to prove a statement to another, what is the minimum amount of information that must be transmitted?
The conceptual north star to keep in mind is that we try to understand and control the flow of information while supporting effective verification.
Zero-Knowledge Safe vs. asymmetric encryption
The idea of the zero-knowledge proof comes from the 70s and 80s era of exploring new conceptual territory in cryptography. This is the same environment that gave us asymmetric encryption. Some ZKP protocols use prime factorization as one-way (or trapdoor) functions along the lines of the Diffie-Hellman key exchange or the RSA encryption algorithm.
With asymmetric encryption, the main goal is for both parties to arrive at a shared secret. In ZKP, the goal is to make claims without revealing extraneous information. In asymmetric encryption, the parties share a secret number; in ZKP, the prover demonstrates their possession of a secret number without revealing that number.
It is not surprising that ZKP is finding greater use in the blockchain.
ZKP in blockchain and web3
The ability to prove statements or claims without revealing the underlying evidentiary data has an exciting range of uses. First, it is entirely possible to use ZKP in conjunction with existing authentication applications. 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 an entire set of attack vectors off the table.
However, using ZKP for password authentication is a small step; it doesn’t really change the basic model we’re familiar with today. For this authentication mechanism to work, you must still transmit your password to the central servers of the service you interacted 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. If so, we start to see alternatives to existing authentication. If governments and banks were to take on the role of issuing cryptographic keys to authenticate important statements, users could use ZKP protocols to authenticate claims.
As a high-level example, if government agencies issued a key as part of a passport, the ZKP could be used to demonstrate a claim to citizenship without revealing the passport number or the citizen’s name. With a little more hashing, the citizen can use the ZKP to demonstrate specific claims such as age.
This type of functionality aligns strongly with web3 because blockchain users already have cryptographic keys and know how to use them. Moreover, ZKP can allow identity and other data authentication in the context of blockchain’s decentralized identity, either together with or apart from existing web2 applications. Giving users the ability to show zero-knowledge proof of their bank statement or credit score via private keys will enable new types of on-chain financial functionality.
The bottom line is that ZKP attempts to minimize the disadvantages associated with current authentication models: loss of control over user data, user data exposure 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 paper used the example of a Hamiltonian graph, which is a type of graph that visits every node in a connected graph.
A naive approach to establishing that one was knowingly in possession of such a graph would be to transfer the graph itself. But that approach leaks a lot of information beyond the fact that the prover holds the graph. In the words of ZKP’s originators, “it contains[s] more knowledge than the single bit Hamiltonian/non-Hamiltonian.”
We can imagine a scenario where the verifier instead repeatedly asks for information about specific lines and points in the graph and the verifier responds. If the prover gives enough valid answers, it becomes likely that they actually 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 made a room furnished with two buttons. She invites Victor to confirm her claim that the buttons work. The proof is that she can see when some button is pressed. To prove the claim in a “zero knowledge” way, Peggy needs to be in a different room than Victor. She can’t see what he’s doing, but she can see when different buttons are pressed and she can communicate what she sees to Victor. Maybe Peggy can see lights that glow different colors depending on which button is pressed. Figure 1 shows the layout in cartoon form.
IDGFigure 1. Peggy’s zero-knowledge room and buttons.
The first time Victor presses a button, Peggy notifies Victor that a button was activated. At this point, Victor can assume that either Peggy has made a good guess or she really is able to see an effect. Both possibilities are equally true.
To increase the odds against Peggy cheating, the two can continue with more rounds. 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 get an acceptable probability.
This scenario proves to Victor that Peggy knows when a button was pressed and the effect of that button – which is all Victor needs to know. The experiment does not reveal the button’s effects or how Peggy is able to monitor them. It 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 has control over which button to press, but he doesn’t know what effect the button has. 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 the zero-knowledge certificate is one probability proof instead of a deterministic one.
Something else to note about Peggy and Victor’s scenario is that it is what is called a interactive evidence. In this model, the verifier is able to interrogate the prover at will. This is in contrast to non-interactive evidence, where the evidence provider performs the verification process on its own and transfers the evidence without interacting with the verifier. Both styles can be used with ZKP.
Going forward with ZPK
Zero-knowledge proof is an expanding field, which provides 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 about zk-SNARK.
Here are some more tips for further study:
- For a practical use of ZKP in blockchains, take a look at the Mina project.
- ZKP also plays a big role in Ethereum level 2, where optimizing performance is central. For a specific project in space, consider Polygon’s Nightfall project.
- For working code and a library, see the Zilch project.
- For how a regular company works in this area, see Auth0’s work on the MATTR project.
The best place to get a grounding in zero knowledge protocols is still the original ZKP white paper. This gives you access to the actual mental wrangling that goes on when you think about how the factor of computation time can be introduced into proof systems to limit the ability of attackers to falsify proofs in NP time. Everything flows from it. Implementing the code and infrastructure to realize the promise of these ideas is where we are today.
