Dump all ed25519 compatability about schnorrkel HOT 2 CLOSED

It's obvious the problem with ristretto not being canonical goes both ways. I therefore pulled out all public key migration code without separating anything in 024bc92 but I put the code in https://github.com/w3f/schnorrkel/tree/master/iffy/migration_from_ed25519/src from which someone can make a migration crate that warns about permitting two different migration crates to exist.

from schnorrkel.

We should understand how this creates insecurity:

ristretto was roughly described by Mike Hamburg in section 7 on page 13 of his Decaf paper, but that does not explain the shortcoming.

According to https://ristretto.group/details/index.html ristretto use an encoding of a Jacobi quartic like in section 4 of the Decaf paper, but with a different isogeny so the explicit formulas for ristretto differ slightly from those given in appendix A.1.

If I understand, the decoding algorithm still works if one chooses another branch of the inverse square root, but these give equivalent resulting ristretto points.

In consequence, if you export an ed25519 public key from ristretto then implementations may export different keys. In particular, users might be unable to access funds from a particular wallet.

I do not know if merely importing an ed25519 key into ristretto creates problems, but the decaf paper's encodings do not restrict to specific points, so they should support importing keys. I'm unsure if ristretto does anything more aggressive here, but presumably no.

There are three changes listed in on page 3 of the Decaf paper: equality, compression, and decompression. We clearly need the decaf compression anytime we hash points in a schnorr proof. Are decaf equality and compression as "hashing form points" really compatible with an ed25519 wire format from which you import keys whenever using them?

I think so, but these compression and decompression operations have non-trivial cost, and the decaf and ristretto ones have similar costs to the ordinary ed2559 ones, so if algorithms cache points correctly then doing this roughly doubles these costs for both proovers and verifiers.

Anyways, I still believe these modules should be extracted into another "ed25519-ristretto-migration" crate, which itself contains a scary warning against exporting keys, or simply removes that functionality.

from schnorrkel.