We investigate the goal of deploying efficient non-interactive zero-knowledge proofs for moderately complex statements.
Motivated by the desire to deploy ZK proofs in real world distributed ledger systems, we seek ZK proof systems that have fast verification time, short proof size, and no trusted setup.
However, in terms of concrete parameters, we can achieve only two out of the three. In particular, it was not known how to achieve all of the following for million-gate circuits:
- fast (milliseconds) verifier;
- short proofs (couple kilobyte-long) ; and
- does not reply on a structured reference string (e.g., trusted setup) for soundness or zero-knowledge.
We propose a new form of proof systems: zk-SHARKs (zero-knowledge Succinct Hybrid ARguments of Knowledge). These combine the fast verification of zk-SNARKs with the no-trusted-setup of some non-succinct NIZKs.
A zk-SHARK has two verification modes: a prudent mode (relying on a uniform random string), and an optimistic mode (relying on a structured reference string).
Crucially, even complete corruption of the setup used by optimistic verification does not invalidate the prudent verification.
Moreover, old "prudent proofs'' can be re-accelerated with a new optimistic mode setup (in case the old setup becomes unconvincing or compromised).
We propose a construction of zk-SHARKs, tailored for efficiency of both modes: it is competitive with both state-of-the-art SNARKs (in terms of prover and verifier time) and NIZKs (in terms of proof size). Our zk-SHARK construction acieves all three properties outlined above.
We also discuss the applicability to transaction and block verification in blockchain applications.