Paper 2019/142

LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs

Matteo Campanelli, IMDEA Software Institute
Dario Fiore, IMDEA Software Institute
Anaïs Querol, IMDEA Software Institute, Universidad Politécnica de Madrid
Abstract

We study the problem of building SNARKs modularly by linking small specialized “proof gadgets" SNARKs in a lightweight manner. Our motivation is both theoretical and practical. On the theoretical side, modular SNARK designs would be flexible and reusable. In practice, specialized SNARKs have the potential to be more efficient than general-purpose schemes, on which most existing works have focused. If a computation naturally presents different “components" (e.g. one arithmetic circuit and one boolean circuit), a general-purpose scheme would homogenize them to a single representation with a subsequent cost in performance. Through a modular approach one could instead exploit the nuances of a computation and choose the best gadget for each component. Our contribution is LegoSNARK, a "toolbox" (or framework) for commit-and-prove zkSNARKs (CP-SNARKs) that includes: 1) General composition tools: build new CP-SNARKs from proof gadgets for basic relations $\mathit{simply}$. 2) A "lifting" tool: add commit-and-prove capabilities to a broad class of existing zkSNARKs $\mathit{efficiently}$. This makes them interoperable (linkable) within the same computation. For example, one QAP-based scheme can be used prove one component; another GKR-based scheme can be used to prove another. 3) A collection of succinct proof gadgets for a variety of relations. Additionally, through our framework and gadgets, we are able to obtain new succinct proof systems. Notably: – $\mathsf{LegoGro16}$, a commit-and-prove version of Groth16 zkSNARK, that operates over data committed with a classical Pedersen vector commitment, and that achieves a 5000$\times$ speed in proving time. – $\mathsf{LegoUAC}$, a pairing-based SNARK for arithmetic circuits that has a universal, circuit-independent, CRS, and proving time linear in the number of circuit gates (vs. the recent scheme of Groth et al. (CRYPTO'18) with quadratic CRS and quasilinear proving time). – CP-SNARKs for matrix multiplication that achieve optimal proving complexity. 4) A codebase written in C$\mathsf{++}$ for highly composable zkSNARKs with commit-and-prove capabilities$^*$. _______________ $^*$ Available at https://github.com/imdea-software/legosnark .

Note: This is the full version of the paper published in CCS'19

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. 2019 ACM SIGSAC Conference on Computer and Communication Security (CCS'19)
DOI
10.1145/3319535.3339820
Keywords
zero knowledge implementation zk-SNARKs framework
Contact author(s)
matteo campanelli @ gmail com
dario fiore @ imdea org
anais querol @ imdea org
History
2022-08-30: last of 9 revisions
2019-02-14: received
See all versions
Short URL
https://ia.cr/2019/142
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/142,
      author = {Matteo Campanelli and Dario Fiore and Anaïs Querol},
      title = {LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2019/142},
      year = {2019},
      doi = {10.1145/3319535.3339820},
      note = {\url{https://eprint.iacr.org/2019/142}},
      url = {https://eprint.iacr.org/2019/142}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.