Number of constraints of ECDSA signature verification

[jeljelih]

I would like to benchmark ECDSA signature verification.
In go package https://pkg.go.dev/github.com/consensys/gnark/std/signature/ecdsa it is reported that 'The cost for a single secp256k1 signature verification is approximately 4M constraints in R1CS'
However when I followed this test file https://github.com/Consensys/gnark/blob/master/std/signature/ecdsa/ecdsa_secpr_test.go to implement signature verification on both p256 and p384 I obtained respectively 293813 and 564007 which is much lower than the expected 4M constraints.
Btw, I compiled the circuit for BN254.
Can you please point to me where the difference can come from?

[yelhousni]

The documentation should be updated. We've been merging many optimizations into master branch and as of today 'The cost for a single secp256k1 signature verification is 122458 constraints in R1CS and 453838 in Plonkish'. So your numbers should be coherent. Thanks for reporting, I will update the comment.

[yelhousni]

fixed #1113

[doutv]

Could you summarize the optimizations? I think it would be great if your team could share the optimization method in detail.

[ivokub]

There are several optimizations we have done:

• we have optimized non-native field arithmetic operations using deferred multiplication checks
• for ECDSA verification we use joint scalar base multiplication as we compute u1 P + u2 G where G is the base point
• we use 2-by-2 windowing when computing the scalar multiplication

[doutv]

@ivokub Could you talk more about "optimized non-native field arithmetic operations using deferred multiplication checks"?
I'm interested in how it works.

[ivokub]

We have some description of the technique in the package documentation: https://pkg.go.dev/github.com/consensys/gnark@v0.11.0/std/math/emulated#hdr-Multiplication

There is also a presentation at ZK study club, you can check it here: https://www.youtube.com/watch?v=05JemsgfEX4