snarkvm_console_algorithms/bhp/hasher/
mod.rs

1// Copyright (c) 2019-2026 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
16mod hash_uncompressed;
17
18#[cfg(test)]
19mod tests;
20
21use crate::Blake2Xs;
22use snarkvm_console_types::prelude::*;
23use snarkvm_utilities::BigInteger;
24
25#[cfg(not(feature = "serial"))]
26use rayon::prelude::*;
27use serde::{Deserialize, Serialize};
28use std::sync::Arc;
29
30/// The BHP chunk size (this implementation is for a 3-bit BHP).
31pub(super) const BHP_CHUNK_SIZE: usize = 3;
32pub(super) const BHP_LOOKUP_SIZE: usize = 1 << BHP_CHUNK_SIZE;
33
34/// The amount of chunks (i.e. bit triplets) to preprocess together in the lookup table.
35// The value 4 results in a total lookup size of ~0.13 GB and a x4 speedup in hash_uncompressed.
36// Switching to 5 would increase the lookup size to an excessive ~0.8 GB lookup for a x5 speedup.
37pub(super) const BHP_NUM_COMBINED_CHUNKS: usize = 4;
38
39/// BHP is a collision-resistant hash function that takes a variable-length input.
40/// The BHP hasher is used to process one internal iteration of the BHP hash function.
41#[derive(Clone, Debug, PartialEq, Deserialize, Serialize)]
42#[serde(bound = "E: Serialize + DeserializeOwned")]
43pub struct BHPHasher<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> {
44    /// The bases for the BHP hash.
45    bases: Arc<Vec<Vec<Group<E>>>>,
46    /// The bases lookup table for the BHP hash.
47    bases_lookup: Arc<Vec<Vec<[Group<E>; BHP_LOOKUP_SIZE]>>>,
48    /// The preprocessed combinations of elements in the bases lookup table.
49    // For each group of BHP_NUM_COMBINED_CHUNKS contiguous
50    // BHP_LOOKUP_SIZE-element tuples in `bases_lookup`, this contains
51    // all possible BHP_LOOKUP_SIZE^BHP_NUM_COMBINED_CHUNKS cross-tuple sums.
52    combined_bases_lookup: Arc<[Vec<Vec<Group<E>>>]>,
53    /// The random base for the BHP commitment.
54    random_base: Arc<Vec<Group<E>>>,
55}
56
57impl<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> BHPHasher<E, NUM_WINDOWS, WINDOW_SIZE> {
58    /// The maximum number of input bits.
59    const MAX_BITS: usize = NUM_WINDOWS as usize * WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
60    /// The minimum number of input bits (at least one window).
61    const MIN_BITS: usize = WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
62
63    /// Initializes a new instance of BHP with the given domain.
64    pub fn setup(domain: &str) -> Result<Self> {
65        #[cfg(feature = "dev-print")]
66        let timer = std::time::Instant::now();
67
68        // Calculate the maximum window size.
69        let mut maximum_window_size = 0;
70        let mut range = E::BigInteger::from(2_u64);
71        while range < E::Scalar::modulus_minus_one_div_two() {
72            // range < (p-1)/2
73            range.muln(4); // range * 2^4
74            maximum_window_size += 1;
75        }
76        ensure!(WINDOW_SIZE <= maximum_window_size, "The maximum BHP window size is {maximum_window_size}");
77
78        // Compute the bases.
79        let bases = (0..NUM_WINDOWS)
80            .map(|index| {
81                // Construct an indexed message to attempt to sample a base.
82                let (generator, _, _) = Blake2Xs::hash_to_curve::<E::Affine>(&format!(
83                    "Aleo.BHP.{NUM_WINDOWS}.{WINDOW_SIZE}.{domain}.{index}"
84                ));
85                let mut base = Group::<E>::new(generator);
86                // Compute the generators for the sampled base.
87                let mut powers = Vec::with_capacity(WINDOW_SIZE as usize);
88                for _ in 0..WINDOW_SIZE {
89                    powers.push(base);
90                    for _ in 0..4 {
91                        base = base.double();
92                    }
93                }
94                powers
95            })
96            .collect::<Vec<Vec<Group<E>>>>();
97        ensure!(bases.len() == NUM_WINDOWS as usize, "Incorrect number of BHP windows ({})", bases.len());
98        for window in &bases {
99            ensure!(window.len() == WINDOW_SIZE as usize, "Incorrect BHP window size ({})", window.len());
100        }
101
102        // Compute the bases lookup.
103        let bases_lookup = cfg_iter!(bases)
104            .map(|window| {
105                window
106                    .iter()
107                    .map(|g| {
108                        let mut lookup = [Group::<E>::zero(); BHP_LOOKUP_SIZE];
109                        for (i, element) in lookup.iter_mut().enumerate().take(BHP_LOOKUP_SIZE) {
110                            *element = *g;
111                            if (i & 0x01) != 0 {
112                                *element += g;
113                            }
114                            if (i & 0x02) != 0 {
115                                *element += g.double();
116                            }
117                            if (i & 0x04) != 0 {
118                                *element = element.neg();
119                            }
120                        }
121                        lookup
122                    })
123                    .collect()
124            })
125            .collect::<Vec<Vec<[Group<E>; BHP_LOOKUP_SIZE]>>>();
126        ensure!(bases_lookup.len() == NUM_WINDOWS as usize, "Incorrect number of BHP lookups ({})", bases_lookup.len());
127        for window in &bases_lookup {
128            ensure!(window.len() == WINDOW_SIZE as usize, "Incorrect BHP lookup window size ({})", window.len());
129        }
130
131        // Compute the preprocessed sums of contiguous base-element tuples. For
132        // instance, for BHP_NUM_COMBINED_CHUNKS = 2, if the first two three-bit
133        // groups of the input are mapped to (P1_0, ..., P1_7) and (P2_0, ...,
134        // P2_7), respectively, this code computes the vector
135        // [
136        //     P1_0 + P2_0, P1_0 + P2_1, ..., P1_0 + P2_7,
137        //     P1_1 + P2_0, P1_1 + P2_1, ..., P1_1 + P2_7,
138        //     ...,
139        //     P1_7 + P2_0, P1_7 + P2_1, ..., P1_7 + P2_7
140        // ]
141        // corresponding to the first six bits of the input. Note that bases
142        // lookup must still be kept around since the ending bits of an input
143        // could end in the middle of any preprocessed combined chunk.
144        let combined_bases_lookup: Arc<[Vec<Vec<Group<E>>>]> = cfg_iter!(bases_lookup)
145            .map(|window| {
146                window
147                    .chunks_exact(BHP_NUM_COMBINED_CHUNKS)
148                    .map(|chunks| {
149                        chunks.iter().fold(vec![Group::<E>::zero()], |prev_sums, new_terms| {
150                            prev_sums
151                                .iter()
152                                .flat_map(|prev_sum| new_terms.iter().map(|new_term| *prev_sum + *new_term))
153                                .collect::<Vec<Group<E>>>()
154                        })
155                    })
156                    .collect::<Vec<_>>()
157            })
158            .collect::<Vec<_>>()
159            .into();
160
161        // Next, compute the random base.
162        let (generator, _, _) =
163            Blake2Xs::hash_to_curve::<E::Affine>(&format!("Aleo.BHP.{NUM_WINDOWS}.{WINDOW_SIZE}.{domain}.Randomizer"));
164        let mut base_power = Group::<E>::new(generator);
165        let mut random_base = Vec::with_capacity(Scalar::<E>::size_in_bits());
166        for _ in 0..Scalar::<E>::size_in_bits() {
167            random_base.push(base_power);
168            base_power = base_power.double();
169        }
170        ensure!(
171            random_base.len() == Scalar::<E>::size_in_bits(),
172            "Incorrect number of BHP random base powers ({})",
173            random_base.len()
174        );
175
176        #[cfg(feature = "dev-print")]
177        {
178            // Display the setup time and approximate hasher size.
179
180            let elapsed = timer.elapsed().as_micros() as f64 / 1000.0;
181
182            println!(
183                " • BHP hasher setup (NUM_WINDOWS = {NUM_WINDOWS}, WINDOW_SIZE = {WINDOW_SIZE}, NUM_COMBINED_CHUNKS = {BHP_NUM_COMBINED_CHUNKS}, DOMAIN = '{domain}'): {elapsed:.2} ms"
184            );
185
186            // The number of group elements stored in the hasher is
187            //    N (basis elements)
188            //  + N * 8 (lookup for basis elements)
189            //  + NUM_W * (W_SIZE // C) * 8^C (combined lookup for basis elements)
190            //  + S (random base)
191            // where
192            //  - NUM_W = NUM_WINDOWS,
193            //  - W_SIZE = WINDOW_SIZE,
194            //  - N = number of basis elements = NUM_W * W_SIZE,
195            //  - C = BHP_NUM_COMBINED_CHUNKS
196
197            let num_els_bases: usize = bases.iter().map(|v| v.len()).sum();
198            let num_els_bases_lookup: usize =
199                bases_lookup.iter().map(|vs| vs.iter().map(|v| v.len()).sum::<usize>()).sum();
200            let num_els_combined_bases_lookup: usize =
201                combined_bases_lookup.iter().map(|vs| vs.iter().map(|v| v.len()).sum::<usize>()).sum();
202            let num_els_random_base = random_base.len();
203
204            let bytes = (num_els_bases + num_els_bases_lookup + num_els_combined_bases_lookup + num_els_random_base)
205                * std::mem::size_of::<Group<E>>();
206
207            println!("   Approximate BHP hasher size: {bytes} B");
208        }
209
210        Ok(Self {
211            bases: Arc::new(bases),
212            bases_lookup: Arc::new(bases_lookup),
213            combined_bases_lookup,
214            random_base: Arc::new(random_base),
215        })
216    }
217
218    /// Returns the bases.
219    pub fn bases(&self) -> &Arc<Vec<Vec<Group<E>>>> {
220        &self.bases
221    }
222
223    /// Returns the random base window.
224    pub fn random_base(&self) -> &Arc<Vec<Group<E>>> {
225        &self.random_base
226    }
227}
snarkvm_console_algorithms/bhp/hasher/mod.rs

snarkvm_console_algorithms/bhp/hasher/
mod.rs
