Knowledge of coefficient

If you read and spent some time on the previous posts on the blog, you should know that a proof will be the hidings of A(P), B(P), C(P), and H(P), all calculated in the hidden space by using the hidings of the “building block” polynomials.

The hidings that compose the proof prove that the equations hold, i.e. they prove that

 hh[A(P)] * hh[B(P)] - hh[C(P)] / hh[Z(P)] = hh[H(P)].

Now, we see all these fancy formulas for these hidings: hh[A(P)], hh[B(P)],  hh[C(P)],  hh[H(P)], ... but in reality they are just numbers: nobody can tell if we really calculated them as hh(A(X)) in P, hh(B(X)) in P, etc. or if we just made those numbers up. We need to make the proof more robust, to make sure that the prover can’t just pick up some numbers that “work”. For this purpose, we are going to use the “knowledge of exponent” (or “knowledge of coefficient” as it’s often called in the zero-knowledge space). Before introducing it, let’s take a closer look at the problem we have to solve now.

What we need to prove is that hh[A(P)] is really the hiding of A(X) in P and we need to prove this in the hidden space, since we don’t know P (nobody knows it!).

How can we do that? Well, we’ll prove that hh[A(P)] is a linear combination of  hh(1), hh[A1(P)], hh[A2(P)], hh[A3(P)], …, i.e. the linear combination of the hidings of the polynomials that, multiplied by the coefficients of w and summed up, output our A(X)!

Similarly, we’ll prove that hh[B(P)] is a linear combination of the hidings of B1(X), B2(X), .. in P, and the same for hh[C(P)] and hh[H(P)]. Good news: we won’t need to prove anything about hh[Z(P)], because Z(X) is a known polynomial:  hh[Z(P)] will be calculated as needed by applying Z(X) coefficients to the usual set-up defined hidings.

Please note, our proofs won’t be “full proofs”: we are evaluating the polynomials in a single point, so it could still be that the prover guesses these polynomials, and that he is so lucky that by chance all of them output the same values of the good ones when calculated in P. In reality, the probability of that happening, not knowing P, is practically zero (i.e. negligible).

Now, proving that the hidings of the polynomials are a linear combination of the hidings of the original elements is not enough. We know that 

and that the same vector w=(1,w1,w2,w3, ...)  is used to calculate in the same way B(X) and C(X).  Well, the use of the very same vector w needs to be proven too!

We need then to prove that the same vector w=(1,w1,w2,w3, ...), applied by the prover to hh[A1(P)], hh[A2(P)], hh[A3(P)], ... to get to hh[A(P)], was also used in the same way to get hh[B(P)] from hh[B1(P)], hh[B2(P)], hh[B3(P)], … and to get hh[C(P)] from hh[C1(P)], hh[C2(P)], hh[C3(P)], … In other words, we have to prove that the same coefficients were applied to all the polynomials.

That can be accomplished by calculating the hidings of the new polynomials K1(P) = A1(P)+B1(P)+C1(P),  K2(P) = A2(P) +B2(P)+C2(P), … and then multiplying them by the w vector, in the same way we did for the other ones, to get hh[K(P)]. With that, we’ll have to prove that hh[K(P)] is equivalent to the sums of the hidings of A(P), B(P) and C(P), and that means that the same w was used.

Ok, all this complexity and we haven’t started addressing the problem yet; we know what we have to prove, but we don’t know how to do it!! All we know, at this point, is that the prover needs to prove that each of the hidings that she provides come from real knowledge of the original polynomials. We also know that in the “hidden space”, hidings will be just numbers, as the polynomials are evaluated in a specific, secret point. So, it’s about time we introduce the property of “knowledge of coefficient”, that’ll do the trick!

The basic concept is: if I know a point P, and another point B=u*P, and I keep those values secret and only reveal hh(P) and hh(B), well then if someone else, who does not know P nor B, shows two values hh(R) and hh(F) such that hh(R) = hh(u*R), i.e. F=u*R, then the only way that this guy could do this is by multiplying both hh(P) and hh(B), the only two values that he knows, by the same number (any number, as long as he multiplied each of them by the same one).

This property can be extended to a linear combination, i.e. a polynomial: if we publicly disclose the hidings hh(1), hh(P), hh(P²), hh(P³), … and hh(u*P), hh[u*P)²], hh[u*P)³], ... , we know that if someone calculates Y1 = hh[A(P)] = 1*hh[A1(P)] + w1*hh[A2(P)] + w2*hh[A3(P)] + … and Y2 = hh[A(u*P)] = 1*hh[A1(u*P)] + w1*hh[A2(u*P)] + w2*hh[A3(u*P)] + …, and shows us just the results Y1 and Y2, if Y2 = u * Y1, then we know that both Y1 and Y2 are calculated as the same linear combination of the two sets of the provided hidings. So, Y1 =  hh[A(P)], i.e.  the hiding of A(X) calculated in P, is indeed a linear combination of the hidings hh[A1(P)], hh[A2(P)], hh[A3(P)], …: so it’s the hiding of [coeff0 * A1(P) + coeff1 * A2(P) + coeff2 * A3(P) + …]  for some coeff0, coeff1, coeff2, ...

Using the same technique, we can prove that the hidings of  B(P) is the hiding of a linear combination of the hidings of B1(P), B2(P), B3(P), … and the same for C(P).

Finally, by applying the same approach to K1(P)=A1(P)+B1(P)+C1(P), K2=A2(P)+B2(P)+C3(P), … and by checking that hh[K(P)] = coeff0*hh[K1(P)] +coeff1*hh[K2(P)] + coeff2*hh[K3(P)] + … = hh[A(P)] + hh[B(P)] + hh[C(P)] , we’ll know that the same coefficients coeff0, coeff1, coeff2, … used to calculate hh[K(P)] were also used, the very same ones,  to also calculate hh[A(P)], hh[B(P)] and hh[C(P)]. Those coefficients are our vector w.

And nobody we’ll be able to make up those numbers any more!