** 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--27x larger circuit sizes than a highly-optimized prior system, and that
its proofs are 2--10x smaller than prior work with similar properties.

** Versions: **

- Manuscript [e-print]