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

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in CRYPTO 2021
Keywords
zero-knowledgesnarksinformation theoretic
Contact author(s)
carla rafols @ upf edu
arantxa zapico @ upf edu
History
2021-08-19: last of 2 revisions
2021-05-10: received
See all versions
Short URL
https://ia.cr/2021/590
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/590,
      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{https://eprint.iacr.org/2021/590}},
      url = {https://eprint.iacr.org/2021/590}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.