halo2curves_axiom/bls12_381/hash_to_curve/
mod.rs

Help
1//! This module implements hash_to_curve, hash_to_field and related
2//! hashing primitives for use with BLS signatures.
3//!
4//! Source: <https://github.com/privacy-scaling-explorations/bls12_381>
5
6use core::ops::Add;
7
8use subtle::Choice;
9
10pub(crate) mod chain;
11
12mod expand_msg;
13pub use self::expand_msg::{
14    ExpandMessage, ExpandMessageState, ExpandMsgXmd, ExpandMsgXof, InitExpandMessage,
15};
16
17mod map_g1;
18mod map_g2;
19mod map_scalar;
20
21use crate::bls12_381::generic_array::{typenum::Unsigned, ArrayLength, GenericArray};
22
23/// Enables a byte string to be hashed into one or more field elements for a given curve.
24///
25/// Implements [section 5 of `draft-irtf-cfrg-hash-to-curve-12`][hash_to_field].
26///
27/// [hash_to_field]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-12#section-5
28pub trait HashToField: Sized {
29    /// The length of the data used to produce an individual field element.
30    ///
31    /// This must be set to `m * L = m * ceil((ceil(log2(p)) + k) / 8)`, where `p` is the
32    /// characteristic of `Self`, `m` is the extension degree of `Self`, and `k` is the
33    /// security parameter.
34    type InputLength: ArrayLength<u8>;
35
36    /// Interprets the given output keying material as a big endian integer, and reduces
37    /// it into a field element.
38    fn from_okm(okm: &GenericArray<u8, Self::InputLength>) -> Self;
39
40    /// Hashes a byte string of arbitrary length into one or more elements of `Self`,
41    /// using [`ExpandMessage`] variant `X`.
42    ///
43    /// Implements [section 5.3 of `draft-irtf-cfrg-hash-to-curve-12`][hash_to_field].
44    ///
45    /// [hash_to_field]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-12#section-5.3
46    fn hash_to_field<X: ExpandMessage>(message: &[u8], dst: &[u8], output: &mut [Self]) {
47        let len_per_elm = Self::InputLength::to_usize();
48        let len_in_bytes = output.len() * len_per_elm;
49        let mut expander = X::init_expand(message, dst, len_in_bytes);
50
51        let mut buf = GenericArray::<u8, Self::InputLength>::default();
52        output.iter_mut().for_each(|item| {
53            expander.read_into(&mut buf[..]);
54            *item = Self::from_okm(&buf);
55        });
56    }
57}
58
59/// Allow conversion from the output of hashed or encoded input into points on the curve
60pub trait MapToCurve: Sized {
61    /// The field element type.
62    type Field: Copy + Default + HashToField;
63
64    /// Maps an element of the finite field `Self::Field` to a point on the curve `Self`.
65    fn map_to_curve(elt: &Self::Field) -> Self;
66
67    /// Clears the cofactor, sending a point on curve E to the target group (G1/G2).
68    fn clear_h(&self) -> Self;
69}
70
71/// Implementation of random oracle maps to the curve.
72pub trait HashToCurve<X: ExpandMessage>: MapToCurve + for<'a> Add<&'a Self, Output = Self> {
73    /// Implements a uniform encoding from byte strings to elements of `Self`.
74    ///
75    /// This function is suitable for most applications requiring a random
76    /// oracle returning points in `Self`.
77    fn hash_to_curve(message: impl AsRef<[u8]>, dst: &[u8]) -> Self {
78        let mut u = [Self::Field::default(); 2];
79        Self::Field::hash_to_field::<X>(message.as_ref(), dst, &mut u);
80        let p1 = Self::map_to_curve(&u[0]);
81        let p2 = Self::map_to_curve(&u[1]);
82        (p1 + &p2).clear_h()
83    }
84
85    /// Implements a **non-uniform** encoding from byte strings to elements of `Self`.
86    ///
87    /// The distribution of its output is not uniformly random in `Self`: the set of
88    /// possible outputs of this function is only a fraction of the points in `Self`, and
89    /// some elements of this set are more likely to be output than others. See
90    /// [section 10.1 of `draft-irtf-cfrg-hash-to-curve-12`][encode_to_curve-distribution]
91    /// for a more precise definition of `encode_to_curve`'s output distribution.
92    ///
93    /// [encode_to_curve-distribution]: https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-12#section-10.1
94    fn encode_to_curve(message: impl AsRef<[u8]>, dst: &[u8]) -> Self {
95        let mut u = [Self::Field::default(); 1];
96        Self::Field::hash_to_field::<X>(message.as_ref(), dst, &mut u);
97        let p = Self::map_to_curve(&u[0]);
98        p.clear_h()
99    }
100}
101
102impl<G, X> HashToCurve<X> for G
103where
104    G: MapToCurve + for<'a> Add<&'a Self, Output = Self>,
105    X: ExpandMessage,
106{
107}
108
109pub(crate) trait Sgn0 {
110    /// Returns either 0 or 1 indicating the "sign" of x, where sgn0(x) == 1
111    /// just when x is "negative". (In other words, this function always considers 0 to be positive.)
112    /// <https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-10#section-4.1>
113    /// The equivalent for draft 6 would be `lexicographically_largest`.
114    fn sgn0(&self) -> Choice;
115}
halo2curves_axiom/bls12_381/hash_to_curve/mod.rs

halo2curves_axiom/bls12_381/hash_to_curve/
mod.rs
