SW <-> TE map for Bandersnatch

[drskalman]

Description

Implement the birational map between the Short Weierstrass and Twisted Edwards forms of the Bandersnatch curve.

It is important because it is significantly cheaper to verifiy SNARK using the incomplete addition formula of SW form while Elligator hash-to-curve is significantly cheaper than WB or SWU hash-to-curve.

Specifically for Bandersnatch serializing in TE form saves a byte from 33 to 32 which is more machine friendly.

• [X] Targeted PR against correct branch (master)
• [X] Linked to GitHub issue with discussion and accepted design OR have an explanation in the PR that describes this work.
• [X] Wrote unit tests
• [X] Updated relevant documentation in the code
• [X] Added a relevant changelog entry to the Pending section in CHANGELOG.md
• [X] Re-reviewed Files changed in the GitHub PR explorer

[weikengchen]

Ok, I need to say that we generally want to have uniformity in the curve repository, so if we want to add, likely we will structure a trait and facilitates it from there. I.e., implementing it for all the curves if possible.

What do you think? It would be preferred, of course, if the implementation can be done for general curves.

But I want to ask a question about the motivation: so, if I remember correctly, the incomplete addition formula for SW should have similar performance with the one in twisted Edwards curve, nope?

[burdges]

I'd think one or more flavors of this map should typically exist whenever the both the TE and SW forms exist, although some exceptions exist. Among other reasons, serialization should be in Edwards, even if the circuts use SW, if only because the serialized form is one byte shorter, but often because advanced compression techniques are only researched for TE.

In particular, Bandersnatch should be serialized as ganderwagon, which reuqires passing through TE. I suppose decaf377 would similarlly be the preferable serialization for BLS12-377.

As a rule, you'll have worse interfaces if you rush into trait design than if you let the requirement emerge organically, with the hash-to-curve shit show being one example. We do not know if multiple isogenies were alredy deployed for bandersnatch, bls12-377, or ed25519.

[mmagician]

I agree with @weikengchen here. Also, contrary to what @burdges says, having an extra trait (say SW_TE_Mapping) doesn't mean the interface will necessarily get bloated. Instead, people can then choose to implement the trait for whatever curves they want.

[burdges]

It's quite general if you do roughly:

pub trait IsogenySW2TE {
    type SW: SWCurveConfig;
    type TE: TECurveConfig;
    ...
}

You can even still do impl IsogenySW2TE for Config { .. } in bls12_377 there, but doing this does not forbid other mappings since the curves are given by associated types.

I'm warning against assuming that particular impl exists, aka ignoring the associated types. I'm especially warning against doing this:

pub trait CannonicalSW2TE: SWCurveConfig + TECurveConfig {
    ...
}

I'm also saying there is no real reason to block providing the mapping upon selecting the trait, but if the general trait exists then whatever.

[moven0831]

Hi, I'm working on the SW <-> TE map for BN254 and came across this PR. Nice work! One question: is it possible to apply the same technique "Short Weierstrass <-> Montgomery <-> Twisted Edwards" for BN254 curve? Thank you.

Update: Since BN254 is a prime order curve, there is no TE model for it. Thanks for the clarification from Pratyush.