miden_core/mast/
node_fingerprint.rs

1use alloc::{collections::BTreeMap, vec::Vec};
2
3use miden_crypto::hash::{
4    Digest,
5    blake::{Blake3_256, Blake3Digest},
6};
7
8use crate::{
9    Operation, Word,
10    mast::{DecoratorId, MastForest, MastForestError, MastNode, 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 [`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    /// Creates a [`MastNodeFingerprint`] from a [`MastNode`].
47    ///
48    /// The `hash_by_node_id` map must contain all children of the node for efficient lookup of
49    /// their fingerprints. This function returns an error if a child of the given `node` is not in
50    /// this map.
51    pub fn from_mast_node(
52        forest: &MastForest,
53        hash_by_node_id: &BTreeMap<MastNodeId, MastNodeFingerprint>,
54        node: &MastNode,
55    ) -> Result<MastNodeFingerprint, MastForestError> {
56        match node {
57            MastNode::Block(node) => {
58                let mut bytes_to_hash = Vec::new();
59
60                for &(idx, decorator_id) in node.decorators() {
61                    bytes_to_hash.extend(idx.to_le_bytes());
62                    bytes_to_hash.extend(forest[decorator_id].fingerprint().as_bytes());
63                }
64
65                // Add any `Assert`, `U32assert2` and `MpVerify` opcodes present, since these are
66                // not included in the MAST root.
67                for (op_idx, op) in node.operations().enumerate() {
68                    if let Operation::U32assert2(inner_value)
69                    | Operation::Assert(inner_value)
70                    | Operation::MpVerify(inner_value) = op
71                    {
72                        let op_idx: u32 = op_idx
73                            .try_into()
74                            .expect("there are more than 2^{32}-1 operations in basic block");
75
76                        // we include the opcode to differentiate between `Assert` and `U32assert2`
77                        bytes_to_hash.push(op.op_code());
78                        // we include the operation index to distinguish between basic blocks that
79                        // would have the same assert instructions, but in a different order
80                        bytes_to_hash.extend(op_idx.to_le_bytes());
81                        let inner_value = u64::from(*inner_value);
82                        bytes_to_hash.extend(inner_value.to_le_bytes());
83                    }
84                }
85
86                if bytes_to_hash.is_empty() {
87                    Ok(MastNodeFingerprint::new(node.digest()))
88                } else {
89                    let decorator_root = Blake3_256::hash(&bytes_to_hash);
90                    Ok(MastNodeFingerprint::with_decorator_root(node.digest(), decorator_root))
91                }
92            },
93            MastNode::Join(node) => fingerprint_from_parts(
94                forest,
95                hash_by_node_id,
96                node.before_enter(),
97                node.after_exit(),
98                &[node.first(), node.second()],
99                node.digest(),
100            ),
101            MastNode::Split(node) => fingerprint_from_parts(
102                forest,
103                hash_by_node_id,
104                node.before_enter(),
105                node.after_exit(),
106                &[node.on_true(), node.on_false()],
107                node.digest(),
108            ),
109            MastNode::Loop(node) => fingerprint_from_parts(
110                forest,
111                hash_by_node_id,
112                node.before_enter(),
113                node.after_exit(),
114                &[node.body()],
115                node.digest(),
116            ),
117            MastNode::Call(node) => fingerprint_from_parts(
118                forest,
119                hash_by_node_id,
120                node.before_enter(),
121                node.after_exit(),
122                &[node.callee()],
123                node.digest(),
124            ),
125            MastNode::Dyn(node) => fingerprint_from_parts(
126                forest,
127                hash_by_node_id,
128                node.before_enter(),
129                node.after_exit(),
130                &[],
131                node.digest(),
132            ),
133            MastNode::External(node) => fingerprint_from_parts(
134                forest,
135                hash_by_node_id,
136                node.before_enter(),
137                node.after_exit(),
138                &[],
139                node.digest(),
140            ),
141        }
142    }
143}
144
145// ------------------------------------------------------------------------------------------------
146/// Accessors
147impl MastNodeFingerprint {
148    pub fn mast_root(&self) -> &Word {
149        &self.mast_root
150    }
151}
152
153fn fingerprint_from_parts(
154    forest: &MastForest,
155    hash_by_node_id: &BTreeMap<MastNodeId, MastNodeFingerprint>,
156    before_enter_ids: &[DecoratorId],
157    after_exit_ids: &[DecoratorId],
158    children_ids: &[MastNodeId],
159    node_digest: Word,
160) -> Result<MastNodeFingerprint, MastForestError> {
161    let pre_decorator_hash_bytes =
162        before_enter_ids.iter().flat_map(|&id| forest[id].fingerprint().as_bytes());
163    let post_decorator_hash_bytes =
164        after_exit_ids.iter().flat_map(|&id| forest[id].fingerprint().as_bytes());
165
166    let children_decorator_roots = children_ids
167        .iter()
168        .filter_map(|child_id| {
169            hash_by_node_id
170                .get(child_id)
171                .ok_or(MastForestError::ChildFingerprintMissing(*child_id))
172                .map(|child_fingerprint| child_fingerprint.decorator_root)
173                .transpose()
174        })
175        .collect::<Result<Vec<DecoratorFingerprint>, MastForestError>>()?;
176
177    // Reminder: the `MastNodeFingerprint`'s decorator root will be `None` if and only if there are
178    // no decorators attached to the node, and all children have no decorator roots (meaning
179    // that there are no decorators in all the descendants).
180    if pre_decorator_hash_bytes.clone().next().is_none()
181        && post_decorator_hash_bytes.clone().next().is_none()
182        && children_decorator_roots.is_empty()
183    {
184        Ok(MastNodeFingerprint::new(node_digest))
185    } else {
186        let decorator_bytes_to_hash: Vec<u8> = pre_decorator_hash_bytes
187            .chain(post_decorator_hash_bytes)
188            .chain(
189                children_decorator_roots
190                    .into_iter()
191                    .flat_map(|decorator_root| decorator_root.as_bytes()),
192            )
193            .collect();
194
195        let decorator_root = Blake3_256::hash(&decorator_bytes_to_hash);
196        Ok(MastNodeFingerprint::with_decorator_root(node_digest, decorator_root))
197    }
198}
miden_core/mast/node_fingerprint.rs

miden_core/mast/
node_fingerprint.rs
