Zero-knowledge proof is an innovative cryptographic protocol that allows the prover to prove they own the information without revealing their privacy. There are two roles in the zero-knowledge proof system: the prover and the verifier. The prover has a secret piece of information to convince the verifier that they have this information without disclosing the actual information. The prover generates a proof based on the secret information, which does not contain the actual information. This proof is usually constructed through mathematical operations that can demonstrate that the prover indeed has the secret information. After receiving the proof, the verifier checks its correctness through a preset verification algorithm. However, the verifier cannot obtain any actual secret information from the proof. If the prover passes the verification, it means the verifier believes that the prover has the secret information without gaining any real knowledge of the secret. This is a "zero knowledge" proof.

 

As the volume of cryptocurrency transactions on blockchain exchanges grows, users need to confirm that exchanges have sufficient reserves to support these transactions. However, the details of user assets and the specific amount of reserves are sensitive information that exchanges do not want to disclose. Zero-knowledge proofs can prove that exchanges have sufficient reserves and solvency without revealing the specific amount. Proof circuits designed with strict constraints ensure that the final proof is derived through a rigorous calculation process, preventing the occurrence of false proofs. Adopting this advanced cryptographic technology can greatly enhance user trust in exchanges while increasing the transparency of exchange funds, serving as a safeguard against financial risks. Compared with traditional external audits, zero-knowledge proofs do not need to hand over all reserve assets to third-party audits, which significantly reduces operating costs and capital risks. This makes Proof of Reserves a routine process that can be performed frequently and disclosed on a regular basis.

 

What is zk-SNARK and how the Groth16 algorithm works

Introduction:

What is zk-SNARK?

The acronym zk-SNARK ("Zero-Knowledge Succinct Non-Interactive Argument of Knowledge") refers to a proof structure in which individuals can prove possession of certain information, such as a secret key, without revealing the actual information, and there is no interaction between the two parties.

"Zero-knowledge" proofs allow one party (the prover) to prove to another party (the verifier) that a statement is true without revealing any information beyond the validity of the statement itself. For example, given the hash of a random number, the prover can convince the verifier that there is indeed a number with that hash value, without revealing what the number is.

In a zero-knowledge “proof of knowledge,” the prover can not only persuade the verifier to believe that the number exists, but that they actually know such a number - again, without revealing anything about the number. The difference between "proof" and "argument" is fairly technical, and we won't delve into it here.

"Succinct" zero-knowledge proofs can be verified in milliseconds. Even for statements of considerably large programs, the proof length is only a few hundred bytes. In the first zero-knowledge protocol, the prover and verifier must communicate multiple rounds. However, in the "non-interactive" structure, the proof consists of a single message sent by the prover to the verifier.

The following is a brief overview of the existing zk-SNARKs:

Groth16: Groth16 is currently the fastest zk-SNARK with the smallest data size. It is used in applications like Zcash. Groth16 is not universal, and its settings need to be bound to a specific circuit. Due to its speed and the small data size, it is often used as a performance benchmark for new zk-SNARKs. See the Groth16 paper link: https://eprint.iacr.org/2016/260

 

Sonic: Sonic is an early general-purpose zk-SNARK protocol. The paper was published in January 2019. Sonic supports generic, upgradable reference strings. Sonic's has a fixed proof size but a high verification cost. In theory, multiple proofs can be verified in batches for better performance. Many of the new zk-SNARKs listed below are based on Sonic. See the Sonic paper link: https://eprint.iacr.org/2019/099

 

Fractal: Fractal is a zk-SNARK that allows for recursion. It enables transparent settings through circuit preprocessing. Proofs can be as large as 250KB, much larger than those generated by other constructions. See the Fractal paper link: https://eprint.iacr.org/2019/1076

 

Halo: Halo supports recursive proof composition without the need for trusted setup. Unlike other new zk-SNARK constructions, Halo has linear verification time. See the Halo paper link: https://eprint.iacr.org/2019/1021

 

SuperSonic: SuperSonic, an improved version of Sonic, is the first transparent zk-SNARK that is practical in terms of verification time and proof data size. See the SuperSonic paper link: https://eprint.iacr.org/2019/1229

 

Marlin: Marlin, also an improvement on Sonic, reduces proof time by 10 times and verification time by 4 times. See the Marlin paper link: https://eprint.iacr.org/2019/1047

 

Plonk: Plonk, another improvement on Sonic, demonstrates a 5x reduction in proof time. See the Plonk paper link: https://eprint.iacr.org/2019/953

 

Our zero-knowledge proofs use groth16. The following is a detailed introduction to the scheme:

1. Implementation route:

We complete our proof through the following six processes:

 

In this document, we use a simple example to help you understand better:

Example: How to prove that we know the solution to the equation x ^ 3 + x + 5 = 35.

 

2. Implementation process and principle:

As we already have our problem, which is to prove that we know the solution to an equation, we start from the second step: The system of calculated equations satisfied -> R1CS circuit.

 

2.1 The system of calculated equations satisfied -> R1CS circuit:

First, we split the above equation into equations that involve only one mathematical operation (addition, subtraction, multiplication, or division) at a time.

E.g., equation x ^ 3 + x + 5 = 35 can be split into:

(1) X0 = x * x

(2) Y0 = X0 * x

(3) Y1 = Y0 + x

(4) Out = Y1 + 5

This way, x ^ 3 + x + 5 = 35 is split into four constraints. In other words, when we can prove that we satisfy the above four constraints simultaneously, we can also prove that we know the solution to the equation.

Next, we need to use a vector set (a, b, c) and a solution vector s to satisfy the following condition <s,a>*<s,b> = <s,c>, where <*, *> represents the dot product of vectors.

To satisfy the above-mentioned relationship between the solution vector s and the vector set (a, b, c), we first construct the solution vector s = (1, Out, x, X0, Y0, Y1) = (1, 35, 3, 9, 27, 30).

From this we can construct the vector a1 = (0, 0, 1, 0, 0, 0), b1=(0,0,1,0,0,0), and c1=(0 ,0,0,1,0,0) we need according to the solution vector s. When we put a1, b1, and c1 into <s,a><*<s,b> = <s,c> respectively, and represent s with (1, Out, x, X0, Y0, Y1), we can easily get the equation (1) X0 = x * x, the vector expression for equation (1). Similarly, we can also obtain the vector expressions for equations (2), (3), and (4) by constructing the following vectors:

a2 = (0, 0, 0, 1, 0, 0), b2 = (0, 0, 1, 0, 0, 0), c2 = (0, 0, 0, 0, 1, 0)

a3 = (0, 0, 1, 0, 1, 0), b3 = (1, 0, 0, 0, 0, 0), c3 = (0, 0, 0, 0, 0, 1)

a4 = (5, 0, 0, 0, 0, 1), b4 = (1, 0, 0, 0, 0, 0), c4 = (0, 1, 0, 0, 0, 0)

So when our solution vector s is entered correctly, it means that we have the correct solution to this system of equations.

From this we get the process of converting the equation system to the R1CS circuit. (Splitting & constructing vectors) That is, we turn the problem of giving the solution to the equation into a problem of finding the equality of the R1CS circuits. In the content introduced above, the circuit definition corresponds to the Define() function in circuit/group_user_circuit.go in our public project; the circuit compiled into R1CS corresponds to the frontend Compile() function in src/keygen/main.go in our public project.

To know more about the problems of the R1CS circuit, please read Reference [1].

 

3. 2. R1CS circuit -> QAP problem:

However, solving this problem through these four vector sets is too complicated, so we hope to use a simpler method. To this end, we need to convert the R1CS circuit into a QAP problem.

Let's list the four sets of vectors we obtained:

a1 = (0, 0, 1, 0, 0, 0), b1 = (0, 0, 1, 0, 0, 0), c1 = (0, 0, 0, 1, 0, 0)

a2 = (0, 0, 0, 1, 0, 0), b2 = (0, 0, 1, 0, 0, 0), c2 = (0, 0, 0, 0, 1, 0)

a3 = (0, 0, 1, 0, 1, 0), b3 = (1, 0, 0, 0, 0, 0), c3 = (0, 0, 0, 0, 0, 1)

a4 = (5, 0, 0, 0, 0, 1), b4 = (1, 0, 0, 0, 0, 0), c4 = (0, 1, 0, 0, 0, 0)

From vectors a1, a2, a3, and a4, we select the first point 0, 0, 0, 5 to form y0, y1, y2, y3, and select 1, 2, 3, 4 to form x0, x1, x2, x3.

Using Lagrange interpolation, we can construct the polynomial fa_0(x) such that fa_0(1) = 0, fa_0(2) = 0, fa_0(3) = 0, fa_0(4) = 5.

Similarly, a total of 18 polynomials of fa_1(x)..., fc_6(x) can be constructed.

Arrange the 18 polynomials as follows:

Vector a = (fa_0(x), fa_1(x), fa_2(x), fa_3(x),…, fa_6(x))

Vectors b and c are constructed in the same way as a. From this, we get three 6-dimensional vectors (the elements are polynomials). By taking x=1, 2, 3, 4 and substituting them into vectors a, b, c, we can reconstruct each of our vector sets (a1, b1, c1),..., (a4, b4, c4).

At this point, when we need to verify the equation <s,a>*<s,b> = <s,c> in R1CS, we only need to substitute x = 1, x = 2, ..., x = 4 for verification, as long as all hold. (At this point, the vector (fa_0(x), fa_1(x), fa_2(x), fa_3(x),..., fa_6(x)) turns back into a numeric vector).

However, individually substituting can be cumbersome. How can we verify them all at once?

Here we define Z(x) = (x - 1)(x - 2)(x - 3)(x - 4), which is the interpolation of x0, x1, x2, x3 selected above.

When x is 1, 2, 3, 4, our <s,a>*<s,b> = <s,c> is correct, which is A(x) * B(x) - C(x) = 0 = H(x)Z(x),

where A(x) = <s,a>, where a is the above vector a = (fa_0(x), fa_1(x), fa_2(x), fa_3(x),…, fa_6(x)), and B(x) and C(x) follow the same way.

That is to say, when we verify that A(x) * B(x) - C(x) is divisible by Z(x), our circuit R1CS is verified. This completes the conversion of R1CS to QAP problem. Completing the verification of the QAP problem means completing the verification of the R1CS circuit, demonstrating that we know the solution to the original equation x ^ 3 + x + 5 = 35.

The above is an instance of a QAP problem.

Let's establish a correspondence between the symbols and real-world problems. A, B, and C represent the A(x), B(x) and C(x) we mentioned above, respectively. D represents the interpolation space we showed above, namely D={1, 2, 3, 4}. Z_D(x) is Z(x) = (x - 1)(x - 2)(x - 3)(x - 4). zi represents the value of each point of our secret vector s=(1, Out, x, X0, Y0, Y1), i.e., zi = si. hi represents the coefficient of H(x) mentioned above. By splitting our secret vector s according to the above method, we get the secret witness vector w = (x, X0, Y0, Y1) and the public witness vector x = (1, Out).

The above process is realized by using some functions in the groth16.SetupLazyWithDump() function in src/keygen/main.go() in the open source project.

To understand the QAP problem more specifically, please read Reference [2].

 

4. 2. QAP Problem -> Generate Proof:

 

Before introducing the process, let's first explain the symbols used:

We use the prover to generate the proof we need using the QAP problem in the following way:

 

We use the prover to generate the proof file we need using the above method - what the prover does is to randomly select the elements in the number field F and calculate them according to our predefined mapping method. This proof file is then saved in the database.

 

5. 2. Generate Proof -> Verification:

When our users need verification, they simply verify the equation in the verifier above by retrieving our proof from the database, the verification key (vk) required for user verification , and input x. Here, x is the above-mentioned public witness (1, Out) = (1, 35). If the equation holds, it indicates that our QAP problem is verified, which means that we know the solution to x ^ 3 + x + 5 = 35, the equation mentioned earlier. Because the elements in our polynomial are the points in the elliptic curve group (group) used, no other information will be leaked, thus ensuring the safety of us and users.

 

 

2.3 The content of the generated proof corresponds to the function groth16.SetupLazyWithDump() in src/keygen/main.go() in the open source project. 2.4 The proof content is implemented through src/verifier/main.go in the open source project.

For specific proof and verification correctness and security issues, we recommend reading Reference [3].

 

 

The above illustrates how our zk-SNARK Groth16 works in achieving zero-knowledge proofs. For the specific zk-POR content, we only need to abstract the real problem into equation systems and follow the above process step by step. To know more about the specific equation (constraint design) of our zk-POR, we recommend reading: How ZKP-based Proof of Reserves (PoR) Work.

 

References:

[1] Howard Wu, Wenting Zheng, Alessandro Chiesa, Raluca Ada Popa, and Ion Stoica. 2018. DIZK: a distributed zero knowledge proof system. In Proceedings of the 27th USENIX Conference on Security Symposium (SEC'18). USENIX Association, USA, 675–692.

https://eprint.iacr.org/2018/691.pdf

[2] Gennaro, Rosario et al. “Quadratic Span Programs and Succinct NIZKs without PCPs.” IACR Cryptology ePrint Archive (2013).

https://eprint.iacr.org/2012/215.pdf

[3] Jens Groth. 2016. On the Size of Pairing-Based Non-interactive Arguments. In Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 9666. Springer-Verlag, Berlin, Heidelberg, 305–326.

https://eprint.iacr.org/2016/260