search

dalek-cryptography / curve25519-dalek

A pure-Rust implementation of group operations on Ristretto and Curve25519
Other
870 stars 439 forks source link

Ristretto to Montgomery #314

Closed vlopes11 closed 4 years ago

vlopes11 commented 4 years ago

Considering RistrettoPoint as a subgroup of edwards, the EdwardsPoint::to_montgomery method have an equivalent implementation for RistrettoPoint.

A use-case is described here: https://github.com/zcash/zcash/issues/3924#issuecomment-494004370

hdevalence commented 4 years ago

Hi there, I think I might not have been very clear in that comment (or assumed additional context), sorry!

The Ristretto group isn't just a subgroup of the Edwards points, and there's no conversion between Ristretto points and Montgomery points. What is possible is for a Ristretto implementation to implement Ristretto using Montgomery points instead of Edwards points internally, while still remaining wire-compatible with other Ristretto implementations. In other words, Ristretto implementations can choose which curve model (or even which curve) they want to use internally without breaking compatibility.

What this would look like is, instead of using the encoding/decoding formulas in the spec that decode to an internal Edwards point representation, an implementation could use different formulas that decode to an internal Montgomery point representation, if it was faster or better for some other reason to use Montgomery points. What are those formulas? They are obtained by tracing out maps in the conceptual diagram, but landing on M_{B,A} instead of E, and working out the explicit formulas.

The context for https://github.com/zcash/zcash/issues/3924#issuecomment-494004370 was that Montgomery formulas are faster in the cost model for ZK proofs, so a ZK proof implementation can use Ristretto with a circuit-friendly model inside of the proof and a machine-friendly model outside of the proof. But this implementation is a software implementation, and the Edwards points used internally are very fast, so there is no reason to use an internal representation based on Montgomery points instead.

Does that help?