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 ark_std::vec::Vec;
5use digest::{DynDigest, ExtendableOutput, Update};
6pub trait Expander {
7    fn construct_dst_prime(&self) -> Vec<u8>;
8    fn expand(&self, msg: &[u8], length: usize) -> Vec<u8>;
9}
10const MAX_DST_LENGTH: usize = 255;
11
12const LONG_DST_PREFIX: [u8; 17] = [
13    //'H', '2', 'C', '-', 'O', 'V', 'E', 'R', 'S', 'I', 'Z', 'E', '-', 'D', 'S', 'T', '-',
14    0x48, 0x32, 0x43, 0x2d, 0x4f, 0x56, 0x45, 0x52, 0x53, 0x49, 0x5a, 0x45, 0x2d, 0x44, 0x53, 0x54,
15    0x2d,
16];
17
18pub(super) struct ExpanderXof<T: Update + Clone + ExtendableOutput> {
19    pub(super) xofer: T,
20    pub(super) dst: Vec<u8>,
21    pub(super) k: usize,
22}
23
24impl<T: Update + Clone + ExtendableOutput> Expander for ExpanderXof<T> {
25    fn construct_dst_prime(&self) -> Vec<u8> {
26        let mut dst_prime = if self.dst.len() > MAX_DST_LENGTH {
27            let mut xofer = self.xofer.clone();
28            xofer.update(&LONG_DST_PREFIX.clone());
29            xofer.update(&self.dst);
30            xofer.finalize_boxed((2 * self.k + 7) >> 3).to_vec()
31        } else {
32            self.dst.clone()
33        };
34        dst_prime.push(dst_prime.len() as u8);
35        dst_prime
36    }
37    fn expand(&self, msg: &[u8], n: usize) -> Vec<u8> {
38        let dst_prime = self.construct_dst_prime();
39        let lib_str = &[((n >> 8) & 0xFF) as u8, (n & 0xFF) as u8];
40
41        let mut xofer = self.xofer.clone();
42        xofer.update(msg);
43        xofer.update(lib_str);
44        xofer.update(&dst_prime);
45        xofer.finalize_boxed(n).to_vec()
46    }
47}
48
49pub(super) struct ExpanderXmd<T: DynDigest + Clone> {
50    pub(super) hasher: T,
51    pub(super) dst: Vec<u8>,
52    pub(super) block_size: usize,
53}
54
55impl<T: DynDigest + Clone> Expander for ExpanderXmd<T> {
56    fn construct_dst_prime(&self) -> Vec<u8> {
57        let mut dst_prime = if self.dst.len() > MAX_DST_LENGTH {
58            let mut hasher = self.hasher.clone();
59            hasher.update(&LONG_DST_PREFIX);
60            hasher.update(&self.dst);
61            hasher.finalize_reset().to_vec()
62        } else {
63            self.dst.clone()
64        };
65        dst_prime.push(dst_prime.len() as u8);
66        dst_prime
67    }
68    fn expand(&self, msg: &[u8], n: usize) -> Vec<u8> {
69        let mut hasher = self.hasher.clone();
70        // output size of the hash function, e.g. 32 bytes = 256 bits for sha2::Sha256
71        let b_len = hasher.output_size();
72        let ell = (n + (b_len - 1)) / b_len;
73        assert!(
74            ell <= 255,
75            "The ratio of desired output to the output size of hash function is too large!"
76        );
77
78        let dst_prime = self.construct_dst_prime();
79        let z_pad: Vec<u8> = vec![0; self.block_size];
80        // // Represent `len_in_bytes` as a 2-byte array.
81        // // As per I2OSP method outlined in https://tools.ietf.org/pdf/rfc8017.pdf,
82        // // The program should abort if integer that we're trying to convert is too large.
83        assert!(n < (1 << 16), "Length should be smaller than 2^16");
84        let lib_str: [u8; 2] = (n as u16).to_be_bytes();
85
86        hasher.update(&z_pad);
87        hasher.update(msg);
88        hasher.update(&lib_str);
89        hasher.update(&[0u8]);
90        hasher.update(&dst_prime);
91        let b0 = hasher.finalize_reset();
92
93        hasher.update(&b0);
94        hasher.update(&[1u8]);
95        hasher.update(&dst_prime);
96        let mut bi = hasher.finalize_reset();
97
98        let mut uniform_bytes: Vec<u8> = Vec::with_capacity(n);
99        uniform_bytes.extend_from_slice(&bi);
100        for i in 2..=ell {
101            // update the hasher with xor of b_0 and b_i elements
102            for (l, r) in b0.iter().zip(bi.iter()) {
103                hasher.update(&[*l ^ *r]);
104            }
105            hasher.update(&[i as u8]);
106            hasher.update(&dst_prime);
107            bi = hasher.finalize_reset();
108            uniform_bytes.extend_from_slice(&bi);
109        }
110        uniform_bytes[0..n].to_vec()
111    }
112}
113
114#[cfg(all(test, feature = "std"))]
115mod tests;
ark_ff/fields/field_hashers/expander/mod.rs

ark_ff/fields/field_hashers/expander/
mod.rs
