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 at most the square root of the witness size, plus d*log(G), for d the depth and
G the width of the verifying circuit.
Moreover, witness-related communication can be reduced below square root,
at the cost of increased verifier runtime. 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.
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's proofs are 2−10x
smaller than prior work with similar properties, and that Hyrax scales to 6−27x
larger circuits than a highly-optimized prior system that requires trusted setup.
Versions: