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 :

  1. i.e. a commitment to the polynomial.
  2. commitments to .
  3. 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:

  1. Set , for some , output .
  2. 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.