1use super::{vec, Rpo256, Vec, Word};
 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<Word>,
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<Word>) -> Self {
19        Self { nodes }
20    }
21
22    // PROVIDERS
23    // --------------------------------------------------------------------------------------------
24
25    /// Computes the merkle root for this opening.
26    pub fn compute_root(&self, mut index: u64, node: Word) -> Word {
27        self.nodes.iter().copied().fold(node, |node, sibling| {
28            // build the input node, considering the parity of the current index.
29            let is_right_sibling = (index & 1) == 1;
30            let input = if is_right_sibling {
31                [sibling.into(), node.into()]
32            } else {
33                [node.into(), sibling.into()]
34            };
35            // compute the node and move to the next iteration.
36            index >>= 1;
37            Rpo256::merge(&input).into()
38        })
39    }
40
41    /// Returns the depth in which this Merkle path proof is valid.
42    pub fn depth(&self) -> u8 {
43        self.nodes.len() as u8
44    }
45
46    /// Verifies the Merkle opening proof towards the provided root.
47    ///
48    /// Returns `true` if `node` exists at `index` in a Merkle tree with `root`.
49    pub fn verify(&self, index: u64, node: Word, root: &Word) -> bool {
50        root == &self.compute_root(index, node)
51    }
52}
53
54impl From<Vec<Word>> for MerklePath {
55    fn from(path: Vec<Word>) -> Self {
56        Self::new(path)
57    }
58}
59
60impl Deref for MerklePath {
61    // we use `Vec` here instead of slice so we can call vector mutation methods directly from the
62    // merkle path (example: `Vec::remove`).
63    type Target = Vec<Word>;
64
65    fn deref(&self) -> &Self::Target {
66        &self.nodes
67    }
68}
69
70impl DerefMut for MerklePath {
71    fn deref_mut(&mut self) -> &mut Self::Target {
72        &mut self.nodes
73    }
74}
75
76impl FromIterator<Word> for MerklePath {
77    fn from_iter<T: IntoIterator<Item = Word>>(iter: T) -> Self {
78        Self::new(iter.into_iter().collect())
79    }
80}
81
82impl IntoIterator for MerklePath {
83    type Item = Word;
84    type IntoIter = vec::IntoIter<Word>;
85
86    fn into_iter(self) -> Self::IntoIter {
87        self.nodes.into_iter()
88    }
89}