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

miden_core/mast/
node_fingerprint.rs
