# Complexity of computing zk-SNARK Proofs

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.

• 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? – crypto9294 Jul 29 '20 at 8:32
• 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. – Matias Díaz Aug 7 '20 at 19:21
• you can see this in the Vfy algorithm detailed in here in section 3.1 – Matias Díaz Aug 7 '20 at 19:39