snarkvm_circuit_collections/merkle_tree/
mod.rs

1// Copyright 2024-2025 Aleo Network Foundation
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
16mod helpers;
17use helpers::{LeafHash, PathHash};
18
19mod verify;
20
21#[cfg(all(test, feature = "console"))]
22use snarkvm_circuit_types::environment::assert_scope;
23
24use snarkvm_circuit_types::{Boolean, Field, U64, environment::prelude::*};
25
26pub struct MerklePath<E: Environment, const DEPTH: u8> {
27    /// The leaf index for the path.
28    leaf_index: U64<E>,
29    /// The `siblings` contains a list of sibling hashes from the leaf to the root.
30    siblings: Vec<Field<E>>,
31}
32
33#[cfg(feature = "console")]
34impl<E: Environment, const DEPTH: u8> Inject for MerklePath<E, DEPTH> {
35    type Primitive = console::merkle_tree::MerklePath<E::Network, DEPTH>;
36
37    /// Initializes a Merkle path from the given mode and native Merkle path.
38    fn new(mode: Mode, merkle_path: Self::Primitive) -> Self {
39        // Initialize the leaf index.
40        let leaf_index = U64::new(mode, merkle_path.leaf_index());
41        // Initialize the Merkle path siblings.
42        let siblings: Vec<_> = merkle_path.siblings().iter().map(|node| Field::new(mode, *node)).collect();
43        // Ensure the Merkle path is the correct depth.
44        match siblings.len() == DEPTH as usize {
45            // Return the Merkle path.
46            true => Self { leaf_index, siblings },
47            false => E::halt("Merkle path is not the correct depth"),
48        }
49    }
50}
51
52#[cfg(feature = "console")]
53impl<E: Environment, const DEPTH: u8> Eject for MerklePath<E, DEPTH> {
54    type Primitive = console::merkle_tree::MerklePath<E::Network, DEPTH>;
55
56    /// Ejects the mode of the Merkle path.
57    fn eject_mode(&self) -> Mode {
58        (&self.leaf_index, &self.siblings).eject_mode()
59    }
60
61    /// Ejects the Merkle path.
62    fn eject_value(&self) -> Self::Primitive {
63        match Self::Primitive::try_from((&self.leaf_index, &self.siblings).eject_value()) {
64            Ok(merkle_path) => merkle_path,
65            Err(error) => E::halt(format!("Failed to eject the Merkle path: {error}")),
66        }
67    }
68}
69
70#[cfg(all(test, feature = "console"))]
71mod tests {
72    use super::*;
73    use snarkvm_circuit_network::AleoV0 as Circuit;
74    use snarkvm_utilities::{TestRng, Uniform};
75
76    use anyhow::Result;
77
78    const ITERATIONS: u128 = 100;
79
80    fn check_new<const DEPTH: u8>(
81        mode: Mode,
82        num_constants: u64,
83        num_public: u64,
84        num_private: u64,
85        num_constraints: u64,
86    ) -> Result<()> {
87        let mut rng = TestRng::default();
88
89        let mut create_leaves = |num_leaves| {
90            (0..num_leaves)
91                .map(|_| console::Field::<<Circuit as Environment>::Network>::rand(&mut rng).to_bits_le())
92                .collect::<Vec<_>>()
93        };
94
95        for i in 0..ITERATIONS {
96            // Determine the number of leaves.
97            let num_leaves = core::cmp::min(2u128.pow(DEPTH as u32), i);
98            // Compute the leaves.
99            let leaves = create_leaves(num_leaves);
100            // Compute the Merkle tree.
101            let merkle_tree = <<Circuit as Environment>::Network as snarkvm_console_network::Network>::merkle_tree_bhp::<
102                DEPTH,
103            >(&leaves)?;
104
105            for (index, leaf) in leaves.iter().enumerate() {
106                // Compute the Merkle path.
107                let merkle_path = merkle_tree.prove(index, leaf)?;
108
109                // // Initialize the Merkle leaf.
110                // let leaf: Vec<Boolean<_>> = Inject::new(mode, leaf.clone());
111
112                Circuit::scope(format!("New {mode}"), || {
113                    let candidate = MerklePath::<Circuit, DEPTH>::new(mode, merkle_path.clone());
114                    assert_eq!(merkle_path, candidate.eject_value());
115                    assert_scope!(num_constants, num_public, num_private, num_constraints);
116                });
117                Circuit::reset();
118            }
119        }
120        Ok(())
121    }
122
123    #[test]
124    fn test_new_constant() -> Result<()> {
125        check_new::<32>(Mode::Constant, 96, 0, 0, 0)
126    }
127
128    #[test]
129    fn test_new_public() -> Result<()> {
130        check_new::<32>(Mode::Public, 0, 96, 0, 64)
131    }
132
133    #[test]
134    fn test_new_private() -> Result<()> {
135        check_new::<32>(Mode::Private, 0, 0, 96, 64)
136    }
137}
snarkvm_circuit_collections/merkle_tree/mod.rs

snarkvm_circuit_collections/merkle_tree/
mod.rs
