Paper 2017/1132

Doubly-efficient zkSNARKs without trusted setup

Riad S. Wahby, Ioanna Tzialla, abhi shelat, Justin Thaler, and Michael Walfish

Abstract

We present a zero-knowledge argument for NP with low communication complexity, low concrete cost for both the prover and the verifier, and no trusted setup, based on standard cryptographic assumptions. Communication is proportional to $d\cdot\log G $ (for $d$ the depth and $G$ the width of the verifying circuit) plus the square root of the witness size. When applied to batched or data-parallel statements, the prover's runtime is linear and the verifier's is sub-linear in the verifying circuit size, both with good constants. In addition, witness-related communication can be reduced, at the cost of increased verifier runtime, by leveraging a new commitment scheme for multilinear polynomials, which may be of independent interest. These properties represent a new point in the tradeoffs among setup, complexity assumptions, proof size, and computational cost. We apply the Fiat-Shamir heuristic to this argument to produce a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) in the random oracle model, based on the discrete log assumption, which we call Hyrax. We implement Hyrax and evaluate it against five state-of-the-art baseline systems. Our evaluation shows that, even for modest problem sizes, Hyrax gives smaller proofs than all but the most computationally costly baseline, and that its prover and verifier are each faster than three of the five baselines.

Note: This version adds a link to the released source code.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.IEEE Security & Privacy 2018
Keywords
zero knowledgesuccinct argumentscomputationally-sound proofs
Contact author(s)
rsw @ cs stanford edu
History
2018-04-19: last of 5 revisions
2017-11-27: received
See all versions
Short URL
https://ia.cr/2017/1132
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1132,
      author = {Riad S.  Wahby and Ioanna Tzialla and abhi shelat and Justin Thaler and Michael Walfish},
      title = {Doubly-efficient zkSNARKs without trusted setup},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1132},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1132}},
      url = {https://eprint.iacr.org/2017/1132}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.