Main Idea
Groth16 can be viewed as an optimized variant of Pinocchio and is designed for QAP relation. On a high-level, Groth16 manages to reduce the number of proof elements to 3 by stashing the following additional elements to :
- i.e. a commitment to the polynomial.
- commitments to .
- i.e. a commitment to
Dropping
Dropping , the prover now has to push to the element i.e.
Dropping
Dropping , we should add (roughly corresponding to in Pinocchio) to and to , so that the pairing equation also guarantees that is in the linear span of . Likewise, to force is in the span of we also add to and to . Now the pairing equation should be slightly adjusted: , where honestly computed , , and are
Dropping
Recall that in Pinocchio essentially forces the prover to apply an identical linear transformation to , , and . In Groth16, this is achieved by having an honest prover compute the above divided by an additional element , while the only CRS involving are and . This constraint also puts in the correct linear span, previously guaranteed by . The pairing equation should be slightly adjusted again: , where honestly computed is
The Protocol
Protocol
- Setup : Output a CRS containing
- for
- for
- for
- for
- Prove: outputs where
- Verify: checks
Groth16 with public inputs
Analogously to Pinocchio with public inputs, we can adjust the above to full-fledged Groth16 for QAP relation.
Protocol
- Setup : Output a CRS containing
- for
- for
- for
- for
- for
- Prove: outputs where
- Verify: computes the public component for as and checks
Groth16 with zero knowledge
Towards ZK, we randomize the two proof elements and , and perturb to retain correctness.
Protocol
- Setup : Output a CRS containing
- for
- for
- for
- for
- for
- Prove: outputs where
- Verify: computes the public component for as and checks
Since and are now masked by independently chosen , we can easily perform ZK simulation by sampling uniform and set such that they meet the verification condition.
Simulator
- SimSetup
- Run . Output and a simulator trapdoor
- SimProof
- Sample uniform and set
- Set
- Output
Groth16 is re-randomizable
It is easy to see that Groth16 is re-randomizable i.e. given for a statement one can generate a valid proof for the same . There are essentially two ways to maul the proof:
- Set , for some , output .
- Set and , output .
It is still possible to show that forging Groth16 proof is hard for i.e. it is weakly non-malleable (see BKSV21). To obtain strong non-malleability, Groth16 can be modified to Groth-Maller proof.