Groth16 Proof-Size Optimality in the Pure Generic Group Model

–

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

View PDF · Download LaTeX source – covers both this statement and its information-theoretic core (see also c/0008)

Abstract

Groth’s 3-group-element SNARK (EUROCRYPT 2016) is knowledge-sound against generic adversaries and is, as far as is known, proof-size optimal. This statement asks whether that optimality actually holds in the pure generic bilinear group model: no random oracle or other channel from group elements to bits, the prover restricted to group operations on reference-string elements, and the verifier restricted to pairing product equations fixed by the statement rather than the proof. Every restriction in that description turns out to be load-bearing; see the problem hub for how dropping each one changes the answer.

The purist model

NoteDefinition (purist pairing-based argument)

A purist pairing-based non-interactive argument for a relation generator \(\mathcal{R}\) is a publicly verifiable argument system in which:

  1. the reference string is a group description plus group elements only, \(\sigma = ([\boldsymbol{\sigma}_1]_1,\, [\boldsymbol{\sigma}_2]_2,\, [\boldsymbol{\sigma}_T]_T)\);
  2. the prover is generic in Maurer’s sense (it touches group elements only through the group, pairing, and equality oracles, and never sees an encoding), so its proof is \[ \pi = \bigl([\Pi_1\boldsymbol{\sigma}_1]_1,\; [\Pi_2\boldsymbol{\sigma}_2]_2,\; [\Pi_T\boldsymbol{\sigma}_T]_T\bigr) \] with matrices depending only on \(R\), \(\phi\), and the observed equality pattern; there are no auxiliary oracles: no random oracle, no channel from group elements to bits;
  3. from \(\phi\) alone the verifier derives matrices \(T_i\) and vectors \(\boldsymbol{t}_i\) (pairing product equations with proof-independent coefficients) and accepts iff \[ [\boldsymbol{\sigma}_1;\boldsymbol{\pi}_1]_1^{\top}\, T_i\, [\boldsymbol{\sigma}_2;\boldsymbol{\pi}_2]_2 = [\boldsymbol{t}_i \cdot (\boldsymbol{\sigma}_T;\boldsymbol{\pi}_T)]_T \quad \text{for all } i . \]

The proof size is \(k_1+k_2+k_T\); completeness error is as for split NILPs. Groth16 is a sound, perfectly complete purist argument of size \((2,1,0)\).

The Conjecture

ImportantConjecture (Groth16 optimality in the pure GGM)

Every sound purist pairing-based non-interactive argument with completeness error at most \(1-1/\mathrm{poly}(\lambda)\) for a relation generator with hard decisional problems has proof size at least three. Equivalently: two-group-element purist SNARGs do not exist, and Groth16 is proof-size optimal in the pure GGM.

An affine prover strategy is a purist prover making no equality tests, so c/0008 implies this conjecture; the converse could fail only via reference strings that are not disclosure-free. A stronger form, dropping restriction (iii) entirely so the verifier can be an arbitrary Maurer-generic algorithm rather than one fixed to proof-independent pairing product equations, is also worth conjecturing but isn’t formally stated here.

This conjecture is open – no proof exists yet.

Once (an attempt at) a proof exists, add its own .tex source and compiled PDF (e.g. latex/proof.tex / pdf/proof.pdf) and link them here, following the same convention as the statement.

Formal artifact.

Not yet formalized in Lean.

This is the compiled, group-level form of c/0008, and the reason both are tracked is that they fail differently. Here the model is what carries the weight: pure generic bilinear groups, meaning no random oracle and no other channel from group elements to bits, a Maurer-style generic prover that never sees an encoding, and public verifiability. Weaken any one of those and the question changes, which is what the published near-misses do.

Since c/0008 implies this statement, a solver aiming at the stronger result should work there; this page exists because the group-level statement is the one people actually cite. See the problem page.