zk-SNARK: Innovative Zero-knowledge Proof and its applications

Background

Zero-knowledge proof (ZKP) is a cryptographic technology that was first proposed by S. Goldwasser, S. Micali, and C. Rackoff in the early 1980s in a paper titled The Knowledge Complexity Of Interactive Proof Systems. In this paper, it was conceptualized as a theoretical model to address the problem of verifying mathematical statements without revealing the evidence. This concept gained significant attention in the academic community as it challenged the limits of traditional encryption techniques and provided a new 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 2010, Groth published a paper titled Short Pairing-based Non-interactive Zero-Knowledge Arguments, which became a seminal work in the development of zk-SNARK, an important solution in ZKP. The most significant practical application of ZKP is the zero-knowledge proof system used by Z-cash in 2015, which achieved privacy protection for transactions and amounts. Subsequently, zk-SNARK combined with smart contracts, leading to a wider range of applications.

Technical Principles of zk-SNARK

The principles that traditional ZKP needs to adhere to are as follows:

• Completeness: If a statement is true, an honest prover can convince the verifier of its truth.
• Soundness: If a statement is false, any fraudulent prover will have only a small probability of misleading the verifier into believing that the statement is true.
• Zero-knowledge: If a statement is true, the verifier will not learn any additional information other than the fact that the statement is true. In other words, the verification process does not reveal any information that can be used to construct a proof.

The principle of ZKP can be understood through a simple example: If I need to prove to A that I have B’s phone number, I don’t need to directly tell A B’s phone number. Instead, I can directly dial B’s phone number and once the call is connected, it can prove that I indeed have B’s phone number. This process does not disclose B’s number information.

And zk-SNARK further upgrades on this basis, with the following characteristics:

• Zero-Knowledge: The verifier cannot obtain any useful information from the proof.
• Concise: The proof is of small size (usually only a few dozen bytes) and the verification time is short (usually only a few milliseconds).
• Non-interactive: The prover only needs to send the proof to the verifier once, without further communication.
• Trusted Parameters: Both the prover and the verifier need to use a Common Reference String (CRS) generated by a trusted third party. The CRS may contain some sensitive information, and if leaked or tampered with, it may threaten the security of the system.

In Groth’s paper, he proposed a non-interactive zero-knowledge proof method based on pairings that transforms a computational problem into a Quadratic Arithmetic Program (QAP), and then constructs an efficient proof using elliptic curve cryptography and hash functions. Later designs of zk-SNARK generally involve four steps:

• Setup: Performed by a trusted third party, it generates a CRS which includes a proving key (pk) for generating proofs and a verification key (vk) for verifying proofs. This process only needs to be executed once, and the CRS can be reused multiple times.
• Problem Encoding: The computation problem f(x) = y is transformed into a QAP form A(x)·B(x) = C(x)·Z(x), where A(x), B(x), C(x) are polynomials determined by the circuit structure of f, Z(x) is a fixed polynomial, x is a randomly chosen point, and y is the output of f. This step can be performed by the prover or verifier, or can be done in advance by a third party.
• Proof Generation: Performed by the prover, it uses pk, x, and the input w of f to generate a proof π to prove that they know a w that satisfies f(w) = y, without revealing the specific value of w. This process involves polynomial calculations, elliptic curve operations, and hash function operations, ultimately generating a π composed of several elliptic curve points and a hash value.
• Proof Verification: Performed by the verifier, it uses vk, x, y, and π to verify if the prover indeed knows a w that satisfies f(w) = y. This process also involves polynomial calculations, elliptic curve operations, and hash function operations, ultimately yielding a Boolean value indicating the validity of the proof.

To help understand, let’s consider a simple example: Suppose you have a treasure map that can guide you to the exact location of the buried treasure. You want to prove to someone that you know the location of the treasure without revealing the contents of the map or the actual location of the treasure. If you use zk-SNARK technology, you would need to create a complex puzzle of the treasure map. You select a small piece of the puzzle (a proof) and show it to the person, which convinces them that you know how the complete puzzle fits together, i.e., the location of the treasure, without seeing the entire puzzle. However, to achieve this, you would need to obtain special markings from a trusted printing house, which serve as evidence that your puzzle piece is genuine.

Why do we need zk-SNARK?

The traditional approach to zero-knowledge proofs involves interactive proof methods, where a prover repeatedly asks a verifier “yes or no?” questions until a correct answer is reached. This process is inefficient. However, zk-SNARK eliminates the need for repeated interactions by obtaining a CRS from a trusted third party. All provers can directly compare the CRS to determine the truthfulness. This greatly improves the efficiency of zero-knowledge proofs.

In addition, zk-SNARK offers the following advantages:

• Privacy protection: zk-SNARK allows a prover to demonstrate knowledge or fulfillment of certain conditions to a verifier without revealing any private information. This is particularly useful in scenarios involving sensitive or private data, such as identity authentication, anonymous voting, and private transactions.
• Scalability: zk-SNARK compresses complex computational problems into small and fast proofs, reducing the computational burden and storage requirements for verifiers. This is beneficial in scenarios that require efficient verification and storage of large amounts of data, such as cloud computing, blockchain scalability, and verifiable computation.
• Security: zk-SNARK is based on mathematically hard problems, such as the discrete logarithm problem and bilinear mapping problem, which provide high security. Under the assumption of non-quantum computing, unless the trusted third party leaks or tamper with the CRS, it is impossible for a prover to forge a proof or a verifier to forge a verification result.

Real-world Applications of zk-SNARK

The first application of zk-SNARK is Zcash, which allows users to engage in fully anonymous transactions by hiding information such as senders, receivers, and amounts using zk-SNARK. In the current Web3 space, zk-SNARK technology plays a significant role in blockchain scalability and exchange reserve management.

Blockchain Scalability

Due to the consensus mechanism and security requirements of blockchain, its throughput and efficiency are greatly limited. To address this issue, a common solution is to use Layer2 technology, which builds an additional layer on top of the blockchain to migrate a large number of transactions or computations from the main chain (Layer1) to Layer2, thereby improving the system’s performance and usability.

zk-SNARK plays an important role in this solution, as it can compress the transactions or computations on Layer2 into a small and fast proof, which is then submitted for verification on the main chain, ensuring the correctness and consistency of Layer2. Currently, there are two mainstream Layer2 solutions based on zk-SNARK: ZK-rollup and Validium.

• ZK-rollup: This solution stores all state data on the main chain but uses proofs to verify the validity of state transitions. This ensures the availability and security of Layer2 data but increases the storage burden on the main chain. For example, zkSync stores state data on the Ethereum main chain and ensures the validity of state transitions through zero-knowledge proofs. Similar projects include Polygon zkEVM and Scroll.
• Validium: This solution stores all state data on Layer2 or other trusted third parties, and only uses proofs to verify the validity of state transitions, submitting the proofs to the main chain. This reduces the storage burden on the main chain but may decrease the availability and security of Layer2 data. DeversiFi utilizes Validium technology to maintain Layer2 transaction speed and efficiency while ensuring data privacy. Loopring provides a Validium mode to alleviate the storage pressure on the main chain.

Reserve Funds in Exchanges

Due to the volatility and uncertainty of the cryptocurrency market, many exchanges need to hold a certain amount of reserve funds to address potential risks or demands. However, these reserve funds often lack transparency and trustworthiness, leaving users uncertain about whether the exchange truly has enough reserve funds to safeguard their assets.

zk-SNARK can provide a solution in this regard by allowing exchanges to prove to users or regulatory bodies that they possess an adequate quantity and value of reserve funds without revealing specific asset details or locations.

A typical example is Gate.io, which utilizes a combination of zk-SNARK and Merkle trees. They encrypt user data and generate proofs of 100 different tokens’ reserve funds using constrained circuits to demonstrate their 100% solvency capability.

Source: https://www.gate.io/proof-of-reserves

Further Reading: How zk-SNARK improves Gate.io Proof of Reserves

In addition to Web3 applications, zk-SNARK can also be used in non-blockchain domains, such as:

• Identity Authentication: zk-SNARK allows users to prove their possession of certain identity attributes or qualifications to third parties without revealing any personal information, such as age, nationality, education, etc. This is useful in scenarios that require identity authentication or authorization, such as online shopping, online education, digital signatures, etc.
• Electronic Voting: zk-SNARK enables users to prove their participation in certain voting activities and compliance with specific protocols or rules to third parties without revealing any voting content or metadata. This is beneficial in scenarios that require protection of voting privacy and security, such as democratic elections, community governance, public decision-making, etc.

Technical Limitations and Challenges

In the previous section, we introduced the technical principles of zk-SNARK, which mentioned that zk-SNARK improves proof efficiency by finding a trusted third party to generate CRS. However, this also leads to some inherent limitations and challenges of zk-SNARK.

• Trusted Parameters: zk-SNARK requires a CRS generated by a trusted third party, which may contain sensitive information. If leaked or tampered with, it could compromise the security of the system. To address this issue, some projects have adopted the approach of Multi-Party Computation (MPC) to generate the CRS, where multiple participants jointly contribute to the generation process and destroy their secret information. However, this approach still faces challenges such as participant integrity, communication costs, and coordination difficulties.
• Universality: Currently, zk-SNARK can only be applied to specific computational problems, such as QAP or R1CS, and cannot be applied to arbitrary computational problems. To address this limitation, some projects have explored the use of General Circuits (GC) or General Recursive Proof (GRS) to extend the applicability of zk-SNARK. However, this approach comes with trade-offs such as increased proof size, decreased efficiency, and increased complexity.
• Verifiability: While zk-SNARK ensures that the prover does not leak any private information, it does not guarantee that the prover will not cheat or deceive the verifier. To address this issue, some projects have introduced Verifiable Random Functions (VRF) or Verifiable Delay Functions (VDF) to enhance the integrity of the prover. However, this approach also increases the complexity and overhead of the system.

In summary, there are various approaches to address the inherent limitations of zk-SNARK.

Future Application Scenarios

zk-SNARK, as an innovative cryptographic technology, has broad future application scenarios, especially in the field of privacy:

• Privacy Smart Contracts: zk-SNARK allows users to prove to a third party that they have executed certain smart contracts and obtained the correct output without revealing any contract logic or state. This is particularly useful in scenarios involving trade secrets or sensitive rules, such as supply chain management, insurance claims, copyright protection, etc.1
• Privacy-preserving Computation: zk-SNARK enables users to prove to a third party that they have performed certain computational tasks and obtained the correct results without revealing any input or output data. This is applicable in scenarios involving sensitive or private data, such as medical diagnosis, data analysis, machine learning, etc.
• Privacy-preserving Communication: zk-SNARK allows users to prove to a third party that they have engaged in certain communication activities and complied with certain protocols or rules without revealing any communication content or metadata. This is beneficial in scenarios where communication privacy or security needs to be protected, such as instant messaging, social networks, email, etc.

Conclusion

The zk-SNARK technology represents a significant breakthrough in the fields of privacy protection and encrypted verification. It is not only promising in providing strong privacy guarantees but also practical in enhancing the scalability of blockchain and various other applications. Despite the existence of technical challenges and limitations, through continuous research and innovation, we expect zk-SNARK to continue evolving, optimizing existing systems, and inspiring new application models to drive the advancement of privacy protection and encryption technology. With the maturity of technology and the increasing emphasis on data privacy in society, zk-SNARK has the potential to become an indispensable tool in the digital age, empowering users with greater control over their information and promoting secure and transparent digital interactions.