snarkvm_circuit_collections/kary_merkle_tree/helpers/
leaf_hash.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::*;
17use snarkvm_circuit_algorithms::{BHP, Hash, Keccak, Poseidon};
18
19/// A trait for a Merkle leaf hash function.
20pub trait LeafHash {
21    type Hash: Default + Inject + Eject + Ternary;
22    type Leaf;
23
24    /// Returns the hash of the given leaf node.
25    fn hash_leaf(&self, leaf: &Self::Leaf) -> Self::Hash;
26}
27
28impl<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> LeafHash for BHP<E, NUM_WINDOWS, WINDOW_SIZE> {
29    type Hash = Field<E>;
30    type Leaf = Vec<Boolean<E>>;
31
32    /// Returns the hash of the given leaf node.
33    fn hash_leaf(&self, leaf: &Self::Leaf) -> Self::Hash {
34        let mut input = Vec::with_capacity(1 + leaf.len());
35        // Prepend the leaf with a `false` bit.
36        input.push(Boolean::constant(false));
37        input.extend_from_slice(leaf);
38        // Hash the input.
39        Hash::hash(self, &input)
40    }
41}
42
43impl<E: Environment, const RATE: usize> LeafHash for Poseidon<E, RATE> {
44    type Hash = Field<E>;
45    type Leaf = Vec<Field<E>>;
46
47    /// Returns the hash of the given leaf node.
48    fn hash_leaf(&self, leaf: &Self::Leaf) -> Self::Hash {
49        let mut input = Vec::with_capacity(1 + leaf.len());
50        // Prepend the leaf with a `0field` element.
51        input.push(Self::Hash::zero());
52        input.extend_from_slice(leaf);
53        // Hash the input.
54        Hash::hash(self, &input)
55    }
56}
57
58impl<E: Environment, const TYPE: u8, const VARIANT: usize> LeafHash for Keccak<E, TYPE, VARIANT> {
59    type Hash = BooleanHash<E, VARIANT>;
60    type Leaf = Vec<Boolean<E>>;
61
62    /// Returns the hash of the given leaf node.
63    fn hash_leaf(&self, leaf: &Self::Leaf) -> Self::Hash {
64        let mut input = Vec::with_capacity(1 + leaf.len());
65        // Prepend the leaf with a `false` bit.
66        input.push(Boolean::constant(false));
67        input.extend_from_slice(leaf);
68        // Hash the input.
69        let output = Hash::hash(self, &input);
70        // Read the first VARIANT bits.
71        let mut result = BooleanHash::default();
72        result.0.clone_from_slice(&output[..VARIANT]);
73        result
74    }
75}
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80    use snarkvm_circuit_algorithms::{BHP1024, Keccak256, Poseidon4, Sha3_256};
81    use snarkvm_circuit_types::environment::Circuit;
82    use snarkvm_utilities::{TestRng, Uniform};
83
84    use anyhow::Result;
85
86    const ITERATIONS: u64 = 10;
87    const DOMAIN: &str = "MerkleTreeCircuit0";
88
89    macro_rules! check_hash_leaf {
90        ($native:ident, $circuit:ident, $mode:ident, $num_inputs:expr, ($num_constants:expr, $num_public:expr, $num_private:expr, $num_constraints:expr)) => {{
91            let mut rng = TestRng::default();
92
93            for i in 0..ITERATIONS {
94                // Sample a random input.
95                let input = (0..$num_inputs).map(|_| Uniform::rand(&mut rng)).collect::<Vec<_>>();
96
97                // Compute the expected hash.
98                let expected = console::kary_merkle_tree::LeafHash::hash_leaf(&$native, &input)?;
99
100                // Prepare the circuit input.
101                let circuit_input: Vec<_> = Inject::new(Mode::$mode, input);
102
103                Circuit::scope(format!("LeafHash {i}"), || {
104                    // Perform the hash operation.
105                    let candidate = $circuit.hash_leaf(&circuit_input);
106                    assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
107                    assert_eq!(expected, candidate.eject_value());
108                });
109                Circuit::reset();
110            }
111            Ok::<_, anyhow::Error>(())
112        }};
113        ($hash:ident, $mode:ident, $num_inputs:expr, ($num_constants:expr, $num_public:expr, $num_private:expr, $num_constraints:expr)) => {{
114            // Initialize the hash.
115            let native = snarkvm_console_algorithms::$hash::<<Circuit as Environment>::Network>::setup(DOMAIN)?;
116            let circuit = $hash::<Circuit>::constant(native.clone());
117
118            check_hash_leaf!(
119                native,
120                circuit,
121                $mode,
122                $num_inputs,
123                ($num_constants, $num_public, $num_private, $num_constraints)
124            )
125        }};
126    }
127
128    #[test]
129    fn test_hash_leaf_bhp1024_constant() -> Result<()> {
130        check_hash_leaf!(BHP1024, Constant, 1024, (1791, 0, 0, 0))
131    }
132
133    #[test]
134    fn test_hash_leaf_bhp1024_public() -> Result<()> {
135        check_hash_leaf!(BHP1024, Public, 1024, (413, 0, 1744, 1744))
136    }
137
138    #[test]
139    fn test_hash_leaf_bhp1024_private() -> Result<()> {
140        check_hash_leaf!(BHP1024, Private, 1024, (413, 0, 1744, 1744))
141    }
142
143    #[test]
144    fn test_hash_leaf_poseidon4_constant() -> Result<()> {
145        check_hash_leaf!(Poseidon4, Constant, 4, (1, 0, 0, 0))
146    }
147
148    #[test]
149    fn test_hash_leaf_poseidon4_public() -> Result<()> {
150        check_hash_leaf!(Poseidon4, Public, 4, (1, 0, 700, 700))
151    }
152
153    #[test]
154    fn test_hash_leaf_poseidon4_private() -> Result<()> {
155        check_hash_leaf!(Poseidon4, Private, 4, (1, 0, 700, 700))
156    }
157
158    #[test]
159    fn test_hash_leaf_keccak256_constant() -> Result<()> {
160        let native = snarkvm_console_algorithms::Keccak256 {};
161        let circuit = Keccak256::<Circuit>::new();
162
163        check_hash_leaf!(native, circuit, Constant, 1024, (256, 0, 0, 0))
164    }
165
166    #[test]
167    fn test_hash_leaf_keccak256_public() -> Result<()> {
168        let native = snarkvm_console_algorithms::Keccak256 {};
169        let circuit = Keccak256::<Circuit>::new();
170
171        check_hash_leaf!(native, circuit, Public, 1024, (256, 0, 152448, 152448))
172    }
173
174    #[test]
175    fn test_hash_leaf_keccak256_private() -> Result<()> {
176        let native = snarkvm_console_algorithms::Keccak256 {};
177        let circuit = Keccak256::<Circuit>::new();
178
179        check_hash_leaf!(native, circuit, Private, 1024, (256, 0, 152448, 152448))
180    }
181
182    #[test]
183    fn test_hash_leaf_sha3_256_constant() -> Result<()> {
184        let native = snarkvm_console_algorithms::Sha3_256 {};
185        let circuit = Sha3_256::<Circuit>::new();
186
187        check_hash_leaf!(native, circuit, Constant, 1024, (256, 0, 0, 0))
188    }
189
190    #[test]
191    fn test_hash_leaf_sha3_256_public() -> Result<()> {
192        let native = snarkvm_console_algorithms::Sha3_256 {};
193        let circuit = Sha3_256::<Circuit>::new();
194
195        check_hash_leaf!(native, circuit, Public, 1024, (256, 0, 152448, 152448))
196    }
197
198    #[test]
199    fn test_hash_leaf_sha3_256_private() -> Result<()> {
200        let native = snarkvm_console_algorithms::Sha3_256 {};
201        let circuit = Sha3_256::<Circuit>::new();
202
203        check_hash_leaf!(native, circuit, Private, 1024, (256, 0, 152448, 152448))
204    }
205}
snarkvm_circuit_collections/kary_merkle_tree/helpers/leaf_hash.rs

snarkvm_circuit_collections/kary_merkle_tree/helpers/
leaf_hash.rs
