Consider using the add-2007-bl and dbl-2009-l formulae

[daira]

Addition (incomplete, any a): http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
Doubling for a = 0: http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l

These are used in Arkworks for short Weierstrass curves. I also implemented a variant of them in the ChudnovskyPoint class in the Sage implementation of Pasta used to generate the hash-to-curve test vectors. (The latter actually modifies the addition formulae to be complete, at some extra cost.)

A possible alternative is https://eprint.iacr.org/2015/1060 (see also privacy-scaling-explorations/halo2curves#15).

[str4d]

We use https://eprint.iacr.org/2015/1060 for bls12_381; we may as well use it here too.

[str4d]

Also, looking at the code, we already use dbl-2009-l for Pallas and Vesta doubling (and dbl-2007-bl for the general doubling code for the Iso points).

[str4d]

Reminded myself how https://eprint.iacr.org/2015/1060 works, and it uses homogeneous coordinates; we currently use Jacobian coordinates because of the tie-in with hash-to-curve. So I think using these addition formulas (which would be concretely faster than the Jacobian ones, per section 4.2 of that paper) is a good idea, as point addition is used significantly more.

[zhenfeizhang]

Reminded myself how https://eprint.iacr.org/2015/1060 works, and it uses homogeneous coordinates; we currently use Jacobian coordinates because of the tie-in with hash-to-curve. So I think using these addition formulas (which would be concretely faster than the Jacobian ones, per section 4.2 of that paper) is a good idea, as point addition is used significantly more.

you can still do Jacobian hash to curves/groups. The output is in affine anyway so it does not really matter right?

[kayabaNerve]

I'd like to note the importance of this given the current addition function isn't constant time, enabling side channel attacks. While I can create a dedicated issue/PR for that, ideally that's handled with this IMO.