ark_ff/fields/field_hashers/
mod.rs

1mod expander;
2
3use core::marker::PhantomData;
4
5use crate::{Field, PrimeField};
6
7use digest::{FixedOutputReset, XofReader};
8use expander::Expander;
9
10use self::expander::ExpanderXmd;
11
12/// Trait for hashing messages to field elements.
13pub trait HashToField<F: Field>: Sized {
14    /// Initialises a new hash-to-field helper struct.
15    ///
16    /// # Arguments
17    ///
18    /// * `domain` - bytes that get concatenated with the `msg` during hashing, in order to separate potentially interfering instantiations of the hasher.
19    fn new(domain: &[u8]) -> Self;
20
21    /// Hash an arbitrary `msg` to `N` elements of the field `F`.
22    fn hash_to_field<const N: usize>(&self, msg: &[u8]) -> [F; N];
23}
24
25/// This field hasher constructs a Hash-To-Field based on a fixed-output hash function,
26/// like SHA2, SHA3 or Blake2.
27/// The implementation aims to follow the specification in [Hashing to Elliptic Curves (draft)](https://tools.ietf.org/pdf/draft-irtf-cfrg-hash-to-curve-13.pdf).
28///
29/// # Examples
30///
31/// ```
32/// use ark_ff::fields::field_hashers::{DefaultFieldHasher, HashToField};
33/// use ark_test_curves::bls12_381::Fq;
34/// use sha2::Sha256;
35///
36/// let hasher = <DefaultFieldHasher<Sha256> as HashToField<Fq>>::new(&[1, 2, 3]);
37/// let field_elements: [Fq; 2] = hasher.hash_to_field(b"Hello, World!");
38///
39/// assert_eq!(field_elements.len(), 2);
40/// ```
41pub struct DefaultFieldHasher<H: FixedOutputReset + Default + Clone, const SEC_PARAM: usize = 128> {
42    expander: ExpanderXmd<H>,
43    len_per_base_elem: usize,
44}
45
46impl<F: Field, H: FixedOutputReset + Default + Clone, const SEC_PARAM: usize> HashToField<F>
47    for DefaultFieldHasher<H, SEC_PARAM>
48{
49    fn new(dst: &[u8]) -> Self {
50        // The final output of `hash_to_field` will be an array of field
51        // elements from F::BaseField, each of size `len_per_elem`.
52        let len_per_base_elem = get_len_per_elem::<F, SEC_PARAM>();
53
54        let expander = ExpanderXmd {
55            hasher: PhantomData,
56            dst: dst.to_vec(),
57            block_size: len_per_base_elem,
58        };
59
60        DefaultFieldHasher {
61            expander,
62            len_per_base_elem,
63        }
64    }
65
66    fn hash_to_field<const N: usize>(&self, message: &[u8]) -> [F; N] {
67        let m = F::extension_degree() as usize;
68
69        // The user requests `N` of elements of F_p^m to output per input msg,
70        // each field element comprising `m` BasePrimeField elements.
71        let len_in_bytes = N * m * self.len_per_base_elem;
72        let uniform_bytes = self.expander.expand(message, len_in_bytes);
73
74        let cb = |i| {
75            let base_prime_field_elem = |j| {
76                let elm_offset = self.len_per_base_elem * (j + i * m);
77                F::BasePrimeField::from_be_bytes_mod_order(
78                    &uniform_bytes[elm_offset..][..self.len_per_base_elem],
79                )
80            };
81            F::from_base_prime_field_elems((0..m).map(base_prime_field_elem)).unwrap()
82        };
83        ark_std::array::from_fn::<F, N, _>(cb)
84    }
85}
86
87pub fn hash_to_field<F: Field, H: XofReader, const SEC_PARAM: usize>(h: &mut H) -> F {
88    // The final output of `hash_to_field` will be an array of field
89    // elements from F::BaseField, each of size `len_per_elem`.
90    let len_per_base_elem = get_len_per_elem::<F, SEC_PARAM>();
91    // Rust *still* lacks alloca, hence this ugly hack.
92    let mut alloca = [0u8; 2048];
93    let alloca = &mut alloca[0..len_per_base_elem];
94
95    let m = F::extension_degree() as usize;
96
97    let base_prime_field_elem = |_| {
98        h.read(alloca);
99        F::BasePrimeField::from_be_bytes_mod_order(alloca)
100    };
101    F::from_base_prime_field_elems((0..m).map(base_prime_field_elem)).unwrap()
102}
103
104/// This function computes the length in bytes that a hash function should output
105/// for hashing an element of type `Field`.
106/// See section 5.1 and 5.3 of the
107/// [IETF hash standardization draft](https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/14/)
108const fn get_len_per_elem<F: Field, const SEC_PARAM: usize>() -> usize {
109    // ceil(log(p))
110    let base_field_size_in_bits = F::BasePrimeField::MODULUS_BIT_SIZE as usize;
111    // ceil(log(p)) + security_parameter
112    let base_field_size_with_security_padding_in_bits = base_field_size_in_bits + SEC_PARAM;
113    // ceil( (ceil(log(p)) + security_parameter) / 8)
114    let bytes_per_base_field_elem =
115        ((base_field_size_with_security_padding_in_bits + 7) / 8) as u64;
116    bytes_per_base_field_elem as usize
117}
ark_ff/fields/field_hashers/mod.rs

ark_ff/fields/field_hashers/
mod.rs
