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
-
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},
url = {https://eprint.iacr.org/2021/590}
}