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