snarkvm_console_collections/merkle_tree/path/
mod.rs

1// Copyright 2024 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
16use super::*;
17
18#[derive(Clone, Debug, PartialEq, Eq, Hash)]
19pub struct MerklePath<E: Environment, const DEPTH: u8> {
20    /// The leaf index for the path.
21    leaf_index: U64<E>,
22    /// The `siblings` contains a list of sibling hashes from the leaf to the root.
23    siblings: Vec<Field<E>>,
24}
25
26impl<E: Environment, const DEPTH: u8> TryFrom<(U64<E>, Vec<Field<E>>)> for MerklePath<E, DEPTH> {
27    type Error = Error;
28
29    /// Returns a new instance of a Merkle path.
30    fn try_from((leaf_index, siblings): (U64<E>, Vec<Field<E>>)) -> Result<Self> {
31        // Ensure the Merkle tree depth is greater than 0.
32        ensure!(DEPTH > 0, "Merkle tree depth must be greater than 0");
33        // Ensure the Merkle tree depth is less than or equal to 64.
34        ensure!(DEPTH <= 64u8, "Merkle tree depth must be less than or equal to 64");
35        // Ensure the leaf index is within the tree depth.
36        ensure!((*leaf_index as u128) < (1u128 << DEPTH), "Found an out of bounds Merkle leaf index");
37        // Ensure the Merkle path is the correct length.
38        ensure!(siblings.len() == DEPTH as usize, "Found an incorrect Merkle path length");
39        // Return the Merkle path.
40        Ok(Self { leaf_index, siblings })
41    }
42}
43
44impl<E: Environment, const DEPTH: u8> MerklePath<E, DEPTH> {
45    /// Returns the leaf index for the path.
46    pub fn leaf_index(&self) -> U64<E> {
47        self.leaf_index
48    }
49
50    /// Returns the siblings for the path.
51    pub fn siblings(&self) -> &[Field<E>] {
52        &self.siblings
53    }
54
55    /// Returns `true` if the Merkle path is valid for the given root and leaf.
56    pub fn verify<LH: LeafHash<Hash = PH::Hash>, PH: PathHash<Hash = Field<E>>>(
57        &self,
58        leaf_hasher: &LH,
59        path_hasher: &PH,
60        root: &PH::Hash,
61        leaf: &LH::Leaf,
62    ) -> bool {
63        // Ensure the leaf index is within the tree depth.
64        if (*self.leaf_index as u128) >= (1u128 << DEPTH) {
65            eprintln!("Found an out of bounds Merkle leaf index");
66            return false;
67        }
68        // Ensure the path length matches the expected depth.
69        else if self.siblings.len() != DEPTH as usize {
70            eprintln!("Found an incorrect Merkle path length");
71            return false;
72        }
73
74        // Initialize a tracker for the current hash, by computing the leaf hash to start.
75        let mut current_hash = match leaf_hasher.hash_leaf(leaf) {
76            Ok(candidate_leaf_hash) => candidate_leaf_hash,
77            Err(error) => {
78                eprintln!("Failed to hash the Merkle leaf during verification: {error}");
79                return false;
80            }
81        };
82
83        // Compute the ordering of the current hash and sibling hash on each level.
84        // If the indicator bit is `true`, then the ordering is (current_hash, sibling_hash).
85        // If the indicator bit is `false`, then the ordering is (sibling_hash, current_hash).
86        let indicators = (0..DEPTH).map(|i| ((*self.leaf_index >> i) & 1) == 0);
87
88        // Check levels between leaf level and root.
89        for (indicator, sibling_hash) in indicators.zip_eq(&self.siblings) {
90            // Construct the ordering of the left & right child hash for this level.
91            let (left, right) = match indicator {
92                true => (current_hash, *sibling_hash),
93                false => (*sibling_hash, current_hash),
94            };
95            // Update the current hash for the next level.
96            match path_hasher.hash_children(&left, &right) {
97                Ok(hash) => current_hash = hash,
98                Err(error) => {
99                    eprintln!("Failed to hash the Merkle path during verification: {error}");
100                    return false;
101                }
102            }
103        }
104
105        // Ensure the final hash matches the given root.
106        current_hash == *root
107    }
108}
109
110impl<E: Environment, const DEPTH: u8> FromBytes for MerklePath<E, DEPTH> {
111    /// Reads in a Merkle path from a buffer.
112    #[inline]
113    fn read_le<R: Read>(mut reader: R) -> IoResult<Self> {
114        // Read the leaf index.
115        let leaf_index = u64::read_le(&mut reader)?;
116        // Read the Merkle path siblings.
117        let siblings =
118            (0..DEPTH).map(|_| Ok(Field::new(FromBytes::read_le(&mut reader)?))).collect::<IoResult<Vec<_>>>()?;
119        // Return the Merkle path.
120        Self::try_from((U64::new(leaf_index), siblings)).map_err(error)
121    }
122}
123
124impl<E: Environment, const DEPTH: u8> ToBytes for MerklePath<E, DEPTH> {
125    /// Writes the Merkle path to a buffer.
126    #[inline]
127    fn write_le<W: Write>(&self, mut writer: W) -> IoResult<()> {
128        // Write the leaf index.
129        self.leaf_index.write_le(&mut writer)?;
130        // Write the Merkle path siblings.
131        self.siblings.iter().try_for_each(|sibling| sibling.write_le(&mut writer))
132    }
133}
134
135impl<E: Environment, const DEPTH: u8> Serialize for MerklePath<E, DEPTH> {
136    fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
137        ToBytesSerializer::serialize(self, serializer)
138    }
139}
140
141impl<'de, E: Environment, const DEPTH: u8> Deserialize<'de> for MerklePath<E, DEPTH> {
142    fn deserialize<D: Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
143        // Compute the size for: u64 + (Field::SIZE_IN_BYTES * DEPTH).
144        let size = 8 + DEPTH as usize * (Field::<E>::size_in_bits() + 7) / 8;
145        FromBytesDeserializer::<Self>::deserialize(deserializer, "Merkle path", size)
146    }
147}
snarkvm_console_collections/merkle_tree/path/mod.rs

snarkvm_console_collections/merkle_tree/path/
mod.rs
