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