snarkvm_circuit_collections/kary_merkle_tree/helpers/
path_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 path hash function.
20pub trait PathHash<E: Environment> {
21    type Hash: Clone
22        + Default
23        + Inject<Primitive = <Self::Primitive as console::kary_merkle_tree::PathHash>::Hash>
24        + Eject<Primitive = <Self::Primitive as console::kary_merkle_tree::PathHash>::Hash>
25        + Equal<Output = Boolean<E>>
26        + Ternary<Boolean = Boolean<E>, Output = Self::Hash>;
27    type Primitive: console::kary_merkle_tree::PathHash;
28
29    /// Returns the hash of the given child nodes.
30    fn hash_children(&self, children: &[Self::Hash]) -> Self::Hash;
31
32    /// Returns the empty hash.
33    fn hash_empty<const ARITY: u8>(&self) -> Self::Hash {
34        let children = vec![Self::Hash::default(); ARITY as usize];
35        self.hash_children(&children)
36    }
37}
38
39impl<E: Environment, const NUM_WINDOWS: u8, const WINDOW_SIZE: u8> PathHash<E> for BHP<E, NUM_WINDOWS, WINDOW_SIZE> {
40    type Hash = Field<E>;
41    type Primitive = console::algorithms::BHP<E::Network, NUM_WINDOWS, WINDOW_SIZE>;
42
43    /// Returns the hash of the given child nodes.
44    fn hash_children(&self, children: &[Self::Hash]) -> Self::Hash {
45        let mut input = Vec::new();
46        // Prepend the nodes with a `true` bit.
47        input.push(Boolean::constant(true));
48        for child in children {
49            child.write_bits_le(&mut input);
50        }
51        // Hash the input.
52        Hash::hash(self, &input)
53    }
54}
55
56impl<E: Environment, const RATE: usize> PathHash<E> for Poseidon<E, RATE> {
57    type Hash = Field<E>;
58    type Primitive = console::algorithms::Poseidon<E::Network, RATE>;
59
60    /// Returns the hash of the given child nodes.
61    fn hash_children(&self, children: &[Self::Hash]) -> Self::Hash {
62        let mut input = Vec::with_capacity(1 + children.len());
63        // Prepend the nodes with a `1field` byte.
64        input.push(Self::Hash::one());
65        for child in children {
66            input.push(child.clone());
67        }
68        // Hash the input.
69        Hash::hash(self, &input)
70    }
71}
72
73impl<E: Environment, const TYPE: u8, const VARIANT: usize> PathHash<E> for Keccak<E, TYPE, VARIANT> {
74    type Hash = BooleanHash<E, VARIANT>;
75    type Primitive = console::algorithms::Keccak<TYPE, VARIANT>;
76
77    /// Returns the hash of the given child nodes.
78    fn hash_children(&self, children: &[Self::Hash]) -> Self::Hash {
79        let mut input = Vec::new();
80        // Prepend the nodes with a `true` bit.
81        input.push(Boolean::constant(true));
82        for child in children {
83            child.write_bits_le(&mut input);
84        }
85        // Hash the input.
86        let output = Hash::hash(self, &input);
87        // Read the first VARIANT bits.
88        let mut result = BooleanHash::default();
89        result.0.clone_from_slice(&output[..VARIANT]);
90        result
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use super::*;
97    use snarkvm_circuit_algorithms::{BHP512, Keccak256, Poseidon2, Sha3_256};
98    use snarkvm_circuit_types::environment::Circuit;
99    use snarkvm_utilities::{TestRng, Uniform};
100
101    use anyhow::Result;
102
103    const ITERATIONS: u64 = 5;
104    const DOMAIN: &str = "MerkleTreeCircuit0";
105
106    macro_rules! check_hash_children {
107        ($native:ident, $circuit:ident, $mode:ident, $arity:expr, ($num_constants:expr, $num_public:expr, $num_private:expr, $num_constraints:expr)) => {{
108            let mut rng = TestRng::default();
109
110            for i in 0..ITERATIONS {
111                // Sample a random input.
112                let children = (0..$arity).map(|_| Uniform::rand(&mut rng)).collect::<Vec<_>>();
113
114                // Compute the expected hash.
115                let expected = console::kary_merkle_tree::PathHash::hash_children(&$native, &children)?;
116
117                // Prepare the circuit input.
118                let children = children.into_iter().map(|child| Inject::new(Mode::$mode, child)).collect::<Vec<_>>();
119
120                Circuit::scope(format!("PathHash {i}"), || {
121                    // Perform the hash operation.
122                    let candidate = $circuit.hash_children(&children);
123                    assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
124                    assert_eq!(expected, candidate.eject_value());
125                });
126                Circuit::reset();
127            }
128            Ok::<_, anyhow::Error>(())
129        }};
130        ($hash:ident, $mode:ident, $arity:expr, ($num_constants:expr, $num_public:expr, $num_private:expr, $num_constraints:expr)) => {{
131            // Initialize the hash.
132            let native = snarkvm_console_algorithms::$hash::<<Circuit as Environment>::Network>::setup(DOMAIN)?;
133            let circuit = $hash::<Circuit>::constant(native.clone());
134
135            check_hash_children!(
136                native,
137                circuit,
138                $mode,
139                $arity,
140                ($num_constants, $num_public, $num_private, $num_constraints)
141            )
142        }};
143    }
144
145    #[test]
146    fn test_hash_children_bhp512_constant() -> Result<()> {
147        check_hash_children!(BHP512, Constant, 2, (1599, 0, 0, 0))?;
148        check_hash_children!(BHP512, Constant, 3, (2792, 0, 0, 0))
149    }
150
151    #[test]
152    fn test_hash_children_bhp512_public() -> Result<()> {
153        check_hash_children!(BHP512, Public, 2, (409, 0, 1879, 1883))?;
154        check_hash_children!(BHP512, Public, 3, (418, 0, 3747, 3755))
155    }
156
157    #[test]
158    fn test_hash_children_bhp512_private() -> Result<()> {
159        check_hash_children!(BHP512, Private, 2, (409, 0, 1879, 1883))?;
160        check_hash_children!(BHP512, Private, 3, (418, 0, 3747, 3755))
161    }
162
163    #[test]
164    fn test_hash_children_poseidon2_constant() -> Result<()> {
165        check_hash_children!(Poseidon2, Constant, 2, (1, 0, 0, 0))?;
166        check_hash_children!(Poseidon2, Constant, 3, (1, 0, 0, 0))?;
167
168        check_hash_children!(Poseidon2, Constant, 4, (1, 0, 0, 0))?;
169        check_hash_children!(Poseidon2, Constant, 5, (1, 0, 0, 0))?;
170        check_hash_children!(Poseidon2, Constant, 6, (1, 0, 0, 0))
171    }
172
173    #[test]
174    fn test_hash_children_poseidon2_public() -> Result<()> {
175        check_hash_children!(Poseidon2, Public, 2, (1, 0, 540, 540))?;
176        check_hash_children!(Poseidon2, Public, 3, (1, 0, 540, 540))?;
177
178        check_hash_children!(Poseidon2, Public, 4, (1, 0, 815, 815))?;
179        check_hash_children!(Poseidon2, Public, 5, (1, 0, 815, 815))?;
180
181        check_hash_children!(Poseidon2, Public, 6, (1, 0, 1090, 1090))?;
182        check_hash_children!(Poseidon2, Public, 7, (1, 0, 1090, 1090))
183    }
184
185    #[test]
186    fn test_hash_children_poseidon2_private() -> Result<()> {
187        check_hash_children!(Poseidon2, Private, 2, (1, 0, 540, 540))?;
188        check_hash_children!(Poseidon2, Private, 3, (1, 0, 540, 540))?;
189
190        check_hash_children!(Poseidon2, Private, 4, (1, 0, 815, 815))?;
191        check_hash_children!(Poseidon2, Private, 5, (1, 0, 815, 815))?;
192
193        check_hash_children!(Poseidon2, Private, 6, (1, 0, 1090, 1090))?;
194        check_hash_children!(Poseidon2, Private, 7, (1, 0, 1090, 1090))
195    }
196
197    #[test]
198    fn test_hash_children_keccak256_constant() -> Result<()> {
199        let native = snarkvm_console_algorithms::Keccak256 {};
200        let circuit = Keccak256::<Circuit>::new();
201
202        check_hash_children!(native, circuit, Constant, 2, (256, 0, 0, 0))?;
203        check_hash_children!(native, circuit, Constant, 3, (256, 0, 0, 0))?;
204        check_hash_children!(native, circuit, Constant, 4, (256, 0, 0, 0))?;
205        check_hash_children!(native, circuit, Constant, 5, (256, 0, 0, 0))?;
206        check_hash_children!(native, circuit, Constant, 8, (256, 0, 0, 0))?;
207        check_hash_children!(native, circuit, Constant, 16, (256, 0, 0, 0))
208    }
209
210    #[test]
211    fn test_hash_children_keccak256_public() -> Result<()> {
212        let native = snarkvm_console_algorithms::Keccak256 {};
213        let circuit = Keccak256::<Circuit>::new();
214
215        check_hash_children!(native, circuit, Public, 2, (256, 0, 151424, 151424))?;
216        check_hash_children!(native, circuit, Public, 3, (256, 0, 151936, 151936))?;
217        check_hash_children!(native, circuit, Public, 4, (256, 0, 152448, 152448))?;
218        check_hash_children!(native, circuit, Public, 5, (256, 0, 306367, 306367))?;
219        check_hash_children!(native, circuit, Public, 8, (256, 0, 307135, 307135))?;
220        check_hash_children!(native, circuit, Public, 12, (256, 0, 461759, 461759))?;
221        check_hash_children!(native, circuit, Public, 16, (256, 0, 616383, 616383))
222    }
223
224    #[test]
225    fn test_hash_children_keccak256_private() -> Result<()> {
226        let native = snarkvm_console_algorithms::Keccak256 {};
227        let circuit = Keccak256::<Circuit>::new();
228
229        check_hash_children!(native, circuit, Private, 2, (256, 0, 151424, 151424))?;
230        check_hash_children!(native, circuit, Private, 3, (256, 0, 151936, 151936))?;
231        check_hash_children!(native, circuit, Private, 4, (256, 0, 152448, 152448))?;
232        check_hash_children!(native, circuit, Private, 5, (256, 0, 306367, 306367))?;
233        check_hash_children!(native, circuit, Private, 8, (256, 0, 307135, 307135))?;
234        check_hash_children!(native, circuit, Private, 12, (256, 0, 461759, 461759))?;
235        check_hash_children!(native, circuit, Private, 16, (256, 0, 616383, 616383))
236    }
237
238    #[test]
239    fn test_hash_children_sha3_256_constant() -> Result<()> {
240        let native = snarkvm_console_algorithms::Sha3_256 {};
241        let circuit = Sha3_256::<Circuit>::new();
242
243        check_hash_children!(native, circuit, Constant, 2, (256, 0, 0, 0))?;
244        check_hash_children!(native, circuit, Constant, 3, (256, 0, 0, 0))?;
245        check_hash_children!(native, circuit, Constant, 4, (256, 0, 0, 0))?;
246        check_hash_children!(native, circuit, Constant, 5, (256, 0, 0, 0))?;
247        check_hash_children!(native, circuit, Constant, 8, (256, 0, 0, 0))?;
248        check_hash_children!(native, circuit, Constant, 16, (256, 0, 0, 0))
249    }
250
251    #[test]
252    fn test_hash_children_sha3_256_public() -> Result<()> {
253        let native = snarkvm_console_algorithms::Sha3_256 {};
254        let circuit = Sha3_256::<Circuit>::new();
255
256        check_hash_children!(native, circuit, Public, 2, (256, 0, 151424, 151424))?;
257        check_hash_children!(native, circuit, Public, 3, (256, 0, 151936, 151936))?;
258        check_hash_children!(native, circuit, Public, 4, (256, 0, 152448, 152448))?;
259        check_hash_children!(native, circuit, Public, 5, (256, 0, 306367, 306367))?;
260        check_hash_children!(native, circuit, Public, 8, (256, 0, 307135, 307135))?;
261        check_hash_children!(native, circuit, Public, 12, (256, 0, 461759, 461759))?;
262        check_hash_children!(native, circuit, Public, 16, (256, 0, 616383, 616383))
263    }
264
265    #[test]
266    fn test_hash_children_sha3_256_private() -> Result<()> {
267        let native = snarkvm_console_algorithms::Sha3_256 {};
268        let circuit = Sha3_256::<Circuit>::new();
269
270        check_hash_children!(native, circuit, Private, 2, (256, 0, 151424, 151424))?;
271        check_hash_children!(native, circuit, Private, 3, (256, 0, 151936, 151936))?;
272        check_hash_children!(native, circuit, Private, 4, (256, 0, 152448, 152448))?;
273        check_hash_children!(native, circuit, Private, 5, (256, 0, 306367, 306367))?;
274        check_hash_children!(native, circuit, Private, 8, (256, 0, 307135, 307135))?;
275        check_hash_children!(native, circuit, Private, 12, (256, 0, 461759, 461759))?;
276        check_hash_children!(native, circuit, Private, 16, (256, 0, 616383, 616383))
277    }
278}
snarkvm_circuit_collections/kary_merkle_tree/helpers/path_hash.rs

snarkvm_circuit_collections/kary_merkle_tree/helpers/
path_hash.rs
