“On the Size of Pairing-Based Non-Interactive Arguments” is a paper by Jens Groth (University College London), published at EUROCRYPT 2016. It presents what became known as the Groth16 zk-SNARK — the most efficient (smallest proofs, fastest verification) general-purpose non-interactive zero-knowledge proof system known as of its publication.

Groth16 proofs consist of just 3 elliptic curve group elements (~200 bytes for BLS12-381) and can be verified with a single pairing equation (roughly 3 pairing computations). This efficiency made Groth16 the practical choice for production zero-knowledge systems, powering Zcash Sapling, Tornado Cash, and many early ZK-Rollup circuits.

> PDF hosting: The paper is at eprint.iacr.org/2016/260 (IACR ePrint archive).

---

Publication and Context

Jens Groth had been working on non-interactive zero-knowledge proofs for years before 2016. The academic field of SNARKs had advanced significantly through Groth and Sahai (2008), Gennaro et al.’s “Quadratic Span Programs” (2013), and Parno et al.’s “Pinocchio” compiler (2013). Each successive construction had improved efficiency.

Groth16 achieved an optimum: it can be proved that 3 group elements is the minimum proof size for any SNARK based on the underlying “knowledge soundness” assumption (assuming a knowledge extractor exists). In this sense, Groth16 is optimal — any other SNARK of the same security model will have at least as large proofs.

Limitations known at publication:

1. Requires a circuit-specific trusted setup (CRS: Common Reference String)
2. Security requires the “knowledge of exponent assumption” — not reducible to standard discrete logarithm hardness

---

zk-SNARKs: Background

A zk-SNARK (zero-knowledge Succinct Non-interactive ARgument of Knowledge) is a proof system with three properties:

• Zero-knowledge: Proof reveals nothing about the witness (private inputs)
• Succinctness: Proof size is small (polylogarithmic or constant in computation size)
• Non-interactive: Prover sends one message; no back-and-forth with verifier

Groth16 achieves these properties for any computation expressible as an arithmetic circuit (additions and multiplications over a finite field).

---

How Groth16 Works (Simplified)

Step 1: Arithmetic Circuit to R1CS

The computation to be proved is compiled to a Rank-1 Constraint System (R1CS): a set of equations of the form (a · b = c) over a field. This is done by the circuit compiler (e.g., Circom, Bellman).

Step 2: R1CS to QAP

The R1CS is converted to a Quadratic Arithmetic Program (QAP) — polynomials that encode the constraint system. The prover will produce a polynomial evaluation proof.

Step 3: Trusted Setup

Given the QAP, a trusted setup generates:

• Proving key (pk): Allows honest provers to generate proofs
• Verification key (vk): Allows anyone to verify proofs (tiny: a few group elements)

The toxic waste (random scalars used in setup) must be destroyed after.

Step 4: Proof Generation

The prover, knowing the private witness (private inputs that make the circuit satisfied), computes three elliptic curve group elements: $(A, B, C)$ — the Groth16 proof.

Step 5: Verification

The verifier checks:

$$e(A, B) = e(alpha, beta) cdot e(sum_{i=0}^{l} a_i u_i(tau) cdot G_1, gamma) cdot e(C, delta)$$

This is three bilinear pairings — fast to compute.

---

Proof Size and Verification Comparison

Proving System	Proof Size	Trusted Setup	Post-Quantum
Groth16	~200 bytes (3 elements)	Circuit-specific	No
PLONK	~400 bytes (6+ elements)	Universal	No
STARKs	~100 KB	None	Yes
Bulletproofs	~1 KB (log N)	None	No (DLOG)
Marlin	~400 bytes	Universal	No

Groth16 has the smallest proofs and fastest verification — significant advantages for on-chain verification where gas costs are proportional to computation.

---

Circuit-Specific Setup: The Main Limitation

Unlike PLONK (which has a universal setup), Groth16 requires a fresh trusted setup for each distinct circuit. For Zcash, this meant separate ceremonies for the Spend circuit and Output circuit. For any new application (a new zk-application or a circuit modification), a new ceremony is needed.

This was a significant operational overhead that motivated the development of universal SNARKs (PLONK, Marlin) which require only one setup for any circuit up to a maximum size.

---

Production Use

Zcash Sapling: Uses Groth16 over BLS12-381 for its Spend and Output circuits

Tornado Cash: Uses Groth16 over BN254 (a.k.a. alt_bn128) for its deposit/withdrawal circuit

Hermez (original Polygon zkEVM): Used Groth16 for its batch proof

Filecoin: Uses Groth16 for Proof-of-Replication and Proof-of-Spacetime

Ethereum precompile: Ethereum includes native EVM precompiles (at 0x06–0x08) for BN254 elliptic curve operations, enabling efficient Groth16 verification on Ethereum for ~70,000–100,000 gas

---

Legacy

Groth16 set the standard for production zk-SNARKs from 2016 to approximately 2021. Many of the most important ZK applications in this period built directly on Groth16. Its successor, PLONK (2019), offered universal setup at the cost of slightly larger proofs, and has now largely superseded Groth16 for new applications. Groth’s work remains foundational to the zero-knowledge proof field.

---

Related Terms

• zk-SNARK
• Zero-Knowledge Proof
• Trusted Setup
• PLONK Whitepaper
• Zcash Sapling Whitepaper

---

Research

• Groth, J. (2016). On the Size of Pairing-Based Non-Interactive Arguments. EUROCRYPT 2016. IACR ePrint 2016/260.

— Primary source. Theorem 1 proves the optimality of 2-element proofs; Theorem 2 the 3-element construction.

• Parno, B., Howell, J., Gentry, C., & Raykova, M. (2013). Pinocchio: Nearly Practical Verifiable Computation. IEEE S&P 2013.

— The predecessor SNARK on which Groth16 improved; introduced practical arithmetic circuit compilation.

• Gabizon, A., Williamson, Z.J., & Ciobotaru, O. (2019). PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. IACR ePrint 2019/953.

— The successor system with universal trusted setup; largely superseded Groth16 for new SNARK applications.