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
52// ------------------------------------------------------------------------------------------------
53/// Augmentation
54impl MastNodeFingerprint {
55    /// Returns a new fingerprint that incorporates the given additional data into the
56    /// decorator root hash.
57    ///
58    /// This is used by the assembler to make the dedup key sensitive to external metadata
59    /// without storing that metadata on the node builder.
60    /// If `data` is empty, the fingerprint is returned unchanged.
61    pub fn augment_with_data(self, data: &[u8]) -> Self {
62        if data.is_empty() {
63            return self;
64        }
65
66        let existing: &[u8] = match &self.decorator_root {
67            Some(root) => root.as_bytes(),
68            None => &[],
69        };
70        let new_root = Blake3_256::hash_iter([existing, data].into_iter());
71        Self {
72            mast_root: self.mast_root,
73            decorator_root: Some(new_root),
74        }
75    }
76}
77
78pub fn fingerprint_from_parts(
79    forest: &MastForest,
80    hash_by_node_id: &impl LookupByIdx<MastNodeId, MastNodeFingerprint>,
81    before_enter_ids: &[DecoratorId],
82    after_exit_ids: &[DecoratorId],
83    children_ids: &[MastNodeId],
84    node_digest: Word,
85) -> Result<MastNodeFingerprint, MastForestError> {
86    let pre_decorator_hash_bytes: Vec<[u8; 32]> = before_enter_ids
87        .iter()
88        .map(|&id| *forest[id].fingerprint().as_bytes())
89        .collect();
90    let post_decorator_hash_bytes: Vec<[u8; 32]> =
91        after_exit_ids.iter().map(|&id| *forest[id].fingerprint().as_bytes()).collect();
92
93    let children_decorator_roots: Vec<[u8; 32]> = {
94        let mut roots = Vec::new();
95        for child_id in children_ids {
96            if let Some(child_fingerprint) = hash_by_node_id.get(*child_id) {
97                if let Some(decorator_root) = child_fingerprint.decorator_root {
98                    roots.push(*decorator_root.as_bytes());
99                }
100            } else {
101                return Err(MastForestError::ChildFingerprintMissing(*child_id));
102            }
103        }
104        roots
105    };
106
107    // Reminder: the `MastNodeFingerprint`'s decorator root will be `None` if and only if there are
108    // no decorators attached to the node, and all children have no decorator roots (meaning
109    // that there are no decorators in all the descendants).
110    if pre_decorator_hash_bytes.is_empty()
111        && post_decorator_hash_bytes.is_empty()
112        && children_decorator_roots.is_empty()
113    {
114        Ok(MastNodeFingerprint::new(node_digest))
115    } else {
116        let decorator_bytes_iter = pre_decorator_hash_bytes
117            .iter()
118            .map(|bytes| bytes.as_slice())
119            .chain(post_decorator_hash_bytes.iter().map(|bytes| bytes.as_slice()))
120            .chain(children_decorator_roots.iter().map(|bytes| bytes.as_slice()));
121
122        let decorator_root = Blake3_256::hash_iter(decorator_bytes_iter);
123        Ok(MastNodeFingerprint::with_decorator_root(node_digest, decorator_root))
124    }
125}
126
127// TESTS
128// ================================================================================================
miden_core/mast/node_fingerprint.rs

miden_core/mast/
node_fingerprint.rs
