snarkvm_console_algorithms/bhp/hasher/
mod.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
16mod hash_uncompressed;
17
18use crate::Blake2Xs;
19use snarkvm_console_types::prelude::*;
20use snarkvm_utilities::BigInteger;
21
22use serde::{Deserialize, Serialize};
23use std::sync::Arc;
24
25/// The BHP chunk size (this implementation is for a 3-bit BHP).
26pub(super) const BHP_CHUNK_SIZE: usize = 3;
27pub(super) const BHP_LOOKUP_SIZE: usize = 1 << BHP_CHUNK_SIZE;
28
29/// BHP is a collision-resistant hash function that takes a variable-length input.
30/// The BHP hasher is used to process one internal iteration of the BHP hash function.
31#[derive(Clone, Debug, PartialEq, Deserialize, Serialize)]
32#[serde(bound = "E: Serialize + DeserializeOwned")]
33pub struct BHPHasher<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> {
34    /// The bases for the BHP hash.
35    bases: Arc<Vec<Vec<Group<E>>>>,
36    /// The bases lookup table for the BHP hash.
37    bases_lookup: Arc<Vec<Vec<[Group<E>; BHP_LOOKUP_SIZE]>>>,
38    /// The random base for the BHP commitment.
39    random_base: Arc<Vec<Group<E>>>,
40}
41
42impl<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> BHPHasher<E, NUM_WINDOWS, WINDOW_SIZE> {
43    /// The maximum number of input bits.
44    const MAX_BITS: usize = NUM_WINDOWS as usize * WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
45    /// The minimum number of input bits (at least one window).
46    const MIN_BITS: usize = WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
47
48    /// Initializes a new instance of BHP with the given domain.
49    pub fn setup(domain: &str) -> Result<Self> {
50        // Calculate the maximum window size.
51        let mut maximum_window_size = 0;
52        let mut range = E::BigInteger::from(2_u64);
53        while range < E::Scalar::modulus_minus_one_div_two() {
54            // range < (p-1)/2
55            range.muln(4); // range * 2^4
56            maximum_window_size += 1;
57        }
58        ensure!(WINDOW_SIZE <= maximum_window_size, "The maximum BHP window size is {maximum_window_size}");
59
60        // Compute the bases.
61        let bases = (0..NUM_WINDOWS)
62            .map(|index| {
63                // Construct an indexed message to attempt to sample a base.
64                let (generator, _, _) = Blake2Xs::hash_to_curve::<E::Affine>(&format!(
65                    "Aleo.BHP.{NUM_WINDOWS}.{WINDOW_SIZE}.{domain}.{index}"
66                ));
67                let mut base = Group::<E>::new(generator);
68                // Compute the generators for the sampled base.
69                let mut powers = Vec::with_capacity(WINDOW_SIZE as usize);
70                for _ in 0..WINDOW_SIZE {
71                    powers.push(base);
72                    for _ in 0..4 {
73                        base = base.double();
74                    }
75                }
76                powers
77            })
78            .collect::<Vec<Vec<Group<E>>>>();
79        ensure!(bases.len() == NUM_WINDOWS as usize, "Incorrect number of BHP windows ({})", bases.len());
80        for window in &bases {
81            ensure!(window.len() == WINDOW_SIZE as usize, "Incorrect BHP window size ({})", window.len());
82        }
83
84        // Compute the bases lookup.
85        let bases_lookup = bases
86            .iter()
87            .map(|x| {
88                x.iter()
89                    .map(|g| {
90                        let mut lookup = [Group::<E>::zero(); BHP_LOOKUP_SIZE];
91                        for (i, element) in lookup.iter_mut().enumerate().take(BHP_LOOKUP_SIZE) {
92                            *element = *g;
93                            if (i & 0x01) != 0 {
94                                *element += g;
95                            }
96                            if (i & 0x02) != 0 {
97                                *element += g.double();
98                            }
99                            if (i & 0x04) != 0 {
100                                *element = element.neg();
101                            }
102                        }
103                        lookup
104                    })
105                    .collect()
106            })
107            .collect::<Vec<Vec<[Group<E>; BHP_LOOKUP_SIZE]>>>();
108        ensure!(bases_lookup.len() == NUM_WINDOWS as usize, "Incorrect number of BHP lookups ({})", bases_lookup.len());
109        for window in &bases_lookup {
110            ensure!(window.len() == WINDOW_SIZE as usize, "Incorrect BHP lookup window size ({})", window.len());
111        }
112
113        // Next, compute the random base.
114        let (generator, _, _) =
115            Blake2Xs::hash_to_curve::<E::Affine>(&format!("Aleo.BHP.{NUM_WINDOWS}.{WINDOW_SIZE}.{domain}.Randomizer"));
116        let mut base_power = Group::<E>::new(generator);
117        let mut random_base = Vec::with_capacity(Scalar::<E>::size_in_bits());
118        for _ in 0..Scalar::<E>::size_in_bits() {
119            random_base.push(base_power);
120            base_power = base_power.double();
121        }
122        ensure!(
123            random_base.len() == Scalar::<E>::size_in_bits(),
124            "Incorrect number of BHP random base powers ({})",
125            random_base.len()
126        );
127
128        Ok(Self { bases: Arc::new(bases), bases_lookup: Arc::new(bases_lookup), random_base: Arc::new(random_base) })
129    }
130
131    /// Returns the bases.
132    pub fn bases(&self) -> &Arc<Vec<Vec<Group<E>>>> {
133        &self.bases
134    }
135
136    /// Returns the random base window.
137    pub fn random_base(&self) -> &Arc<Vec<Group<E>>> {
138        &self.random_base
139    }
140}
snarkvm_console_algorithms/bhp/hasher/mod.rs

snarkvm_console_algorithms/bhp/hasher/
mod.rs
