Optimization: implement RCB15 group addition for BN curves

[zhenfeizhang]

The current group law uses 16 field multiplications.

https://github.com/privacy-scaling-explorations/halo2curves/blob/main/src/derive/curve.rs#L810

We may use the method from https://eprint.iacr.org/2015/1060 which requires only 12 field multiplications.

I have a demo implementation of this algorithm here:
https://github.com/zhenfeizhang/rcb15-group-law

This should improve the proving speed by 25% or so.
(I noticed that both Halo2 and Arkworks didn't use this 8 years old method. Did I missed anything here?)

[CPerezz]

@davidnevadoc (and possibly others) will do some checks to the paper and discuss whether to go for an implementation as this requires to change the macros that implement everything for the curves.

[zhenfeizhang]

Sounds good.

My demo has shows that both the group law can be integrated to both arkworks and halo2.
The tricky part here is that it requires standard projective coordinates, while arkworks/halo2 both uses jacobian coordinates.

I see two way to move forward

1. have a simple MSM api that internally use RCB15 -- this is where performance is critical anyway -- and leave the rest untouched. This is simpler and can be done quite quickly
2. to completely redo the curve trait which may take quite some time

Option 1 could serve as a temp patch until 2 is ready

[zhenfeizhang]

updates: it looks like arkworks 0.4.0 uses 9 mul, incomplete version over jacobian coordinates.

maybe that is a better choice as it doesn't require a change of coordinate system

no arkworks also used 16 mul version

[CPerezz]

I think @kilic has already started to implement the Field encoding required for this. So we should be able to adopt it soon.

[zhenfeizhang]

very nice!

[davidnevadoc]

I went for approach number 2 and switched to homogeneous coordinates. Are you aware of any downsides of using these instead of jacobian coordinates? @zhenfeizhang
Aside from a comment made in this issue regarding hash to curve, I haven't found anything.

[zhenfeizhang]

I am not aware of any downside other than that the doubling is slightly more costly IIRC