quadratic arithmetic program

A Quadratic Arithmetic Program (QAP) is the clever algebraic trick that turns a whole list of R1CS constraints into one polynomial equation. The insight is interpolation: assign each constraint an index point (say 1, 2, 3, …), and for each variable build polynomials that pass through that variable's coefficients at those indices. The columns of the R1CS matrices A, B, C become polynomials A(x), B(x), C(x); now "every constraint holds" is equivalent to saying that the single polynomial A(x)·B(x) − C(x) is zero at every constraint index.

A polynomial that is zero at the points r1, …, rm is exactly a multiple of the vanishing polynomial Z(x) = (x − r1)(x − r2)…(x − rm). So the entire constraint system collapses to one statement: there exists a quotient polynomial H(x) such that A(x)·B(x) − C(x) = H(x)·Z(x). Checking thousands of constraints has become checking one divisibility relation. This is enormously powerful because a single polynomial identity can be verified probabilistically at one random point — by the Schwartz-Zippel lemma, two different low-degree polynomials almost never agree at a random evaluation.

The QAP is what makes Groth16 succinct. The trusted setup encodes the verifier's secret random point τ "in the exponent" of group elements; the prover evaluates the QAP polynomials at τ blindly using those elements, and a pairing equation checks the divisibility A·B − C = H·Z at τ without anyone learning τ. The verifier never sees the polynomials or the witness — only a constant-size proof and a couple of pairings.