zk-SNARK in a nutshell(2)

In the previous article we introduced some concepts and preliminaries, in this article we will introduce how to convert a general program into a QAP problem and verify it using zk-SNARK.

Let’s first look at the following equation:

For the above equation, we can actually decompose it into the following equation of order 1:

At the same time, for some common operators, we can decompose them into the form of constraints of order 1. That is, R1CS, the full name is Rank-1 Constraint System.

Next we convert the above constraints into vector form. We let s=(1,out,x,s_1,s_2), where 1 represents the constant term in the equation, out=120, and we know that the equation has a solution x=3.

Then for the above constraints, we can have the following transformations:

we order

Then you can get s·W=s·U*s·V

Next we use the following Lagrangian interpolation polynomial to interpolate the matrix W as an example:

We take the three values (0,0,0) of the first column of W and then take their row number as the abscissa to get three points (1,0),(2,0), (3,0), and then interpolate to get:

In the same way, the remaining columns can be interpolated to obtain the following interpolation polynomial:

The same is true for matrices U and V, so we have

We can get s·W=s·U*s·V ⇔ s·W(x)=s·U(x)*s·V(x).

Next, we further transform the operation of vector s and polynomial W(x), U(x), V(x) into a QAP problem.

The abscissas selected when we perform Lagrangian interpolation above are all 1, 2, and 3. We make z(x)=(x-1)(x-2)(x-3), when x=1,2,3, z(x)=0, the QAP polynomial s·W(x)-s·U(x)*s·V(x)=0, and the order of the QAP polynomial greater than the order of z(x), so we can get a quotient polynomial h(x)=(s·W(x)-s·U(x)*s·V(x))/z(x)

That is, there are the following equivalent transformations:

So far, we have transformed the initial program into a target polynomial that divides the QAP polynomial, and review the previous QAP problem:

Known target polynomials z(x) and w_1(x), w_2(x), w_3(x), w_4(x), w_5(x); u_1(x), u_2(x), u_3(x ),u_4(x),u_5(x);v_1(x),v_2(x),v_3(x),v_4(x),v_5(x) three sets of polynomials, find the vector s, so that the target polynomial z(x) divides the QAP polynomial s·W(x)-s·U(x)*s·V(x)

Now we have three polynomials: QAP polynomial, z(x) and h(x). As we mentioned in the previous article, the knowledge of the polynomial is actually the coefficient of the polynomial.

Next, the prover performs elliptic curve encryption on the QAP polynomial s·W(x)-s·U(x)*s·V(x) coefficients a_1,…,a_m and get (a_1)·G, …,(a_m)·G, extracts the coefficients z_1,…,z_l from z(x) and performs elliptic curve encryption: (z_1)·G,…,(z_l)·G, extracts the coefficients h_1,…,h_{m-l} from h( x) and performs elliptic curve encryption: (h_1)·G,…,(h_{m-l})·G, and the verifier verifies the divisibility relationship of the encryped value through bilinear mapping, thereby verifying the correctness of the NP problem.



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store