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)*…
- L
_{i}(X) = β *A_{i}(X) + α * B_{i}(X) + C_{i}(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}**L**,

_{l+1}(τ)/δ**L**, ...,

_{l+2}(τ)/δ**L**,

_{m}(τ)/δ**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, L**,_{0}(τ)/γ**L**,_{1}(τ)/γ**L**, ...,_{2}(τ)/γ**L**)_{l}(τ)/γ_{1} - G2 elements: (
**1**,**γ**,**δ**)_{2} - A Gt element (precomputed pairing): (
**α**_{1}***β**_{2})_{t}

**Proof Generation**

Given a witness vector *w* = (1, w_{1}, w_{2}, w_{3}, …, w_{m }), 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:

**A**_{1} = **α**_{1} + w_{0}***A _{0}(τ)**

_{1}+ w

_{1}*

**A**

_{1}(τ)_{1}+ w

_{2}*

**A**

_{2}(τ)_{1}+ w

_{3}*

**A**

_{3}(τ)_{1}+ … + w

_{m}*

**A**

_{m}(τ)_{1}+ r*

**δ**

_{1}

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

**α**_{1}= α***g1****A**_{o}(τ)_{1}= A_{o}(τ)***g1**- … and so on

A_{i}(τ)***g1** can be calculated from the coefficients of A_{i}(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:

**B**_{2} = **β**_{2} + w_{0}***B _{0}(τ)**

_{2}+ w

_{1}*

**B**

_{1}(τ)_{2}+ w

_{2}*

**B**

_{2}(τ)_{2}+ w

_{2}*

**B**

_{3}(τ)_{2}+ … + w

_{m}*

**B**

_{m}(τ)_{2}+ s*

**δ**

_{2}

and C is again a point in G1:

**C**_{1} = w_{l+1}*(**L _{l+1}(τ)/δ)**

_{1}+ … + w

_{m}*(

**L**

_{m}(τ)/δ)_{1}+ H(τ)

***(Z(τ)/δ)**

_{1}+ s*

**A**

_{1}+ r*

**B**

_{1}- 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: **B**_{1} = **β**_{1} + w_{0}***B _{0}(τ)**

_{1}+ w

_{1}*

**B**

_{1}(τ)_{1}+ … + w

_{m}*

**B**

_{m}(τ)_{1}+ s*

**δ**

_{1}

**Verification**

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

**A**_{1} * **B**_{2} = **α**_{1 }* **β**_{2 }+ ** **(w_{0}***L _{0}(τ)/y **+ w

_{1}*

**L**w

_{1}(τ)/y + … +_{l}*

**L**)

_{l}(τ)/y_{1 }*

**y**

_{2}

**+**

**C**

_{1}*

**δ**

_{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 τ:

A_{0}(τ)*g1, A_{1}(τ)*g1, A_{2}(τ)*g1, … , B_{0}(τ)*g1, B_{1}(τ)*g1, …, C_{0}(τ)*g1, C_{1}(τ)*g1, …

and

B_{0}(τ)*g2, B_{1}(τ)*g2, …