miden_crypto/merkle/
path.rs

1use alloc::vec::Vec;
2use core::{
3    num::NonZero,
4    ops::{Deref, DerefMut},
5};
6
7use super::{InnerNodeInfo, MerkleError, NodeIndex, Rpo256, Word};
8use crate::utils::{ByteReader, 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(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
19pub struct MerklePath {
20    nodes: Vec<Word>,
21}
22
23impl MerklePath {
24    // CONSTRUCTORS
25    // --------------------------------------------------------------------------------------------
26
27    /// Creates a new Merkle path from a list of nodes.
28    ///
29    /// The list must be in order of deepest to shallowest.
30    pub fn new(nodes: Vec<Word>) -> Self {
31        assert!(nodes.len() <= u8::MAX.into(), "MerklePath may have at most 256 items");
32        Self { nodes }
33    }
34
35    // PROVIDERS
36    // --------------------------------------------------------------------------------------------
37
38    /// Returns a reference to the path node at the specified depth.
39    ///
40    /// The `depth` parameter is defined in terms of `self.depth()`. Merkle paths conventionally do
41    /// not include the root, so the shallowest depth is `1`, and the deepest depth is
42    /// `self.depth()`.
43    pub fn at_depth(&self, depth: NonZero<u8>) -> Option<Word> {
44        let index = u8::checked_sub(self.depth(), depth.get())?;
45        self.nodes.get(index as usize).copied()
46    }
47
48    /// Returns the depth in which this Merkle path proof is valid.
49    pub fn depth(&self) -> u8 {
50        self.nodes.len() as u8
51    }
52
53    /// Returns a reference to the [MerklePath]'s nodes, in order of deepest to shallowest.
54    pub fn nodes(&self) -> &[Word] {
55        &self.nodes
56    }
57
58    /// Computes the merkle root for this opening.
59    pub fn compute_root(&self, index: u64, node: Word) -> Result<Word, MerkleError> {
60        let mut index = NodeIndex::new(self.depth(), index)?;
61        let root = self.nodes.iter().copied().fold(node, |node, sibling| {
62            // compute the node and move to the next iteration.
63            let input = index.build_node(node, sibling);
64            index.move_up();
65            Rpo256::merge(&input)
66        });
67        Ok(root)
68    }
69
70    /// Verifies the Merkle opening proof towards the provided root.
71    ///
72    /// # Errors
73    /// Returns an error if:
74    /// - provided node index is invalid.
75    /// - root calculated during the verification differs from the provided one.
76    pub fn verify(&self, index: u64, node: Word, root: &Word) -> Result<(), MerkleError> {
77        let computed_root = self.compute_root(index, node)?;
78        if &computed_root != root {
79            return Err(MerkleError::ConflictingRoots {
80                expected_root: *root,
81                actual_root: computed_root,
82            });
83        }
84
85        Ok(())
86    }
87
88    /// Given the node this path opens to, return an iterator of all the nodes that are known via
89    /// this path.
90    ///
91    /// Each item in the iterator is an [InnerNodeInfo], containing the hash of a node as `.value`,
92    /// and its two children as `.left` and `.right`. The very first item in that iterator will be
93    /// the parent of `node_to_prove`, either `left` or `right` will be `node_to_prove` itself, and
94    /// the other child will be `node_to_prove` as stored in this [MerklePath].
95    ///
96    /// From there, the iterator will continue to yield every further parent and both of its
97    /// children, up to and including the root node.
98    ///
99    /// If `node_to_prove` is not the node this path is an opening to, or `index` is not the
100    /// correct index for that node, the returned nodes will be meaningless.
101    ///
102    /// # Errors
103    /// Returns an error if the specified index is not valid for this path.
104    pub fn authenticated_nodes(
105        &self,
106        index: u64,
107        node_to_prove: Word,
108    ) -> Result<InnerNodeIterator<'_>, MerkleError> {
109        Ok(InnerNodeIterator {
110            nodes: &self.nodes,
111            index: NodeIndex::new(self.depth(), index)?,
112            value: node_to_prove,
113        })
114    }
115}
116
117// CONVERSIONS
118// ================================================================================================
119
120impl From<MerklePath> for Vec<Word> {
121    fn from(path: MerklePath) -> Self {
122        path.nodes
123    }
124}
125
126impl From<Vec<Word>> for MerklePath {
127    fn from(path: Vec<Word>) -> Self {
128        Self::new(path)
129    }
130}
131
132impl From<&[Word]> for MerklePath {
133    fn from(path: &[Word]) -> Self {
134        Self::new(path.to_vec())
135    }
136}
137
138impl Deref for MerklePath {
139    // we use `Vec` here instead of slice so we can call vector mutation methods directly from the
140    // merkle path (example: `Vec::remove`).
141    type Target = Vec<Word>;
142
143    fn deref(&self) -> &Self::Target {
144        &self.nodes
145    }
146}
147
148impl DerefMut for MerklePath {
149    fn deref_mut(&mut self) -> &mut Self::Target {
150        &mut self.nodes
151    }
152}
153
154// ITERATORS
155// ================================================================================================
156
157impl FromIterator<Word> for MerklePath {
158    fn from_iter<T: IntoIterator<Item = Word>>(iter: T) -> Self {
159        Self::new(iter.into_iter().collect())
160    }
161}
162
163impl IntoIterator for MerklePath {
164    type Item = Word;
165    type IntoIter = alloc::vec::IntoIter<Word>;
166
167    fn into_iter(self) -> Self::IntoIter {
168        self.nodes.into_iter()
169    }
170}
171
172/// An iterator over internal nodes of a [MerklePath]. See [`MerklePath::authenticated_nodes()`]
173pub struct InnerNodeIterator<'a> {
174    nodes: &'a Vec<Word>,
175    index: NodeIndex,
176    value: Word,
177}
178
179impl Iterator for InnerNodeIterator<'_> {
180    type Item = InnerNodeInfo;
181
182    fn next(&mut self) -> Option<Self::Item> {
183        if !self.index.is_root() {
184            let sibling_pos = self.nodes.len() - self.index.depth() as usize;
185            let (left, right) = if self.index.is_value_odd() {
186                (self.nodes[sibling_pos], self.value)
187            } else {
188                (self.value, self.nodes[sibling_pos])
189            };
190
191            self.value = Rpo256::merge(&[left, right]);
192            self.index.move_up();
193
194            Some(InnerNodeInfo { value: self.value, left, right })
195        } else {
196            None
197        }
198    }
199}
200
201// MERKLE PATH CONTAINERS
202// ================================================================================================
203
204/// A container for a [crate::Word] value and its [MerklePath] opening.
205#[derive(Clone, Debug, Default, PartialEq, Eq)]
206pub struct MerkleProof {
207    /// The node value opening for `path`.
208    pub value: Word,
209    /// The path from `value` to `root` (exclusive).
210    pub path: MerklePath,
211}
212
213impl MerkleProof {
214    /// Returns a new [MerkleProof] instantiated from the specified value and path.
215    pub fn new(value: Word, path: MerklePath) -> Self {
216        Self { value, path }
217    }
218}
219
220impl From<(MerklePath, Word)> for MerkleProof {
221    fn from((path, value): (MerklePath, Word)) -> Self {
222        MerkleProof::new(value, path)
223    }
224}
225
226/// A container for a [MerklePath] and its [crate::Word] root.
227///
228/// This structure does not provide any guarantees regarding the correctness of the path to the
229/// root. For more information, check [MerklePath::verify].
230#[derive(Clone, Debug, Default, PartialEq, Eq)]
231pub struct RootPath {
232    /// The node value opening for `path`.
233    pub root: Word,
234    /// The path from `value` to `root` (exclusive).
235    pub path: MerklePath,
236}
237
238// SERIALIZATION
239// ================================================================================================
240
241impl Serializable for MerklePath {
242    fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
243        assert!(self.nodes.len() <= u8::MAX.into(), "Length enforced in the constructor");
244        target.write_u8(self.nodes.len() as u8);
245        target.write_many(&self.nodes);
246    }
247}
248
249impl Deserializable for MerklePath {
250    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
251        let count = source.read_u8()?.into();
252        let nodes = source.read_many::<Word>(count)?;
253        Ok(Self { nodes })
254    }
255}
256
257impl Serializable for MerkleProof {
258    fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
259        self.value.write_into(target);
260        self.path.write_into(target);
261    }
262}
263
264impl Deserializable for MerkleProof {
265    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
266        let value = Word::read_from(source)?;
267        let path = MerklePath::read_from(source)?;
268        Ok(Self { value, path })
269    }
270}
271
272impl Serializable for RootPath {
273    fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
274        self.root.write_into(target);
275        self.path.write_into(target);
276    }
277}
278
279impl Deserializable for RootPath {
280    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
281        let root = Word::read_from(source)?;
282        let path = MerklePath::read_from(source)?;
283        Ok(Self { root, path })
284    }
285}
286
287// TESTS
288// ================================================================================================
289
290#[cfg(test)]
291mod tests {
292    use crate::merkle::{MerklePath, int_to_node};
293
294    #[test]
295    fn test_inner_nodes() {
296        let nodes = vec![int_to_node(1), int_to_node(2), int_to_node(3), int_to_node(4)];
297        let merkle_path = MerklePath::new(nodes);
298
299        let index = 6;
300        let node = int_to_node(5);
301        let root = merkle_path.compute_root(index, node).unwrap();
302
303        let inner_root =
304            merkle_path.authenticated_nodes(index, node).unwrap().last().unwrap().value;
305
306        assert_eq!(root, inner_root);
307    }
308}
miden_crypto/merkle/path.rs

miden_crypto/merkle/
path.rs
