search

arkworks-rs / algebra

Libraries for finite field, elliptic curve, and polynomial arithmetic
https://arkworks.rs
Apache License 2.0
601 stars 235 forks source link

Support mapping to all Weierstrass curves (Shallue-van de Woestijne method) #815

Open slumber opened 5 months ago

slumber commented 5 months ago

Only a handful of arkworks SW curves implement mapping, following https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-09 it's done for bls curves.

Suggestions:

  1. Introduce non-simplified SWU from here. There're existing implementations in Rust, and sage script for finding constants. Add a note for users

    For curves supported by the Simplified SWU method (Section 6.6.2), that mapping is the recommended one. Otherwise, the Simplified SWU method for AB == 0 (Section 6.6.3) is recommended if the goal is best performance, while the Shallue-van de Woestijne method (Section 6.6.1) is recommended if the goal is simplicity of implementation. (The reason for this distinction is that the Simplified SWU method for AB == 0 requires implementing an isogeny map in addition to the mapping function, while the Shallue-van de Woestijne method does not.)The Shallue-van de Woestijne method (Section 6.6.1) works with any curve, and may be used in cases where a generic mapping is required. Note, however, that this mapping is almost always more computationally expensive than the curve-specific recommendations above.

  2. Implement new trait for curves like BN254, ideally for all available curves. For example, the smallest degree of isogeny with ab != 0 for BN254 is 59, which should be super inefficient.
  3. Implement simplified SWU for the pasta cycle, as the isogeny for it exists https://github.com/zcash/pasta_curves/blob/main/src/hashtocurve.rs

Problems:

  1. Name clash of SWU with currently available (simplified) SWU. Other projects call non-simplified version SVDW. Alternatively, SWU can be renamed to SSWU. This is less favorable because existing code will seamlessly start using computationally expensive version.
  2. Having different mappings doesn't favor usage of generics, i.e. users will not be able to replace one curve with another, say bn254 with bls12-381 because of different algorithms. I believe users should choose "default" mapping themselves with adding their own trait and implementing it on used curves. Related https://github.com/arkworks-rs/algebra/issues/629
slumber commented 5 months ago

@Pratyush @mmagician @weikengchen

In case you agree with the issue I can submit PRs with implementations