Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / zero-knowledge, snarks, information theoretic

Original Publication (with minor differences): IACR-CRYPTO-2021

Date: received 5 May 2021, last revised 19 Aug 2021

Contact author: carla rafols at upf edu, arantxa zapico at upf edu

Available format(s): PDF | BibTeX Citation

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

Version: 20210819:091849 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]