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

Matteo Campanelli; Dario Fiore; Anaïs Querol

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 . 2) A "lifting" tool: add commit-and-prove capabilities to a broad class of existing zkSNARKs . 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: – , a commit-and-prove version of Groth16 zkSNARK, that operates over data committed with a classical Pedersen vector commitment, and that achieves a 5000 speed in proving time. – , 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 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. Minor revision. 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: 2024-05-23: last of 10 revisions; 2019-02-14: received; See all versions
Short URL: https://ia.cr/2019/142
License: 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},
      url = {https://eprint.iacr.org/2019/142}
}