1  // Copyright (c) 2019-2025 Alpha-Delta Network Inc.
  2  // This file is part of the alphavm 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  
 16  mod hash_uncompressed;
 17  
 18  #[cfg(test)]
 19  use alphavm_circuit_types::environment::assert_scope;
 20  
 21  use crate::HashUncompressed;
 22  use alphavm_circuit_types::prelude::*;
 23  
 24  /// The BHP chunk size (this implementation is for a 3-bit BHP).
 25  const BHP_CHUNK_SIZE: usize = 3;
 26  
 27  /// The x-coordinate and y-coordinate of each base on the Montgomery curve.
 28  type BaseLookups<E> = (Vec<Field<E>>, Vec<Field<E>>);
 29  
 30  /// BHP is a collision-resistant hash function that takes a variable-length input.
 31  /// The BHP hasher is used to process one internal iteration of the BHP hash function.
 32  pub struct BHPHasher<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> {
 33      /// The bases for the BHP hash.
 34      bases: Vec<Vec<BaseLookups<E>>>,
 35      /// The random base for the BHP commitment.
 36      random_base: Vec<Group<E>>,
 37  }
 38  
 39  impl<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> BHPHasher<E, NUM_WINDOWS, WINDOW_SIZE> {
 40      /// The BHP lookup size per iteration.
 41      const BHP_LOOKUP_SIZE: usize = 4;
 42      /// The maximum number of input bits.
 43      const MAX_BITS: usize = NUM_WINDOWS as usize * WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
 44      /// The minimum number of input bits (at least one window).
 45      const MIN_BITS: usize = WINDOW_SIZE as usize * BHP_CHUNK_SIZE;
 46  
 47      #[cfg(test)]
 48      /// Returns the bases.
 49      pub(crate) fn bases(&self) -> &Vec<Vec<BaseLookups<E>>> {
 50          &self.bases
 51      }
 52  
 53      /// Returns the random base window.
 54      pub(crate) fn random_base(&self) -> &Vec<Group<E>> {
 55          &self.random_base
 56      }
 57  }
 58  
 59  impl<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> Inject for BHPHasher<E, NUM_WINDOWS, WINDOW_SIZE> {
 60      type Primitive = console::BHP<E::Network, NUM_WINDOWS, WINDOW_SIZE>;
 61  
 62      /// Initializes a new instance of a BHP circuit with the given BHP variant.
 63      fn new(_mode: Mode, bhp: Self::Primitive) -> Self {
 64          // Compute the bases.
 65          let bases = bhp
 66              .bases()
 67              .iter()
 68              .take(NUM_WINDOWS as usize)
 69              .map(|window| {
 70                  // Construct the window with the base.
 71                  let mut powers = Vec::with_capacity(WINDOW_SIZE as usize);
 72                  for base in window.iter().take(WINDOW_SIZE as usize).map(|base| Group::constant(*base)) {
 73                      let mut x_bases = Vec::with_capacity(Self::BHP_LOOKUP_SIZE);
 74                      let mut y_bases = Vec::with_capacity(Self::BHP_LOOKUP_SIZE);
 75                      let mut accumulator = base.clone();
 76                      for _ in 0..Self::BHP_LOOKUP_SIZE {
 77                          // Convert each base from twisted Edwards point into a Montgomery point.
 78                          let x = (Field::one() + accumulator.to_y_coordinate())
 79                              / (Field::one() - accumulator.to_y_coordinate());
 80                          let y = &x / accumulator.to_x_coordinate();
 81  
 82                          x_bases.push(x);
 83                          y_bases.push(y);
 84                          accumulator += &base;
 85                      }
 86                      powers.push((x_bases, y_bases));
 87                  }
 88                  powers
 89              })
 90              .collect::<Vec<Vec<BaseLookups<E>>>>();
 91          assert_eq!(bases.len(), NUM_WINDOWS as usize, "Incorrect number of BHP windows ({})", bases.len());
 92          bases.iter().for_each(|window| assert_eq!(window.len(), WINDOW_SIZE as usize));
 93  
 94          // Initialize the random base.
 95          let random_base = Vec::constant(bhp.random_base().iter().copied().collect());
 96          assert_eq!(random_base.len(), console::Scalar::<E::Network>::size_in_bits());
 97  
 98          Self { bases, random_base }
 99      }
100  }
101  
102  #[cfg(test)]
103  mod tests {
104      use super::*;
105      use alphavm_circuit_types::environment::{Circuit, Eject};
106  
107      use anyhow::Result;
108  
109      const ITERATIONS: usize = 10;
110      const MESSAGE: &str = "BHPCircuit0";
111  
112      #[test]
113      fn test_setup_constant() -> Result<()> {
114          for _ in 0..ITERATIONS {
115              let native = console::BHP::<<Circuit as Environment>::Network, 8, 32>::setup(MESSAGE)?;
116              let circuit = BHPHasher::<Circuit, 8, 32>::new(Mode::Constant, native.clone());
117  
118              native.bases().iter().zip(circuit.bases.iter()).for_each(|(native_bases, circuit_bases)| {
119                  native_bases.iter().zip(circuit_bases).for_each(|(native_base, circuit_base_lookups)| {
120                      // Check the first circuit base (when converted back to twisted Edwards) matches the native one.
121                      let (circuit_x, circuit_y) = {
122                          let (x_bases, y_bases) = circuit_base_lookups;
123                          // Convert the Montgomery point to a twisted Edwards point.
124                          let edwards_x = &x_bases[0] / &y_bases[0]; // 1 constraint
125                          let edwards_y = (&x_bases[0] - Field::one()) / (&x_bases[0] + Field::one());
126                          (edwards_x, edwards_y)
127                      };
128                      assert_eq!(native_base.to_x_coordinate(), circuit_x.eject_value());
129                      assert_eq!(native_base.to_y_coordinate(), circuit_y.eject_value());
130                  })
131              });
132          }
133          Ok(())
134      }
135  }