miden_crypto/merkle/
path.rs

1use alloc::vec::Vec;
2use core::{
3    num::NonZero,
4    ops::{Deref, DerefMut},
5};
6
7use super::{Eidos, InnerNodeInfo, MerkleError, NodeIndex, Word};
8use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
9
10// MERKLE PATH
11// ================================================================================================
12
13/// A merkle path container, composed of a sequence of nodes of a Merkle tree.
14///
15/// Indexing into this type starts at the deepest part of the path and gets shallower. That is,
16/// the node at index `0` is deeper than the node at index `self.len() - 1`.
17#[derive(Clone, Debug, Default, PartialEq, Eq)]
18#[cfg_attr(
19    all(feature = "arbitrary", test),
20    miden_test_serialization_macros::serialization_test
21)]
22pub struct MerklePath {
23    nodes: Vec<Word>,
24}
25
26impl MerklePath {
27    // CONSTRUCTORS
28    // --------------------------------------------------------------------------------------------
29
30    /// Creates a new Merkle path from a list of nodes.
31    ///
32    /// The list must be in order of deepest to shallowest.
33    ///
34    /// # Panics
35    ///
36    /// Panics if more than 255 nodes are provided.
37    pub fn new(nodes: Vec<Word>) -> Self {
38        assert!(nodes.len() <= u8::MAX.into(), "MerklePath may have at most 255 items");
39        Self { nodes }
40    }
41
42    // PROVIDERS
43    // --------------------------------------------------------------------------------------------
44
45    /// Returns a reference to the path node at the specified depth.
46    ///
47    /// The `depth` parameter is defined in terms of `self.depth()`. Merkle paths conventionally do
48    /// not include the root, so the shallowest depth is `1`, and the deepest depth is
49    /// `self.depth()`.
50    pub fn at_depth(&self, depth: NonZero<u8>) -> Option<Word> {
51        let index = u8::checked_sub(self.depth(), depth.get())?;
52        self.nodes.get(index as usize).copied()
53    }
54
55    /// Returns the depth in which this Merkle path proof is valid.
56    pub fn depth(&self) -> u8 {
57        u8::try_from(self.nodes.len()).expect("MerklePath may have at most 255 items")
58    }
59
60    /// Returns a reference to the [MerklePath]'s nodes, in order of deepest to shallowest.
61    pub fn nodes(&self) -> &[Word] {
62        &self.nodes
63    }
64
65    /// Computes the merkle root for this opening.
66    pub fn compute_root(&self, index: u64, node: Word) -> Result<Word, MerkleError> {
67        let mut index = NodeIndex::new(self.depth(), index)?;
68        let root = self.nodes.iter().copied().fold(node, |node, sibling| {
69            // compute the node and move to the next iteration.
70            let input = index.build_node(node, sibling);
71            index.move_up();
72            Eidos::merge(&input)
73        });
74        Ok(root)
75    }
76
77    /// Verifies the Merkle opening proof towards the provided root.
78    ///
79    /// # Errors
80    /// Returns an error if:
81    /// - provided node index is invalid.
82    /// - root calculated during the verification differs from the provided one.
83    pub fn verify(&self, index: u64, node: Word, root: &Word) -> Result<(), MerkleError> {
84        let computed_root = self.compute_root(index, node)?;
85        if &computed_root != root {
86            return Err(MerkleError::ConflictingRoots {
87                expected_root: *root,
88                actual_root: computed_root,
89            });
90        }
91
92        Ok(())
93    }
94
95    /// Given the node this path opens to, return an iterator of all the nodes that are known via
96    /// this path.
97    ///
98    /// Each item in the iterator is an [InnerNodeInfo], containing the hash of a node as `.value`,
99    /// and its two children as `.left` and `.right`. The very first item in that iterator will be
100    /// the parent of `node_to_prove`, either `left` or `right` will be `node_to_prove` itself, and
101    /// the other child will be `node_to_prove` as stored in this [MerklePath].
102    ///
103    /// From there, the iterator will continue to yield every further parent and both of its
104    /// children, up to and including the root node.
105    ///
106    /// If `node_to_prove` is not the node this path is an opening to, or `index` is not the
107    /// correct index for that node, the returned nodes will be meaningless.
108    ///
109    /// # Errors
110    /// Returns an error if the specified index is not valid for this path.
111    pub fn authenticated_nodes(
112        &self,
113        index: u64,
114        node_to_prove: Word,
115    ) -> Result<InnerNodeIterator<'_>, MerkleError> {
116        Ok(InnerNodeIterator {
117            nodes: &self.nodes,
118            index: NodeIndex::new(self.depth(), index)?,
119            value: node_to_prove,
120        })
121    }
122}
123
124// CONVERSIONS
125// ================================================================================================
126
127impl From<MerklePath> for Vec<Word> {
128    fn from(path: MerklePath) -> Self {
129        path.nodes
130    }
131}
132
133impl From<Vec<Word>> for MerklePath {
134    fn from(path: Vec<Word>) -> Self {
135        Self::new(path)
136    }
137}
138
139impl From<&[Word]> for MerklePath {
140    fn from(path: &[Word]) -> Self {
141        path.iter().copied().collect()
142    }
143}
144
145impl Deref for MerklePath {
146    type Target = [Word];
147
148    fn deref(&self) -> &Self::Target {
149        &self.nodes
150    }
151}
152
153impl DerefMut for MerklePath {
154    fn deref_mut(&mut self) -> &mut Self::Target {
155        &mut self.nodes
156    }
157}
158
159// ITERATORS
160// ================================================================================================
161
162impl FromIterator<Word> for MerklePath {
163    fn from_iter<T: IntoIterator<Item = Word>>(iter: T) -> Self {
164        Self::new(iter.into_iter().take(usize::from(u8::MAX) + 1).collect())
165    }
166}
167
168impl IntoIterator for MerklePath {
169    type Item = Word;
170    type IntoIter = alloc::vec::IntoIter<Word>;
171
172    fn into_iter(self) -> Self::IntoIter {
173        self.nodes.into_iter()
174    }
175}
176
177/// An iterator over internal nodes of a [MerklePath]. See [`MerklePath::authenticated_nodes()`]
178pub struct InnerNodeIterator<'a> {
179    nodes: &'a [Word],
180    index: NodeIndex,
181    value: Word,
182}
183
184impl Iterator for InnerNodeIterator<'_> {
185    type Item = InnerNodeInfo;
186
187    fn next(&mut self) -> Option<Self::Item> {
188        if !self.index.is_root() {
189            let sibling_pos = self.nodes.len() - self.index.depth() as usize;
190            let (left, right) = if self.index.is_position_odd() {
191                (self.nodes[sibling_pos], self.value)
192            } else {
193                (self.value, self.nodes[sibling_pos])
194            };
195
196            self.value = Eidos::merge(&[left, right]);
197            self.index.move_up();
198
199            Some(InnerNodeInfo { value: self.value, left, right })
200        } else {
201            None
202        }
203    }
204}
205
206// MERKLE PATH CONTAINERS
207// ================================================================================================
208
209/// A container for a [crate::Word] value and its [MerklePath] opening.
210#[derive(Clone, Debug, Default, PartialEq, Eq)]
211#[cfg_attr(
212    all(feature = "arbitrary", test),
213    miden_test_serialization_macros::serialization_test
214)]
215pub struct MerkleProof {
216    /// The node value opening for `path`.
217    pub value: Word,
218    /// The path from `value` to `root` (exclusive).
219    pub path: MerklePath,
220}
221
222impl MerkleProof {
223    /// Returns a new [MerkleProof] instantiated from the specified value and path.
224    pub fn new(value: Word, path: MerklePath) -> Self {
225        Self { value, path }
226    }
227}
228
229impl From<(MerklePath, Word)> for MerkleProof {
230    fn from((path, value): (MerklePath, Word)) -> Self {
231        MerkleProof::new(value, path)
232    }
233}
234
235/// A container for a [MerklePath] and its [crate::Word] root.
236///
237/// This structure does not provide any guarantees regarding the correctness of the path to the
238/// root. For more information, check [MerklePath::verify].
239#[derive(Clone, Debug, Default, PartialEq, Eq)]
240#[cfg_attr(
241    all(feature = "arbitrary", test),
242    miden_test_serialization_macros::serialization_test
243)]
244pub struct RootPath {
245    /// The node value opening for `path`.
246    pub root: Word,
247    /// The path from `value` to `root` (exclusive).
248    pub path: MerklePath,
249}
250
251// SERIALIZATION
252// ================================================================================================
253
254impl Serializable for MerklePath {
255    fn write_into<W: ByteWriter>(&self, target: &mut W) {
256        // Keep the wire-format length prefix safe if an internal construction path ever violates
257        // the type invariant.
258        assert!(self.nodes.len() <= u8::MAX.into(), "MerklePath may have at most 255 items");
259        target.write_u8(self.nodes.len() as u8);
260        target.write_many(&self.nodes);
261    }
262}
263
264impl Deserializable for MerklePath {
265    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
266        let count = source.read_u8()?.into();
267        let nodes: Vec<Word> = source.read_many_iter(count)?.collect::<Result<_, _>>()?;
268        Ok(Self { nodes })
269    }
270}
271
272impl Serializable for MerkleProof {
273    fn write_into<W: ByteWriter>(&self, target: &mut W) {
274        self.value.write_into(target);
275        self.path.write_into(target);
276    }
277}
278
279impl Deserializable for MerkleProof {
280    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
281        let value = Word::read_from(source)?;
282        let path = MerklePath::read_from(source)?;
283        Ok(Self { value, path })
284    }
285}
286
287impl Serializable for RootPath {
288    fn write_into<W: ByteWriter>(&self, target: &mut W) {
289        self.root.write_into(target);
290        self.path.write_into(target);
291    }
292}
293
294impl Deserializable for RootPath {
295    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
296        let root = Word::read_from(source)?;
297        let path = MerklePath::read_from(source)?;
298        Ok(Self { root, path })
299    }
300}
301
302// TESTS
303// ================================================================================================
304
305#[cfg(test)]
306mod tests {
307    use crate::{
308        merkle::{MerklePath, int_to_node},
309        utils::Serializable,
310    };
311
312    #[test]
313    #[should_panic(expected = "MerklePath may have at most 255 items")]
314    fn new_rejects_more_than_255_nodes() {
315        let _ = MerklePath::new(vec![int_to_node(0); u8::MAX as usize + 1]);
316    }
317
318    /// The `Arbitrary` impl only generates paths up to `SMT_MAX_DEPTH` (64) nodes, so the
319    /// round-trip proptest never reaches the 65..=255 length range the wire format supports.
320    /// These cases cover the length-prefix boundaries explicitly, including the maximum.
321    #[test]
322    fn serialization_roundtrip_boundary_lengths() {
323        use miden_serde_utils::Deserializable;
324
325        use crate::merkle::MerklePath;
326
327        for len in [65usize, 254, 255] {
328            let path = MerklePath::new((0..len as u64).map(int_to_node).collect());
329            let bytes = path.to_bytes();
330            let round_trip = MerklePath::read_from_bytes(&bytes).unwrap();
331            assert_eq!(path, round_trip, "round trip failed for length {len}");
332        }
333    }
334
335    #[test]
336    #[should_panic(expected = "MerklePath may have at most 255 items")]
337    fn from_iter_caps_allocation_and_rejects_excess_nodes() {
338        // Model an attacker-controlled size hint without materializing the input.
339        let nodes = (0..usize::MAX).map(|_| int_to_node(0));
340        let _ = MerklePath::from_iter(nodes);
341    }
342
343    #[test]
344    #[should_panic(expected = "MerklePath may have at most 255 items")]
345    fn depth_rejects_an_internally_invalid_length() {
346        // Public construction rejects this state; construct it directly to exercise the
347        // defense-in-depth check in `depth()`.
348        let path = MerklePath {
349            nodes: vec![int_to_node(0); u8::MAX as usize + 1],
350        };
351        let _ = path.depth();
352    }
353
354    #[test]
355    #[should_panic(expected = "MerklePath may have at most 255 items")]
356    fn serialization_rejects_an_internally_invalid_length() {
357        let path = MerklePath {
358            nodes: vec![int_to_node(0); u8::MAX as usize + 1],
359        };
360        let _ = path.to_bytes();
361    }
362
363    #[test]
364    fn test_inner_nodes() {
365        let nodes = vec![int_to_node(1), int_to_node(2), int_to_node(3), int_to_node(4)];
366        let merkle_path = MerklePath::new(nodes);
367
368        let index = 6;
369        let node = int_to_node(5);
370        let root = merkle_path.compute_root(index, node).unwrap();
371
372        let inner_root =
373            merkle_path.authenticated_nodes(index, node).unwrap().last().unwrap().value;
374
375        assert_eq!(root, inner_root);
376    }
377}
miden_crypto/merkle/path.rs

miden_crypto/merkle/
path.rs
