Theorem 1 — Knowledge Soundness

Groth16: extracting a witness from any successful affine prover
About this walkthrough

What you're looking at. Groth's theorem proves knowledge soundness: any prover that outputs an accepting (A, B, C) as an affine combination of the CRS elements yields a valid QAP witness. The walkthrough does this constructively — each step forces another coefficient of the polynomial identity to match, progressively pinning down the form of A, B, C.

Strategy. Treat A, B, C as formal Laurent polynomials in the indeterminates . The verifier equation must hold as a polynomial identity; Schwartz–Zippel (at setup) means it holds on a uniformly random point only if the polynomials are equal. We then compare coefficients monomial-by-monomial.

Omissions. The ZK randomizers r, s added to A, B at honest proving time are irrelevant here — an adversarial affine prover can pick any coefficients, so we absorb r, s into the generic Aδ, Bδ terms.

Common Reference String
Coefficients matched so far
A — after this step
B — after this step
C — after this step
prev/next  ·  Home End jump to start/end