Ordering on curve points

[paberr]

For some applications it might be necessary to define an order on the elliptic curve points. To give you an example, I am currently building an application using BLS signature built on top of this pairing library that needs to order the public keys by some deterministic ordering.

Currently, the only way to do that is using the encoded forms. And that leaves us with three options:

• Storing PublicKeys in a serialised form
• Serialising PublicKeys for every comparison
• Storing PublicKeys in both, serialised and point form

None of these options is really attractive.

To mitigate this, there would be multiple options available:

1. Implementing Ord on curve points
2. Adding a function similar to the Ord::cmp
3. Adding an option to expose the internals of a curve point

Since the ordering is not really well defined, I am not a big fan of option 1. I also don't like exposing the internal coordinates too much (could also be done for the specific curve implementations only), although I would see it as a valid option. Option 2 currently seems to be the cleanest to me.

I'd like to hear other opinions as well.

Edit: I saw that Fq/Fq2 implement Ord as well and define lexicographic ordering, so option 1. might still be in. An example of how to implement a lexicographic ordering can be found in my fork.

[burdges]

You must normalize curve points before any ordering makes sense, btw. I added this in https://github.com/burdges/pairing/blob/master-hashing-derives_borrows_etc0/src/bls12_381/ec.rs#L780 for BLS too. I also addressed the BLS aggregation issues in https://github.com/w3f/bls including doing the batch normalization operations in sensible places, but that used hashmaps mostly.

We've a discussion thread at https://github.com/filecoin-project/research/issues/53 on attempting to use the same fork until librustzcash refactor gets done. https://github.com/filecoin-project/research/issues/53