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