miden_crypto/merkle/
path.rs

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

miden_crypto/merkle/
path.rs
