ark_ff/fields/field_hashers/expander/
mod.rs

1// The below implementation is a rework of https://github.com/armfazh/h2c-rust-ref
2// With some optimisations
3
4use core::marker::PhantomData;
5
6use ark_std::vec::*;
7
8use arrayvec::ArrayVec;
9use digest::{ExtendableOutput, FixedOutputReset, Update};
10
11pub trait Expander {
12    fn expand(&self, msg: &[u8], length: usize) -> Vec<u8>;
13}
14const MAX_DST_LENGTH: usize = 255;
15
16const LONG_DST_PREFIX: &[u8; 17] = b"H2C-OVERSIZE-DST-";
17
18/// Implements section [5.3.3](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#section-5.3.3)
19/// "Using DSTs longer than 255 bytes" of the
20/// [IRTF CFRG hash-to-curve draft #16](https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-16#section-5.3.3).
21pub struct DST(arrayvec::ArrayVec<u8, MAX_DST_LENGTH>);
22
23impl DST {
24    pub fn new_xmd<H: FixedOutputReset + Default>(dst: &[u8]) -> DST {
25        let array = if dst.len() > MAX_DST_LENGTH {
26            let mut long = H::default();
27            long.update(&LONG_DST_PREFIX[..]);
28            long.update(&dst);
29            ArrayVec::try_from(long.finalize_fixed().as_ref()).unwrap()
30        } else {
31            ArrayVec::try_from(dst).unwrap()
32        };
33        DST(array)
34    }
35
36    #[allow(dead_code)]
37    pub fn new_xof<H: ExtendableOutput + Default>(dst: &[u8], k: usize) -> DST {
38        let array = if dst.len() > MAX_DST_LENGTH {
39            let mut long = H::default();
40            long.update(&LONG_DST_PREFIX[..]);
41            long.update(&dst);
42
43            let mut new_dst = [0u8; MAX_DST_LENGTH];
44            let new_dst = &mut new_dst[0..((2 * k + 7) >> 3)];
45            long.finalize_xof_into(new_dst);
46            ArrayVec::try_from(&*new_dst).unwrap()
47        } else {
48            ArrayVec::try_from(dst).unwrap()
49        };
50        DST(array)
51    }
52
53    pub fn update<H: Update>(&self, h: &mut H) {
54        h.update(self.0.as_ref());
55        // I2OSP(len,1) https://www.rfc-editor.org/rfc/rfc8017.txt
56        h.update(&[self.0.len() as u8]);
57    }
58}
59
60#[allow(dead_code)]
61pub(super) struct ExpanderXof<H: ExtendableOutput + Clone + Default> {
62    pub(super) xofer: PhantomData<H>,
63    pub(super) dst: Vec<u8>,
64    pub(super) k: usize,
65}
66
67impl<H: ExtendableOutput + Clone + Default> Expander for ExpanderXof<H> {
68    fn expand(&self, msg: &[u8], n: usize) -> Vec<u8> {
69        let mut xofer = H::default();
70        xofer.update(msg);
71
72        // I2OSP(len,2) https://www.rfc-editor.org/rfc/rfc8017.txt
73        let lib_str = (n as u16).to_be_bytes();
74        xofer.update(&lib_str);
75
76        DST::new_xof::<H>(self.dst.as_ref(), self.k).update(&mut xofer);
77        xofer.finalize_boxed(n).into_vec()
78    }
79}
80
81pub(super) struct ExpanderXmd<H: FixedOutputReset + Default + Clone> {
82    pub(super) hasher: PhantomData<H>,
83    pub(super) dst: Vec<u8>,
84    pub(super) block_size: usize,
85}
86
87static Z_PAD: [u8; 256] = [0u8; 256];
88
89impl<H: FixedOutputReset + Default + Clone> Expander for ExpanderXmd<H> {
90    fn expand(&self, msg: &[u8], n: usize) -> Vec<u8> {
91        use digest::typenum::Unsigned;
92        // output size of the hash function, e.g. 32 bytes = 256 bits for sha2::Sha256
93        let b_len = H::OutputSize::to_usize();
94        let ell = (n + (b_len - 1)) / b_len;
95        assert!(
96            ell <= 255,
97            "The ratio of desired output to the output size of hash function is too large!"
98        );
99
100        let dst_prime = DST::new_xmd::<H>(self.dst.as_ref());
101        // Represent `len_in_bytes` as a 2-byte array.
102        // As per I2OSP method outlined in https://tools.ietf.org/pdf/rfc8017.pdf,
103        // The program should abort if integer that we're trying to convert is too large.
104        assert!(n < (1 << 16), "Length should be smaller than 2^16");
105        let lib_str: [u8; 2] = (n as u16).to_be_bytes();
106
107        let mut hasher = H::default();
108        hasher.update(&Z_PAD[0..self.block_size]);
109        hasher.update(msg);
110        hasher.update(&lib_str);
111        hasher.update(&[0u8]);
112        dst_prime.update(&mut hasher);
113        let b0 = hasher.finalize_fixed_reset();
114
115        hasher.update(&b0);
116        hasher.update(&[1u8]);
117        dst_prime.update(&mut hasher);
118        let mut bi = hasher.finalize_fixed_reset();
119
120        let mut uniform_bytes: Vec<u8> = Vec::with_capacity(n);
121        uniform_bytes.extend_from_slice(&bi);
122        for i in 2..=ell {
123            // update the hasher with xor of b_0 and b_i elements
124            for (l, r) in b0.iter().zip(bi.iter()) {
125                hasher.update(&[*l ^ *r]);
126            }
127            hasher.update(&[i as u8]);
128            dst_prime.update(&mut hasher);
129            bi = hasher.finalize_fixed_reset();
130            uniform_bytes.extend_from_slice(&bi);
131        }
132        uniform_bytes.truncate(n);
133        uniform_bytes
134    }
135}
136
137#[cfg(all(test, feature = "std"))]
138mod tests;
ark_ff/fields/field_hashers/expander/mod.rs

ark_ff/fields/field_hashers/expander/
mod.rs
