toposware / cheetah

A STARK-friendly elliptic curve defined over a sextic extension of a small prime field.
Apache License 2.0
38 stars 3 forks source link

Introduce other point coordinate systems #6

Closed Nashtare closed 2 years ago

Nashtare commented 2 years ago

We currently have only Affine and Projective coordinates logic for the curve arithmetic. Being able to support other point coordinate systems may bring some performance benefits, for instance in the schnorr-sig crate.

For instance Jacobian coordinates are known for yielding relatively fast point doubling methods (about 2/3 of the running time of a point doubling in Projective coordinates) for a slightly slower addition algorithm. However, the use of Straus-Shamir's trick in signature verification reduces the impact of such change (as we have now N doublings and 2N additions).

Jacobian coordinates variants (like Chudnovsky) could also be investigated, though at the cost of a heavier point representation (240B instead of 144B for Jacobian/Projective).

Nashtare commented 2 years ago

It seems using Jacobian coordinates, while offering a speed-up of ~10% in the computation of s.G + h.P in the Schnorr signature verification, would be tricky to integrate inside our AIR program, as they are not complete and we would need a selector for the first bit set to 1 in the scalar multiplication (adding P. to acc = Infinity) to just assign the value of P instead of computing the addition.

Complete addition formulas for Jacobian coordinates, while possible, would induce a higer bidegree, which would make then impractical with respect to existing Projective coordinates formulas.

Nashtare commented 2 years ago

The use of Jacobian coordinates now that Lookups are integrated would actually be much more beneficial (while still problematic in the AIR program). In particular, we now have 256 doublings and 64 additions (compared to 256 doublings and 256 additions with prior double-and-add algorithms) for a scalar multiplication, i.e. 80% of doublings.

Nashtare commented 2 years ago

There's actually one issue with the use of Jacobian coordinates is constant-time addition of points (either homogenous or mixed with an affine point). While doubling can be made easily constant-time and still efficient (necessitating a final check before returning, similarly to its projective counterpart), there is no efficient exception-free jacobian addition formula, which requires to perform several additional checks (whether p1 or p2 is the infinity point, or if p1 = +/- p2), which would make any jacobian scalar multiplication non-competitive with the existing projective coordinates based one.

Nashtare commented 2 years ago

It may make sense to have Jacobian coordinates (or variants) for variable-time operation purposes only, as in that case it would be faster than equivalent variable time scalar multiplication methods in other coordinate systems.