The construction and case of zk-SNARK

TL;DR

• **What is the construction process of SNARK? **

Problems to be Proved-Arithmetic Circuits-R1CS-Polynomials

• **Why convert to polynomial in the end? **

Because of the characteristics of polynomials, the verification time is effectively shortened, and simplicity is achieved.

• **How to achieve zero knowledge? **

To put it simply, in the process of deriving the polynomial, two more random numbers are selected, so that the derived polynomial can prevent the verifier from obtaining the coefficients of the original polynomial, that is, the secret input of the prover, so as to realize ZK.

• **How to achieve non-interaction? **

Before the proof begins, a third party is introduced, that is, a trusted setting, which assigns the original verifier the task of picking random numbers to the trusted setting, thereby realizing non-interaction between the verifier and the prover.

ZK technology has attracted much attention in the Web3 field in the past two years. Starting from Rollup, more and more projects on different tracks are trying to use ZK technology. Among them, SNARK and STARK are the two most commonly heard terms. In order to better understand the application of ZK technology in the later stage, **this article will simplify the proof logic of SNARK from a non-technical perspective, and then use * * Scroll's zk Rollup ** is used as an example to illustrate the operation of the zk proof system. **

The purpose of the article is to explain the basic logic, which is easy to read. It will try to avoid the use of terminology, and will not go into details such as mathematical transformations. Please forgive me for any omissions.

In January 2012, Alessandro Chiesa, a professor at the University of California, Berkeley, co-authored a paper on SNARK and proposed the term zk-SNARK.

zk-SNARK, full name Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge, is a proof system using ZK technology. **It should be noted that SNARK is the name of a class of schemes, and there are many different combination methods that can implement SNARK. **

• Zero-Knowledge (Zero-Knowledge): The content that only the prover knows will be hidden, and no one else can see it except the prover.
• Short (Succinct): The generated proof is small and the verification time is fast.
• Non-Interactive (Non-Interactive): There is little or no interaction between the prover and the verifier.
• Argument: The verification of the verifier is only valid for the prover with limited computing power, because the prover with super computing power can forge the proof, that is to say, the system has computational reliability.
• Knowledge: The prover can only calculate the proof if he knows some information that the verifier does not know.

What zk-SNARK needs to solve is the "calculation verification problem", that is, whether the verifier can efficiently verify the calculation results without knowing the privacy of the prover.

The following will use the simplified construction process of zk-SNARK to illustrate how the system combines zero knowledge to achieve efficient verification. **

Zk-SNARK Construction

Transform the problem to be proved into a polynomial

To put it simply, the idea of SNARK is to convert the proof of whether the statement is true or not into the proof of whether the polynomial equality is true or not.

The whole conversion process: problems to be verified ➡ arithmetic circuit ➡ R1CS ➡ polynomial ➡ conversion between polynomials

Question to be verified➡Arithmetic circuit

To prove whether a question is true through calculation, the question to be proved must first be transformed into a calculation problem, and any calculation can be described as an arithmetic circuit.

Arithmetic circuits are usually composed of constants, "addition gates", and "multiplication gates". Through the superposition of gates, we can construct complex polynomials.

The polynomial constructed by the arithmetic circuit in the figure above is: (Inp1+Inp2)*(-1) = Output

The problem in reality is extremely complicated to turn into an arithmetic circuit. We can simply understand it as: input some content, the content is transformed by the circuit, and finally output a result. Right now:

Based on the concept of arithmetic circuits, we construct an arithmetic circuit for generating proofs, namely:

The circuit contains two sets of inputs, the public input x and the secret input w. The public input x means that the content is a fixed value of the problem to be proved, which is known to both the verifier and the prover, and the secret input w means that the content is known only to the prover.

The arithmetic circuit we built is C( x, w ) = 0, that is, input x and w through the circuit, and the final output result is 0. When the prover and verifier know that the output of the circuit is 0 and the public input is x, the prover needs to prove that he knows the secret input w.

Arithmetic circuit ➡R1CS

We finally need a polynomial, but the arithmetic circuit cannot be directly converted into a polynomial, and R1CS is needed as an intermediary between the two, so the arithmetic circuit is converted into R1CS first.

R1CS, full name Rank-1 Constraints (first-order constraint system), is a language for describing circuits, which is essentially a matrix-vector equation. Specifically, R1CS is a sequence of three vectors (a,b,c), and the solution to R1CS is a vector s, where s must satisfy the equation:

Among them. represents the inner product operation.

The specific mathematical conversion here can be found in Vatalik: Quadratic Arithmetic Programs: from Zero to Hero

We only need to know that the role of **R1CS is to limit the description of each gate in the arithmetic circuit, so that the vectors between each gate satisfy the above relationship. **

R1CS➡Polynomial

After getting the medium of R1CS, we can convert it into a polynomial equivalent.

Equivalent conversions between matrices and polynomials can be performed as shown in the following figure:

polynomial

convert to matrix

According to the nature of the above equivalent transformation, for a matrix that satisfies R1CS, we can use Lagrange interpolation method to restore each coefficient of the polynomial. Based on this relationship, we can derive the R1CS matrix as a polynomial relationship, namely:

Note: A, B, C represent a polynomial respectively

A polynomial corresponds to an R1CS matrix constraint corresponding to the problem we want to prove. Through the above conversion, we can know that if the polynomials satisfy the above relationship, it means that our R1CS matrix is correct, thus indicating that the prover is in the arithmetic circuit. The secret input for is also correct.

Up to this point, our problem is simplified to: the verifier randomly selects a number x, and asks the certifier to prove that A(x) * B(x)=C(x) is established. If it is established, it means that the certifier's secret input is correct.

Conversion between polynomials

In complex arithmetic circuits, there are tens of thousands of gates, and we need to verify whether each gate satisfies the R1CS constraint. In other words, we need to verify the equality of A(x) * B(x)=C(x) several times, but the efficiency of separate verification one by one is too low. How can we verify the correctness of all gate constraints at one time? sex?

For the convenience of understanding, we introduce a P(x), let P(x) = A(x) * B(x) – C(x)

We know that any polynomial can be decomposed into linear polynomials as long as it has a solution. So we split P(x) into F(x) and H(x), namely:

Then F(x) is public, which means that there is a H(x) = P(x)/F(x), so the polynomial we want to verify finally turns into:

A(x) * B(x) – C(x): Contains the coefficients of the polynomial, known only to the prover, that is, the secret input.

F(x) : A public polynomial known to both the verifier and the prover, i.e. public input.

H(x): The prover knows it through calculation, but the verifier is unknowable.

**The final problem to be proved is: the polynomial equation A(x) * B(x) – C(x) = F(x) * H(x), holds true on all x. **

Now it is only necessary to verify the polynomial once to verify that all constraints satisfy the matrix relations.

**Here we have completed the transformation of the problem to be proved into a polynomial that only needs to be verified once, realizing the simplicity of the system. **

But the simplicity of this implementation is to shorten the verification time of the verifier, so what about the proof size?

**Simply speaking, in the proof protocol, the Merkle tree structure is used, which effectively reduces the size of the proof. **

After the entire conversion process is completed, two problems will naturally arise:

• Why convert to polynomial?

Because polynomials enable the simplicity of the proof. The problem of zero-knowledge proof is to verify that calculations satisfy multiple constraints, and polynomials can verify multiple constraints at one point. In other words, the verifier has to verify n times to confirm the problem, but now only needs to verify once to confirm the correctness of the proof with a high probability.

• Why can two polynomials A(x) * B(x) – C(x )= F(x) * H(x) be established by verifying a point on the polynomial?

This is determined by the characteristics of polynomials, that is, the calculation result of a polynomial at any point can be regarded as the representation of its unique identity. For two polynomials, they will only intersect at a finite number of points.

For the above two polynomials of degree d: A(x) * B(x) – C(x) and F(x) * H(x), if they are not equal, they will only be at most d points Intersect, that is, the solutions at d points are the same.

After completing the polynomial conversion, we will enter the polynomial proof stage.

Prove that the polynomial holds

For the sake of illustration, we use the polynomial P(x) = F(x) * H(x).

Now, the problem that the prover wants to prove is: on all x, P(x) = F(x) * H(x).

The verification process of the above polynomial by the prover and the verifier is as follows:

• The verifier chooses a random challenge point x, assuming x = s;
• After the prover receives s, calculate P(s) and H(s), and give these two values to the verifier;
• The verifier first calculates F(s), then calculates F(s) * H(s), and judges whether F(s) * H(s) = P(s) is true, and if it is true, the verification is passed.

But if we think carefully, we will find that there are some problems in the above process:

• The prover can know the information of the whole equation. If he receives a random point s, he can calculate F(s), and then construct a pair of fake P(x) and H(x), so that P(s) = F(s) * H(s) to fool the verifier.
• The prover does not use the s given by the verifier to calculate F(s) and H(s), but calculates with other values to deceive the verifier.
• The value received by the verifier is calculated by the public input and the private input of the prover. If the verifier has a large computing power, it can crack the private input of the prover.

To solve the above problems, we make the following optimizations:

• After the verifier selects a random point s, it performs homomorphic encryption on s. Homomorphic encryption means the solution calculated after encryption = the solution encrypted after calculation; in this encryption form, the prover can calculate solution, but cannot construct false P(x) and H(x).
• When the verifier chooses the challenge point s, another random parameter λ is selected to generate an additional linear relationship between s and λ. The verifier sends both s and λ after homomorphic encryption to the prover. The prover sends the proof back, and the verifier needs to verify the relationship between the random parameter λ and s in addition to verifying whether the proof is true.
• **Aiming at the problem that the verifier can crack the secret input, we can introduce ZK. ** Looking at the entire proof, we can find that during the verification process, the prover only sends the calculated polynomial value to the verifier, and the verifier can deduce the coefficient of the polynomial through the value, which is the secret input of the prover. In order to prevent the verifier from pushing back, we can select two more random numbers and add a set of values when deriving polynomials A, B, and C from R1CS, so that the restored polynomial is one order more than the original polynomial, so that the verification The reader cannot obtain the information of the original polynomial from the encrypted polynomial to realize ZK.

After optimization, we found that the proof system still requires interaction between the verifier and the prover. How can we achieve non-interaction?

Implement non-interactive

**In order to achieve non-interaction, SNARK introduces trusted settings (Setup). **

In other words, before the start of the proof, the verifier's right to choose random challenge points is handed over to a trusted third party. After the third party chooses the random parameter λ, it puts the encrypted λ in the R1CS circuit. In this way, CRS (Common Reference String, public reference string) is generated. The verifier can obtain its own Sv from the CRS, and the prover can obtain its own Sp from the CRS.

It should be noted that λ needs to be destroyed after generating Sv and Sp. If λ is leaked, it may be used to forge transactions through false verification.

zk-SNARK Workflow

After understanding the construction process of SNARK, based on the arithmetic circuit we constructed that can generate proofs, the proof process of zk-SNARK is as follows:

• Setup:(C circuit, λ)= (Sv, Sp)

Through the circuit C and the random parameter λ, the random parameters Sv and Sp used by the subsequent prover and verifier are generated.

• Prove(Sp,x,w) = Π

The prover calculates the proof Π through the random parameter Sp, the public input x, and the secret input w.

• Verify(Sv,x,Π) == (∃ w s.t. C(x,w))

The verifier verifies whether C(x,w)=0 exists through random parameter Sv, public input x and proof Π. At the same time, verify whether the proof is calculated by circuit C or not.

At this point, we have completed the explanation of the entire zk-SNARK. Let's take a look at the actual application case.

Case: Take Scroll's zk Rollup as an example

The role of the proof system is to allow the prover to convince the verifier to believe one thing;

For the zk proof system, it is necessary for the verifier to believe that the Zero-Knowledge Proof (zero-knowledge proof) calculated by the zk algorithm is true.

We take Scroll's zk Rollup as an example to illustrate the operation of the zk proof system.

Rollup refers to off-chain calculation and on-chain verification. For zk Rollup, after the transaction is executed off-chain, the prover needs to generate a zk certificate for the new state root generated after the transaction is executed, and then pass the certificate to the L1 Rollup contract for on-chain verification.

It should be noted that there are two types of blocks in zk Rollup:

• L1 Rollup block: the block submitted to Ethereum
• L2 block: a block composed of transactions submitted by users on L2

The following is the workflow of Scroll's zk Rollup:

• The user initiates a transaction in L2, the Sequencer retrieves the transaction, executes the transaction off-chain and generates an L2 block and a new state root; at the same time, submits the transaction data and the new state root to the Rollup contract on Ethereum (submitting transaction data is for data availability);
• When the L2 block is generated, the Coordinator will receive the execution track of the block from the Sequencer, and then randomly assign the track to any Roller;
• Roller converts the received execution track into circuits, and generates a validity certificate for each circuit, and then sends the certificate back to the Coordinator;
• Every time k L2 blocks are generated, the Coordinator will send an aggregation task to another Roller to aggregate the proofs of k blocks into a single aggregated proof;
• The Coordinator submits a single aggregation proof to the Rollup contract, and the Rollup contract verifies the aggregation proof combined with the previously submitted state root and transaction data. If the verification passes, the corresponding block is deemed to be finalized on Scroll.

As can be seen from the above process, Roller is the prover in the system, and the Rollup contract is the verifier. Roller generates a zk proof for transactions executed off-chain; the Rollup contract verifies the proof, and if the verification passes, the Rollup contract will directly adopt the submitted state root as its new state root.