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