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