Zk-SNARKs: Under the Hood. This is the third part of a series of… | by Vitalik Buterin

Remember that the solution to a QAP is a set of polynomials (A, B, C) such that A(x) * B(x) – C(x) = H(x) * Z(x), where:

• A is a linear combination of a set of polynomials {A_1…A_m}
• B is the linear combination of {B_1…B_m} with the same coefficients
• C is a linear combination of {C_1…C_m} with the same coefficients

The sets {A_1…A_m}, {B_1…B_m} and {C_1…C_m} and the polynomial Z are part of the problem statement.

However, in most real-world cases, A, B and C are extremely large; for something with many thousands of circuit gates like a hash function, the polynomials (and the factors for the linear combinations) may have many thousands of terms. Hence, instead of having the prover provide the linear combinations directly, we are going to use the trick that we introduced above to have the prover prove that they are providing something which is a linear combination, but without revealing anything else.

You might have noticed that the trick above works on elliptic curve points, not polynomials. Hence, what actually happens is that we add the following values to the trusted setup:

• G * A_1(t), G * A_1(t) * k_a
• G * A_2(t), G * A_2(t) * k_a
• …
• G * B_1(t), G * B_1(t) * k_b
• G * B_2(t), G * B_2(t) * k_b
• …
• G * C_1(t), G * C_1(t) * k_c
• G * C_2(t), G * C_2(t) * k_c
• …

You can think of t as a “secret point” at which the polynomial is evaluated. G is a “generator” (some random elliptic curve point that is specified as part of the protocol) and t, k_a, k_b and k_c are “toxic waste”, numbers that absolutely must be deleted at all costs, or else whoever has them will be able to make fake proofs. Now, if someone gives you a pair of points P, Q such that P * k_a = Q (reminder: we don’t need k_a to check this, as we can do a pairing check), then you know that what they are giving you is a linear combination of A_i polynomials evaluated at t.

Hence, so far the prover must give:

• π_a = G * A(t), π’_a = G * A(t) * k_a
• π_b = G * B(t), π’_b = G * B(t) * k_b
• π_c = G * C(t), π’_c = G * C(t) * k_c

Note that the prover doesn’t actually need to know (and shouldn’t know!) t, k_a, k_b or k_c to compute these values; rather, the prover should be able to compute these values just from the points that we’re adding to the trusted setup.