Some last-minute obfuscation elements
In a zk-Snark, the prover wants to fully hide its vector w. However, the mapping to the elliptic curve of the A, B, C and H polynomials in P still provides some information about it.
For instance, by calculating them for another vector w’, someone could see that, if the mapped points are different, then w and w’ are also different. To avoid this, the Pinocchio protocol asks the prover to add a random “Z shift” to each polynomial. In more mathematical language, the prover chooses random δ1 , δ2 and δ3. Then, when calculating A(x), she will add δ1 ⋅ Z(x) to it. She will do the same for B(x) and C(z), by multiplying Z(x) respectively by δ2 and δ3 and then adding these new components.
The resulting P’(x) polynomial will be
P’ = A’⋅B’ - C’ = ( A + δ1 ⋅ Z ) ( B + δ2 ⋅ Z ) - C - δ3 ⋅ C = ( A⋅B - C) + δ2⋅A⋅Z + δ1⋅B⋅Z + δ1⋅ δ2⋅Z^2 - δ3⋅Z = Z ⋅ ( H + δ2⋅A + δ1⋅B + δ1⋅δ2⋅Z - δ3)
and that means that, if we define H’ = H + δ2⋅A + δ1⋅B + δ1⋅δ2⋅Z - δ3, we have that A’ ⋅ B’ - C’ = Z ⋅ H’.
The verifier will then accept this, as Z divides P’, and now the prover reveals no information about w!
Trusted set-up
We can now look at the last ingredient, the “trusted set-up”. A trusted set-up is needed to offer to the provers and to the verifiers all the basic building blocks in the hidden space to create and verify proofs. These basic elements are generated by mapping to points of the elliptic curve some randomly sampled numbers, that then must be discarded and forgotten, leaving no track of them. When used in production systems relying on no trusted third party, we clearly need a robust way to randomly select these secrets values, while reducing the risk that someone could get to know them to a minimum. Usually that is accomplished through “ceremonies”, and the most famous of them is still the one that generated the first public parameters for zcash, or through protocols, where the generation of the parameters is iteratively calculated one participant after the other. The typical underlying assumption of these techniques is that, if at least one participant is honest and does not collude with the other ones, no one will be able to discover the original parameters. A folkloristic note: you can find published videos of past ceremonies where laptops were destroyed or thrown into the sea after having delivered their cycle of calculation; this helped turn these events into modern myth. Behind the modern mythology, though, we actually have some challenging math, so let’s take a look at the output of these ceremonies!
Common (or “Structured”) Reference String
As we now know, he prover needs to know the hidings of A1(P), A2(P), … A1(u*P), u*A2(u*P), and the same for B and C. With them, by knowing the vector w, the prover can calculate the hidings of A(P), A(u*P), … She also needs to know the hidings of 1, P, P2, P3, … With these, after having calculated the polynomial H(x), by using the same coefficients she can calculate the hiding of H(P).
The verifier will instead need some of the hidings related to the public input, so that he can calculate a defined input-related part of the proof just before verifying it, in a way that the proof is bound to those public inputs. He will also need to know the hidings of u, and the hidings of Z(P), to check pairing.
All the above elements, needed by the prover and the verifier, are made available at set-up as a “proving key” pk, and a “verifying key” vk; without them, nobody will be able to create or verify proofs.
It’s evident that the set-up phase is a very delicate one, since it requires sampling the point P, and various “u” values (“u” is not just one, we’ll use different ones for the different polynomials) as well as the δ1 , δ2 and δ3 values mentioned above. At set-up, all these random field elements get mapped to points of the elliptic curve in one of the two G1 or G2 groups, and then saved. The originating values need to be immediately deleted: no tracks should be kept (“toxic waste”). The proving key and verifying key just produced, are made available to provers and verifiers as a sequence of points packed into a “Common Reference String” (or “Structured Reference String” as it’s now called).
The prover Alice, only needs to know the proving key, and the polynomials A(x), B(x) and C(x). She then performs all the steps of the computation and populates the vector w with all the values taken in the process. With all the above, she can now compute a succinct proof, made of several elements of the groups G1 (seven, to be precise) and G2 (just one, the one associated to the coefficients of the B(x) polynomial in P).
The verifier only needs the proof, the verifying key and the public inputs (if any) to verify the proof. He will then perform a total of 5 equality of pairings calculations: one for each of the three A, B and C polynomials, one to verify the use of the same “vector w” coefficients when calculating the A, B and C polynomials, and at last the one to check divisibility of P’(P) by Z(P)
These 5 equalities require calculating 12 paring mappings. If all 5 equalities are met, the proof is verified!