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 ·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× larger circuit sizes than a highlyoptimized
prior system, and that its proofs are 2–10× smaller
than prior work with similar properties.
3 Likes