In this chapter, we’ll be looking at the internals of how Groth16’s CRS works, so it might be useful to very briefly describe how the system works. For another succinct resource on Groth16, see Kurt Pan’s Notes.
We work over a circuit taking inputs, which we write as . There is an index such that the are the public inputs, and the are the private inputs.
The constraints of our circuit are encoded as a list of polynomials of degree , along with a polynomial , of degree . The inputs satisfy the circuit when the following equation holds: (Note that saying that is equivalent to saying that there exists an , of degree at most , such that ).
The goal of a proof is to prove knowledge of the satisfying these constraints, without revealing information about what their values might be.
The CRS involves generating private parameters, and then performing some calculations to derive public elements, which are then used for creating and verifying proofs. It’s important that these private parameters are destroyed after being used to derive the public parameters.
As a shorthand, we define the following polynomial: which gets used many times in the CRS itself.
The private parameters consist of randomly sampled scalars:
The public parameters are then derived from these private ones, producing the following list of elements:
(Note that given for up to a given degree , we can then compute , for any polynomial of degree up to , since this element is a linear combination of these monomial elements. We write to denote this process.)
Next we describe the proving and verification equations:
A proof consists of three group elements: , and .
The proof requires the generation of two fresh random scalars and , which are then used to compute the following elements:
Finally, the proof is returned as .
Given a proof , verification checks:
BGM17 (Section 6) proposed a slightly modified CRS, adding extra elements, in order to simplify the setup ceremony. They also proved that adding these elements did not affect the security (specifically, knowledge soundness) of the scheme.
The CRS becomes:
The main change is that has been removed, and that we now have access to higher degrees of in , along with direct access to and .