Idiomatic HashToField

[burdges]

Is construct_dst_prime from ExpanderXof anywhere in the spec? If not, then maybe we should remove it? Anyways..

I'd think ExpanderXof should become a free pub fn like

fn update_dst_prime<H, const K: u16>(h &mut H, dst: &[u8]) 
where H: ExtendableOutput+Default+Sized,
{
    if self.dst.len() > MAX_DST_LENGTH {
        let mut long = H::default();
        long.update(&LONG_DST_PREFIX.clone());
        long.update(&self.dst);
        let mut dst = [0u8; MAX_DST_LENGTH];
        long.finalize_xof_into(dst);
        h.update( dst[0..(2 * K + 7) >> 3] );
    } else {
        h.update(dst);
    };
    // I2OSP(len,1) https://www.rfc-editor.org/rfc/rfc8017.txt
    h.update(dst.len() as u8);
}

pub fn expand_xof<H>(domain: &[u8], message: &[u8]) -> Result<<H as ExtendableOutput>::Reader, &'static str>
where H: ExtendableOutput+Default+Sized
{
    if message.len() > u16::MAX as usize {
        return Err("expand_message_xof cannot handle messages longer than 2^16 bytes.");
    }
    let len = message.len() as u16;
    let mut h = H:default();

    h.update(message)
    /// I2OSP(len,2) https://www.rfc-editor.org/rfc/rfc8017.txt
    h.update(len.to_be_bytes())
    update_dst_prime(&mut h,domain);
    h.finalize_xof()
}

We could seemingly impl<H: Digest+Clone> XofReader for ExpanderXmd<H> too. I think KeyInit cannot work here, so we'd provide some free fn like

pub fn expand_xmd<H: Digest+Clone>(domain: &[u8], message: &[u8]) -> ExpanderXmd<H> { ... }

It's possible the rust crypto project would upstream this somehow even.

At this point, XoFs have become our common currency, so our HashToField trait also becomes a free fn like

pub fn hash_to_field<F: Field,H: XofReader>(h: &mut H) -> F { .. }

As field hashers are specified for each curve, individual curves might specify them via

pub trait HashToCurve: CurveGroup {
    pub fn hash_to_curve(domain: &[u8], message: &[u8]) -> Self { ... }
}

Assuming #629 this looks like:

impl HashToCurve for Projective<Config> {
    pub fn hash_to_curve(domain: &[u8], message: &[u8]) -> Self {
        ark_ec::hashing::xof_to_curve( ark_ec::hashing::expand_xmd::<sha2::sha256>(domain, message) )
    }
}

where

// Produce a hash of the message, using the hash to field and map to curve
// traits. This uses the IETF hash to curve's specification for Random
// oracle encoding (hash_to_curve) defined by combining these components.
// See https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-09#section-3
pub fn xof_to_curve<C: MapToCurve,H:XofReader>(h: &mut H) -> C {
    // IETF spec of hash_to_curve, from hash_to_field and map_to_curve
    // sub-components
    // 1. u = hash_to_field(msg, 2)
    // 2. Q0 = map_to_curve(u[0])
    // 3. Q1 = map_to_curve(u[1])
    // 4. R = Q0 + Q1              # Point addition
    // 5. P = clear_cofactor(R)
    // 6. return P
    let rand_curve_elem_0 = C::map_to_curve(hash_to_field(h));
    let rand_curve_elem_1 = C::map_to_curve(hash_to_field(h));

    // TODO: Avoid the extra affine conversion before clearing the cofactor. 
    Ok( (rand_curve_elem_0 + rand_curve_elem_1).into().mul_by_cofactor_to_group() )
}

[burdges]

I've slightly wrong here, the IRTF draft cannot be described using XofReader because they hash the output length. We might still simplify the code along similar lines, using our own XoF-like trait, but not really sure. I'll close this for now.

[burdges]

I think XofReader works anyways, but then under the hood you're taking the same field as input in two places, only a minor wart in the higher level interface.

[burdges]

It's mostly done in https://github.com/w3f/arkworks-algebra/tree/xof_reader but we should still clean up the map_to_curve mess ala #629