Groth16 is the most widely used zkSNARK in practice. Its Verifier performance is fast and the proof string is short. The disadvantage is that it needs to perform a trusted initialization for each circuit.
Original title: “Together to understand the most popular zkSNARK program-introduction to zero-knowledge proof (3)”
Written by: Cyte
In the previous article, we introduced the basic concepts of zero-knowledge proof and the basic ideas and methods of constructing zkSNARK. Starting from this article, we will introduce the most popular zkSNARK solutions one by one. The article aims to allow readers to understand the basic principles of these programs. In order to facilitate the narrative and easy to understand, when narrating the plan, we will do some simplification, focusing on conveying the core idea of ​​the plan.
This article describes the Groth16 program. The Groth16 scheme, as the name suggests, is the scheme proposed in a paper [Gro16] published by Groth in 2016. So far, Groth16 is the most widely used zkSNARK in practice (no one). In particular, the zkSNARK scheme currently used by Zcash is Groth16. In terms of performance, the Verifier performance of Groth16 is the fastest among all zkSNARKs, and its proof string is also the shortest.
The biggest disadvantage of Groth16 is that it needs to perform a trusted initialization for each circuit.
Before introducing Groth16, briefly review the problem that zkSNARK is trying to solve. We call this problem the “calculation verification problem.”
Calculation verification problem
Any calculation can be described as an arithmetic circuit. An arithmetic circuit can perform arithmetic operations on numbers. The circuit consists of addition gates, multiplication gates and some constant gates, as shown in the figure below:
The circuit in this example contains 15 gates. The calculation process described by this circuit requires input of five numbers x1 to x5 and output of four numbers.
Given a set of input numbers, each gate in this circuit needs to be calculated once to calculate the output of this circuit. In this example, if the input is (1,2,3,4,5), the output of the circuit is (-27,14,80,171), as shown in the following figure:
The computational verification problem means that if a verifier—maybe called Verifier—only gets a set of inputs and outputs of the circuit, such as (1,2,3,4,5) and (-27,14) in this example ,80,171), how does it verify that this is a legal pair of input and output? The simplest and rude way is to throw this input into the circuit again. If the circuit is large, the biggest disadvantage of this verification method is efficiency.
In some scenarios, efficiency is not the only problem. For example, the input may contain secret information that Verifier cannot know. Assuming that (3,4,5) in the above example is a secret input, Verifier can only see (1,2), as shown in the figure below. At this time, the question Verifier needs to verify becomes “is there (?,?,?) so that the output of the circuit when the input is (1,2,?,?,?) is (-27,14,80,171)” . In this scenario, even simple and crude recalculations are no longer feasible.
Summarize the calculation verification problem in one sentence: Can Verifier efficiently verify the calculation results without knowing the secret input?
From the circuit to the R1CS problem
A zkSNARK is a solution to the above problems. Using zkSNARK, a prover, called Prover, can generate a short proof string for the calculation process. Verifier can read this string to determine whether the given public input and output are legal.
Groth16 is one of many zkSNARK construction schemes. Next, we introduce how Groth16 solves the calculation verification problem.
First, we re-examine the task of Verifier: we only know that the first two inputs of the circuit are (1,2), and our goal is to determine whether there is a set of legal secret inputs such that the output of the circuit is (-27, 14,80,171). If we look at this problem from another angle, it can actually be described as: For a circuit, some blanks can be filled with numbers, and some blanks have been filled with numbers. Is there a filling method that can satisfy the logic of each gate at the same time?
From this new perspective, the calculation verification problem has been transformed into a number-filling game similar to Sudoku: there are some blanks, some of which have already been filled, please fill in some other blanks to meet some restrictions.
Then, we make an equation for each condition to be satisfied. Here, each condition to be met is actually the logic of a gate: the output of the addition gate is equal to the sum of two inputs, and the output of the multiplication gate is equal to the product of the two inputs. As a result, the original fill-in-the-blank game becomes a multivariate equation system. The equations converted from the above example are as follows:
Finally, we do some sorting of this equation so that it can be written in the form of matrices and vectors, more tidy and concise. We write each equation as a pattern of * = * x *. Although not all equations have multiplication, we can multiply an equation without multiplication. So the system of equations becomes like this:
Put all the equations together and get the matrix representation of the original equations
We call the resulting matrix vector equation a Rank-1 Constraint System (R1CS) .
To summarize, in this section we transformed the computational verification problem into a mathematical problem R1CS.
In the calculation and verification problem, Verifier knows a circuit, gets the input of the public part, and the output of the circuit, and judges whether they are legal.
From R1CS question to QAP question
In the field of zero-knowledge proof, R1CS is basically synonymous with circuits. Many zkSNARKs have R1CS problems as target problems. However, most zkSNARKs will not directly start with R1CS, but continue to transform the R1CS problem to obtain an equivalent polynomial problem, and then design a proof scheme for this polynomial problem. Groth16 is no exception. Different zkSNARKs choose different polynomial problems. Groth16 chooses a problem called Quadratic Arithmetic Programming (QAP) .
This section introduces how to transform the R1CS problem into an equivalent QAP problem.
Then, we replaced these column vectors with polynomials, making the polynomial equations equivalent to the original vector equations.
One way to convert a vector into a polynomial is to use polynomial interpolation.
Polynomial interpolation
QAP issues
Now, we directly replace the column vectors in the R1CS matrix with their polynomial interpolation, and the result is shown in the figure below.
We use a table to summarize all the issues mentioned above.
Why do we need to get more complicated and turn circuit problems into QAP problems? A simple answer: just to introduce polynomials! Polynomial is a powerful tool. The function of polynomials can be understood as a “lever” or “error amplifier”. If we want to check whether two vectors of length 10,000 are equal, we must check 10,000 times. Even if 9999 points are checked, they are the same, there is no guarantee that the last point is the same. And two polynomials of degree 10000, even if they are very close, for example, their coefficients are the same in 9999, or their values ​​at these points are all equal, but as long as one point is different, the two polynomials are completely different. This means that if within a large range, for example, a point is uniformly selected randomly, there is only a chance that two different polynomials are equal at this point. Checking whether two polynomials are equal is much faster than checking vectors of the same scale. This is almost the fundamental principle for all zkSNARKs to improve the efficiency of Verifier.
Construct zkSNARK for QAP problem
The QAP problem is the final problem that Groth16 will use to construct zkSNARK. However, before explaining the construction details of Groth16, let’s prepare some tools.
Preparation tools
We assume that readers have an understanding of the basic characteristics and applications of elliptic curve groups, and use the notation of additive groups to describe the points and operations in elliptic curve groups. The elements in the elliptic curve group can be used to represent polynomials and restrict Prover from having to use the given polynomials for linear combinations. This is exactly what QAP needs to use.
Let’s take a look at how elliptic curves are used to represent polynomials.
KoE assumption
However, the above intuition cannot be strictly proven from the discrete logarithm hypothesis. Therefore, it can only be used as a new security assumption. This assumption is called the Knowledge-of-Exponent (KoE) assumption.
How do KoE assumptions apply to QAP issues? That is, KoE allows us to use elliptic curve points to represent polynomials, and forces Prover to generate new polynomials only from linear combinations of known polynomials.
However, so far, we have overlooked two key issues:
Regarding the second problem, one solution is bilinear pairing .
Bilinear pairing
Now, we have prepared the tools: KoE hypothesis and bilinear pairing. Next, we will introduce how Groth16 constructs zkSNARK for QAP problems.
Groth16 plan
Setup
Prove
Verify
Parsing
Let us briefly explain why the above structure works. As for why it is safe, please refer to the original text of [Gro16] for interested readers.
Of course, Verifier’s verification formula also contains many other items, but under the careful design of Groth, they are all eliminated. Those who are interested can verify by themselves.
summary
In this article, we explained the construction principle of the zkSNARK scheme of Groth16. We started from the arithmetic circuit and introduced how to convert the calculation verification problem into the R1CS problem and QAP problem. Then we explained how to use the Groth16 scheme to prove that we know the solution of a QAP problem. The Groth16 scheme uses the KoE assumption and bilinear pairing. Its disadvantage is that it requires a trusted third party to initialize, and the initialization process needs to be performed once for each circuit. At the same time, Groth16 enjoys the most efficient Verifier algorithm and the shortest proof string, making Groth16 the most widely used zkSNARK solution.
Reference
[Gro16] Jen Groth. On the Size of Pairing-based Non-interactive Argument. 2016.
