Branch: master
Find file History
Latest commit 0065474 Apr 9, 2018

Below is performance information about several preprocessing zkSNARKs in libsnark that work with the R1CS relation.

Empirical performance

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, %
PGHR13/BCTV14a 104.85 128.60 4.3 7%
Groth16 72.53 84.01 1.3 11%
GM17 100.41 116.42 2.3 12%
Proof system PK size VK size Proof size
MB #G1 #G2 bytes #G1 #G2 bytes #G1 #G2
PGHR13/BCTV14a 312 7048603 1000004 812 12 5 287 7 1
Groth16 201 4048574 1000004 558 10 2 127 2 1
GM17 385 8097184 2000014 605 13 3 127 2 1

Asymptotic performance

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
count domain size #G1 #G2
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)
Proof system PK VK
#G1 #G2 #G1 #G2
PGHR13/BCTV14a 6N+M+n N n O(1)
Groth16 3N+M N n O(1)
GM17 3N+5M+4n N+M+n n O(1)