# 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?

• 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