QAP

A quick recap of some of the previous posts, before we move ahead. We have a defined computation and we want to prove that we did run it. 

To do that, we expressed it in a very basic programming language, and then transformed it into a collection of numerical vectors that verify some defined equations among them.

Unfortunately, we are not done with our transformations yet: we need to convert our set of vectors into something else, to be able to handle them in the zero-knowledge, succinct, non-interactive proving technology that we are building here: a Pinocchio zk-Snark.

If you read my previous post, we ended up with a collection of different sets of vectors: exactly three vectors (c,a,b) for each constraint. We are now going to build some polynomials in x that, when evaluated for x=1, x=2, x=3, ... bind the computation variables in the same way expressed by the corresponding constraint no. 1, 2, 3, ...

As it’s getting more and more convoluted, it’s perhaps better that we start this time directly with an example. Let’s use our usual computation: 

We already know that in our case, a vector that can “solve it” is w = (1, 11, 1, 1, 2, 4, 4). In my last post, I also already calculated our c, a and b vectors . We now need to create some polynomials C1(X), C2(X), C3(X), … A1(X), A2(X), A3(X), … and B1(X), B2(X), B3(X), … in such a way that, when we multiply each of them by the elements of the w vector, we get the polynomials C(X), A(X) and B(X):

C(X) = 1 * C1(X) + 11 * C2(X) + 1 * C3(X) + 1 * C4(X) + 2 * C5(X) + 4 * C6(X) + 4 * C7(X)

A(X) = 1 * A1(X) + 11 * A2(X) + 1 * A3(X) + 1 * A4(X) + 2 * A5(X) + 4 * A6(X) + 4 * A7(X)

B(X) = 1 * B1(X) + 11 * B2(X) + 1 * B3(X) + 1 * B4(X) + 2 * B5(X) + 4 * B6(X) + 4 * B7(X)

and, for X=1, the polynomials C(1), A1(1) and B(1) output exactly the same values of the first constraint: C(1) = 1, A(1)=1, and B(1)=1, and so C(1) = A(1) * B(1).

For X=2, the polynomials A1(2), B(2) and C(2) will output the same values of the second constraint, and so forth, so that for each value of X, with X in the range [1 -  number_of_constraints], we’ll get the corresponding constraint (we all remember that a constraint is in fact one line of our unrolled computation).

Again in our example, for X=3, we’ll want  C(3) = 4, A(3)=2, and B(3)=2, and that means that C(3) = A(3) * B(3).

But how can we build our polynomials C1(X), C2(X), C3(X), … A1(X), A2(X), A3(X), … B1(X), B2(X), B3(X), … so that they have this property? To achieve that, we’ll build each of these polynomials as a sum of Lagrange polynomials: polynomials that, for each integer X in the range [1 - number_of_constraints],  have the value we need at that specific value of X, and output 0 at all other integer values of X in that range.

Again, let’s go back to our example, and start from the first constraint. For X=1 (first constraint), we want that C4(1) = 1, and that C1(1)=0, C2(1)=0, C3(1)=0, C5(1)=0, C6(1)=0, C7(1)=0.

To build C4(X) so that its value is 1 when X=1, we build first of all the component that is zero in all other points, and then make sure that it instead outputs 1 when X=1:

(please note: in reality, zk-Snarks can only handle finite field elements, so integer numbers modulo p. That means that the coefficients of the above polynomial won’t be rational numbers; for instance the coefficient (-1/6)  won’t really be -0.1666666.., but it will be the result of that same calculation when performed modulo p. I’ll write about finite field as we introduce elliptic curves).

In our example, C4(X) is associated to the variable T1, that as an output of our enrolled computation shows up only in the first constraint: T1 = x  * x. So C4(X) will have to be zero for all other X (i.e. it does not appear in any other output of any other line of the computation), and so the polynomial calculated above is complete. If we need the polynomial to assume a non-zero value in another point, we just need to add another Lagrange polynomial. For instance, in our computation the variable X, that is at the third position in our w vector, shows up in the A(X) vector both in the first constraint:

1)  T1 = x  * x

and in the third constraint:

3)  T3 = 2 * x  * z 

So, our A3(X) polynomial (the one associated to the x variable, third position in the w vector), should output “1” when X=1 (first constraint, T1 = 1*x  * 1*x), and it should output “2” when X=3 (third constraint, T3 = 2*x  * 1*z). So the polynomial will be: 

Well done: we have all these nice polynomials A1(X), A2(X), … A7(X) - as many as the variables used in the computation + 1, as well as the polynomials B1(X), B2(X), … B7(X) and  C1(X), C2(X), … C7(X). The degree of the polynomials will be at most: number_of_constraints - 1; in our case, it will be degree 3, e.g. (-1/6)*X³ + 3/2 *X² + ... 

If we now sum up each of them for the elements of the w vector, we get the C(X), A(X) and B(X) polynomials that we were looking for: 

C(X) = 1 * C1(x) + 11 * C2(x) + 1 * C3(X) + 1 * C4(X) + 2 * C5(X) + 4 * C6(X) + 4*C7(X)

A(X) = 1 * A1(x) + 11 * A2(x) + 1 * A3(X) + 1 * A4(X) + 2 * A5(X) + 4 * A6(X) + 4*A7(X)

B(X) = 1 * B1(x) + 11 * B2(x) + 1 * B3(X) + 1 * B4(X) + 2 * B5(X) + 4 * B6(X) + 4*B7(X)

A note: the above polynomials will really be calculated, i.e. the software that implements our Pinocchio zk-Snark technology has to multiply each coefficient of each polynomial component for its associated variable value, and then sum all of them up together, to get the coefficients that define the polynomials A(X), B(X) and C(X). They will be polynomials of degree (number_of_constraints - 1), that can be represented in software as arrays of coefficients.

Recap: the C(X), A(X) and B(X) polynomials have been built in such a way that, for X=1, X=2, X=3 and so on until X=number_of_constraints:

C(X) = A(X) * B(X)

And so we can write:

P(X) = A(X)*B(X) - C(X) = 0

The above in turn means that P(X) is a polynomial that can be divided by

 Z(X)=(X-1)(X-2)(X-3)....(X-number_of_constraints). In our example:

 Z(X)=(X-1)(X-2)(X-3)(X-4) =X^4 - 10*X^3 + 35*X^2 - 50*X + 24 

P(X) can be divided by Z(X), because Z(X) is the minimal polynomial that goes to 0 for X=1, X=2, X=3,... and so P(X) is a multiple of it.

If P(X) can be divided by Z(X), then it exists H(X) so that  P(X)/Z(X) = [C(X) - A(X)*B(X)] / Z(X) = H(X)

with no remainder.    

And this is the final step that covers how we are going to represent the computation we want to prove inside our zk-Snark: everyone (both provers and verifiers) will have to know the coefficients of C1(X), C2(X), C3(X), … A1(X), A2(X), A3(X), … B1(X), B2(X), B3(X),... as these polynomials nail the computation being proved; they will be made available by the author of the circuit. The polynomial Z(X) will also be known by everyone, easily calculated once the number of constraints is set.

The prover, when creating a proof, will have to compute the “unrolled” computation, and build the vector w as each variable is calculated. The prover will also have to calculate P(X)=A(X)*B(X) - C(X), by using the known polynomial components C1(X), C2(X)… A1(X), A2(X), … B1(X), B2(X)... and applying the w vector to them. With that, he will calculate the coefficients of H(X), by dividing P(X) by  Z(X). With all this information available, the prover can prove that she performed the computation. But she will now need to find a way to prove knowledge of w and H(X) without revealing them, as we want a zero-knowledge system. So, since there’s a need to hide information, there is a obviously a need for some serious cryptography...