snarkvm_circuit_collections/kary_merkle_tree/
verify.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::*;
17
18impl<E: Environment, PH: PathHash<E>, const DEPTH: u8, const ARITY: u8> KaryMerklePath<E, PH, DEPTH, ARITY> {
19    /// Returns `true` if the Merkle path is valid for the given root and leaf.
20    pub fn verify<LH: LeafHash<Hash = PH::Hash>>(
21        &self,
22        leaf_hasher: &LH,
23        path_hasher: &PH,
24        root: &PH::Hash,
25        leaf: &LH::Leaf,
26    ) -> Boolean<E> {
27        // Ensure the leaf index is within the tree depth.
28        if (*self.leaf_index.eject_value() as u128) >= (ARITY as u128).pow(DEPTH as u32) {
29            E::halt("Found an out of bounds Merkle leaf index")
30        }
31        // Ensure the path length matches the expected depth.
32        else if self.siblings.len() != DEPTH as usize {
33            E::halt("Found an incorrect Merkle path length")
34        }
35
36        // Ensure the Merkle path has the correct arity.
37        for sibling in &self.siblings {
38            if sibling.len() != ARITY.saturating_sub(1) as usize {
39                return E::halt("Merkle path is not the correct depth");
40            }
41        }
42
43        // Initialize a tracker for the current hash, by computing the leaf hash to start.
44        let mut current_hash = leaf_hasher.hash_leaf(leaf);
45
46        let arity = U64::<E>::new(Mode::Constant, console::U64::new(ARITY as u64));
47
48        let indicator_indexes = (0..DEPTH).map(|i| {
49            let index = U16::<E>::new(Mode::Constant, console::U16::new(i as u16));
50            &self.leaf_index / (arity.clone().pow(index)) % arity.clone()
51        });
52
53        // Initialize the zero index.
54        let zero_index = U64::<E>::zero();
55        // Initialize the last index.
56        let last_index = U64::<E>::new(Mode::Constant, console::U64::new(ARITY.saturating_sub(1) as u64));
57
58        // Check levels between leaf level and root.
59        for (indicator_index, sibling_hashes) in indicator_indexes.zip_eq(&self.siblings) {
60            // Assemble the children based on the ternary results.
61            let mut children = Vec::with_capacity(sibling_hashes.len() + 1);
62
63            // Add the first child.
64            let first_child =
65                PH::Hash::ternary(&indicator_index.is_equal(&zero_index), &current_hash, &sibling_hashes[0]);
66
67            children.push(first_child);
68
69            // Calculate the middle children.
70            for i in 1..sibling_hashes.len() {
71                // Index of the current sibling
72                let index = U64::<E>::new(Mode::Constant, console::U64::new(i as u64));
73
74                // When the index is less than the indicator index, use the current index. Otherwise, use the previous index.
75                let option_a = PH::Hash::ternary(
76                    &index.is_less_than(&indicator_index),
77                    &sibling_hashes[i],
78                    &sibling_hashes[i - 1],
79                );
80
81                // When the index is equal to the indicator index, use the current hash.
82                let option_b = PH::Hash::ternary(&index.is_equal(&indicator_index), &current_hash, &option_a);
83
84                // Push the final option to the children
85                children.push(option_b);
86            }
87
88            // Add the last child.
89            let last_child = PH::Hash::ternary(
90                &indicator_index.is_equal(&last_index),
91                &current_hash,
92                sibling_hashes.last().unwrap(),
93            );
94
95            children.push(last_child);
96
97            // Update the current hash for the next level.
98            current_hash = path_hasher.hash_children(&children);
99        }
100
101        // Ensure the final hash matches the given root.
102        root.is_equal(&current_hash)
103    }
104}
105
106#[cfg(all(test, feature = "console"))]
107mod tests {
108    use super::*;
109    use snarkvm_circuit_algorithms::{BHP512, BHP1024, Keccak256, Poseidon2, Poseidon4, Sha3_256};
110    use snarkvm_circuit_types::environment::Circuit;
111    use snarkvm_utilities::{TestRng, Uniform};
112
113    use anyhow::Result;
114
115    const ITERATIONS: u128 = 10;
116    const DOMAIN: &str = "MerkleTreeCircuit0";
117
118    macro_rules! check_verify {
119        ($lh:ident, $ph:ident, $mode:ident, $depth:expr, $arity:expr, $num_inputs:expr, ($num_constants:expr, $num_public:expr, $num_private:expr, $num_constraints:expr)) => {{
120            // Initialize the leaf hasher.
121            let native_leaf_hasher =
122                snarkvm_console_algorithms::$lh::<<Circuit as Environment>::Network>::setup(DOMAIN)?;
123            let circuit_leaf_hasher = $lh::<Circuit>::constant(native_leaf_hasher.clone());
124
125            let mut rng = TestRng::default();
126
127            // Initialize the path hasher.
128            let native_path_hasher =
129                snarkvm_console_algorithms::$ph::<<Circuit as Environment>::Network>::setup(DOMAIN)?;
130            let circuit_path_hasher = $ph::<Circuit>::constant(native_path_hasher.clone());
131
132            for i in 0..ITERATIONS {
133                // Determine the number of leaves.
134                let num_leaves = core::cmp::min(($arity as u128).pow($depth as u32), i);
135                // Compute the leaves.
136                let leaves = (0..num_leaves)
137                    .map(|_| (0..$num_inputs).map(|_| Uniform::rand(&mut rng)).collect::<Vec<_>>())
138                    .collect::<Vec<_>>();
139                // Compute the Merkle tree.
140                let merkle_tree = console::kary_merkle_tree::KaryMerkleTree::<_, _, $depth, $arity>::new(
141                    &native_leaf_hasher,
142                    &native_path_hasher,
143                    &leaves,
144                )?;
145
146                for (index, merkle_leaf) in leaves.iter().enumerate() {
147                    // Compute the Merkle path.
148                    let merkle_path = merkle_tree.prove(index, merkle_leaf)?;
149
150                    // Initialize the Merkle path.
151                    let path =
152                        KaryMerklePath::<Circuit, $ph<Circuit>, $depth, $arity>::new(Mode::$mode, merkle_path.clone());
153
154                    assert_eq!(merkle_path, path.eject_value());
155                    // Initialize the Merkle root.
156                    let root = Field::new(Mode::$mode, *merkle_tree.root());
157                    // Initialize the Merkle leaf.
158                    let leaf: Vec<_> = Inject::new(Mode::$mode, merkle_leaf.clone());
159
160                    Circuit::scope(format!("Verify {}", Mode::$mode), || {
161                        let candidate = path.verify(&circuit_leaf_hasher, &circuit_path_hasher, &root, &leaf);
162                        assert!(candidate.eject_value());
163                        assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
164                    });
165                    Circuit::reset();
166
167                    // Initialize an incorrect Merkle root.
168                    let incorrect_root = root.clone() + Field::one();
169
170                    Circuit::scope(format!("Verify (Incorrect Root) {}", Mode::$mode), || {
171                        let candidate = path.verify(&circuit_leaf_hasher, &circuit_path_hasher, &incorrect_root, &leaf);
172                        assert!(!candidate.eject_value());
173                        assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
174                    });
175                    Circuit::reset();
176
177                    // Initialize an incorrect Merkle leaf.
178                    let mut incorrect_leaf = leaf.clone();
179                    let mut incorrect_value = Uniform::rand(&mut rng);
180                    while incorrect_value == incorrect_leaf[0].eject_value() {
181                        incorrect_value = Uniform::rand(&mut rng);
182                    }
183                    incorrect_leaf[0] = Inject::new(Mode::$mode, incorrect_value);
184
185                    Circuit::scope(format!("Verify (Incorrect Leaf) {}", Mode::$mode), || {
186                        let candidate = path.verify(&circuit_leaf_hasher, &circuit_path_hasher, &root, &incorrect_leaf);
187                        assert!(!candidate.eject_value());
188                        assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
189                    });
190                    Circuit::reset();
191                }
192            }
193            Ok(())
194        }};
195    }
196
197    macro_rules! check_verify_keccak {
198        ($lh:ident, $ph:ident, $mode:ident, $depth:expr, $arity:expr, $num_inputs:expr, ($num_constants:expr, $num_public:expr, $num_private:expr, $num_constraints:expr)) => {{
199            // Initialize the leaf hasher.
200            let native_leaf_hasher = snarkvm_console_algorithms::$lh::default();
201            let circuit_leaf_hasher = $lh::<Circuit>::new();
202
203            let mut rng = TestRng::default();
204
205            // Initialize the path hasher.
206            let native_path_hasher = snarkvm_console_algorithms::$ph::default();
207            let circuit_path_hasher = $ph::<Circuit>::new();
208
209            for i in 0..ITERATIONS {
210                // Determine the number of leaves.
211                let num_leaves = core::cmp::min(($arity as u128).pow($depth as u32), i);
212                // Compute the leaves.
213                let leaves = (0..num_leaves)
214                    .map(|_| (0..$num_inputs).map(|_| Uniform::rand(&mut rng)).collect::<Vec<_>>())
215                    .collect::<Vec<_>>();
216                // Compute the Merkle tree.
217                let merkle_tree = console::kary_merkle_tree::KaryMerkleTree::<_, _, $depth, $arity>::new(
218                    &native_leaf_hasher,
219                    &native_path_hasher,
220                    &leaves,
221                )?;
222
223                for (index, merkle_leaf) in leaves.iter().enumerate() {
224                    // Compute the Merkle path.
225                    let merkle_path = merkle_tree.prove(index, merkle_leaf)?;
226
227                    // Initialize the Merkle path.
228                    let path =
229                        KaryMerklePath::<Circuit, $ph<Circuit>, $depth, $arity>::new(Mode::$mode, merkle_path.clone());
230
231                    assert_eq!(merkle_path, path.eject_value());
232                    // Initialize the Merkle root.
233                    let root = <$ph<Circuit> as PathHash<Circuit>>::Hash::new(Mode::$mode, *merkle_tree.root());
234                    // Initialize the Merkle leaf.
235                    let leaf: Vec<_> = Inject::new(Mode::$mode, merkle_leaf.clone());
236
237                    Circuit::scope(format!("Verify {}", Mode::$mode), || {
238                        let candidate = path.verify(&circuit_leaf_hasher, &circuit_path_hasher, &root, &leaf);
239                        assert!(candidate.eject_value());
240                        assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
241                    });
242                    Circuit::reset();
243
244                    // Initialize an incorrect Merkle root.
245                    let incorrect_root =
246                        <$ph<Circuit> as PathHash<Circuit>>::Hash::new(Mode::$mode, Default::default());
247
248                    Circuit::scope(format!("Verify (Incorrect Root) {}", Mode::$mode), || {
249                        let candidate = path.verify(&circuit_leaf_hasher, &circuit_path_hasher, &incorrect_root, &leaf);
250                        assert!(!candidate.eject_value());
251                        assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
252                    });
253                    Circuit::reset();
254
255                    // Initialize an incorrect Merkle leaf.
256                    let mut incorrect_leaf = leaf.clone();
257                    let mut incorrect_value = Uniform::rand(&mut rng);
258                    while incorrect_value == incorrect_leaf[0].eject_value() {
259                        incorrect_value = Uniform::rand(&mut rng);
260                    }
261                    incorrect_leaf[0] = Inject::new(Mode::$mode, incorrect_value);
262
263                    Circuit::scope(format!("Verify (Incorrect Leaf) {}", Mode::$mode), || {
264                        let candidate = path.verify(&circuit_leaf_hasher, &circuit_path_hasher, &root, &incorrect_leaf);
265                        assert!(!candidate.eject_value());
266                        assert_scope!($num_constants, $num_public, $num_private, $num_constraints);
267                    });
268                    Circuit::reset();
269                }
270            }
271            Ok(())
272        }};
273    }
274
275    #[test]
276    fn test_verify_bhp512_constant() -> Result<()> {
277        check_verify!(BHP1024, BHP512, Constant, 10, 4, 1024, (39234, 0, 0, 0))
278    }
279
280    #[test]
281    fn test_verify_bhp512_public() -> Result<()> {
282        check_verify!(BHP1024, BHP512, Public, 10, 4, 1024, (9465, 0, 53876, 54056))
283    }
284
285    #[test]
286    fn test_verify_bhp512_private() -> Result<()> {
287        check_verify!(BHP1024, BHP512, Private, 10, 4, 1024, (9465, 0, 53876, 54056))
288    }
289
290    #[test]
291    fn test_verify_poseidon2_constant() -> Result<()> {
292        check_verify!(Poseidon4, Poseidon2, Constant, 10, 4, 4, (3584, 0, 0, 0))
293    }
294
295    #[test]
296    fn test_verify_poseidon2_public() -> Result<()> {
297        check_verify!(Poseidon4, Poseidon2, Public, 10, 4, 4, (4843, 0, 14152, 14232))
298    }
299
300    #[test]
301    fn test_verify_poseidon2_private() -> Result<()> {
302        check_verify!(Poseidon4, Poseidon2, Private, 10, 4, 4, (4843, 0, 14152, 14232))
303    }
304
305    #[test]
306    fn test_verify_keccak256_constant() -> Result<()> {
307        check_verify_keccak!(Keccak256, Keccak256, Constant, 10, 4, 256, (6388, 0, 0, 0))
308    }
309
310    #[test]
311    fn test_verify_keccak256_public() -> Result<()> {
312        check_verify_keccak!(Keccak256, Keccak256, Public, 10, 4, 256, (7648, 0, 1696439, 1696519))
313    }
314
315    #[test]
316    fn test_verify_keccak256_private() -> Result<()> {
317        check_verify_keccak!(Keccak256, Keccak256, Private, 10, 4, 256, (7648, 0, 1696439, 1696519))
318    }
319
320    #[test]
321    fn test_verify_sha3_256_constant() -> Result<()> {
322        check_verify_keccak!(Sha3_256, Sha3_256, Constant, 10, 4, 256, (6388, 0, 0, 0))
323    }
324
325    #[test]
326    fn test_verify_sha3_256_public() -> Result<()> {
327        check_verify_keccak!(Sha3_256, Sha3_256, Public, 10, 4, 256, (7648, 0, 1696439, 1696519))
328    }
329
330    #[test]
331    fn test_verify_sha3_256_private() -> Result<()> {
332        check_verify_keccak!(Sha3_256, Sha3_256, Private, 10, 4, 256, (7648, 0, 1696439, 1696519))
333    }
334}
snarkvm_circuit_collections/kary_merkle_tree/verify.rs

snarkvm_circuit_collections/kary_merkle_tree/
verify.rs
