Welcome to the resource topic for 2020/1318
Title:
Poppins: A Direct Construction for Asymptotically Optimal zkSNARKs
Authors: Abhiram Kothapalli, Elisaweta Masserova, 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.
ePrint: https://eprint.iacr.org/2020/1318
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .