search

Consensys / gnark

gnark is a fast zk-SNARK library that offers a high-level API to design circuits. The library is open source and developed under the Apache 2.0 license
https://hackmd.io/@gnark
Apache License 2.0
1.42k stars 368 forks source link

perf: optimize ecdsa circuit #461

Open gbotrel opened 1 year ago

gbotrel commented 1 year ago
ivokub commented 1 year ago

Referencing #372 for comments:

  • implement separate variable and base point scalar mul. Base point scalar mul can take advantage of huge precomputation tables + lookups.
  • variable point scalar multiplication requires building lookup tables per-point. For a single signature this allows to implement windowed scalar multiplication and reduce the cost several times. See https://0xparc.org/blog/zk-ecdsa-2.
  • 0xPARC blog describes an interesting idea for checking only a random linear combination of signatures. This would require applying Fiat-Shamir and a lot of hashing, but may probably be more efficient than point operations.
  • When we combine two lookup tables, then can build window over two scalars at a time for ECDSA.

I have a few more links in the list:

ivokub commented 1 year ago

From #497, notes from Halo2 book