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