Groth16

1. R1CS and QAP: turning computation into a checkable math problem

1.1. Step 1: Break every computation into adds and multiplies (Arithmetic Circuit)

First convert the program you want to prove into an Arithmetic Circuit: a graph of simple gates. Logic, branches, and loops still bottom out as many additions and multiplications.

Take proving $x^3 + x + 5 == 35$. The prover knows the secret $x=3$. That computation splits into gates like:

$gate 1: sym1 = x * x$ $gate 2: y = sym1 * x$ $gate 3: sym2 = y + x$ $gate 4: out = sym2 + 5$ $gate 5: out == 35$ (constraint)

That flow of simple ops is the arithmetic circuit. The prover must show each gate computed correctly.

1.2. Step 2: Constraint matrices (A, B, C) and the vector equation (R1CS)

R1CS folds every gate constraint into one vector equation shape: $((a · s) * (b · s) - (c · s) = 0)$. Gates stay separate steps; some multiply, some add.

1. Solution vector ($s$)

Pack every variable into one long vector. It is the full computation state, and the prover knows every entry.

$s = [1, x, out, sym1, y, sym2]$ (the leading $1$ is a dummy for constants, $x$ is the private witness, $out$ is the public output). With $x=3$, a correct solution is $s = [1, 3, 35, 9, 27, 30]$.

2. Turn each gate into a vector equation

For each gate, build three vectors $a$, $b$, $c$ that pick variables out of $s$ so the multiply/add relation holds. That produces constraint matrices A, B, C. For $gate 1: sym1 = x * x$:

$a = [0, 1, 0, 0, 0, 0]$ (pick $x$) $b = [0, 1, 0, 0, 0, 0]$ (pick $x$) $c = [0, 0, 0, 1, 0, 0]$ (pick $sym1$)

Do this for every gate and you get one $(a_i, b_i, c_i)$ triple per gate. That collection is R1CS.

$(a · s) * (b · s) = (c · s)$ holds ($(x) * (x) = (sym1)$). Stack those rows into matrices $A$, $B$, $C$. R1CS then asks for an $s$ such that $(A · s) ◦ (B · s) - (C · s) = 0$ (element-wise product).

You still have to check one equation per gate, so this form alone is expensive.

1.3. Step 3: Compress many constraints into one polynomial (QAP)

QAP compresses R1CS into a single polynomial-divisibility check.

Idea: if two degree-$d$ polynomials agree at $n$ distinct points and $n > d$, they are the same polynomial.

Process

1. Assign coordinates: give each R1CS constraint an x-coordinate (gate 1 at $x=1$, gate 2 at $x=2$, …).
2. Matrices to polynomials: Lagrange-interpolate each column of $A, B, C$ into a polynomial (column $j$ of $A$ becomes $A_j(x)$, with $A_j(k) = A_{kj}$).
3. Define the combined polynomials with solution entries $s_j$ as coefficients:

$A(X) = Σ s_j·A_j(X)$ $B(X) = Σ s_j·B_j(X)$ $C(X) = Σ s_j·C_j(X)$

Evaluating at $X=k$ recovers the k-th R1CS inner products: $A(k) = a_k · s$, and likewise for B and C.

4. Target polynomial $T(X)$: roots at every constraint coordinate:

$T(X) = (X-1)(X-2)...(X-n)$

5. QAP form: all R1CS constraints hold iff $P(X) = A(X)·B(X) - C(X)$ vanishes on $\{1,…,n\}$, iff $T(X)$ divides $P(X)$: $A(X)·B(X) - C(X) = H(X) · T(X)$.

The prover now only needs to show: “I know an $s$ that builds $A, B, C$ such that a quotient $H(X)$ exists.” Many constraints became one division check.

2. NIZK (Non-Interactive Zero-Knowledge)

You still have to prove the QAP without revealing $s$ and without chatting with the verifier. NIZK does that with a CRS (Common Reference String) from a Trusted Setup.

After the reduction, the prover must convince a verifier that $A(X)·B(X) - C(X) = H(X)·T(X)$ holds for polynomials they know.

Trusted Setup

CRS generation has to be honest. A malicious setup can break the whole system. That ceremony is the Trusted Setup.

Groth16 uses secret scalars such as:

$τ$ (tau): secret evaluation point for the polynomials $α$ (alpha), $β$ (beta): consistency / zero-knowledge $δ$ (delta), $γ$ (gamma): randomization and finishing the verification equation

They are sampled from a strong RNG.

After key material is derived, those secrets must be destroyed forever — the toxic waste. Leak them and anyone can forge proofs.

Role of the CRS

With a CRS, the prover can send one proof and the verifier decides alone. The CRS holds encrypted evaluations at the secret $τ$. The proving key includes values like $[τ⁰]₁, [τ¹]₁, ..., [τⁿ]₁$ (points in elliptic-curve group G₁).

So the prover never learns $τ$, yet can form $[P(τ)]₁$ for any degree-$≤n-1$ polynomial $P$ by linear combination of those powers. Proving key plus verification key together are the CRS.

The prover holds the proving key; the verifier holds the verification key. The prover must prove the QAP at secret $τ$ while hiding witness w.

1. Prover computation

   • Build $A, B, C, H$ from the private witness $w$.
   • Using encrypted powers in $pk$, compute $[A(τ)]₁$, $[B(τ)]₂$, $[C(τ)]₁$, $[H(τ)]₁$.
   • Homomorphism of the curve group lets $[P(τ)]₁ = p₀[τ⁰]₁ + p₁[τ¹]₁ + …$ without knowing $τ$.
   • Package those into the final proof $π$.

2. Verifier

   • Check one pairing equation with $π$ and $vk$.
   • That equation tests $A(τ)·B(τ) - C(τ) = H(τ)·T(τ)$ in the encrypted domain.

Toxic waste

Once the CRS exists, destroy $τ, α, β, δ, γ$ permanently. Anyone who keeps them can forge $H(X)$ and mint fake proofs.

Production systems use Multi-Party Computation (MPC) — Zcash-style ceremonies. Each participant contributes a secret share, updates the CRS, and deletes their share. If at least one participant is honest and destroys their share, the full secret is unknown to everyone.

3. Groth16 proof shape: three group elements

The goal is to show the QAP holds at secret $τ$. Submitting the polynomials in the clear is not an option.

Groth16 compresses that information into three curve points $π = ([A]₁, [C]₁, [B]₂)$. They are cryptographic commitments that only become meaningful inside the verification equation.

3.1. [A]₁ and [B]₂

These commit to $A(X)$ and $B(X)$, which carry most of the private witness.

[A]₁ (G₁): commitment to $A(X)$

Built as a linear combination of proving-key material:

$A₁ = α + A(τ) + r·δ$

• $A(τ)$: evaluation of the prover’s $A(X)$ at $τ$ — the core claim.
• $α$: blocks knowledge-of-coefficient style forgeries and forces consistency.
• $r·δ$: fresh prover randomness $r$ times setup secret $δ$, so identical statements produce different $[A]₁$ (zero knowledge).

[B]₂ (G₂): commitment to $B(X)$

Same structure, but in G₂:

$B₂ = β + B(τ) + s·δ$

• $β$, $s$ play the roles of $α$, $r$ on G₂.
• Why two groups? Pairing $e(G₁, G₂)$ needs one element from each. Splitting $[A]₁$ and $[B]₂$ lets verification multiply $A(τ)·B(τ)$ in the exponent via pairing.

3.2. [C]₁

$[C]₁$ ties $[A]₁$ and $[B]₂$ to an honest QAP. Without it, a prover could pick unrelated $A$ and $B$ and still hope to pass.

Its job is to cancel garbage terms in the verification equation and leave the QAP identity.

Conceptually:

$C₁ = s·A(τ) + r·B(τ) + r·s·δ + L(x, τ) + H(τ)·T(τ)$ (real formulas also scale by setup secrets $γ$, $δ$).

• $s·A(τ)$ and $r·B(τ)$ cancel cross terms from $e([A]₁, [B]₂)$.
• $r·s·δ$ cancels the product of the randomization limbs.
• $L(x, τ)$ covers the public-input slice of $C(X)$.
• $H(τ)·T(τ)$ is the QAP quotient claim.

In short:

• [A]₁: encrypted $A(τ)$ with ZK randomness
• [B]₂: encrypted $B(τ)$ with ZK randomness, in the other group for pairing
• [C]₁: auxiliary proof that those commitments are consistent with a real quotient $H$

4. Verification: one equation, three pairings

Goal

Check that $π = ([A]₁, [C]₁, [B]₂)$ really witnesses $A(X)·B(X) - C(X) = H(X)·T(X)$ at $τ$.

4.1. Pairing

$e: G₁ × G₂ → Gᴛ$

Bilinearity:

$e([a]₁, [b]₂) = e(a·G₁, b·G₂) = e(G₁, G₂)^{(a·b)}$ $e([a]₁ + [c]₁, [b]₂) = e([a]₁, [b]₂) · e([c]₁, [b]₂)$

You never open $a$ or $b$, yet pairing recovers the product in the target-group exponent — enough to check $A(τ)·B(τ)$.

4.2. Verification equation

$e(A, B) = e(α, β) · e(L(x), γ) · e(C, δ)$

1. LHS: the prover’s claim

With $A = α + A(τ) + r·δ$ and $B = β + B(τ) + s·δ$, bilinearity expands $e(A, B)$ into many exponent terms, including the desired $A(τ)B(τ)$ plus auxiliary junk.

2. RHS: rebuild QAP pieces and cancel junk

• $e(α, β)$ matches the $αβ$ term; $vk$ ships $[α]₁$, $[β]₂$.
• $e(L(x), γ)$ handles public inputs; the verifier builds $[L(x, τ)]₁$ from $vk$ and $x$.
• $e(C, δ)$ uses the prover’s $C$, which was built to cancel the LHS auxiliaries and supply $H(τ)T(τ)$.

After cancellation, the surviving relation is equivalent to:

$A(τ)B(τ) - C(τ) = H(τ)T(τ)$

One pairing equation is enough to conclude the prover knows a witness whose derived polynomials satisfy QAP.

4.3. Cost

• Constant-time verification: three pairings, independent of circuit size $n$ or $m$. That is the “succinct” part.
• Public inputs (MSM): time grows with public-input length $l$ when forming $L(x, τ)$, but Multi-Scalar Multiplication keeps that cheaper than $l$ naive curve adds.