pathfinder
pathfinder copied to clipboard
feat(crypto): add xyzz coordinates
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).