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