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(vec![computed_root, root.clone()]));
65 }
66
67 Ok(())
68 }
69
70 /// Returns an iterator over every inner node of this [MerklePath].
71 ///
72 /// The iteration order is unspecified.
73 ///
74 /// # Errors
75 /// Returns an error if the specified index is not valid for this path.
76 pub fn inner_nodes(
77 &self,
78 index: u64,
79 node: RpoDigest,
80 ) -> Result<InnerNodeIterator, MerkleError> {
81 Ok(InnerNodeIterator {
82 nodes: &self.nodes,
83 index: NodeIndex::new(self.depth(), index)?,
84 value: node,
85 })
86 }
87}
88
89// CONVERSIONS
90// ================================================================================================
91
92impl From<MerklePath> for Vec<RpoDigest> {
93 fn from(path: MerklePath) -> Self {
94 path.nodes
95 }
96}
97
98impl From<Vec<RpoDigest>> for MerklePath {
99 fn from(path: Vec<RpoDigest>) -> Self {
100 Self::new(path)
101 }
102}
103
104impl From<&[RpoDigest]> for MerklePath {
105 fn from(path: &[RpoDigest]) -> Self {
106 Self::new(path.to_vec())
107 }
108}
109
110impl Deref for MerklePath {
111 // we use `Vec` here instead of slice so we can call vector mutation methods directly from the
112 // merkle path (example: `Vec::remove`).
113 type Target = Vec<RpoDigest>;
114
115 fn deref(&self) -> &Self::Target {
116 &self.nodes
117 }
118}
119
120impl DerefMut for MerklePath {
121 fn deref_mut(&mut self) -> &mut Self::Target {
122 &mut self.nodes
123 }
124}
125
126// ITERATORS
127// ================================================================================================
128
129impl FromIterator<RpoDigest> for MerklePath {
130 fn from_iter<T: IntoIterator<Item = RpoDigest>>(iter: T) -> Self {
131 Self::new(iter.into_iter().collect())
132 }
133}
134
135impl IntoIterator for MerklePath {
136 type Item = RpoDigest;
137 type IntoIter = alloc::vec::IntoIter<RpoDigest>;
138
139 fn into_iter(self) -> Self::IntoIter {
140 self.nodes.into_iter()
141 }
142}
143
144/// An iterator over internal nodes of a [MerklePath].
145pub struct InnerNodeIterator<'a> {
146 nodes: &'a Vec<RpoDigest>,
147 index: NodeIndex,
148 value: RpoDigest,
149}
150
151impl<'a> Iterator for InnerNodeIterator<'a> {
152 type Item = InnerNodeInfo;
153
154 fn next(&mut self) -> Option<Self::Item> {
155 if !self.index.is_root() {
156 let sibling_pos = self.nodes.len() - self.index.depth() as usize;
157 let (left, right) = if self.index.is_value_odd() {
158 (self.nodes[sibling_pos], self.value)
159 } else {
160 (self.value, self.nodes[sibling_pos])
161 };
162
163 self.value = Rpo256::merge(&[left, right]);
164 self.index.move_up();
165
166 Some(InnerNodeInfo { value: self.value, left, right })
167 } else {
168 None
169 }
170 }
171}
172
173// MERKLE PATH CONTAINERS
174// ================================================================================================
175
176/// A container for a [crate::Word] value and its [MerklePath] opening.
177#[derive(Clone, Debug, Default, PartialEq, Eq)]
178pub struct ValuePath {
179 /// The node value opening for `path`.
180 pub value: RpoDigest,
181 /// The path from `value` to `root` (exclusive).
182 pub path: MerklePath,
183}
184
185impl ValuePath {
186 /// Returns a new [ValuePath] instantiated from the specified value and path.
187 pub fn new(value: RpoDigest, path: MerklePath) -> Self {
188 Self { value, path }
189 }
190}
191
192impl From<(MerklePath, Word)> for ValuePath {
193 fn from((path, value): (MerklePath, Word)) -> Self {
194 ValuePath::new(value.into(), path)
195 }
196}
197
198/// A container for a [MerklePath] and its [crate::Word] root.
199///
200/// This structure does not provide any guarantees regarding the correctness of the path to the
201/// root. For more information, check [MerklePath::verify].
202#[derive(Clone, Debug, Default, PartialEq, Eq)]
203pub struct RootPath {
204 /// The node value opening for `path`.
205 pub root: RpoDigest,
206 /// The path from `value` to `root` (exclusive).
207 pub path: MerklePath,
208}
209
210// SERIALIZATION
211// ================================================================================================
212
213impl Serializable for MerklePath {
214 fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
215 assert!(self.nodes.len() <= u8::MAX.into(), "Length enforced in the constructor");
216 target.write_u8(self.nodes.len() as u8);
217 target.write_many(&self.nodes);
218 }
219}
220
221impl Deserializable for MerklePath {
222 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
223 let count = source.read_u8()?.into();
224 let nodes = source.read_many::<RpoDigest>(count)?;
225 Ok(Self { nodes })
226 }
227}
228
229impl Serializable for ValuePath {
230 fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
231 self.value.write_into(target);
232 self.path.write_into(target);
233 }
234}
235
236impl Deserializable for ValuePath {
237 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
238 let value = RpoDigest::read_from(source)?;
239 let path = MerklePath::read_from(source)?;
240 Ok(Self { value, path })
241 }
242}
243
244impl Serializable for RootPath {
245 fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
246 self.root.write_into(target);
247 self.path.write_into(target);
248 }
249}
250
251impl Deserializable for RootPath {
252 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
253 let root = RpoDigest::read_from(source)?;
254 let path = MerklePath::read_from(source)?;
255 Ok(Self { root, path })
256 }
257}
258
259// TESTS
260// ================================================================================================
261
262#[cfg(test)]
263mod tests {
264 use crate::merkle::{int_to_node, MerklePath};
265
266 #[test]
267 fn test_inner_nodes() {
268 let nodes = vec![int_to_node(1), int_to_node(2), int_to_node(3), int_to_node(4)];
269 let merkle_path = MerklePath::new(nodes);
270
271 let index = 6;
272 let node = int_to_node(5);
273 let root = merkle_path.compute_root(index, node).unwrap();
274
275 let inner_root = merkle_path.inner_nodes(index, node).unwrap().last().unwrap().value;
276
277 assert_eq!(root, inner_root);
278 }
279}