openvm_stark_backend/
hasher.rs

1use std::{fmt::Debug, marker::PhantomData};
2
3use derivative::Derivative;
4use p3_field::Field;
5use p3_symmetric::{CryptographicHasher, PseudoCompressionFunction};
6#[cfg(feature = "multi-field-transcript")]
7use {
8    super::multi_field_packing::{checked_num_packed_f_elms, pack_f_to_sf},
9    itertools::Itertools,
10    p3_field::{PrimeField, PrimeField32},
11    p3_symmetric::CryptographicPermutation,
12};
13
14/// Trait abstracting Merkle tree hash operations. This trait is used as part of the definition of
15/// the [`StarkProtocolConfig`](crate::StarkProtocolConfig).
16///
17/// The `MerkleHasher` is parameterized over the base field `F` used as leaves,
18/// and provides a `Digest` type for internal nodes.
19pub trait MerkleHasher: 'static + Clone + Send + Sync {
20    type F: Field;
21    type Digest: 'static + Copy + Send + Sync;
22
23    /// Hash a slice of field elements into a digest (used for leaf hashing).
24    fn hash_slice(&self, vals: &[Self::F]) -> Self::Digest;
25
26    /// Compress two digests into one (used for internal Merkle tree nodes).
27    fn compress(&self, left: Self::Digest, right: Self::Digest) -> Self::Digest;
28
29    /// Compress a vector of digests (must be power-of-two length) into a single digest
30    /// by repeated binary compression.
31    fn tree_compress(&self, mut hashes: Vec<Self::Digest>) -> Self::Digest {
32        debug_assert!(hashes.len().is_power_of_two());
33        while hashes.len() > 1 {
34            let mut next = Vec::with_capacity(hashes.len() / 2);
35            for pair in hashes.chunks_exact(2) {
36                next.push(self.compress(pair[0], pair[1]));
37            }
38            hashes = next;
39        }
40        hashes.pop().unwrap()
41    }
42}
43
44/// [MerkleHasher] implementation built from a cryptographic hash function and a compression
45/// function. This struct is intended for use by the protocol verifier. Prover backends may use
46/// independent but functionally equivalent implementations.
47///
48/// The compression function does not need to be collision-resistant and only needs to be a pseudo-cryptographic function: <https://eprint.iacr.org/2026/089>.
49#[derive(Derivative, derive_new::new)]
50#[derivative(
51    Clone(bound = "H: Clone, C: Clone"),
52    Debug(bound = "H: Debug, C: Debug")
53)]
54pub struct Hasher<F, Digest, H, C> {
55    hash: H,
56    compress: C,
57    _phantom: PhantomData<(F, Digest)>,
58}
59
60impl<F, Digest, H, C> MerkleHasher for Hasher<F, Digest, H, C>
61where
62    F: Field,
63    Digest: 'static + Copy + Send + Sync,
64    H: 'static + Send + Sync + CryptographicHasher<F, Digest>,
65    C: 'static + Send + Sync + PseudoCompressionFunction<Digest, 2>,
66{
67    type F = F;
68    type Digest = Digest;
69
70    fn hash_slice(&self, vals: &[Self::F]) -> Self::Digest {
71        self.hash.hash_slice(vals)
72    }
73
74    fn compress(&self, left: Self::Digest, right: Self::Digest) -> Self::Digest {
75        self.compress.compress([left, right])
76    }
77}
78
79/// A padding-free, overwrite-mode sponge that operates natively over `PF` but accepts elements
80/// of `F: PrimeField32`, packing them at base-2^(F::bits()).
81///
82/// This differs from Plonky3's `MultiField32PaddingFreeSponge` which packs at base-2^32.
83/// For BabyBear (31-bit field), base-2^31 packing is injective into BN254, whereas
84/// base-2^32 packing of 8 elements can exceed the BN254 modulus.
85#[cfg(feature = "multi-field-transcript")]
86#[derive(Clone, Debug)]
87pub struct MultiFieldHasher<F, PF, P, const WIDTH: usize, const RATE: usize, const OUT: usize> {
88    permutation: P,
89    num_f_elms: usize,
90    _phantom: PhantomData<(F, PF)>,
91}
92
93#[cfg(feature = "multi-field-transcript")]
94impl<F, PF, P, const WIDTH: usize, const RATE: usize, const OUT: usize>
95    MultiFieldHasher<F, PF, P, WIDTH, RATE, OUT>
96where
97    F: PrimeField32,
98    PF: PrimeField,
99{
100    pub fn new(permutation: P) -> Self {
101        let num_f_elms = checked_num_packed_f_elms::<F, PF>();
102
103        Self {
104            permutation,
105            num_f_elms,
106            _phantom: PhantomData,
107        }
108    }
109}
110
111#[cfg(feature = "multi-field-transcript")]
112impl<F, PF, P, const WIDTH: usize, const RATE: usize, const OUT: usize>
113    CryptographicHasher<F, [PF; OUT]> for MultiFieldHasher<F, PF, P, WIDTH, RATE, OUT>
114where
115    F: PrimeField32,
116    PF: PrimeField + Default + Copy,
117    P: CryptographicPermutation<[PF; WIDTH]>,
118{
119    fn hash_iter<I>(&self, input: I) -> [PF; OUT]
120    where
121        I: IntoIterator<Item = F>,
122    {
123        let mut state = [PF::default(); WIDTH];
124        for block_chunk in &input.into_iter().chunks(RATE) {
125            for (chunk_id, chunk) in (&block_chunk.chunks(self.num_f_elms))
126                .into_iter()
127                .enumerate()
128            {
129                state[chunk_id] = pack_f_to_sf(&chunk.collect_vec());
130            }
131            state = self.permutation.permute(state);
132        }
133
134        state[..OUT].try_into().unwrap()
135    }
136}
openvm_stark_backend/hasher.rs

openvm_stark_backend/
hasher.rs
