Hashing to a field element

[tarcieri]

The elliptic-curve crate presently has a FromDigest trait which it uses for hashing to a scalar:

https://docs.rs/elliptic-curve/0.6.2/elliptic_curve/trait.FromDigest.html

I think it might make sense to move that trait into this crate (possibly gated on a digest cargo feature) so it can be used for implementing protocols generically which require hash-to-scalar.

[Pratyush]

It's probably better to leave that up to something like merlin, no?

[tarcieri]

The elliptic_curve::FromDigest trait above is used for ECDSA, so it'd be useful for at least that.

The immediate use case I have in mind for this feature request is FROST, and the possibility of having a generic implementation that works across bls12_381 and potentially things like a Taproot Schnorr implementation on secp256k1 (on the k256 crate) and potentially also Ristretto as well.

[tarcieri]

An alternative API that would probably also suffice for these cases would be something like from_repr_mod_order

[burdges]

In schnorrkel, I've had a witness delinearization trick for multi-signatures similar to FROST since early January 2020 (and discussed the approach with folks like Neven before that). It's a handy trick. I'll caution the "round optimized" part FROST still looks dangerous though.

Anyways, you want either (a) merlin-like construction or else (2) a hash plus from_repr_mod_order plus either (a) a stream cipher or (b) Clone. If you need Digest+Clone anyways then yeah maybe (1b) works best.

[str4d]

If we were to add an API for this, I think it would be from_bytes_mod_order_wide (a la curve25519_dalek::Scalar::from_bytes_mod_order_wide). If you are trying to hash to a field element, you almost certainly want something close to uniformly-distributed, and an API that permits taking slices close-to or smaller than the field representation length will not provide that guarantee. This would probably require adding a dependency on generic_array until we bump the MSRV to 1.51 for const generics.

[tarcieri]

In hindsight, I think this is a much thornier topic than I had originally considered when I opened the issue.

To take a step back, my original motivations were ECDSA, and the approach used by ECDSA is both one of many possible approaches and biased as it doesn't use a "wide" reduction.

The elliptic_curve::FromDigest trait as used and implemented presently is expressing something more of an eccentricity of ECDSA, and perhaps in that regard should be ecdsa::FromDigest instead.

Anyway, I'll leave this issue open at your discretion, as what should be done about a generalized trait for this purpose seems tricky at best.

[str4d]

If we're going to hash to a field element, I would suggest we bring in hash_to_field from the hash-to-curve ID. zkcrypto/bls12_381#59 includes a HashToField trait which I'm going to start thinking about / workshopping in bls12_381 with the intention of eventually migrating it into ff (and similarly the MapToCurve / HashToCurve traits into group).

[tarcieri]

Semi-related: there's @mikelodder7's hash2field crate which implements draft-irtf-cfrg-hash-to-curve-11, and includes some traits:

https://docs.rs/hash2field/0.2.0/hash2field/

[str4d]

We're now MSRV 1.51 for ff (due to bitvec 0.22), so I'd be interested in figuring out an approach compatible with const generics (which hash2field is using). I'm not sure how well it will interact with the digest crate though, which is still reliant on generic-array.

[tarcieri]

@str4d there are some hacks you can do to try to bridge the const generics and generic-array worlds. Here's an example:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=2303347b13be5981e1f5323adf30428a

use typenum::{U256, U384, U512};
use generic_array::{GenericArray, ArrayLength};

pub struct MyStruct<const N: usize>;

pub trait HashSize {
    type Size: ArrayLength<u8>;
}

impl HashSize for MyStruct<256> {
    type Size = U256;
}

impl HashSize for MyStruct<384> {
    type Size = U384;
}

impl HashSize for MyStruct<512> {
    type Size = U512;
}

pub type Hash256 = GenericArray<u8, <MyStruct<256> as HashSize>::Size>;