MystenLabs / fastcrypto

Common cryptographic library used in software at Mysten Labs.
Apache License 2.0
244 stars 138 forks source link

Use double scalar multiplication optimisations in the ristretto255 group and the ECVRF impl #388

Closed jonas-lj closed 1 year ago

jonas-lj commented 1 year ago
          > Interesting comparison results, I was originally surprised they are so close because for Ed25519 we've found that the sweet point was at about 40x, but here it's only 4x. I can imagine the results makes sense because in ECVRF we use
  • map to point (which doesn't exist in ed25519)
  • operations over non group generators (every H(m) and ChaumPed proofs result to unknown points) (and for ed25519 we applied precomputed tables which improve performance by far)
  • Ristretto implementations are slightly more expensive than pure ed25519 in Rust.
  • we don't utilize aG + bP double scalar mul optimizations.

There are a multiple different operations and libraries in play which makes it hard to compare them, so I suggest that we create benchmarks for basic operations (hash-to-curve, arithmetic) for the groups we support to make comparison easier.

We don't utilise double scalar multiplication, but I'll check if it's possible.

Originally posted by @jonas-lj in https://github.com/MystenLabs/fastcrypto/issues/381#issuecomment-1411609755

jonas-lj commented 1 year ago

This seems to speed-up verification with ~35%. A PR is coming up.