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///
28/// 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).
29///
30/// # Examples
31///
32/// ```
33/// use ark_ff::fields::field_hashers::{DefaultFieldHasher, HashToField};
34/// use ark_test_curves::bls12_381::Fq;
35/// use sha2::Sha256;
36///
37/// let hasher = <DefaultFieldHasher<Sha256> as HashToField<Fq>>::new(&[1, 2, 3]);
38/// let field_elements: [Fq; 2] = hasher.hash_to_field(b"Hello, World!");
39///
40/// assert_eq!(field_elements.len(), 2);
41/// ```
42pub struct DefaultFieldHasher<H: FixedOutputReset + Default + Clone, const SEC_PARAM: usize = 128> {
43    expander: ExpanderXmd<H>,
44    len_per_base_elem: usize,
45}
46
47impl<F: Field, H: FixedOutputReset + Default + Clone, const SEC_PARAM: usize> HashToField<F>
48    for DefaultFieldHasher<H, SEC_PARAM>
49{
50    fn new(dst: &[u8]) -> Self {
51        // The final output of `hash_to_field` will be an array of field
52        // elements from F::BaseField, each of size `len_per_elem`.
53        let len_per_base_elem = get_len_per_elem::<F, SEC_PARAM>();
54
55        let expander = ExpanderXmd {
56            hasher: PhantomData,
57            dst: dst.to_vec(),
58            block_size: len_per_base_elem,
59        };
60
61        DefaultFieldHasher {
62            expander,
63            len_per_base_elem,
64        }
65    }
66
67    fn hash_to_field<const N: usize>(&self, message: &[u8]) -> [F; N] {
68        let m = F::extension_degree() as usize;
69
70        // The user requests `N` of elements of F_p^m to output per input msg,
71        // each field element comprising `m` BasePrimeField elements.
72        let len_in_bytes = N * m * self.len_per_base_elem;
73        let uniform_bytes = self.expander.expand(message, len_in_bytes);
74
75        let cb = |i| {
76            let base_prime_field_elem = |j| {
77                let elm_offset = self.len_per_base_elem * (j + i * m);
78                F::BasePrimeField::from_be_bytes_mod_order(
79                    &uniform_bytes[elm_offset..][..self.len_per_base_elem],
80                )
81            };
82            F::from_base_prime_field_elems((0..m).map(base_prime_field_elem)).unwrap()
83        };
84        ark_std::array::from_fn(cb)
85    }
86}
87
88pub fn hash_to_field<F: Field, H: XofReader, const SEC_PARAM: usize>(h: &mut H) -> F {
89    // The final output of `hash_to_field` will be an array of field
90    // elements from F::BaseField, each of size `len_per_elem`.
91    let len_per_base_elem = get_len_per_elem::<F, SEC_PARAM>();
92    // Rust *still* lacks alloca, hence this ugly hack.
93    let mut alloca = [0u8; 2048];
94    let alloca = &mut alloca[0..len_per_base_elem];
95
96    let m = F::extension_degree() as usize;
97
98    let base_prime_field_elem = |_| {
99        h.read(alloca);
100        F::BasePrimeField::from_be_bytes_mod_order(alloca)
101    };
102    F::from_base_prime_field_elems((0..m).map(base_prime_field_elem)).unwrap()
103}
104
105/// This function computes the length in bytes that a hash function should output
106/// for hashing an element of type `Field`.
107/// See section 5.1 and 5.3 of the
108/// [IETF hash standardization draft](https://datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve/14/)
109const fn get_len_per_elem<F: Field, const SEC_PARAM: usize>() -> usize {
110    // ceil(log(p))
111    let base_field_size_in_bits = F::BasePrimeField::MODULUS_BIT_SIZE as usize;
112    // ceil(log(p)) + security_parameter
113    let base_field_size_with_security_padding_in_bits = base_field_size_in_bits + SEC_PARAM;
114    // ceil( (ceil(log(p)) + security_parameter) / 8)
115    let bytes_per_base_field_elem =
116        base_field_size_with_security_padding_in_bits.div_ceil(8) as u64;
117    bytes_per_base_field_elem as usize
118}
ark_ff/fields/field_hashers/mod.rs

ark_ff/fields/field_hashers/
mod.rs
