Cryptology ePrint Archive: Report 2019/142

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

Matteo Campanelli and Dario Fiore and Anaïs Querol

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.

Category / Keywords: cryptographic protocols / zero knowledge, implementation, zk-SNARKs, framework

Original Publication (with major differences): 2019 ACM SIGSAC Conference on Computer and Communication Security (CCS'19)
DOI:
10.1145/3319535.3339820

Date: received 11 Feb 2019, last revised 17 Oct 2019

Contact author: matteo campanelli at gmail com

Available format(s): PDF | BibTeX Citation

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

Version: 20191017:100041 (All versions of this report)

Short URL: ia.cr/2019/142


[ Cryptology ePrint archive ]