miden_core/mast/
node_fingerprint.rs

1use alloc::vec::Vec;
2
3use crate::{
4    Word,
5    crypto::hash::{Blake3_256, Blake3Digest},
6    mast::{DecoratorId, MastForest, MastForestError, MastNodeId},
7    utils::LookupByIdx,
8};
9
10// MAST NODE EQUALITY
11// ================================================================================================
12
13pub type DecoratorFingerprint = Blake3Digest<32>;
14
15/// Represents the hash used to test for equality between [`crate::mast::MastNode`]s.
16///
17/// The decorator root will be `None` if and only if there are no decorators attached to the node,
18/// and all children have no decorator roots (meaning that there are no decorators in all the
19/// descendants).
20#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
21pub struct MastNodeFingerprint {
22    mast_root: Word,
23    decorator_root: Option<DecoratorFingerprint>,
24}
25
26// ------------------------------------------------------------------------------------------------
27/// Constructors
28impl MastNodeFingerprint {
29    /// Creates a new [`MastNodeFingerprint`] from the given MAST root with an empty decorator root.
30    pub fn new(mast_root: Word) -> Self {
31        Self { mast_root, decorator_root: None }
32    }
33
34    /// Creates a new [`MastNodeFingerprint`] from the given MAST root and the given
35    /// [`DecoratorFingerprint`].
36    pub fn with_decorator_root(mast_root: Word, decorator_root: DecoratorFingerprint) -> Self {
37        Self {
38            mast_root,
39            decorator_root: Some(decorator_root),
40        }
41    }
42}
43
44// ------------------------------------------------------------------------------------------------
45/// Accessors
46impl MastNodeFingerprint {
47    pub fn mast_root(&self) -> &Word {
48        &self.mast_root
49    }
50}
51
52pub fn fingerprint_from_parts(
53    forest: &MastForest,
54    hash_by_node_id: &impl LookupByIdx<MastNodeId, MastNodeFingerprint>,
55    before_enter_ids: &[DecoratorId],
56    after_exit_ids: &[DecoratorId],
57    children_ids: &[MastNodeId],
58    node_digest: Word,
59) -> Result<MastNodeFingerprint, MastForestError> {
60    let pre_decorator_hash_bytes: Vec<[u8; 32]> =
61        before_enter_ids.iter().map(|&id| forest[id].fingerprint().as_bytes()).collect();
62    let post_decorator_hash_bytes: Vec<[u8; 32]> =
63        after_exit_ids.iter().map(|&id| forest[id].fingerprint().as_bytes()).collect();
64
65    let children_decorator_roots: Vec<[u8; 32]> = {
66        let mut roots = Vec::new();
67        for child_id in children_ids {
68            if let Some(child_fingerprint) = hash_by_node_id.get(*child_id) {
69                if let Some(decorator_root) = child_fingerprint.decorator_root {
70                    roots.push(decorator_root.as_bytes());
71                }
72            } else {
73                return Err(MastForestError::ChildFingerprintMissing(*child_id));
74            }
75        }
76        roots
77    };
78
79    // Reminder: the `MastNodeFingerprint`'s decorator root will be `None` if and only if there are
80    // no decorators attached to the node, and all children have no decorator roots (meaning
81    // that there are no decorators in all the descendants).
82    if pre_decorator_hash_bytes.is_empty()
83        && post_decorator_hash_bytes.is_empty()
84        && children_decorator_roots.is_empty()
85    {
86        Ok(MastNodeFingerprint::new(node_digest))
87    } else {
88        let decorator_bytes_iter = pre_decorator_hash_bytes
89            .iter()
90            .map(|bytes| bytes.as_slice())
91            .chain(post_decorator_hash_bytes.iter().map(|bytes| bytes.as_slice()))
92            .chain(children_decorator_roots.iter().map(|bytes| bytes.as_slice()));
93
94        let decorator_root = Blake3_256::hash_iter(decorator_bytes_iter);
95        Ok(MastNodeFingerprint::with_decorator_root(node_digest, decorator_root))
96    }
97}
98
99// TESTS
100// ================================================================================================
miden_core/mast/node_fingerprint.rs

miden_core/mast/
node_fingerprint.rs
