Exploring ZK Proofs: A Focus on the Groth16 proof system

Aligned is designed to verify every proof system.

Groth16 was one of the first efficient proof systems. It's used by projects like Zcash, Worldcoin, RISC Zero, and SP1 by Succinct Labs.

At the core of Groth16 lie pairing-friendly elliptic curves, such as BN254 and BLS12-381.

These curves allow us to define a special function, the pairing, which possesses two crucial properties: bi-linearity and non-degeneracy.

In essence, they enable us to multiply scalars that are concealed in the exponent of elliptic curve points.

For instance, if P=g^a and Q=g^b, we can demonstrate that a*b = c without any knowledge of a or b!

Groth16 is a proof system that needs a trusted setup for each program/circuit. Before proving or verifying, we need to obtain the setup, from which we will derive the keys.

While setups are inconvenient, they come with an amazing advantage: proofs are the shortest among proof systems. Using BN254, they can be as small as 1024 bits!

Groth16 is designed to work with rank one constraint systems (R1CS): these are systems of equations of the form (Az)*(Bz)=Cz, where A, B, and C are matrices, z = (1,x,w) is a vector containing the public input x and witness w, and * denotes the component-wise product.

To transform our program to R1CS, we need DSL or write the code as an arithmetic circuit.

We use univariate polynomials to encode the system of equations as a quadratic arithmetic program. We choose a domain D and view each matrix’s columns as evaluations of a polynomial over D.

Using interpolation, we can reconstruct the polynomials and show that the system of equations holds if and only if the resulting polynomial is divisible by the vanishing polynomial over D.

To build a zero-knowledge proof, the protocol adds randomness, splits the terms related to public input and witness, and enforces additional checks to ensure that the prover is not cheating.

The more expensive parts are related to quotient evaluation and polynomial commitments, where the prover has to perform multiscalar multiplications (MSM).

The proof consists of two elliptic curve points in the first group of the pairing and a single point in the second group.

Elements in the second group take up twice the space as in the first group. Verification needs a small MSM equal to the size of the public input and three pairings.

Ethereum contains several precompiles that make Groth16 verification cost around 250,000 gas.

It is used by several developers due to the small size of the proofs, lower on-chain verification costs and the experience accumulated over the years using this proof system.

For more details about Groth16, see the following blog post from LambdaClass.

Stay tuned:  🐦 Twitter | 🗨️ Telegram | 👾 Discord | 🌐 Website | 🌌 Galxe | 📝 Manifesto