Paper 2019/142
LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs
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. Minor revision. 2019 ACM SIGSAC Conference on Computer and Communication Security (CCS'19)
- DOI
- 10.1145/3319535.3339820
- Keywords
- zero knowledgeimplementationzk-SNARKsframework
- 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} }