std/sw: use faster double-and-add for scalar multiplication and add constant scalar multiplication fast-path

[ivokub]

See #181 - I wasn't able to change the branch for this PR and I couldn't get CI running for my fork.

[yelhousni]

LGTM, few remarks:

• To be consistant with the literature nomenclature and with gnark-crypto, main/companion curves are outer/inner curves. e.g. inner: BLS12-377 and outer:BW6-761. Also, in gnark-crypto, we coined "companion curves" to be the twisted Edwards curves for SNARK-friendly ops. Can you please do the renaming?
• the inner-outer (companion-main) mapping is a 1-1 mapping at the sw_XXX package level, so not sure it helps at this level.
• this GLV improvement works also for G2. So the same code should be used in g2.go (as in gnark-crypto). That is said, we can have a 4-dimensional GLV (GLS) in sw_bls12377/g2 and 8-dimensional in in sw_bls24315/g2 (instead of 2-dimensional in g1). This is low priority as it is not used in groth16 verifier gadget and it's not implemented in gnark-crypto yet. But it might be worth it once we implement PlonK verifier gadget (or just KZG verifier) as it involves a single scalar mul in G2.

[ivokub]

LGTM, few remarks:

• To be consistant with the literature nomenclature and with gnark-crypto, main/companion curves are outer/inner curves. e.g. inner: BLS12-377 and outer:BW6-761. Also, in gnark-crypto, we coined "companion curves" to be the twisted Edwards curves for SNARK-friendly ops. Can you please do the renaming?

Renamed "companion" to "inner" curves. Renamed "main" to "outer" curves.

• the inner-outer (companion-main) mapping is a 1-1 mapping at the sw_XXX package level, so not sure it helps at this level.

It is not too useful right now, but I was at some point in the middle of merging sw_bls24315 and sw_bls12377. Then it would make a bit more sense as the only curve-specific parameters are in the mapping, not in the multiplication implementation. However, if it is too premature right now, then I can remove in this PR and reintroduce when I get back to merging. What do you think?

• this GLV improvement works also for G2. So the same code should be used in g2.go (as in gnark-crypto). That is said, we can have a 4-dimensional GLV (GLS) in sw_bls12377/g2 and 8-dimensional in in sw_bls24315/g2 (instead of 2-dimensional in g1). This is low priority as it is not used in groth16 verifier gadget and it's not implemented in gnark-crypto yet. But it might be worth it once we implement PlonK verifier gadget (or just KZG verifier) as it involves a single scalar mul in G2.

I'll open a new issue for that if there isn't anymore.

[yelhousni]

It is not too useful right now, but I was at some point in the middle of merging sw_bls24315 and sw_bls12377. Then it would make a bit more sense as the only curve-specific parameters are in the mapping, not in the multiplication implementation. However, if it is too premature right now, then I can remove in this PR and reintroduce when I get back to merging. What do you think?

That makes sense, let's keep it then. Also from a theoretical perspective, there isn't a unique outer BW6 curve. Moreover, there are also (different) outer CP8 competitive with BW6 (over BLS24), e.g. implemented here (a fork of gnark-crypto). If this gets merged sometime, then this mapping is doubly worth it.

I'll open a new issue for that if there isn't anymore.

sounds good