search

zcash / pasta_curves

Rust implementation for zcash/pasta
Other
81 stars 49 forks source link

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

Open daira opened 1 year ago

daira commented 1 year ago

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 https://github.com/privacy-scaling-explorations/halo2curves/issues/15).

str4d commented 1 year ago

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

str4d commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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 commented 1 year ago

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.