Paper 2021/590

An Algebraic Framework for Universal and Updatable SNARKs

Carla Ràfols and Arantxa Zapico

Abstract

We introduce Checkable Subspace Sampling Arguments, a new information theoretic interactive proof system in which the prover shows that a vector has been sampled in a subspace according to the verifier's coins. We show that this primitive provides a unifying view that explains the technical core of most of the constructions of universal and updatable pairing-based (zk)SNARKs. This characterization is extended to a fully algebraic framework for designing such SNARKs in a modular way. We propose new constructions of CSS arguments that lead to SNARKs with different performance trade-offs. Our most efficient construction, Basilisk, seems to have the smallest proof size in the literature, although it pays a price in terms of structure reference string for the number of multiplicative gates whose fan-out exceeds a certain bound.

Note: 19/08: New technique for degree checks. It eliminates 1G and 1F elements of the proof in all constructions. (App. E, F) 02/07: Framework extended to a more general proof system that includes further constructions. We rolled out several CSS schemes and present our most efficient zkSNARK. Changes over the previous version are mainly in the Appendix. (App. A, B, C, D, F).