A Detailed Explanation of Zero-Knowledge Proofs (ZKP)

Background

Zero-Knowledge Proof (ZKP) is a cryptographic technology first introduced in a paper titled “The Knowledge Complexity Of Interactive Proof Systems” in the early 1980s by S.Goldwasser, S.Micali, and C.Rackoff. Originally conceived as a theoretical model, it aimed to address the challenge of verifying mathematical statements without revealing any evidence. This concept garnered widespread attention in the academic world for challenging the boundaries of traditional encryption techniques and offering a novel approach to handling sensitive information.

Over time, ZKP evolved from an abstract theoretical concept into concrete protocols that can be integrated into various applications. In the early 21st century, with the explosive growth of the internet and digital communication, ZKP’s potential began to be explored in the real world. Particularly with the rise of blockchain and cryptocurrencies, ZKP demonstrated its ability to enhance privacy and security while maintaining the efficiency of transactions and data processing.

Today, ZKP is not only a hot topic in cryptographic research but has also been integrated into multiple blockchain platforms and applications. For instance, zk-SNARKs’ application on Ethereum Layer2 offers anonymous transactions without revealing transaction details. This transition from theory to practical application not only proves the practical value of ZKP but also drives the exploration of more efficient and secure digital interactions. With continual technological advancements, ZKP plays an increasingly critical role in protecting personal privacy, ensuring data security, and establishing trustworthy digital systems.

Definition and Principle of ZKP

Zero-Knowledge Proof (ZKP) is an encryption method that allows one party (the prover) to prove the correctness of a statement to another party (the verifier) without revealing any additional information, i.e., without disclosing any knowledge on which the correctness of the statement depends. This process not only protects the privacy of the prover but also ensures that the verifier cannot replicate the proof process or use it to gain any additional information.

Zero-Knowledge Proofs Conceptual Diagram (Source: ChainLink)

The core principles of Zero-Knowledge Proofs (ZKP) can be defined by the following three attributes:

• Completeness: If a statement is true, an honest prover can always pass the verifier’s test.
• Soundness: If a statement is false, any deceitful prover will have only a slim chance of misleading the verifier into believing the statement is true.
• Zero-Knowledge: If the statement is true, the verifier learns no additional information other than the fact that the statement is correct. In other words, the verification process does not reveal any information that could be used to construct the proof.

The principle of ZKP is often understood through simple examples: If I need to prove to person A that I have person B’s phone number, I don’t need to directly reveal B’s number to A. Instead, I can prove it by calling B’s number. Once the call connects, it demonstrates that I indeed possess B’s number, without disclosing any information about the number itself.

In practical applications, ZKP usually requires complex mathematical constructions like polynomial equations, elliptical curves, or other mathematical challenges. The security of these constructions is based on the computational difficulty of problems like factorization or discrete logarithms. With the advancement of cryptography, various implementations of ZKP have emerged, such as zk-SNARKs and zk-STARKs, offering effective privacy protection in different contexts, especially in the fields of blockchain and cryptocurrencies.

The basic form of zero-knowledge proof consists of three elements: witness, challenge, and response.

Witness: In zero-knowledge proof, the prover wants to demonstrate knowledge of some hidden information. This secret information acts as the “witness” to the proof. The prover, based on their knowledge of the witness, sets up a set of questions that only someone with knowledge of the information can answer. Thus, the prover randomly selects a question to initiate the proof, calculates the answer, and then sends it to the verifier.

Challenge: The verifier randomly picks another question from the set and asks the prover to answer it.

Response: The prover receives the question, calculates the answer, and sends it back to the verifier. The prover’s response allows the verifier to check if the prover indeed has access to the witness. To ensure that the prover isn’t just blindly guessing correctly by chance, the verifier selects another question for inquiry. By repeating this process multiple times, the likelihood of the prover fabricating the truth greatly reduces until the verifier is satisfied.

In the aforementioned phone call example, “I” am the unwilling-to-disclose-information witness, while A is the verifier, and the challenge posed is “Prove that ‘I’ possess B’s number.” The response process involves “me” connecting a call to B’s number to prove I truly have it.

Why is ZKP Needed?

As previously discussed, Zero-Knowledge Proofs (ZKP) inherently offer significant advantages in the realm of privacy protection. In today’s era of information overload, personal data is often stored on third-party platforms, increasing the risk of data breaches. Moreover, due to technical barriers and the lag in legal sanctions, information security largely relies on ethical constraints, making it difficult for users to truly control their private information. The advent of ZKP technology provides a solution that both protects privacy and enhances verification efficiency and security.

Compared to other encryption technologies, ZKP has multiple advantages:

• Privacy Protection: ZKP allows individuals and institutions to prove the truthfulness of certain information without revealing the actual content of the information. For example, it can be used to prove that a person meets age requirements without revealing the actual age or birth date.
• Enhanced Security: Since ZKP does not require revealing sensitive information, it reduces the risk of data leaks. Even if interception occurs during the proof process, no substantial data is disclosed.
• Reduced Fraud: In financial transactions, ZKP can be used to verify the legitimacy of a transaction without exposing specific details, thereby reducing opportunities for fraud.
• Efficiency: Some types of ZKP, like zk-SNARKs, are very fast to create and verify, which is beneficial for systems that need to process a large number of transactions or verification operations.
• Interoperability: ZKP provides a common framework for verification between different systems and domains, allowing information to be securely verified and shared among various systems.
• Scalability: With the evolution of computing technology, the implementation of ZKP is becoming more efficient and scalable, meaning it can be deployed in larger-scale systems.
• Compliance: In today’s regulatory environment that demands consumer privacy protection, ZKP can help companies verify and process data without violating privacy laws.
• User Control: ZKP enhances users’ control over their data because they can choose the amount of information to disclose.
• Decentralization: In blockchain and distributed technologies, ZKP offers a powerful privacy tool for decentralization, enabling users to transact and interact without reliance on central authorities.

Whether in traditional Web 2.0 or the emerging Web 3.0 domain, the application prospects of ZKP are extensive.

Types of Zero-Knowledge Proofs (ZKPs)

There are multiple implementations of zero-knowledge proofs, such as zk-SNARKs, zk-STARKs, PLONK, and Bulletproofs. Each type has its advantages and disadvantages in terms of proof size, prover time, and verification time. This article focuses on introducing the four types that are most commonly used in application scenarios.

zk-SNARKs

zk-SNARKs, standing for “Zero-Knowledge Succinct Non-Interactive Argument of Knowledge,” are cryptographic tools used to prove that someone knows a piece of information without revealing any of the information itself. In zk-SNARKs, “zero-knowledge” means the prover can prove a statement is true without providing any information other than its correctness. “Succinctness” refers to the small size of the proof and the speed of the verification process. “Non-interactive” means once a proof is generated, it can be verified by anyone without further interaction between the prover and the verifier. The core components of zk-SNARKs include:

• Trusted Setup: During system initialization, a pair of public/private keys (parameters) need to be generated. This process must be executed by a trusted party, as the security of the system can be compromised if the private key is leaked.
• Proof Generation: The prover knows a secret piece of information but does not wish to reveal it to the verifier. They use this secret information and the public parameters to construct a proof that sufficiently shows they know the secret without revealing any details about it.
• Verification Process: Once the verifier receives the proof, they can use the public parameters to verify its correctness. If the prover has constructed a correct proof, the verification process will output “yes,” otherwise “no.”

zk-SNARKs are used in various privacy-preservation scenarios, such as cryptocurrencies with anonymous transactions, secure voting systems, privacy-preserving authentication and data sharing, and blockchain scalability technologies.

zk-STARKs

zk-STARKs, or “Zero-Knowledge Scalable Transparent Arguments of Knowledge,” allow one party (the prover) to prove to another (the verifier) that they know certain information without revealing the information itself. Unlike zk-SNARKs, zk-STARKs do not require a trusted setup process. This means they do not rely on the confidentiality of certain private information, a feature often considered crucial for security, as the trusted setup can be a systemic vulnerability.

zk-STARKs work based on concepts from several mathematical fields, including hash functions, polynomial computations, and error correction theory. They utilize a construction known as “zero-knowledge scalable transparent argument,” allowing for proof generation without a trusted setup. The potential applications of zk-STARKs are similar to those of zk-SNARKs, but due to their scalability and transparency, they are particularly suitable for large-scale applications, including privacy-preserving cryptocurrencies, blockchain scalability technologies, and secure verification in cloud computing.

PLONK

PLONK, not an acronym, refers to the surnames of its creators. It’s designed to provide a universal and efficient ZKP solution, especially in blockchain applications such as smart contracts and privacy-protected transactions. The core of PLONK is the use of a “homomorphic hiding” technique, allowing arithmetic operations on data without revealing the original data. It employs a special algorithm - a polynomial commitment scheme - to create proofs, enabling provers to efficiently prove they have the correct calculation results for a set of data.

One key feature of PLONK is its universality. Once parameters are set for a specific computational task (through a one-time trusted setup), they can be reused multiple times to create new proofs, without needing new setups each time. This makes PLONK highly efficient in creating and verifying proofs and is often designed to support various computational tasks in blockchain and other distributed systems.

Bulletproofs

Bulletproofs, a newly introduced ZKP solution, do not require a trusted setup and are specifically designed for constructing range proofs and certain types of arithmetic proofs. Proposed by Benedikt Bunz, Jonathan Bootle, Dan Boneh, and others in 2017, Bulletproofs operate on complex mathematical constructs like homomorphic encryption and elliptic curve cryptography. They leverage a series of mathematical techniques to allow provers to create an effective range proof for a number without revealing its exact value. Especially in the cryptocurrency domain, this can be used to prove that transaction values fall within a legal range without exposing the actual transaction amounts.

Due to their range-proof feature, Bulletproofs are widely used in the cryptocurrency and blockchain fields, particularly in privacy coins like Monero, to hide transaction amounts while verifying the legitimacy of transactions. Additionally, they can be employed in other applications where numerical privacy is required.

Case Study

Let’s better understand these four different Zero-Knowledge Proof (ZKP) technologies—zk-SNARKs, zk-STARKs, PLONK, and Bulletproofs—through a treasure map analogy.

Imagine you have a treasure map that leads to the exact location of a buried treasure. You want to prove to someone that you know where the treasure is without revealing the map’s contents or the treasure’s actual location.

zk-SNARKs: You create a complex jigsaw puzzle of the treasure map. You select a small, key piece of this puzzle (a proof) and show it to the other party, sufficient to convince them that you know how to assemble the complete puzzle, i.e., the treasure’s location, without revealing the whole puzzle. However, to do this, you need special markers from a trusted printer to prove that your puzzle piece is genuine.

zk-STARKs: You show a part of the treasure map to the other party, telling them they can use a special magnifying glass (a verification algorithm) to randomly check the map’s details to verify it indeed points to the treasure, without needing to know the exact location of the treasure. This magnifying glass is so powerful that even future technologies (quantum computers) can’t crack the secret of your treasure map.

PLONK: This time, you create a set of riddles, each pointing to the treasure’s location. You present a universal method of verifying solutions to these riddles (a universal setup) to the other party, sufficient for them to believe you know all the answers without having to solve each riddle individually.

Bulletproofs: You decide to prove that you know the approximate range of the treasure’s location without revealing its exact position. You provide a series of mathematical problem solutions that demonstrate the range of the treasure’s location. Your method doesn’t require any special markers or printing techniques, meaning no initial trust requirement.

In this analogy:

• zk-SNARKs require trust in the source of your puzzle piece (a trusted setup) but offer a very small and fast-to-verify proof.
• zk-STARKs don’t need trust in any source, making the proofs more robust, and suitable for long-term security and future threats.
• PLONK offers a one-time setup, multiple-use efficient verification method, meaning you need to make the effort once to prove multiple times that you know the treasure’s location.
• Bulletproofs allow you to prove information about the treasure’s location range without any initial trust requirement, though the efficiency of generating and verifying proofs might not match the former two.

Each method has its trade-offs in practical applications, and the choice depends on the specific application scenario and security needs.

Simple Comparison of Different ZKP Schemes

Before comparing, we need to understand the criteria for evaluating ZKPs:

• Proof size: The amount of data in the proof, affecting storage and transmission costs
• Verification time: The time required to verify a proof
• Proof time: The time required to generate a proof
• Memory usage: The amount of memory needed during the proof generation and verification processes
• Universality: Whether the proof system is applicable to various types of computations
• Trusted setup: Whether an initial trusted setup phase is required
• Post-quantum security: Whether it resists future quantum computer attacks

Now, let’s compare zk-SNARKs, zk-STARKs, PLONK, and Bulletproofs based on these indicators and discuss their pros and cons.

zk-SNARKs

Pros

• Proof size: Very small, making them suitable for bandwidth-limited environments
• Verification time: Fast verification, suitable for scenarios needing quick responses
• Universality: Applicable to various complex computations

Cons

• Proof time and memory usage: Proof generation may be both time-consuming and memory-intensive
• Trusted setup: Requires an initial trusted setup phase; if compromised, the system’s security is at risk
• Post-quantum security: Most constructions are not post-quantum secure

zk-STARKs

Pros

• No trusted setup: Eliminates the need for a trusted setup, enhancing system security
• Post-quantum security: Resists attacks from quantum computers
• Proof size: Although larger than zk-SNARKs, still manageable under certain conditions

Cons

• Proof size: Larger than zk-SNARKs, potentially reducing storage and transmission efficiency
• Proof time: Possibly slower than zk-SNARKs, especially in complex computations

PLONK

Pros

• Universality: One set of parameters applies to multiple different proofs, reducing redundant work
• Proof size: Relatively small, although larger than zk-SNARKs
• Updatability: Easy to update and maintain

Cons

• Trusted setup: Although less stringent than zk-SNARKs’, a setup is still required
• Post-quantum security: Similarly, most constructions are not post-quantum secure

Bulletproofs

Pros

• No trusted setup: No need for a trusted setup, reducing security risks
• Proof size: The proof size grows slowly with the complexity of the statement
• Verification time: Fast for range proofs

Cons

• Proof time: Generating proofs may take a longer time
• Proof size: Although smaller, still larger than zk-SNARKs in larger proofs
• Post-quantum security: Not specifically designed for a post-quantum environment

Application Cases of ZKP in Web3

In Web3, there are many application cases of ZKP, and we have selected two typical cases for study.

Blockchain Scaling - Ethereum Layer2

zk-Rollups are a Layer 2 solution that bundles hundreds or thousands of transactions off-chain and generates a zk-SNARK proof. This proof, along with transaction data, is submitted to the Ethereum main chain. It allows for the validation of transactions without the main chain processing each transaction, thereby reducing fees and increasing throughput. zk-Sync Era and Starknet have adopted zk-rollup technology, and Polygon has recently introduced Polygon zk-EVM using zk-rollups.

An application demonstration of zk-SNARKs in Layer 2 (Source: Simon Brown)

Data Privacy - Exchange Reserve Proof

Exchange reserve proof refers to the verification of balances held by cryptocurrency exchanges or other financial institutions, ensuring that the recorded assets match the actual assets held. Initially, exchanges used Merkle trees and third-party audit firms for this verification, but this process relied on third parties and could leak private user data such as account balances. Exchanges like Gate.io are now utilizing zk-SNARKs technology for reserve proofs, encrypting user data, and obtaining user asset numbers through zk-SNARK circuits, thereby issuing complete reserve proof reports.

Conclusion

The diverse solutions of zero-knowledge proof technology highlight its powerful potential in Web3. From data privacy protection to blockchain scaling, ZKP is important to building a secure and efficient Web3 infrastructure. While different approaches have their advantages and limitations, they collectively point toward a more trustworthy and privacy-protected digital future. As technology advances, the challenges of optimizing performance and security with ZKP will gradually be overcome, indicating its increasingly significant role in the digital world.