A zero-knowledge proof, also known as ZKP protocol, attempts to establish a fact between parties with a minimum amount of information exchange. In cryptography, it is intended to limit the transfer of information during authentication activities. ZKP's originators explicitly studied the movement of information, or knowledge, in computer proofs. The zero-knowledge proof was a significant advancement in introducing a new area 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 knowledge-aware proofs. The first paper to propose 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 of 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 efficient verification.
Zero-knowledge proof vs. asymmetric encryption
The idea of the zero-knowledge proof comes out of the '70s and '80s era of exploring new conceptual territory in cryptography. This is the same milieu that brought us asymmetric encryption. Some ZKP protocols use prime factorization as one-way (or trap door) 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 divulging that number.
It's not surprising that ZKP is finding greater use in the blockchain.
ZKP in the blockchain and web3
The ability to prove statements or claims without unveiling the underlying proof data has an exciting range of uses. For one thing, it is quite possible to use ZKP in conjunction with existing authentication applications. If you can demonstrate you are in possession of your password without revealing the actual plain text of the password, you've just swept a whole set of attack vectors off the table.
Using ZKP for password authentication is a baby step, though; it doesn't really change the fundamental model we are familiar with today. For this authentication mechanism to work, you would still have to transmit your password to the central servers of the service you were 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 that case, we begin to see alternatives to existing authentication. If governments and banks were to take 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, then ZKP could be used to demonstrate a claim of citizenship without revealing the passport number or the citizen’s name. With a bit 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. Moreover, ZKP could allow for identity and other data authentication in the context of blockchain's decentralized identity, either together or apart from existing web2 applications. Giving users the means to show zero-knowledge proof evidence of their bank statement or credit score via private keys would enable new kinds of financial functionality on-chain.
The bottom line is that ZKP seeks to minimize the downsides associated with current authentication models: loss of control of user data, user data exposure to hacking, and nonconsensual 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 besides 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 a prover was in possession of such a graph would be to transmit 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 “contain[s] more knowledge than the single bit Hamiltonian/non-Hamiltonian.”
We can imagine a scenario where the verifier instead queries repeatedly for information about specific lines and points in the graph and the prover responds. If the prover provides enough valid responses, it becomes probable 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 that Peggy has created a room furnished with two buttons. She invites Victor to confirm her claim that the buttons are working. The proof is that she can tell when one or another button is pressed. To prove the claim in a “zero knowledge” fashion, Peggy must be in a different room from Victor. She can't see what he is doing, but she can tell when different buttons are pushed and she can communicate what she sees to Victor. Perhaps Peggy can see lights that illuminate with different colors depending on the button pushed. Figure 1 shows the layout in cartoon form.
IDG
Figure 1. Peggy’s zero-knowledge room and buttons.
The first time Victor pushes a button, Peggy alerts 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. Either possibility is equally true.
To increase the odds against Peggy cheating, the two can proceed with multiple rounds. Victor can either press the same button or a different button each time. If she's guessing, Peggy's deception will be revealed quickly. The probability of guessing correctly grows smaller with each round. The process can be repeated for as many rounds as they want to get to an acceptable probability.
This scenario proves to Victor that Peggy knows when a button was pushed and the effect of that button—which is all that Victor needs to know. The experiment doesn’t reveal the button's effects or how Peggy is able to monitor them. It demonstrates to Victor that the buttons have differing effects, but he doesn't need to know what they are.
Proof and probability
The key here is that Victor has control over which button to press, but he doesn't know the button's effect. He is dependent on Peggy to complete the feedback loop. At the same time, he retains the ability to tell with a high degree of probability if Peggy is legitimately able to see which button was pushed. This is why we say that the zero-knowledge proof is a probabilistic proof rather than a deterministic one.
Something else to note about Peggy and Victor's scenario is that it's what’s called an interactive proof. In this model, the verifier is able to interrogate the prover at will. This is contrasted to non-interactive proofs, where the prover conducts the verification process on their own and transmits the proof without interacting with the verifier. Either style can be applied using ZKP.
Going further with ZPK
Zero-knowledge proof is an expanding field, which makes for 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 a few more pointers for further study:
- For a hands-on application 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 the space, consider Polygon’s Nightfall project.
- For working code and a library, look at 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 get a grounding in zero-knowledge proof protocols remains the original ZKP white paper. This gives you access to the actual mental wrangling going on in conceiving of how the factor of computational time can be introduced into proof systems to limit the ability of attackers to spoof proofs in NP time. Everything flows from that. Implementing the code and infrastructure to realize the promise of those ideas is where we are today.