Part1Groth16

,

return

return

Check

Part2Framework for Aggregation

An Argument for Aggregation is a proof system that takes as input multiple proofs and computes a new smaller proof, in this case for initial proofs we end up with a final aggregated proof of size .

1Overview of the protocol

The high-level idea of Groth16 aggregation is quite simple: since Groth16 verification consists in checking a pairing equation between the proof elements , instead of checking that pairing equations are simultaneously satisfied it is sufficient to prove that only one inner pairing product of a random linear combination of these initial equations defined by a verifier's random challenge holds.

In a bit more detail, Groth16 verification asks to check an equation of the type for where is a value computed from each statement and are proof triples. The aggregation will instead check a single randomized equation:

This can be rewritten using an inner product notation as :

where we denoted by .

What is left after checking that this unified equation holds is to verify that the elements are consistent with the initial proof triples in the sense that they compute the required inner product. This is done by combining pairing commitments schemes with TIPP and MIPP arguments: the TIPP argument shows that for some initial vectors committed using the MIPP argument shows that for some vector committed under .

More formally, we introduce the relation for aggregating Groth16 proof vectors with respect to a fixed verification key vk:

where for

Part3SnarkPack: Aggregation Scheme

SP.Setup

1. Generate commitment key for :

2. Set commitment key for
3. Call
4. Choose a hash function given by its description hk
5. Set aggregation public parameters:

SP.Prove

1. Parse proving key
2. Parse
3. Commit to and :

4. Commit to
5. Hash these commitments
6. Derive random challenge and set
7. Compute
8. Compute
9. Run MT proof:

10. Set

SP. Verify

1. Parse SNARK instances
2. Parse verification key
3. Hash the commitments
4. Parse vk
5. Derive random challenge
6. Set statement
7. Check MT proof MT.Verify , statement,
8. Compute for all
9. Check Groth16 final equation to the decision bit :

10. Set decision bit