SnarkPack: How to aggregate SNARKs efficiently

Nicolas Gailly

A guided dive into the cryptographic techniques of SnarkPack

This post exposes the inner workings of SnarkPack, a practical scheme to aggregate Groth16 proofs, a derivation of the Inner Pairing Product work of Bünz et al., and its application to Filecoin. It explains Groth16 proofs, the inner product argument, and the difference between the original IPP paper and our modifications. This posts ends by showing the performance of our scheme and the optimizations we made to attain that performance.

TLDR: SnarkPack can aggregate 8192 proofs in 8 seconds, producing a proof which is 38x smaller in size and can be verified in 33ms, including deserialization. The scheme scales logarithmically, yielding an exponentially faster verification scheme than batching: the more you aggregate, the faster you can verify a proof.

SNARKs & Scalability

SNARKs are Succinct Non-interactive ARguments of Knowledge; in short, they allow one to prove to a verifier, in a succinct way, that they executed a computation correctly with the correct inputs. They have tremendously impacted the blockchain world by opening up multiple uses cases that were previously impracticable, such as anonymous transactions ( Zcash), fast light clients / compact blockchain ( Celo, Mina), and provable decentralized storage ( Filecoin).

The most prominent SNARK system deployed in production is the construction proposed by Jens Groth in Eurocrypt 2016, who showed how to obtain a succinct proof of knowledge with an efficient verifier for any arithmetic circuits. Note that this proof system requires a structured reference string: a vector of elements specially crafted for a specific computation. To generate the SRS, we need to run a trusted setup, a complicated setup ceremony run by multiple users to generate keys that provers and verifiers require...

Due to its rapid and massive adoption, systems that use SNARKs face a scalability challenge similar to issues Ethereum is currently facing. The reason is that all the nodes in the network have to process each proof individually to agree on the final state, which enforces an implicit limit as to how many proofs the network can verify per day...

Multiple solutions have been developed to face this challenge with respect to SNARKs. The most recent and efficient is based on the notion of proof carrying data, which enables fully recursive proof system: one proof can verify another proof and the level of recursion is infinite. This is the approach that the Mina protocol and Halo2 (from Zcash) are currently pursuing. Unfortunately, this approach requires a complete new proof system which is incompatible with the current Groth16 proof system. Ideally, we’d like to be able to scale the current proofs that we have now in production...

Fortunately, a result that came out in 2019 from Bünz, Maller, Mishra, Tyagi, and Vesely showed a rather elegant solution to aggregate Groth16 proofs together, yielding a logarithmic-sized proof and not requiring any change in the proof system itself! In other words, one can aggregate current proofs and bring scalability to the current systems without drastic changes!

Groth16 proofs in Filecoin

Filecoin miners need to prove they have encoded a 32 GiB portion of storage correctly, i.e. that they reserved 32 GiB of storage. That’s their stake, with which they can participate in the consensus and mine blocks. In order to do that, miners run a special encoding function (the Proof of Replication) which works in consecutive steps...

Notations

We will give a high level overview of how the proof aggregation works but, before that, we need to define some notations:

• We work in pairing-equipped curves, such as BLS12-381, used by Filecoin and Zcash.
• We have one field called Fq with q prime
  • It simply means we deal with numbers between 0 and q−1
  • Addition and multiplication are done mod q
  • All scalars in this field are written in lowercase
• We have two base groups 𝟙G1 and 𝟚G2 and one target group Gt all written in uppercase.

...

Generalized Inner Product Argument (GIPA)

Let’s first see a small example to understand the principles behind GIPA.

Example

The idea at its core, explained in the original paper, is relatively simple. For the sake of simplicity, let’s look at an example where vectors are of length 2...

Trusted Inner Pairing Product (TIPP)

In this section, we explore an instantiation of GIPA required to compute a proof of corect Groth16 aggregation. It is called TIPP and produces a proof showing the prover correctly computed the pairing product Z=∏e(Ai,Bi) given a commitment to A and B. To prove such a statement, we need a commitment scheme suitable for GIPA.

Commitment Scheme

...

Performance

We implemented the scheme in Rust, using our Bellman fork called Bellperson. The implementation is derived from the implementation in Arkworks...

TLDR: We can aggregate more than 8192 proofs in around 8 seconds. Aggregated proofs are smaller than 40 KiB (versus 1.1 MiB with individual proofs) and can be verified in 33ms, including deserialization!

Conclusion

We have seen how can we prove an inner product in an efficient manner and how this is used to aggregate Groth16 proofs. Our implementation is fast and is being implemented in Filecoin (FIP 13 is open!). If you’re interested in this topic or want to find out more about what we do at Protocol Labs Research, check out our CryptoNetLab page, join the discussion in our GitHub forum, or reach out via email.