BatchAffineAddition

[gbotrel]

Figure out best algorithm and implement.

May be useful for MultiExponentiation with lots of 1 ( gnark circuit with binary decomposition for example) .

[yelhousni]

The cost of bucket-list MSM is roughly: b/c*(n+2^c) additions where n is the number of points, b the bitsize of scalars and c the chosen window bitsize. For large instances, this is dominated by the n additions that correspond to summing the buckets contents. In gnark-crypto, this is a mixed addition of affine points and Jacobian extended points (XYZZ), which costs 10 field multiplications per addition (10 M), assuming a square costs the same as a multiplication (1S=1M).

Note: The only shapes-coordinates with faster mixed addition are Jacobi quartics XXYZZ/XXYZZR (9M), Edwards projective/inverted (9M), twisted Edwards extended (8M) and twisted Edwards extended with a=-1 (7M). To convert a short Weierstrass to a twisted Edwards or a Jacobi quartic, we need a point of order 2 to map to a Montgomery curve which has then a bijection with these shapes. However, only BLS12-377, BLS24-315 and BW6-761 satisfy this condition (on G1). Moreover, we need to implement the new arithmetic on these shapes.

The idea behind this issue is to compare mixed addition in Jacobian extended to a batched affine addition. Assuming 1S=1M, the cost of an affine addition is 3M+1I (I is a field inverse). For a single addition, this is not worth it as usually 1I > 7M = 10M-3M but this might be different for a batch addition that leverages Montgomery's batch inversion trick. One can accumulate L points in affine and batch add them which costs 3L*M+L*I= 6L*M + 1I (with Montgomery's trick costing L*I = 3L*M + 1I). Assuming I = C*M, this is worth it if we accumulate a number of points L > C/4.

e.g. for BLS12-381, currently in gnark-crypto, C=143 over Fp and C=43 over Fp2. This means that one can expect MSM speedups on G1 when L > 36 and on G2 when L > 11. Note that, the inverse cost can be reduced with Pornin's algorithm for example.