snarkvm_circuit_algorithms/bhp/
hash_uncompressed.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use super::*;
17
18impl<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> HashUncompressed
19    for BHP<E, NUM_WINDOWS, WINDOW_SIZE>
20{
21    type Input = Boolean<E>;
22    type Output = Group<E>;
23
24    /// Returns the BHP hash of the given input as an affine group element.
25    ///
26    /// This uncompressed variant of the BHP hash function is provided to support
27    /// the BHP commitment scheme, as it is typically not used by applications.
28    fn hash_uncompressed(&self, input: &[Self::Input]) -> Self::Output {
29        // The number of hasher bits to fit.
30        let num_hasher_bits = NUM_WINDOWS as usize * WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
31        // The number of data bits in the output.
32        let num_data_bits = E::BaseField::size_in_data_bits();
33        // The maximum number of input bits per iteration.
34        let max_input_bits_per_iteration = num_hasher_bits - num_data_bits;
35
36        debug_assert!(num_data_bits < num_hasher_bits);
37        debug_assert_eq!(num_data_bits - 64, self.domain.len());
38
39        // Initialize a variable to store the hash from the current iteration.
40        let mut digest = Group::zero();
41
42        // Prepare a reusable vector for the preimage.
43        let mut preimage = Vec::with_capacity(num_hasher_bits);
44
45        // Compute the hash of the input.
46        for (i, input_bits) in input.chunks(max_input_bits_per_iteration).enumerate() {
47            // Determine if this is the first iteration.
48            match i == 0 {
49                // Construct the first iteration as: [ 0...0 || DOMAIN || LENGTH(INPUT) || INPUT[0..BLOCK_SIZE] ].
50                true => {
51                    // Initialize a vector for the hash preimage.
52                    preimage.extend(self.domain.clone());
53                    U64::constant(console::U64::new(input.len() as u64)).write_bits_le(&mut preimage);
54                    preimage.extend_from_slice(input_bits);
55                }
56                // Construct the subsequent iterations as: [ PREVIOUS_HASH[0..DATA_BITS] || INPUT[I * BLOCK_SIZE..(I + 1) * BLOCK_SIZE] ].
57                false => {
58                    // Initialize a vector for the hash preimage.
59                    digest.to_x_coordinate().write_bits_le(&mut preimage);
60                    preimage.truncate(num_data_bits);
61                    preimage.extend_from_slice(input_bits);
62                }
63            }
64            // Hash the preimage for this iteration.
65            digest = self.hasher.hash_uncompressed(&preimage);
66            // Clear the preimage vector for the next iteration.
67            preimage.clear();
68        }
69
70        digest
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77    use snarkvm_circuit_types::environment::Circuit;
78    use snarkvm_curves::{AffineCurve, ProjectiveCurve};
79    use snarkvm_utilities::{TestRng, Uniform};
80
81    use anyhow::Result;
82
83    const ITERATIONS: u64 = 100;
84    const DOMAIN: &str = "BHPCircuit0";
85
86    macro_rules! check_hash_uncompressed {
87        ($bhp:ident, $mode:ident, $num_bits:expr, ($num_constants:expr, $num_public:expr, $num_private:expr, $num_constraints:expr), $rng:expr) => {{
88            // Initialize BHP.
89            let native = console::$bhp::<<Circuit as Environment>::Network>::setup(DOMAIN)?;
90            let circuit = $bhp::<Circuit>::constant(native.clone());
91
92            for i in 0..ITERATIONS {
93                // Sample a random input.
94                let input = (0..$num_bits).map(|_| Uniform::rand($rng)).collect::<Vec<_>>();
95                // Compute the expected hash.
96                let expected = console::HashUncompressed::hash_uncompressed(&native, &input)?;
97                // Prepare the circuit input.
98                let circuit_input: Vec<Boolean<_>> = Inject::new(Mode::$mode, input);
99
100                Circuit::scope(format!("BHP {i}"), || {
101                    // Perform the hash operation.
102                    let candidate = circuit.hash_uncompressed(&circuit_input);
103                    assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
104                    assert_eq!(expected, candidate.eject_value());
105                    assert!(candidate.eject_value().to_affine().is_on_curve());
106                    assert!(candidate.eject_value().to_affine().is_in_correct_subgroup_assuming_on_curve());
107                });
108                Circuit::reset();
109            }
110            Ok::<_, anyhow::Error>(())
111        }};
112    }
113
114    fn check_hash_uncompressed<const NUM_WINDOWS: u8, const WINDOW_SIZE: u8>(
115        mode: Mode,
116        num_constants: u64,
117        num_public: u64,
118        num_private: u64,
119        num_constraints: u64,
120    ) -> Result<()> {
121        use console::HashUncompressed as H;
122
123        // Initialize BHP.
124        let native = console::BHP::<<Circuit as Environment>::Network, NUM_WINDOWS, WINDOW_SIZE>::setup(DOMAIN)?;
125        let circuit = BHP::<Circuit, NUM_WINDOWS, WINDOW_SIZE>::new(Mode::Constant, native.clone());
126        // Determine the number of inputs.
127        let num_input_bits = NUM_WINDOWS as usize * WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
128
129        let mut rng = TestRng::default();
130
131        for i in 0..ITERATIONS {
132            // Sample a random input.
133            let input = (0..num_input_bits).map(|_| bool::rand(&mut rng)).collect::<Vec<bool>>();
134            // Compute the expected hash.
135            let expected = native.hash_uncompressed(&input).expect("Failed to hash native input");
136            // Prepare the circuit input.
137            let circuit_input: Vec<Boolean<_>> = Inject::new(mode, input);
138
139            Circuit::scope(format!("BHP {mode} {i}"), || {
140                // Perform the hash operation.
141                let candidate = circuit.hash_uncompressed(&circuit_input);
142                assert_scope!(num_constants, num_public, num_private, num_constraints);
143                assert_eq!(expected, candidate.eject_value());
144            });
145            Circuit::reset();
146        }
147        Ok(())
148    }
149
150    #[test]
151    fn test_hash_uncompressed_constant() -> Result<()> {
152        check_hash_uncompressed::<32, 48>(Mode::Constant, 7239, 0, 0, 0)
153    }
154
155    #[test]
156    fn test_hash_uncompressed_public() -> Result<()> {
157        check_hash_uncompressed::<32, 48>(Mode::Public, 470, 0, 8774, 8776)
158    }
159
160    #[test]
161    fn test_hash_uncompressed_private() -> Result<()> {
162        check_hash_uncompressed::<32, 48>(Mode::Private, 470, 0, 8774, 8776)
163    }
164
165    #[test]
166    fn test_hash_uncompressed_bhp256_constant() -> Result<()> {
167        let mut rng = TestRng::default();
168        check_hash_uncompressed!(BHP256, Constant, 261, (756, 0, 0, 0), &mut rng)
169    }
170
171    #[test]
172    fn test_hash_uncompressed_bhp256_public() -> Result<()> {
173        let mut rng = TestRng::default();
174        check_hash_uncompressed!(BHP256, Public, 261, (403, 0, 445, 445), &mut rng)
175    }
176
177    #[test]
178    fn test_hash_uncompressed_bhp256_private() -> Result<()> {
179        let mut rng = TestRng::default();
180        check_hash_uncompressed!(BHP256, Private, 261, (403, 0, 445, 445), &mut rng)
181    }
182
183    #[test]
184    fn test_hash_uncompressed_bhp512_constant() -> Result<()> {
185        let mut rng = TestRng::default();
186        check_hash_uncompressed!(BHP512, Constant, 522, (1113, 0, 0, 0), &mut rng)
187    }
188
189    #[test]
190    fn test_hash_uncompressed_bhp512_public() -> Result<()> {
191        let mut rng = TestRng::default();
192        check_hash_uncompressed!(BHP512, Public, 522, (409, 0, 895, 895), &mut rng)
193    }
194
195    #[test]
196    fn test_hash_uncompressed_bhp512_private() -> Result<()> {
197        let mut rng = TestRng::default();
198        check_hash_uncompressed!(BHP512, Private, 522, (409, 0, 895, 895), &mut rng)
199    }
200
201    #[test]
202    fn test_hash_uncompressed_bhp768_constant() -> Result<()> {
203        let mut rng = TestRng::default();
204        check_hash_uncompressed!(BHP768, Constant, 783, (1488, 0, 0, 0), &mut rng)
205    }
206
207    #[test]
208    fn test_hash_uncompressed_bhp768_public() -> Result<()> {
209        let mut rng = TestRng::default();
210        check_hash_uncompressed!(BHP768, Public, 783, (429, 0, 1365, 1365), &mut rng)
211    }
212
213    #[test]
214    fn test_hash_uncompressed_bhp768_private() -> Result<()> {
215        let mut rng = TestRng::default();
216        check_hash_uncompressed!(BHP768, Private, 783, (429, 0, 1365, 1365), &mut rng)
217    }
218
219    #[test]
220    fn test_hash_uncompressed_bhp1024_constant() -> Result<()> {
221        let mut rng = TestRng::default();
222        check_hash_uncompressed!(BHP1024, Constant, 1043, (1815, 0, 0, 0), &mut rng)?;
223        check_hash_uncompressed!(BHP1024, Constant, 1044, (1815, 0, 0, 0), &mut rng)?;
224        check_hash_uncompressed!(BHP1024, Constant, 1046, (2413, 0, 0, 0), &mut rng)
225    }
226
227    #[test]
228    fn test_hash_uncompressed_bhp1024_public() -> Result<()> {
229        let mut rng = TestRng::default();
230        check_hash_uncompressed!(BHP1024, Public, 1043, (413, 0, 1775, 1775), &mut rng)?;
231        check_hash_uncompressed!(BHP1024, Public, 1044, (413, 0, 1775, 1775), &mut rng)?;
232        check_hash_uncompressed!(BHP1024, Public, 1046, (418, 0, 2709, 2711), &mut rng)
233    }
234
235    #[test]
236    fn test_hash_uncompressed_bhp1024_private() -> Result<()> {
237        let mut rng = TestRng::default();
238        check_hash_uncompressed!(BHP1024, Private, 1043, (413, 0, 1775, 1775), &mut rng)?;
239        check_hash_uncompressed!(BHP1024, Private, 1044, (413, 0, 1775, 1775), &mut rng)?;
240        check_hash_uncompressed!(BHP1024, Private, 1046, (418, 0, 2709, 2711), &mut rng)
241    }
242
243    #[test]
244    fn test_hash_uncompressed_cost_comparison() -> Result<()> {
245        // The cost to hash 512 bits for each BHP variant is:
246        let mut rng = TestRng::default();
247        check_hash_uncompressed!(BHP256, Private, 512, (410, 0, 1799, 1801), &mut rng)?;
248        check_hash_uncompressed!(BHP512, Private, 512, (409, 0, 880, 880), &mut rng)?;
249        check_hash_uncompressed!(BHP768, Private, 512, (423, 0, 900, 900), &mut rng)?;
250        check_hash_uncompressed!(BHP1024, Private, 512, (407, 0, 875, 875), &mut rng)
251    }
252}
snarkvm_circuit_algorithms/bhp/hash_uncompressed.rs

snarkvm_circuit_algorithms/bhp/
hash_uncompressed.rs
