Background

Zero-Knowledge Proof (ZKP) is a cryptographic technique 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 the paper, it was conceptualized as a theoretical model to solve the problem of verifying mathematical statements without revealing the evidence. This concept has attracted widespread attention in academia because it challenges the boundaries of traditional cryptographic techniques and provides new methods for processing sensitive information.

Over time, ZKP has 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 the theoretical milestone for zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge), an important solution in ZKP. The most important progress in the application of zero-knowledge proof is the zero-knowledge proof system used by Z-cash in 2015, which provides privacy protection for transactions and amounts. Subsequently, zk-SNARK combined with smart contracts, extending its application to a wider range of application scenarios.

Basic Principles of zk-SNARK

Traditional ZKP adheres to three principles:

• Completeness: If the statement is true, an honest prover can always convince the verifier.
• Soundness: If the statement is false, any fraudulent prover can only mislead the verifier with a small probability.
• Zero-knowledge: If the statement is true, the verifier will not be able to acquire anything other than the fact that the statement is true. In other words, the verification process will not reveal any information that can be used to construct the 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 reveal B’s phone number. Instead, I can directly dial B’s phone number and prove that I do have B’s phone number after getting through it. This process will not leak B’s phone number.
zk-SNARK further enhances these principles with the following characteristics:

• Zero-knowledge: The verifier does not get any useful information from the proof.
• Succinct: The proof size is small (usually a few dozen bytes) and the verification time is short (usually a few milliseconds);
• Non-interactive: The prover only needs to send the proof to the verifier once, without further communication required.
• Trusted parameters: Both the prover and validator need to use a Common Reference String (CRS) generated by a trusted third party, which may contain sensitive information that, if leaked or tampered with, may threaten the security of the system.

In Groth’s paper, he proposed a non-interactive zero-knowledge proof method based on pairings to transform a computational problem into a Quadratic Arithmetic Program (QAP). This method utilizes elliptic curve cryptography and hash functions to construct an effective proof. Subsequent zk-SNARK designs typically involve four steps.

• System Setup: Performed by a trusted third party. It involves generating a CRS, including a proof key (pk) and a verifying key (vk). This process only needs to be executed once, and the CRS can be reused multiple times.
• Problem Encoding: Transform a computational problem f (x) = y 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 selected point, and y is the output of f. This process can be performed by a prover or verifier, or by a third party in advance.
• Proof Generation: Performed by the prover. It involves using the input w of pk, x, and f to generate a proof \pi, proving that he knows 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 \pi composed of several elliptic curve points and a hash value.
• Proof Verification: Performed by the verifier. It involves using vk, x, y, and \pi for verification, determining whether the prover knows a w that satisfies f (w) = y. This process also involves polynomial calculation, elliptic curve operations, and hash function operations. It finally obtains a boolean value indicating whether the proof is valid.

To illustrate with a simple example, suppose you have a treasure map that can guide you to the exact location of a buried treasure. You want to prove to someone that you know the location of the treasure, but you don’t want to reveal the content of the treasure map or the actual location of the treasure. If you use the zk-SNARK technology, you need to create a complex puzzle of the treasure map. You choose a small piece of the crucial puzzle (a proof) and show it to the other person, convincing them that you know how the entire puzzle, i.e., the treasure’s location, fits together without revealing the entire puzzle. However, to do this, you need to obtain some special marks from a trusted printing house, which are used to prove the authenticity of your puzzle piece.

Combination of Exchange Reserves with zk-SNARK

The previous discussion mentioned that zk-SNARK allows setting a common reference string, which means constraints can be set on the running circuit. Taking Gate.io reserve as an example, it sets five core constraints in the circuit, as shown below:

① Before inserting the user’s net assets into the Merkle tree, the node corresponding to the user ID is empty.
② Calculate the user’s total assets/liabilities based on the user’s asset list and the price of each asset. The total assets must be greater than the total liabilities.
③ Add the user’s assets/liabilities to the exchange’s assets/liabilities.
④ Calculate the user’s state hash using the user ID, total assets/liabilities, and asset list. Insert the user‘s state into the Merkle tree to obtain a new Merkle Root.
⑤ The hash value of the root node of the tree before the previous user creates a user operation must be equal to the hash value after the subsequent user creates a user operation.
(Operation ① can avoid node data from being false, operation ② can avoid negative balance accounts, and operation ⑤ can ensure that user data is not changed before and after the operation.)
This ensures the resolution of the negative balance issue. The exchange data only needs to pass through the circuit to automatically perform constraint checks and obtain the asset number. However, this solution requires certain computing power and hardware conditions. It takes 15 days to calculate the proof of assets of 10 million users on a 32-core machine with 128GB of RAM. The calculation of the Proof of Reserves can be parallelized. If there are 10 machines, it only takes 1.5 days.

Conclusion

By setting relevant constraints, zk-SNARK can avoid the occurrence of negative value problems and better protect users’ privacy and security. Gate.io’s Proof of Reserves can now prove reserve ratios for 100+ coins, and users can view it by simply clicking the link. In the next lesson, we will take you to verify your asset security within 3 minutes.