### Poppins: A Direct Construction for Asymptotically Optimal zkSNARKs

Abhiram Kothapalli, Elisaweta Masserova, and Bryan Parno

##### Abstract

We present Poppins, a direct construction of a zero-knowledge argument system for general computation that features an $O_{\lambda}(n)$ time prover and an $O_{\lambda}(1)$ time verifier (after a single $O_{\lambda}(n)$ public setup) for computations of size $n$. Our scheme utilizes a universal linear-size structured reference string (SRS) that allows a single trusted setup to be used across all computation instances of a bounded size. Concretely, for computations of size $n$, our prover's cost is dominated by $35$ multi-exponentiations of size $n$ and our verifier's cost is dominated by $34$ pairings. To achieve the stated asymptotics, we first construct a nearly-optimal zkSNARK with a logarithmic verifier in the random oracle model. We then show how to achieve a constant-time verifier using (single-layer) proof composition. Along the way we design (1) a new polynomial commitment scheme for evaluation-based representations of polynomials, (2) an asymptotically optimal inner-product argument system, (3) an asymptotically optimal multi-Hadamard-product argument system, and (4)~a new constraint system for NP that is particularly well-suited for our bundle of techniques.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
verifiable computationzero knowledgezkSNARKs
Contact author(s)
akothapa @ andrew cmu edu
elisawem @ andrew cmu edu
parno @ cmu edu
History
2021-03-04: revised
See all versions
Short URL
https://ia.cr/2020/1318

CC BY

BibTeX

@misc{cryptoeprint:2020/1318,
author = {Abhiram Kothapalli and Elisaweta Masserova and Bryan Parno},
title = {Poppins: A Direct Construction for Asymptotically Optimal zkSNARKs},
howpublished = {Cryptology ePrint Archive, Paper 2020/1318},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/1318}},
url = {https://eprint.iacr.org/2020/1318}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.