perf: optimize ecdsa circuit

[gbotrel]

• Batch verification
• MSM in-circuit
• Pre-compute constant points

[ivokub]

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:

• https://github.com/privacy-scaling-explorations/halo2wrong/pull/22/files
• https://personaelabs.org/posts/efficient-ecdsa-1/

[ivokub]

From #497, notes from Halo2 book