In part V we saw how a statement Alice would like to prove to Bob can be converted into an equivalent form in the “language of polynomials” called a Quadratic Arithmetic Program (QAP).
In this part, we show how Alice can send a very short proof to Bob showing she has a satisfying assignment to a QAP. We will use the Pinocchio Protocol of Parno, Howell, Gentry and Raykova. But first let us recall the definition of a QAP we gave last time:
A Quadratic Arithmetic Program :math:`Q` of degree :math:`d` and size :math:`m` consists of polynomials :math:`L_1,\ldots,L_m`, :math:`R_1,\ldots,R_m`, :math:`O_1,\ldots,O_m` and a target polynomial :math:`T` of degree :math:`d`.
An assignment :math:`(c_1,\ldots,c_m)` satisfies :math:`Q` if, defining
:math:`L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i` and :math:`P:=L\cdot R -O`, we have that :math:`T` divides :math:`P`.
As we saw in Part V, Alice will typically want to prove she has a satisfying assignment possessing some additional constraints, e.g. :math:`c_m=7`; but we ignore this here for simplicity, and show how to just prove knowledge of some satisfying assignment.
If Alice has a satisfying assignment it means that, defining :math:`L,R,O,P` as above, there exists a polynomial :math:`H` such that :math:`P=H\cdot T`. In particular, for any :math:`s\in\mathbb{F}_p` we have :math:`P(s)=H(s)\cdot T(s)`.
Suppose now that Alice doesn’t have a satisfying assignment, but she still constructs :math:`L,R,O,P` as above from some unsatisfying assignment :math:`(c_1,\ldots,c_m)`. Then we are guaranteed that :math:`T` does not divide :math:`P`. This means that for any polynomial :math:`H` of degree at most :math:`d`, :math:`P` and :math:`H\cdot T` will be different polynomials. Note that :math:`P` and :math:`H\cdot T` here are both of degree at most :math:`2d`.
Now we can use the famous Schwartz-Zippel Lemma that tells us that two different polynomials of degree at most :math:`2d` can agree on at most :math:`2d` points :math:`s\in\mathbb{F}_p`. Thus, if :math:`p` is much larger than :math:`2d` the probability that :math:`P(s)=H(s)\cdot T(s)` for a randomly chosen :math:`s\in\mathbb{F}_p` is very small.
This suggests the following protocol sketch to test whether Alice has a satisfying assignment.
- Alice chooses polynomials :math:`L,R,O,H` of degree at most :math:`d`.
- Bob chooses a random point :math:`s\in\mathbb{F}_p`, and computes :math:`E(T(s))`.
- Alice sends Bob the hidings of all these polynomials evaluated at :math:`s`, i.e. :math:`E(L(s)),E(R(s)),E(O(s)),E(H(s))`.
- Bob checks if the desired equation holds at :math:`s`. That is, he checks whether :math:`E(L(s)\cdot R(s)-O(s))=E(T(s)\cdot H(s))`.
Again, the point is that if Alice does not have a satisfying assignment, she will end up using polynomials where the equation does not hold identically, and thus does not hold at most choices of :math:`s`. Therefore, Bob will reject with high probability over his choice of :math:`s` in such a case.
The question is whether we have the tools to implement this sketch. The most crucial point is that Alice must choose the polynomials she will use, without knowing :math:`s`. But this is exactly the problem we solved in the verifiable blind evaluation protocol, that was developed in Parts II-IV.
Given that we have that, there are four main points that need to be addressed to turn this sketch into a zk-SNARK. We deal with two of them here, and the other two in the next part.
Making sure Alice chooses her polynomials according to an assignment
Here is an important point: If Alice doesn’t have a satisfying assignment, it doesn’t mean she can’t find any polynomials :math:`L,R,O,H` of degree at most :math:`d` with :math:`L\cdot R-O=T\cdot H`, it just means she can’t find such polynomials where :math:`L,R` and :math:`O` were “produced from an assignment”; namely, that :math:`L:=\sum_{i=1}^m c_i\cdot L_i, R:=\sum_{i=1}^m c_i\cdot R_i, O:=\sum_{i=1}^m c_i\cdot O_i` for the same :math:`(c_1,\ldots,c_m)`.
The protocol of Part IV just guarantees she is using some polynomials :math:`L,R,O` of the right degree, but not that they were produced from an assignment. This is a point where the formal proof gets a little subtle; here we sketch the solution imprecisely.
Let’s combine the polynomials :math:`L,R,O` into one polynomial :math:`F` as follows:
:math:`F=L+X^{d+1}\cdot R+X^{2(d+1)}\cdot O`
The point of multiplying :math:`R` by :math:`X^{d+1}` and :math:`O` by :math:`X^{2(d+1)}` is that the coefficients of :math:`L,R,O` “do not mix” in :math:`F`: The coefficients of :math:`1,X,\ldots,X^d` in :math:`F` are precisely the coefficients of :math:`L`, the next :math:`d+1` coefficients of :math:`X^{d+1},\ldots,X^{2d+1}` are precisely the coefficients of :math:`R`, and the last :math:`d+1` coefficients are those of :math:`O`.
Let’s combine the polynomials in the QAP definition in a similar way, defining for each :math:`i\in \{1,\ldots,m\}` a polynomial :math:`F_i` whose first :math:`d+1` coefficients are the coefficients of :math:`L_i`, followed be the coefficients of :math:`R_i` and then :math:`O_i`. That is, for each :math:`i\in \{1,\ldots,m\}` we define the polynomial
:math:`F_i=L_i+X^{d+1}\cdot R_i+X^{2(d+1)}\cdot O_i`
Note that when we sum two of the :math:`F_i`’s the :math:`L_i`, :math:`R_i`, and :math:`O_i` “sum separately”. For example, :math:`F_1+F_2 = (L_1+L_2)+X^{d+1}\cdot (R_1+R_2)+X^{2(d+1)}\cdot(O_1+O_2)`.
More generally, suppose that we had :math:`F=\sum_{i=1}^mc_i\cdot F_i` for some :math:`(c_1,\ldots,c_m)`. Then we’ll also have :math:`L=\sum_{i=1}^m c_i\cdot L_i, R=\sum_{i=1}^m c_i\cdot R_i, O=\sum_{i=1}^m c_i\cdot O_i` for the same coefficients :math:`(c_1,\ldots,c_m)`. In other words, if :math:`F` is a linear combination of the :math:`F_i`’s it means that :math:`L,R,O` were indeed produced from an assignment.
Therefore, Bob will ask Alice to prove to him that :math:`F` is a linear combination of the :math:`F_i`’s. This is done in a similar way to the protocol for verifiable evaluation:
Bob chooses a random :math:`\beta\in\mathbb{F}^*_p`, and sends to Alice the hidings :math:`E(\beta\cdot F_1(s)),\ldots,E(\beta\cdot F_m(s))`. He then asks Alice to send him the element :math:`E(\beta\cdot F(s))`. If she succeeds, an extended version of the Knowledge of Coefficient Assumption implies she knows how to write :math:`F` as a linear combination of the :math:`F_i`’s.
Adding the zero-knowledge part – concealing the assignment
In a zk-SNARK Alice wants to conceal all information about her assignment. However the hidings :math:`E(L(s)),E(R(s)),E(O(s)),E(H(s))` do provide some information about the assignment.
For example, given some other satisfying assignment :math:`(c’_1,\ldots,c’_m)` Bob could compute the corresponding :math:`L’,R’,O’,H’` and hidings :math:`E(L'(s)),E(R'(s)),E(O'(s)),E(H'(s))`. If these come out different from Alice’s hidings, he could deduce that :math:`(c’_1,\ldots,c’_m)` is not Alice’s assignment.
To avoid such information leakage about her assignment, Alice will conceal her assignment by adding a “random :math:`T`-shift” to each polynomial. That is, she chooses random :math:`\delta_1,\delta_2,\delta_3\in\mathbb{F}^*_p`, and defines :math:`L_z:=L+\delta_1\cdot T,R_z:=R+\delta_2\cdot T,O_z:=O+\delta_3\cdot T`.
Assume :math:`L,R,O` were produced from a satisfying assignment; hence, :math:`L\cdot R-O = T\cdot H` for some polynomial :math:`H`. As we’ve just added a multiple of :math:`T` everywhere, :math:`T` also divides :math:`L_z\cdot R_z-O_z`. Let’s do the calculation to see this:
:math:`L_z\cdot R_z-O_z = (L+\delta_1\cdot T)(R+\delta_2\cdot T) – O-\delta_3\cdot T` :math:`= (L\cdot R-O) + L\cdot \delta_2\cdot T + \delta_1\cdot T\cdot R + \delta_1\delta_2\cdot T^2 – \delta_3\cdot T\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;` :math:`=T\cdot (H+L\cdot \delta_2 + \delta_1\cdot R + \delta_1 \delta_2\cdot T – \delta_3)`
Thus, defining :math:`H_z=H+L\cdot\delta_2 + \delta_1\cdot R + \delta_1\delta_2\cdot T-\delta_3`, we have that :math:`L_z\cdot R_z-O_z=T\cdot H_z`. Therefore, if Alice uses the polynomials :math:`L_z,R_z,O_z,H_z` instead of :math:`L,R,O,H`, Bob will always accept.
On the other hand, these polynomials evaluated at :math:`s\in\mathbb{F}_p` with :math:`T(s)\neq 0` (which is all but :math:`d` :math:`s`’s), reveal no information about the assignment. For example, as :math:`T(s)` is non-zero and :math:`\delta_1` is random, :math:`\delta_1\cdot T(s)` is a random value, and therefore :math:`L_z(s)=L(s)+\delta_1\cdot T(s)` reveals no information about :math:`L(s)` as it is masked by this random value.
What’s left for next time?
We presented a sketch of the Pinocchio Protocol in which Alice can convince Bob she possesses a satisfying assignment for a QAP, without revealing information about that assignment. There are two main issues that still need to be resolved in order to obtain a zk-SNARK:
- In the sketch, Bob needs an HH that “supports multiplication”. For example, he needs to compute :math:`E(H(s)\cdot T(s))` from :math:`E(H(s))` and :math:`E(T(s))`. However, we have not seen so far an example of an HH that enables this. We have only seen an HH that supports addition and linear combinations.
- Throughout this series, we have discussed interactive protocols between Alice and Bob. Our final goal, though, is to enable Alice to send single-message non-interactive proofs, that are publicly verifiable – meaning that anybody seeing this single message proof will be convinced of its validity, not just Bob (who had prior communication with Alice).
Both these issues can be resolved by the use of pairings of elliptic curves, which we will discuss in the next and final part.