miden-crypto/src/merkle/path.rs
src/merkle/path.rsRaw
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}