What is Zero-Knowledge Proof - a hot technology bringing trustworthiness to Web3 privacy?
Recently, "zero-knowledge proof" is attracting attention. In 2019, the World Economic Forum announced zero-knowledge proof as one of the five privacy-enhancing technologies that bring new value to the financial sector (*1). Why is this idea, invented in the 1980s, receiving attention now? This article gives an overview of the technology, examples of its application, and looks into its future.
What is Zero-Knowledge Proof?
Zero-knowledge proof; ZKP is a technology in which a person who wants to prove something (Prover; hereafter referred to as P) proves the fact that he knows the knowledge without giving any other knowledge to the person who wants to verify it (Verifier; hereafter referred to as V).
As a result, V can only verify the fact that P knows the knowledge without obtaining any other knowledge (Figure 1).
Figure 1: Concept of Zero-Knowledge Proof
In the real world, when you want to assert that you hold certain credentials, it is common to present evidence to convince the other person that you hold the credentials.
However, when you do so, the other person may be presented with too much information about what you want to prove, such as your address or age in the evidence. If you cannot trust the other person, you may feel uncomfortable giving them too much information. However, if you don't show them the evidence, they are unlikely to trust your claim. How can you convince someone that you hold the qualification without giving them extra information?
The technology to achieve this is zero-knowledge proof. The idea of zero-knowledge proof originated in cryptography research in the 1980s (*2).
-
(*2)
Goldwasser, S., Micali, S., Rackoff, C.: "The knowledge complexity of interactive proof-systems," STOC 1985.
The claims that can be proven with zero-knowledge proof are knowledge about propositions. A proposition is a verbal expression of a judgment that is clearly true or false (*3). - (*3) For example, "2023 is equal to 7×17×17" is a proposition, and it is a true fact. "I know the prime factorization of 2023" is knowledge related to the stated proposition and is an example of a claim that can be used for zero-knowledge proof. On the other hand, "2023 is a large number" is subjective and not a proposition. Therefore, the claim that "I know 2023 is a big number" is not a subject of zero-knowledge proof.
In general, a zero-knowledge proof must satisfy three properties: completeness, soundness, and zero-knowledge (Table 1).
| Nature | Overview |
|---|---|
| Completeness | If the prover is correct, it will be determined to be correct by the verifier |
| Soundness | If the prover is incorrect, it must be determined to be incorrect by the verifier with a high probability |
| Zero-Knowledge | The verifier cannot obtain any knowledge other than the fact that the prover wants to prove |
Table 1: Requirements for a zero-knowledge proof
Intuitive understanding of Zero-Knowledge Proofs
Here are two examples to help you understand zero-knowledge proofs intuitively.
1. The cave problem
This explanation was introduced in the paper "How to explain zero-knowledge protocols to your children" (*4).
Inside the cave is a magic door that opens when you say the password. The prover P knows the password and gives it in exchange for money. The door is at the far end of the cave shown in Figure 2. There are two paths to the door, A and B. The person who knows the password can open the door and move from A to B or vice versa.
Figure 2: The Cave Problem
V, the verifier, wants to buy the password, but he doubts whether P really knows the password and cannot start a transaction. If P can convince V that P knows the secret password without telling V the secret password itself, V can start a transaction. So, here's what they are trying to do.
First, V waits outside the cave. Then P enters the cave, randomly chooses either path A or B, and goes to the door (Figure 3).
Figure 3: Prover P's Random Selection
Next, V enters the cave, goes to the branching point of the paths, randomly chooses A or B in their head, and shouts to P to come out from the chosen path (Figure 4).
Figure 4: Verifier V's Random Selection
If P knows the password:
P can use the password to open the door and come out of the designated path, whichever way V tells him to go (Figure 5). This means completeness.
Figure 5: The Case that Prover P Knows the Password
If P does not know the password:
P can only come out of the path he entered, so the probability of coming out of the path chosen by V is 50%. If they repeat this process over and over again, it's almost impossible for P to fool V every time (Figure 6). For example, if they try 30 times, the probability that P can fool V is about 0.0000001%. This means soundness.
Figure 6: The Case that Prover P Does Not Know the Password
So, if P succeeds on all his attempts, V must be convinced that P knows the password. If V tries even more, he can get his chance of being cheated as close to 0% as V wants. At this time, V will not gain any knowledge about the password. This means zero-knowledge.
Literally, what P wants to prove has been proved to V with zero-knowledge.
2. The Problem of Finding a Seabird
Professor Amit Sahai of the University of California, Los Angeles (UCLA) explains the concept of zero-knowledge proof on YouTube to children, teenagers, college students, graduate students, and experts in five different difficulty levels (*5). Here is a child-friendly explanations that will help you get a sense of the main points.
The professor shows the child a picture. The picture shows a crowd of hundreds of penguins. He says, "There is one puffin (a penguin-like seabird), and I know where it is, but I don't want to tell you. Do you believe me? I'm going to prove it without revealing its location."
Figure 7: The Problem of Finding a Seabird
The professor pulls out a piece of black paper several times larger than the photo. The paper has a small hole, and the photo is pasted on the back of the paper so that the hole matches the position of the puffin. The child looks into the hole and says, "I see a puffin". But the child can't see the position of the photo on the back of the paper, so she can't tell where the puffin is in the original photo. "This is an example of a zero-knowledge proof," the professor explains (Figure 8).
Figure 8: Zero-Knowledge Proof for the Problem of Finding a Seabird
This exchange satisfies completeness because a professor who knows the location of the puffin can always prove it.
Furthermore, it satisfies soundness because if the professor does not know the location of the puffin, the cheating will be exposed with a high probability if the child looks into the hole and confirms it.
Furthermore, it satisfies zero-knowledge because the child cannot obtain any knowledge other than the fact that the professor knows the location of the puffin.
Social Application Examples
This paper introduces an application example of zero-knowledge proof to society and considers prospects.
1. Blockchain Privacy Enhancement
Blockchain is widely used in society, a representative example being virtual currencies. Its transparency is maintained by decentralized management of its ledger by all participants in the blockchain. However, due to its high transparency, securing user privacy may be a challenge.
In recent years, zero-knowledge proofs have begun to be used to improve blockchain privacy. For example, in the case of cryptocurrencies, methods known collectively as zk-SNARK (*6) and zk-STARK (*7) have begun to be introduced as zero-knowledge proofs to show that the transaction operation was indeed performed, without disclosing the transaction contents such as the sender, recipient, and remittance amount.
In addition, zero-knowledge proofs have attracted even more attention because they can contribute to speeding up blockchain processing.
- (*6) zk-SNARK: Zero-Knowledge Succinct Non-Interactive Argument of Knowledge
- (*7) zk-STARK: Zero-Knowledge Scalable Transparent Argument of Knowledge
2. Proof of Income Range
In November 2017, ING, a major Dutch bank, developed zero-knowledge range proofs (ZKRP) (*8). ZKRP is an application of zero-knowledge proofs. ZKRP can prove that a numerical value, such as an amount of money, is within a certain range without showing the numerical value to the other party. For example, mortgage applicants can prove that their income is within a certain range required by loan screening without telling the income itself.
3. Selective Disclosure of Attribute Information
The W3C, which standardizes Web technologies, has standardized a data model for the concept of verifiable credentials (VC) (*9). It introduces zero-knowledge proof, in which you select your attribute information and prove only that the attribute satisfies certain conditions.
For example, it shows a use case in which you select and prove only the information that a university graduate received a degree without revealing his or her identity or other unnecessary personal information.
-
(*9)
W3C Recommendation, Verifiable Credentials Data Model v1.1, 2022.
VC is currently being discussed in the "Trusted Web" initiative led by the Cabinet Secretariat of Japan. It shows the expectation of zero-knowledge proof as a method to realize selective disclosure of data(*10). - (*10) Secretariat of the Headquarters for Digital Market Competition, the Cabinet Secretariat of Japan, "Trusted Web White Paper Ver 2.0, Overview" August 2022 (PDF: 1.7MB)
4. User Authentication
Currently, ID and password authentication is mainly used for websites of various services. However, since the string length of a password is limited to a range that can be remembered or managed by the human brain, it is vulnerable to brute-force and password-list-type attacks.
Furthermore, if an attacker takes over the server, not only the password itself, but also information useful for guessing the password is leaked, which becomes a hint for the attacker, and the password may be leaked in the future. If user authentication is implemented with zero-knowledge proof, the server can be more secure because no information related to the password exists from the beginning.
As a zero-knowledge proof that can be applied to user authentication, there is the Schnorr protocol (*11). In this method, knowledge about the solution of a mathematically difficult problem called the discrete logarithm problem is assumed to be information that only the user can know and is authenticated with zero-knowledge proof. Compared with the ID and password method, this method has not been adopted in the world for many years due to its disadvantages such as high communication volume, slow processing speed, and "The size of the data to be kept secret is too large for humans to remember."
In recent years, however, with the spread of technologies such as "faster communication networks," "faster processing speeds of servers and terminals," and "memory areas that can be securely stored in smart cards and smartphones," conventional disadvantages are going to be no longer disadvantages.
Prospect
In recent years, the term "Web3" has attracted attention, and although there are various interpretations, its constituent concepts are said to be centered on "blockchain," "decentralization" and "decentralized ID." Application cases (1) and (2) mentioned above are measures to improve the privacy of blockchain, and (3) and (4) are related to decentralization and decentralized ID. Therefore, zero-knowledge proof can be said to be "a technology that brings trustworthiness to the privacy of Web3."
In the future, zero-knowledge proof will become an essential technology for safe and secure future societies that require a high level of privacy.
NTT DATA will continue to keep up with the latest trends and accumulate and disclose know-hows.
Hiroaki Oguro
NTT DATA Japan Corporation
He engages in R&D, in-house applications, and business applications in cryptography, Web application security, and software engineering. CISSP. Senior member of the Information Processing Society of Japan (IPSJ). Expert committee member of the Special Interest Groups (SIG) of the Computer Security (CSEC) in IPSJ.