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