Disclaimer: I have no background in cryptography, and everything I'm asking about is what I've learnt from last couple of days of frantic reading on this topic. Any help is much appreciated.

Q: What does the computational complexity of generating a zkSNARK proof and verifying it scale with?

Specifically, how many bilinear pairings, curve point additions and scalar multiplications are involved in generating and verifying a proof? Are these linear in the number of constraints in the system?

Here, I can see that there each verification requires the verifier to compute $11$ curve pairings, $3*m$ scalar multiplications, and $3(m+1)$ curve point additions. First of all, is my understanding correct? Second, what is $m$? Is that the number of constraints? Third, how can I similarly calculate the number of pairings, additions and multiplications that the prover has to compute if I know the number of constraints?


Its depend on the protocol used. The last and more efficient is Groth16 that use only 3 curve points in its proofs. You can see the size of the keys and the the proofs in the table 2 of Groth's paper. The computation complexity of the pairing depends of whats curve is used. In general ZoKrates/Ethereum and ZCash use the bn256 curve paramters and the pairing algorithm used in their package (at least in the golang's one) is the algorithm 1 of the miller ate pairings.

You see zk-SNARK is an amalgamation of various works and its complexity depends on the implementation that is evolving day to day.

  • $\begingroup$ Could you clarify what the size of the instance $l$ represents when it is stated (E.g. in Table 1 here) that the Verifier computation cost in Groth16 is $3$ Pairings + $l$ Exponentations? Is $l$ supposed to be the number of public inputs provided to the snarkVerifier call? $\endgroup$ – crypto9294 Jul 29 '20 at 8:32
  • $\begingroup$ In the Groth16 verification protcol you have to construct a sigma element by multiplying the $vk_x$ element of the verifier key with the public inputs and then verify the pairing equation of the protocol. So yeah, I think $l$-size statement means $l$ public inputs. $\endgroup$ – Matias Díaz Aug 7 '20 at 19:21
  • $\begingroup$ you can see this in the Vfy algorithm detailed in here in section 3.1 $\endgroup$ – Matias Díaz Aug 7 '20 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.