parameters (proving and verification keys for
zk-SNARK
s, and a common reference string for
NIZK
s). Both provide the same guarantees of completeness, proof of knowledge, and zero knowledge.
The difference lies in efficiency guarantees. In a
NIZK
, the proof length and verification time depend
on the
NP
language being proved. For instance, for the language of circuit satisfiability, the proof
length and verification time in [GOS06b, GOS06a] are linear in the circuit size. Conversely, in a
zk-SNARK
, proof length depends only on the security parameter, and verification time depends
only on the instance size (and security parameter) but not on the circuit or witness size.
Thus,
zk-SNARK
s can be thought of as “succinct
NIZK
s”, having short proofs and fast verifica-
tion times. Succinctness comes with a caveat: known
zk-SNARK
constructions rely on stronger
assumptions than NIZKs do (see below).
2.3 Known constructions and security
There are many
zk-SNARK
constructions in the literature [Gro10, Lip12, BCI
+
13, GGPR13,
PGHR13, BCG
+
13, Lip13, BCTV14]. We are interested in
zk-SNARK
s for arithmetic circuit
satisfiability, and the most efficient ones for this language are based on quadratic arithmetic
programs [GGPR13, BCI
+
13, PGHR13, BCG
+
13, BCTV14]; such constructions provide a linear-
time KeyGen, quasilinear-time Prove, and linear-time Verify.
Security of
zk-SNARK
s is based on knowledge-of-exponent assumptions and variants of Diffie–
Hellman assumptions in bilinear groups [Gro10, BB04, Gen04]. While knowledge-of-exponent
assumptions are fairly strong, there is evidence that such assumptions may be inherent for con-
structing zk-SNARKs [GW11, BCCT12].
Remark
(fully-succinct
zk-SNARK
s)
.
The key generator
KeyGen
takes a circuit
C
as input. Thus,
KeyGen
’s running time is at least linear in the size of the circuit
C
. One could require
KeyGen
to not
have to take
C
as input, and have its output keys work for all (polynomial-size) circuits
C
. In such
a case,
KeyGen
’s running time would be independent of
C
. A
zk-SNARK
satisfying this stronger
property is fully succinct. Theoretical constructions of fully-succinct
zk-SNARK
s are known, based
on various cryptographic assumptions [Mic00, Val08, BCCT13]. Despite achieving essentially-optimal
asymptotics [BFLS91, BGH
+
05, BCGT13b, BCGT13a, BCCT13] no implementations of them have
been reported in the literature to date.
2.4 zk-SNARK implementations
There are three published implementations of
zk-SNARK
s: (i) Parno et al. [PGHR13] present
an implementation of
zk-SNARK
s for programs having no data dependencies;
9
(ii) Ben-Sasson
et al. [BCG
+
13] present an implementation of
zk-SNARK
s for arbitrary programs (with data
dependencies); and (iii) Ben-Sasson et al. [BCTV14] present an implementation of
zk-SNARK
s
that supports programs that modify their own code (e.g., for runtime code generation); their
implementation also reduces costs for programs of larger size and allows for universal key pairs.
Each of the works above also achieves
zk-SNARK
s for arithmetic circuit satisfiability as a
stepping stone towards their respective higher-level efforts. In this paper we are only interested in
a
zk-SNARK
for arithmetic circuit satisfiability, and we rely on the implementation of [BCTV14]
for such a
zk-SNARK
.
10
The implementation in [BCTV14] is itself based on the protocol of Parno
et al. [PGHR13]. We thus refer the interested reader to [PGHR13] for details of the protocol, its
9
They only support programs where array indices are restricted to be known compile-time constants; similarly,
loop iteration counts (or at least upper bounds to these) must be known at compile time.
10
In [BCTV14], one optimization to the verifier’s runtime requires preprocessing the verification key
vk
; for simplicity,
we do not use this optimization.
12