You are looking at a specific version 20171127:161506 of this paper. See the latest version.

Paper 2017/1132

Doubly-efficient zkSNARKs without trusted setup

Riad S. Wahby and Ioanna Tzialla and abhi shelat and 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 (DDH). Specifically, communication is proportional to the square root of the size of the witness, plus $d\cdot\log(G)$ where $d$ is the depth and $G$ is the width of the verifying circuit. When applied to batched or data-parallel statements, the prover's cost is linear and the verifier's cost is sub-linear in the verifying circuit size, both with good constants. Together, these properties represent a new point in the tradeoffs among setup, complexity assumptions, proof size, and computational cost. Our argument is public coin, so we apply the Fiat-Shamir heuristic to produce a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK), which we call Hyrax. We evaluate Hyrax on three benchmarks, SHA-256 Merkle trees, image transformation, and matrix multiplication. We find that Hyrax scales to 6--27$\times$ larger circuit sizes than a highly-optimized prior system, and that its proofs are 2--10$\times$ smaller than prior work with similar properties.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
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
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.