Bilinear pairing ⇒ zk-SNARK

Free reduction · generic group model · Gro16

Statement

In an asymmetric bilinear group with a per-circuit trusted CRS, Groth’s construction is a zk-SNARK for arithmetic circuit satisfiability with perfect completeness and perfect zero-knowledge, knowledge-sound against generic bilinear-group adversaries; a proof is three group elements (two in ${\mathbb{G}}_1$, one in ${\mathbb{G}}_2$) and verification is one pairing-product equation — Gro16.

Sketch

The circuit is arithmetized as a quadratic arithmetic program; the CRS holds encodings of the QAP polynomials at a secret point $\tau$, scaled by secret $\alpha ,\beta ,\gamma ,\delta$, and the prover combines them into $A,B,C$, folding the quotient term $h(\tau )t(\tau )$ into $C$, so that one pairing-product check encodes QAP divisibility at $\tau$. A generic adversary’s proof elements are known linear combinations of CRS elements, and the verification equation holding as a polynomial identity in $\tau ,\alpha ,\beta ,\gamma ,\delta$ forces those coefficients to contain a satisfying assignment, which the extractor outputs.

Notes

• In the algebraic group model, knowledge soundness of Groth’s construction reduces to a $q$-type discrete-logarithm assumption — FKL18.
• For a circuit with $m$ wires and $n$ multiplication gates, the CRS has about $m+2n$ elements of ${\mathbb{G}}_1$ and $n$ of ${\mathbb{G}}_2$, the prover computes about $m+3n$ exponentiations in ${\mathbb{G}}_1$ and $n$ in ${\mathbb{G}}_2$, and the verifier computes one exponentiation in ${\mathbb{G}}_1$ per public input and three pairings — Gro16.