miden_core/mast/
node_fingerprint.rs

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

miden_core/mast/
node_fingerprint.rs
