Faster ECDSA verification

[Stentonian]

https://hackmd.io/juvO0SxlSqWa2pTYDKCOcw?view=#Better-ECDSA-verification

[Stentonian]

Research notes

There are 2 libraries to research: efficient-ecdsa & spartan-ecdsa

Here is a nice overview of ZK ECDSA, which mentions the above 2 libraries.

Efficient ECDSA

~160k R1CS constraints to verify a signature.

These guys use efficient-ecdsa https://github.com/bankisan/zkShield

Links:

• blog explainer (doesn't do all the technicals): https://personaelabs.org/posts/efficient-ecdsa-1/
• first post mentioning the idea: https://crypto.stackexchange.com/questions/81089/is-this-a-safe-way-to-prove-the-knowledge-of-an-ecdsa-signature
• another post building on the idea: https://ethresear.ch/t/efficient-ecdsa-signature-verification-using-circom/13629/9
• starting with a security proof https://hackmd.io/HQZxucnhSGKT_VfNwB6wOw#Does-R-leak-anything-about-s-and-Q_a

Spartan ECDSA

Current best ECDSA verification perf, ~8k R1CS constraints.

These guys are using spartan-ecdsa: https://github.com/dmpierre/nova-browser-ecdsa

Links:

• https://github.com/nullity00/audits/blob/b4aea5880dd06ca09c62713d836705c136f0d597/Spartan-ecdsa.md
• https://github.com/microsoft/Spartan
• spartan: https://eprint.iacr.org/2019/550
• Blog explainer https://personaelabs.org/posts/spartan-ecdsa/

Other

Some good circom circuits for ecdsa & merkle tree things to do set membership (and non-membership) check: anonklub

ZKAttest: Ring and Group Signatures for existing ECDSA keys https://eprint.iacr.org/2021/1183.pdf

Aggregating secp256k1 ECDSA with Nova: https://hackmd.io/mArMuUx5TC2LEcYecc741Q

[Stentonian]

Changing PoA to using spartan-ecdsa is going to be a lot of work because it is a different proving system. If we want to be able to snark recursion then we may have to do a lot of work because verifying a Spartan proof is not simple.

Using the older efficient-ecdsa circuits is a much simpler change. All we need to do is import the circuits and switch over, no need to change the proving system or main parallel/recursive workflow design. One potential issue is the large number of public inputs to the circuit (the pre-computes), which would make the g16 verifier inside layer 2 have an enormous number of constraints. But we can get around this my hashing the public inputs, having the hash be the public input, and then making the pre-computes be private inputs.

[Stentonian]

It doesn't make sense to use efficient-ecdsa circuits..

The circuits require pre-computing some values, and having those values be public inputs to the snark. They have to be public inputs so that they can be checked by the verifier.

We have to keep the number of public inputs small so that the recursion into layer 2 is still possible (many pub inputs => very large circuit size for verifying g16 proofs). The number of pre-computed values needed per signature is ~65k, so we absolutely cannot have these as public inputs. We could get around this by having them as private inputs, and then computing their hash inside the circuit. But unfortunately, this gives us more constraints than the original circuit, because there are so many values to hash.

See here for changes: https://github.com/silversixpence-crypto/zk-proof-of-assets/tree/stent/efficient-ecdsa

Number of constraints for 1 signature for layer 1 circuit:

• Original circuit: ~1.5M
• efficient-ecdsa + hashing of precomputes: ~2.7M