Paper 2020/1318
A Direct Construction for Asymptotically Optimal zkSNARKs
Abhiram Kothapalli and Elisaweta Masserova and Bryan Parno
Abstract
We present the first direct construction of a zero-knowledge argument system for general computation that features a linear-time prover and a constant-time verifier (after a single linear-time public setup) in terms of the number of field and group operations. 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 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.
Metadata
- 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
- 2020-10-23: received
- See all versions
- Short URL
- https://ia.cr/2020/1318
- License
-
CC BY