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]> = before_enter_ids
61        .iter()
62        .map(|&id| *forest[id].fingerprint().as_bytes())
63        .collect();
64    let post_decorator_hash_bytes: Vec<[u8; 32]> =
65        after_exit_ids.iter().map(|&id| *forest[id].fingerprint().as_bytes()).collect();
66
67    let children_decorator_roots: Vec<[u8; 32]> = {
68        let mut roots = Vec::new();
69        for child_id in children_ids {
70            if let Some(child_fingerprint) = hash_by_node_id.get(*child_id) {
71                if let Some(decorator_root) = child_fingerprint.decorator_root {
72                    roots.push(*decorator_root.as_bytes());
73                }
74            } else {
75                return Err(MastForestError::ChildFingerprintMissing(*child_id));
76            }
77        }
78        roots
79    };
80
81    // Reminder: the `MastNodeFingerprint`'s decorator root will be `None` if and only if there are
82    // no decorators attached to the node, and all children have no decorator roots (meaning
83    // that there are no decorators in all the descendants).
84    if pre_decorator_hash_bytes.is_empty()
85        && post_decorator_hash_bytes.is_empty()
86        && children_decorator_roots.is_empty()
87    {
88        Ok(MastNodeFingerprint::new(node_digest))
89    } else {
90        let decorator_bytes_iter = pre_decorator_hash_bytes
91            .iter()
92            .map(|bytes| bytes.as_slice())
93            .chain(post_decorator_hash_bytes.iter().map(|bytes| bytes.as_slice()))
94            .chain(children_decorator_roots.iter().map(|bytes| bytes.as_slice()));
95
96        let decorator_root = Blake3_256::hash_iter(decorator_bytes_iter);
97        Ok(MastNodeFingerprint::with_decorator_root(node_digest, decorator_root))
98    }
99}
100
101// TESTS
102// ================================================================================================
miden_core/mast/node_fingerprint.rs

miden_core/mast/
node_fingerprint.rs
