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

ark_ff/fields/field_hashers/expander/
mod.rs
