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                        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) -> &RpoDigest {
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: RpoDigest,
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
