We can now put all the elements together. First of all, a summary of what we’ve seen in our rather long journey.

Our goal: to be able to give a succinct proof that we know some values that, used in a defined and known computation, output one or more published values. We wrote our computation as a long list of simple operations on a large set of variables, then transformed that into a sequence of constraints on those variables, expressed as equations on vectors and matrices (btw, we can think of that as a big snapshot of all the values associated to each variable used during the computation, as if each of those variables had a fixed and immutable location and couldn’t be released).

We then “transformed” that to equations on polynomials, and, given the known polynomial Z(x)=(x-1)*(x-2)*(x-3)*...*(x - num_constraints), we realized that we can prove that those constraints hold, if we can show that we know some polynomials A(x), B(x), C(x) and H(x) such that [A(x)*B(x)-C(x)]/Z(x) = H(x).

We understood that, if someone picks a x = a random P, unknown to the prover, and if the prover then shows that [A(P)*B(P)-C(P)]/Z(P) = H(P), that is a good enough proof that the computation was performed. Of course, the prover should not know P, otherwise she could build some polynomials A’(x), B’(x), C’(x) and H’(x) that solve that equation in P, just in P, and that would give her the possibility to forge a fake proof that would verify.

We have to keep this P secret then, and to do that we learnt how to map a number, belonging to a finite field, to a point on an elliptic curve. We used a homomorphic mapping, so that the prover could calculate the hidings of A(P), B(P), C(P) i.e. the corresponding points on our elliptic curve of those polynomials calculated in the secret point P, by only knowing the hidings of A1(P), A2(P), ...B1(P), B2(P),..., C1(P), C2(P) and the vector w: we just needed to multiply the hidings for the vector w and then sum them up. The vector w is the one that contains the values taken by each variable used during the computation, so it’s in fact the “witness” that the prover indeed performed the computation and knows the value of each variable. As a further reminder, the polynomials A1(x), A2(x), ...B1(x), B2(x),..., C1(x), C2(x) are the polynomial components that, when evaluated for x=1, x=2, x=3 etc, output an element of the vector that specifies a constraint, one constraint for each x.

We then get 3 points on the curve, that are the hidings of the original 3 polynomials A(x), B(x) and C(x) calculated in the secret point P.

By knowing  the hiding of 1 (the hiding of 1 is the generator g), of P (that will be P*g), of P2 (= P2*g), P3, etc the prover can also calculate the hiding of H(P), by applying to that list of hidings the same coefficients of the polynomial H(X), that she can calculate as she knows A(x), B(x) and C(x), and so she just needs to perform some polynomial algebra to calculate its coefficients: H(x)=A(x)*B(x)-C(x).

We also learnt a way to prove that the point hh[A(P)] was indeed calculated as a linear combination of the hidings of hh[A1(P)], hh[A2(P)], hh[A3(P)], ....; the prover needs to calculate and also show the hiding of hh[A(u*P)]. Of course, it’s essential that the prover does not know P, nor u, otherwise she could make up polynomials that solve the equation in just P, and also calculate the value in (u*P) of that made-up polynomial: with that the prover would have no problem forging fake proofs!

As she did for A(P), the prover should also prove that the hidings of B(P) and C(P) were calculated as linear combinations of the hidings of B1(P), B2(P),...  and of C1(P), C2(P),..., and with a similar technique, she should also prove that the very same coefficients that she applied to the hidings of A1(P), A2(P), ... to calculate the hiding of A(P), were also used both to calculate the hiding of B(P), and the one of C(P). In other words, prove that its the same w vector that is used all the time to calculate A(x), B(x) and C(x) from their original polynomial components.

Lastly, we read about a method to check, by using a pairing function, that all the equations mapped in the hidden space and calculated in P:

  • hh[A(u*P)] == hh(u) * hh[A(P)]
  • hh[B(u*P)] == hh(u) * hh[B(P)]
  • ...
  • hh[A(P)] * hh[B(P)] = hh[H(P)] * hh[Z(P)] + hh[C(P)]

hold. To use the “pairing” feature, we had to map our various hidings to two different groups, and to do that we had to build two different finite fields, and two different group generators. Some of our hidings now end up in the G1 group, and others in G2. As a result of the pairing function, the equality checks that confirm that the equations hold are performed over elements of a third group (Gt), where we further map those elements.

In conclusion, we could check that all the equations hold, without revealing any secret information, such as the vector w, used to calculate A(P), B(P), C(P) and known only to the prover, and the points P and the u*P, that nobody knows.