1use super::{vec, MerkleError, NodeIndex, 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, index: u64, node: Word) -> Result<Word, MerkleError> {
 27        let mut index = NodeIndex::new(self.depth(), index)?;
 28        let root = self.nodes.iter().copied().fold(node, |node, sibling| {
 29            // compute the node and move to the next iteration.
 30            let input = index.build_node(node.into(), sibling.into());
 31            index.move_up();
 32            Rpo256::merge(&input).into()
 33        });
 34        Ok(root)
 35    }
 36
 37    /// Returns the depth in which this Merkle path proof is valid.
 38    pub fn depth(&self) -> u8 {
 39        self.nodes.len() as u8
 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: Word, root: &Word) -> bool {
 46        match self.compute_root(index, node) {
 47            Ok(computed_root) => root == &computed_root,
 48            Err(_) => false,
 49        }
 50    }
 51}
 52
 53impl From<Vec<Word>> for MerklePath {
 54    fn from(path: Vec<Word>) -> Self {
 55        Self::new(path)
 56    }
 57}
 58
 59impl Deref for MerklePath {
 60    // we use `Vec` here instead of slice so we can call vector mutation methods directly from the
 61    // merkle path (example: `Vec::remove`).
 62    type Target = Vec<Word>;
 63
 64    fn deref(&self) -> &Self::Target {
 65        &self.nodes
 66    }
 67}
 68
 69impl DerefMut for MerklePath {
 70    fn deref_mut(&mut self) -> &mut Self::Target {
 71        &mut self.nodes
 72    }
 73}
 74
 75impl FromIterator<Word> for MerklePath {
 76    fn from_iter<T: IntoIterator<Item = Word>>(iter: T) -> Self {
 77        Self::new(iter.into_iter().collect())
 78    }
 79}
 80
 81impl IntoIterator for MerklePath {
 82    type Item = Word;
 83    type IntoIter = vec::IntoIter<Word>;
 84
 85    fn into_iter(self) -> Self::IntoIter {
 86        self.nodes.into_iter()
 87    }
 88}
 89
 90// MERKLE PATH CONTAINERS
 91// ================================================================================================
 92
 93/// A container for a [Word] value and its [MerklePath] opening.
 94#[derive(Clone, Debug, Default, PartialEq, Eq)]
 95pub struct ValuePath {
 96    /// The node value opening for `path`.
 97    pub value: Word,
 98    /// The path from `value` to `root` (exclusive).
 99    pub path: MerklePath,
100}
101
102/// A container for a [MerklePath] and its [Word] root.
103///
104/// This structure does not provide any guarantees regarding the correctness of the path to the
105/// root. For more information, check [MerklePath::verify].
106#[derive(Clone, Debug, Default, PartialEq, Eq)]
107pub struct RootPath {
108    /// The node value opening for `path`.
109    pub root: Word,
110    /// The path from `value` to `root` (exclusive).
111    pub path: MerklePath,
112}