Paper 2021/590

An Algebraic Framework for Universal and Updatable SNARKs

Carla Ràfols and Arantxa Zapico


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).

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2021
zero-knowledgesnarksinformation theoretic
Contact author(s)
carla rafols @ upf edu
arantxa zapico @ upf edu
2021-08-19: last of 2 revisions
2021-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Carla Ràfols and Arantxa Zapico},
      title = {An Algebraic Framework for Universal and Updatable SNARKs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/590},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.