Below is performance information about several preprocessing zkSNARKs in
libsnark that work with the R1CS relation.
We benchmark proof systems on an R1CS instance with 106 constraints and 106 variables, of which 10 are input variables. The benchmarks were obtained using a 3.40 GHz Intel Core i7-4770 CPU, in single-threaded mode, using the BN128 curve.
Our R1CS instance was chosen to be dense, therefore the generator and prover runtimes given here are upper bounds on what one would expect for real world (i.e. sparse) R1CS instances.
The prover spends almost all of its time either doing FFTs or multiexponentiations. The percentage of time doing FFTs is given in the table.
Abbreviations used: PK = proving key, VK = verifying key, MB = megabyte (106 bytes), #G1/#G2 = number of elements of the respective group in a proof/key.
|Proof system||Generator time, s||Prover time, s||Verifier time, ms||Prover time spent in FFTs, %|
|Proof system||PK size||VK size||Proof size|
We estimate asymptotic performance of the proof systems.
We use the same abbreviations as above, along with additional notation: M = number of constraints in R1CS instance, N = number of variables in R1CS instance, n = number of inputs in R1CS instance.
Constant terms were dropped from all columns except number of FFTs in the prover and domain size.
The number of exponentiations in the prover and the generator are the same. In the generator, they are groups of single-base exponentiations (calculating [ae1, ae2, ...]), and in the prover, they are groups of multiple exponentiations where only the product of the results matters (calculating a1e1 · a2e2 · ...). Thus the table gives not only the total number of base/exponent pairs, but also how they are grouped.
|Proof system||FFTs in prover||Exponentiations in generator/prover|
|PGHR13/BCTV14a||7||M+n+1||6N+M+n = 6*(N) + (M+n)||N|
|Groth16||7||M+n+1||3N+M = 2*(N) + (M+n) + (N-n)||N|
|GM17||5||2M+2n+1||3N+5M+4n = 2*(N+M+n) + (N+M) + (2M+2n)||(N+M+n)|