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// SERIALIZATION
195// ================================================================================================
196
197impl Serializable for MerklePath {
198 fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
199 assert!(self.nodes.len() <= u8::MAX.into(), "Length enforced in the constructor");
200 target.write_u8(self.nodes.len() as u8);
201 self.nodes.write_into(target);
202 }
203}
204
205impl Deserializable for MerklePath {
206 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
207 let count = source.read_u8()?.into();
208 let nodes = RpoDigest::read_batch_from(source, count)?;
209 Ok(Self { nodes })
210 }
211}
212
213impl Serializable for ValuePath {
214 fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
215 self.value.write_into(target);
216 self.path.write_into(target);
217 }
218}
219
220impl Deserializable for ValuePath {
221 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
222 let value = RpoDigest::read_from(source)?;
223 let path = MerklePath::read_from(source)?;
224 Ok(Self { value, path })
225 }
226}
227
228impl Serializable for RootPath {
229 fn write_into<W: winter_utils::ByteWriter>(&self, target: &mut W) {
230 self.root.write_into(target);
231 self.path.write_into(target);
232 }
233}
234
235impl Deserializable for RootPath {
236 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
237 let root = RpoDigest::read_from(source)?;
238 let path = MerklePath::read_from(source)?;
239 Ok(Self { root, path })
240 }
241}
242
243// TESTS
244// ================================================================================================
245
246#[cfg(test)]
247mod tests {
248 use crate::merkle::{int_to_node, MerklePath};
249
250 #[test]
251 fn test_inner_nodes() {
252 let nodes = vec![int_to_node(1), int_to_node(2), int_to_node(3), int_to_node(4)];
253 let merkle_path = MerklePath::new(nodes);
254
255 let index = 6;
256 let node = int_to_node(5);
257 let root = merkle_path.compute_root(index, node).unwrap();
258
259 let inner_root = merkle_path.inner_nodes(index, node).unwrap().last().unwrap().value;
260
261 assert_eq!(root, inner_root);
262 }
263}