Understanding the hash-to-curve Function

It remains to take a look at what the hash_to_curve function defined in the src/hash module is doing exactly:

use ark_bls12_381::{G1Affine, G1Projective};
use ark_crypto_primitives::crh::{
    pedersen::{Window, CRH},
    CRH as CRHScheme,
};
use rand::SeedableRng;
use rand_chacha::ChaCha20Rng;

// --snip--

#[derive(Clone)]
struct ZkHackPedersenWindow {}

impl Window for ZkHackPedersenWindow {
    const WINDOW_SIZE: usize = 1;
    const NUM_WINDOWS: usize = 256;
}

pub fn hash_to_curve(msg: &[u8]) -> (Vec<u8>, G1Affine) {
    let rng_pedersen = &mut ChaCha20Rng::from_seed([
        1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
        1, 1,
    ]);
    let parameters = CRH::<G1Projective, ZkHackPedersenWindow>::setup(rng_pedersen).unwrap();
    let b2hash = blake2s_simd::blake2s(msg);
    (
        b2hash.as_bytes().to_vec(),
        CRH::<G1Projective, ZkHackPedersenWindow>::evaluate(&parameters, b2hash.as_bytes())
            .unwrap(),
    )
}

This function first initializes the pseudorandom number generator ChaCha20 with a 32-byte seed and feeds this RNG to the setup function. We look up the setup function in the crypto_primitives::crh::pedersen submodule (how do we know where to look? we check the use statement which brings CRH into scope at the beginning of the src/hash.rs file) and arrive here. Documentation is nonexistent so we jump to the code. Here are the relevant lines:

pub struct Parameters<C: ProjectiveCurve> {
    pub generators: Vec<Vec<C>>,
}

pub struct CRH<C: ProjectiveCurve, W: Window> {
    group: PhantomData<C>,
    window: PhantomData<W>,
}

impl<C: ProjectiveCurve, W: Window> CRHTrait for CRH<C, W> {
    const INPUT_SIZE_BITS: usize = W::WINDOW_SIZE * W::NUM_WINDOWS;
    type Output = C::Affine;
    type Parameters = Parameters<C>;

    fn setup<R: Rng>(rng: &mut R) -> Result<Self::Parameters, Error> {
        // ...
        let generators = Self::create_generators(rng);
        // ...
        Ok(Self::Parameters { generators })
    }

    // ...
}

impl<C: ProjectiveCurve, W: Window> CRH<C, W> {
    pub fn create_generators<R: Rng>(rng: &mut R) -> Vec<Vec<C>> {
        let mut generators_powers = Vec::new();
        for _ in 0..W::NUM_WINDOWS {
            generators_powers.push(Self::generator_powers(W::WINDOW_SIZE, rng));
        }
        generators_powers
    }

    pub fn generator_powers<R: Rng>(num_powers: usize, rng: &mut R) -> Vec<C> {
        let mut cur_gen_powers = Vec::with_capacity(num_powers);
        let mut base = C::rand(rng);
        for _ in 0..num_powers {
            cur_gen_powers.push(base);
            base.double_in_place();
        }
        cur_gen_powers
    }
}

Each invocation of generator_powers draws a random group element and returns the vector where W::WINDOW_SIZE. This function is called NUM_WINDOWS times by create_generators which then returns a vector where are random group elements. In hash_to_curve, this function is called with constants WINDOW_SIZE = 1 and NUM_WINDOWS = 256 as defined in the implementation of trait Window for struct ZkHackPedersenWindow. Hence, the line

let parameters = CRH::<G1Projective, ZkHackPedersenWindow>::setup(rng_pedersen).unwrap();

defines a Parameters<G1Projective> struct whose field generators holds a tuple of 256 random group elements of type G1Projective.

Then, the message is hashed with hash function BLAKE2s and the result is passed to the evaluate function, whose core is as follows:

    fn evaluate(parameters: &Self::Parameters, input: &[u8]) -> Result<Self::Output, Error> {
        // ...

        // Compute sum of h_i^{m_i} for all i.
        let bits = bytes_to_bits(input);
        let result = cfg_chunks!(bits, W::WINDOW_SIZE)
            .zip(&parameters.generators)
            .map(|(bits, generator_powers)| {
                let mut encoded = C::zero();
                for (bit, base) in bits.iter().zip(generator_powers.iter()) {
                    if *bit {
                        encoded += base;
                    }
                }
                encoded
            })
            .sum::<C>();

        // ...

        Ok(result.into())
    }

First, the input is converted into a vector of booleans using the bytes_to_bits function from the pedersen module. Then, it is split into NUM_WINDOWS chunks of size WINDOW_SIZE and zipped with parameters.generators which contains the points returned by setup. The closure inside map takes a chunk of bits and a vector of points and returns where is the integer whose bit representation is The final value of result is the sum over the windows of the output of this closure, i.e., where is the integer corresponding to the -th chunk of bits of the input.

In the specific case of hash_to_curve, we have and Hence, if we let denote the 256 group elements returned by setup and denote the output of the BLAKE2s hash function applied to message seen as a vector of bits, then the hash_to_curve function applied to returns the point on defined by

Hence, can be seen as the composition of BLAKE2s and an instance of Pedersen hashing. Since both BLAKE2s and Pedersen hashing are collision-resistant (assuming hardness of the discrete logarithm problem for Pedersen hashing), is collision-resistant as well. Is it sufficient to make BLS signatures secure though?

Now that we understand all parts of the code, we can get down to solving the puzzle.