Is the latency linear to only the number of public parameters whenever Groth16 is used with Gnark?

[akakou]

Is the latency linear to only the number of public parameters ($\ell$) whenever Groth16 is used with Gnark? As far as I know, Groth16's verification cost is typically linear in $\ell$ [1], but I would like to know if Gnark optimized it additionally.

[1] https://medium.com/@mehialiabadi/plonk-vs-groth16-50254c157196

[ivokub]

The prover speed is O(n logn) in the number of constraints (essentially circuit size). The verifier cost is indeed linear in the number of public parameters. For this reason if the circuit would require many public inputs, then it makes sense to hash them and only provide hash of the public parameters as a single public input and then in-circuit verify that the hash is correctly computed. This helps for example when implementing Solidity verifier.

That said - we unfortunately right now don't have separate Solidity library for MiMC/Poseidon2 hashing. So it would be necessary to implement yourself. Other option is to use SHA2/Keccak which has native Ethereum support, but it is expensive to compute in-circuit.

We also have one additional optimization for proving performance, which computes a Fiat-Shamir challenge efficiently in-circuit. But this requires one additional pairing computation by the verifier. This optimization is toggled automatically depending if the circuit uses features which require Fiat-Shamir challenges (non-native arithmetic, SHA2/3 hashing).

[akakou]

@ivokub
Thank you for your courteous response—I understand it well.

May I ask if there are cases where verification speeds up beyond a certain number of public inputs (for example, due to caching)? I apologize for not being able to show you the code at this time, but with the circuit I’m working on, the relationship isn’t cleanly proportional; it seems to accelerate partway (I confirmed the number of inputs with GetNbPublicVariables()).

[ivokub]

Indeed - I gave a simplified explanation, but essentially for Groth16 proof verification there are a few components which count towards the verification time:

• multi-scalar multiplication for public variables (single scalar mul for every public variable)
• pairingcheck with 3 inputs for the proof
  Additionally, when in-circuit challenge computation is performed, we additionally have (n number of commitments)
• n+1 scalar multiplications for every commitment
• pairingcheck with n+1 inputs
  But in practice we always have n=1 or we don't have commitment at all.

And usually the scalar multiplication is a lot cheaper than pairingcheck, so if you increase number of public inputs by a little (i.e. 1->2), then the pairingcheck cost dominates total verifier cost. But if you would already have hundreds or thousands of public inputs, then it already starts to dominate.

For Solidity verifier though I think the pairingcheck precompile is relatively cheaper than mulcheck - so I think already after 10 public inputs the scalar multiplication gas cost starts to dominate.

[akakou]

Thank you for letting me know. After investigating my code, I found that the calculations only stopped being linear when a large number of zeros were provided as public input. At least, that issue is now resolved. Thank you very much for your thorough response despite your busy schedule.