Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement hash_to_scalar and hash_to_point #129

Closed
moCello opened this issue Dec 8, 2023 · 1 comment · Fixed by #130
Closed

Implement hash_to_scalar and hash_to_point #129

moCello opened this issue Dec 8, 2023 · 1 comment · Fixed by #130
Assignees

Comments

@moCello
Copy link
Member

moCello commented Dec 8, 2023

Summary

We need functionalities to hash an arbitrary slice of bytes to elements of the curve.
This includes hash_to_scalar and hash_to_point implementations.

Possible solution design or implementation

  • hash_to_scalar will sample an element of 2^512 bits and take the result modulo r with
r = 0x0e7db4ea6533afa906673b0101343b00a6682093ccc81082d0970e5ed6f72cb7
  • hash_to_point will be implemented naively with the same algorithm as used to derive GENERATOR_NUMS:
    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 r
    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 bls #137
and bls #139

@moCello
Copy link
Member Author

moCello commented Dec 8, 2023

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 added a commit that referenced this issue Dec 8, 2023
moCello added a commit that referenced this issue Dec 11, 2023
This was referenced Dec 12, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant