pathfinder icon indicating copy to clipboard operation
pathfinder copied to clipboard

feat(crypto): add xyzz coordinates

Open mikdk opened this issue 9 months ago • 0 comments

This PR adds XYZZ coordinates support for faster table-based scalar-multiplication:

  • Positive: Decreases the main elliptic curve operation used from 13M+2S to 8M+2S, where M is the field multiplications and S the number of squares.
  • Negative: Increases an elliptic curve point representation to four coordinates (x, y, zz, zzz) instead of standard two or three.

It is currently only applied to Pedersen, but should be applied to ECDSA during future revisions. From the decrease in field operation count, we should be able to get >30% off in theory. In practice, given the representation overhead, we get some ~10% off the table-based Pedersen-hash.

Additional notes:

  • We now let z=0 represent infinity in projective/xyzz coordinates (not affine), which is pretty standard and saves one word, concretely measured to 5-6% faster against the old projective-based Pedersen-hash during dev.
  • While this is faster, we should consider Jacobian for scalar-multiplication: More field operations than XYZZ, but less than Projective, while still only requiring three coordinates (x,y,z).

mikdk avatar May 10 '24 13:05 mikdk