Before introducing the cryptographic tools we need, just a brief recap of some of my previous posts. We can express an instance of a problem as three vectors of polynomials, and a solution to that computation as a vector of values.
With a series of transformations (“reductions”), we can convert a computation that we want to prove execution of to this polynomial format. Knowing all the values of the solution vector w actually means knowing the values of each variable used during our computation. If a polynomial H(X) exists, as defined in the QAP post, it means that all the variables were calculated as defined by the computations, i.e. that all constraints were met. Nothing so far is “zero knowledge”: we need some technique to hide information.
The first ingredient is, not unexpectedly, a one-way function: we can call it hh(X). hh(X) is like a hashing function, but it also supports addition and multiplication, i.e. it maps X to a “space” where the operations of addition and multiplication are defined, and in there it preserves the structure of linear combinations of the inputs. So, hh(a*X+b*Z) = a*hh(X)+b*xx(Z).
That’s cool, but how are we going to use this one-way function? Well, we’ll use it to prove that we know the H(X) polynomial we calculated in the QAP post. But we’ll do that without exposing the coefficients of H(X): instead, we’ll disclose the value of H(X) evaluated in a randomly chosen secret point P and mapped into this new space. This is critical: to make sure that the prover cannot make up the proof, we need to be sure that he does not know the value of the secret point P: P must be secret, calculated once by someone, deleted and totally forgotten, unknown to the world!
… I can pretty much guess what you’re thinking: how can we evaluate H(P) and map it to this hidden space, if nobody knows P? We can do that because multiplications of terms for their coefficients, and their sums, maintain the same “meaning” in the new space, so we can calculate the polynomial in the new space by applying the same linear combination expressed by the original polynomial to the hidings hh(1), hh(P), hh(P2), hh(P3), …
Of course to do that, the prover needs to know the hidings hh(1), hh(P), hh(P2), hh(P3), … they will have to be provided, and that explains the need, in our zk-Snark, of a “trusted setup”, I’ll write a specific post about that when I have time, I guess towards the end of the protocol presentation.
Before the prover proves anything then, someone must have randomly sampled a point P, calculated the elements hh(1), hh(P), hh(P2), hh(P3), … (as many as the number of constraints - 1), made them publicly available, deleted and cancelled from memory the point P. These hidings are made available as part of the CRS, the common reference string, or “structured reference string” as it’s now called (as promised, more on this to come).
Putting things together, to give proof that we performed a given computation, we’ll prove that we know the polynomials A(X), B(X), C(X), and H(X) by mapping those polynomials, calculated in a secret point P, into the hiding space. The verifier will verify the proof by checking that the hidings of [A(P)*B(P)-C(P)], divided by the hidings of Z(P), is equal to the hiding of H(P). To verify this, without revealing secrets, we’ll need a new ingredient, called “pairing”, which will have its own dedicated post.
One last thing before we move on: why does the the point P need to be secret? Well, if it’s not secret, a malicious prover could make up other polynomials A1'(X), A2'(X), A3'(X), … B1'(X),.. C1'(X),... and make up a vector w' such that A'(X)*B'(X) - C'(X) only in that point P. That wouldn’t be too difficult to achieve, so the prover could in fact make up false proofs. By keeping P secret, we are (statistically) proving that the polynomials hold that equation in ANY point, not just in that point P.