dusk-network / bls12_381

Implementation of the BLS12-381 pairing-friendly elliptic curve group with extra features needed by the Dusk-Network team
Other
19 stars 20 forks source link

Implement `hash_to_point` #139

Closed moCello closed 9 months ago

moCello commented 9 months ago

Summary

Implement hash_to_point function for hashing an arbitrary slice of bytes to a point on the bls12-381 elliptic curve.

Possible solution design or implementation

If possible make use of the hash_to_curve module, if not implement naive algorithm for not:

  1. hash the input bytes to a scalar using the above method
  2. use the scalar as x-coordinate and calculate y-coordinate according to the elliptic curve equation
  3. check whether the resulting point is in the group of elliptic curve points of order q with
    q = 0x73eda753299d7d483339d80809a1d80553bda402fffe5bfeffffffff00000001
  4. if not, increment x-coordinate by 1
  5. repeat until a correct element is found

Note: This implementation of hash_to_point is not ideal, in the long run we want to implement an algorithm outlined here, but we start with this implementation in order to be able to use the API already.

Additional context

See also jubjub #129

moCello commented 9 months ago

The algorithm for hash_to_point as outlined above has a drawback: With the equation

y^2 = x^3 + ax + b

there will always be two solutions (y and -y) for each valid x-coordinate. To avoid this ambiguity we can pick a slightly modified algorithm:

  1. hash the input and counter into an 32 bytes long array
  2. try to de-serialize the array into an affine point
  3. check if that affine point is on the curve and part of the subgroup
  4. increment counter if it isn't and repeat
moCello commented 9 months ago

I tried an implementation for G1Affine:

    pub fn hash_to_point(input: &[u8]) -> Self {
        let mut counter = 0u64;
        let mut array = [0u8; 48];
        loop {
            let state = blake2b_simd::Params::new()
                .hash_length(48)
                .to_state()
                .update(input)
                .update(&counter.to_le_bytes())
                .finalize();
            let bytes = state.as_bytes();

            array.copy_from_slice(&bytes[..48]);

            if let Ok(point) = <Self as Serializable<48>>::from_bytes(&array) {
                if point.is_torsion_free().into() {
                    return point.into();
                }
            }
            counter += 1
        }
    }

but the loop never terminated. The group elements seem to be too sparsely distributed for this approach to be feasible. Abandoning this effort for now as the user can already make use of the hash_to_curve module.