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