# Groth16

Pinocchio was the first practical implementation of a zero-knowledge proving system; for instance, zCash implemented it to deliver their original shielded transaction protocol.

[ Disclaimer: this reading makes sense only if you’re already familiar with the Pinocchio proving system. You can find an overview of that protocol in this blog, pls see the Blog Index ].

In 2016, Jens Groth published a paper where he formalized a proving system that significantly improved performance compared to Pinocchio. In particular, for arithmetic circuits, proofs consist of only 2 elements in G1 and 1 in G2, compared to Pinocchio’s 7 elements in G1, and 1 in G2. Furthermore, verification is faster, with just 3 pairings instead of 12. The CRS is also shorter.

Everything looks the same up to QAP reduction, where we end up with polynomials A1(X), A2(X), A3(X), … and also B1(X), B2(X), B3(X), … and C1(X), C2(X), C3(X), …

So, we need as usual a good base field Fq, a nice pairing-friendly elliptic curve, the generators g1 and g2, and all the good Pinocchio's building blocks. With all that available, let's look at what's different.

CRS

At set-up, we’ll sample the following random field elements (all toxic waste):

α, β, γ, δ, τ.

Given:

• A computation with m variables, of which l as public input
• n constraints
• Z(X) as defined in our QAP post, i.e Z(X)=(X-1)*(X-2)*(X-3)*…
• Li(X) = β *Ai(X) + α * Bi(X) + Ci(X)

Our proving key will be made of:

• G1 elements (all the elements in bold are scalar “multiplied” for the generator point g1):

(αδ, 1, τ, τ2, τ3, ..., τn-1, Ll+1(τ)/δ, Ll+2(τ)/δ, ..., Lm(τ)/δ, Z(τ)/δ, τ*Z(τ)/δ, τ2*Z(τ)/δ, ..., τn-2*Z(τ)/δ)1

• G2 elements (all the elements in bold are scalar “multiplied” for the generator point g2):

(β, δ, 1, τ, τ2, τ3, ..., τn-1)2

The proving key will also include the circuit, i.e. the coefficients of the A1(X), A2(X), A3(X), …, B1(X), B2(X), B3(X), … and C1(X), C2(X), C3(X),… polynomials, and the Z(X) polynomial.

The verification key will be made of:

• G1 elements: (1, L0(τ)/γ, L1(τ)/γ, L2(τ)/γ, ..., Ll(τ)/γ)1
• G2 elements: (1, γ, δ)2
• A Gt element (precomputed pairing): (α1 * β2)t

Proof Generation

Given a witness vector w = (1, w1, w2, w3, …, wm ), and two random field elements r and s, a proof is made of three points A, B and C.

A is a point in G1:

A1α1 + w0*A0(τ)1 + w1*A1(τ)1 + w2*A2(τ)1 + w3*A3(τ)1 + … + wm*Am(τ)1 + r*δ1

All the elements of this sum are G1 elements, so for instance:

• α1 = α*g1
• Ao(τ)1 = Ao(τ)*g1
• … and so on

Ai(τ)*g1  can be calculated from the coefficients of Ai(X), by multiplying each of them for the corresponding term g1, τ*g1, τ2*g1, … , that are points made available by the CRS.

B is a point in G2:

B2 =  β2 + w0*B0(τ)2 + w1*B1(τ)2 + w2*B2(τ)2 + w2*B3(τ)2 + … + wm*Bm(τ)2 + s*δ2

and C is again a point in G1:

C1 = wl+1*(Ll+1(τ)/δ)1 + … + wm*(Lm(τ)/δ)1  +  H(τ)*(Z(τ)/δ)1  +  s*A1  +  r*B1  -  r*s* δ1

H(τ)*Z(τ)/δ * g1 can be calculated from the coefficients of H(X), by multiplying each of them for the corresponding term (Z(τ)/δ) * g1, (τ*Z(τ)/δ) * g1,( τ2*Z(τ)/δ) * g1, …, that are points made available by the CRS.

The polynomial H(X) can be calculated by calculating the polynomial A(X), B(X) and C(X) using the witness vector w on the polynomials A1(X), A2(X), A3(X), …, B1(X), B2(X), B3(X), … and C1(X), C2(X), C3(X),… provided by the CRS. As we recall from the QAP post, H(X) = [A(X) * B(X) – C(X)] / Z(X)

We also need to calculate B in G1: B1 =  β1 + w0*B0(τ)1 + w1*B1(τ)1 + … + wm*Bm(τ)1 + s*δ1

Verification

To verify a proof, we’ll just need to check the following equality:

A1 * B2   =    α1 * β2    +    (w0*L0(τ)/y + w1*L1(τ)/y + … + wl*Ll(τ)/y)1 * y2   +   C1 * δ2

That requires just three pairings, considering that  α1 * β2  is already available in the verifying key.

We can easily see that the left term A * B is:

[α + A(τ) + r*δ] * [β + B(τ) + s*δ]

=  α*βα*B(τ) + s*α*δ + A(τ)*β + A(τ)*B(τ) + s*A(τ)*δ + r*δ *β + r*δ*B(τ) + s*r*δ*δ

= A(τ)*B(τ) + α*β + α*B(τ) + β*A(τ) +  s*α*δ + s*A(τ)*δ + r*β*δ + r*B(τ)*δ + s*r*δ*δ

While the right term is:

α*β + L(τ) + H(τ)*Z(τ) + s*α*δ + s*A(τ)*δ + s*r*δ *δ + r*β*δ + r*B(τ)* δ + s*r*δ*δ - r*s*δ*δ

= α*β + β*A(τ) + α*B(τ) + C(τ) + H(τ)*Z(τ) + s*α*δ + s*A(τ)*δ + s*r*δ *δ + r*β*δ + r*B(τ)* δ

= C(τ) + H(τ)*Z(τ) + α*β + α *B(τ) + β*A(τ) + s*α*δ + s*A(τ)*δ + r*β*δ + r*B(τ)* δ + s*r*δ *δ

And so if the above equality hold, it means that:

A(τ)*B(τ) = C(τ) + H(τ)*Z(τ)

Mission accomplished!

As we can see, Groth16 does not use the “knowledge of coefficient” (that requires in the proof two group elements for each polynomial) , but uses the secret field elements α, β to force A, B and C to use the same vector w. The other two secret field elements γ, δ are used to make the public input independent from the other witness components.

The real-world instantiations of this proving system, extend the CRS to include some pre-computed points that make proof calculation faster, such as the hidings of the polynomial components evaluated in τ:

A0(τ)*g1, A1(τ)*g1, A2(τ)*g1, … , B0(τ)*g1, B1(τ)*g1, …, C0(τ)*g1, C1(τ)*g1, …

and

B0(τ)*g2, B1(τ)*g2, …