miden_core/mast/node/
external.rs

1use alloc::{boxed::Box, vec::Vec};
2use core::fmt;
3
4use miden_formatting::{
5    hex::ToHex,
6    prettier::{Document, PrettyPrint, const_text, text},
7};
8
9use super::{MastForestContributor, MastNodeContext, MastNodeExt};
10use crate::{
11    Felt, Word,
12    mast::{MastForest, MastForestError, MastNodeId},
13    utils::LookupByIdx,
14};
15
16// EXTERNAL NODE
17// ================================================================================================
18
19/// Node for referencing procedures not present in a given [`MastForest`] (hence "external").
20///
21/// External nodes can be used to verify the integrity of a program's hash while keeping parts of
22/// the program secret. They also allow a program to refer to a well-known procedure that was not
23/// compiled with the program (e.g. a procedure in the core library).
24///
25/// The hash of an external node is the hash of the procedure it represents, such that an external
26/// node can be swapped with the actual subtree that it represents without changing the MAST root.
27#[derive(Clone, Debug, PartialEq, Eq)]
28pub struct ExternalNode {
29    digest: Word,
30}
31
32// PRETTY PRINTING
33// ================================================================================================
34
35impl ExternalNode {
36    pub(super) fn to_display<'a>(&'a self, _mast_forest: &'a MastForest) -> impl fmt::Display + 'a {
37        self.clone()
38    }
39
40    pub(super) fn to_pretty_print<'a>(
41        &'a self,
42        _mast_forest: &'a MastForest,
43    ) -> impl PrettyPrint + 'a {
44        self.clone()
45    }
46}
47
48impl PrettyPrint for ExternalNode {
49    fn render(&self) -> Document {
50        const_text("external") + const_text(".") + text(self.digest.as_bytes().to_hex_with_prefix())
51    }
52}
53
54impl fmt::Display for ExternalNode {
55    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
56        use crate::prettier::PrettyPrint;
57        self.pretty_print(f)
58    }
59}
60
61// MAST NODE TRAIT IMPLEMENTATION
62// ================================================================================================
63
64impl MastNodeExt for ExternalNode {
65    /// Returns the commitment to the MAST node referenced by this external node.
66    ///
67    /// The hash of an external node is the hash of the procedure it represents, such that an
68    /// external node can be swapped with the actual subtree that it represents without changing
69    /// the MAST root.
70    fn digest(&self) -> Word {
71        self.digest
72    }
73
74    fn to_display<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn fmt::Display + 'a> {
75        Box::new(ExternalNode::to_display(self, mast_forest))
76    }
77
78    fn to_pretty_print<'a>(&'a self, mast_forest: &'a MastForest) -> Box<dyn PrettyPrint + 'a> {
79        Box::new(ExternalNode::to_pretty_print(self, mast_forest))
80    }
81
82    fn has_children(&self) -> bool {
83        false
84    }
85
86    fn append_children_to(&self, _target: &mut Vec<MastNodeId>) {
87        // No children for external nodes
88    }
89
90    fn for_each_child<F>(&self, _f: F)
91    where
92        F: FnMut(MastNodeId),
93    {
94        // ExternalNode has no children
95    }
96
97    fn domain(&self) -> Felt {
98        panic!("Can't fetch domain for an `External` node.")
99    }
100
101    type Builder = ExternalNodeBuilder;
102
103    fn to_builder(self, _forest: &MastForest) -> Self::Builder {
104        ExternalNodeBuilder::new(self.digest)
105    }
106}
107
108// ------------------------------------------------------------------------------------------------
109/// Builder for creating [`ExternalNode`] instances.
110#[derive(Debug)]
111pub struct ExternalNodeBuilder {
112    digest: Word,
113}
114
115impl ExternalNodeBuilder {
116    /// Creates a new builder for an ExternalNode with the specified procedure hash.
117    pub fn new(digest: Word) -> Self {
118        Self { digest }
119    }
120
121    /// Builds the ExternalNode.
122    pub fn build(self) -> ExternalNode {
123        ExternalNode { digest: self.digest }
124    }
125}
126
127#[cfg(any(test, feature = "arbitrary"))]
128impl ExternalNodeBuilder {
129    /// Adds this builder to a mutable forest for test and arbitrary data construction.
130    pub fn add_to_forest(self, forest: &mut MastForest) -> Result<MastNodeId, MastForestError> {
131        let node_id = forest
132            .nodes
133            .push(self.build().into())
134            .map_err(|_| MastForestError::TooManyNodes)?;
135        forest.commitment = forest.compute_mast_forest_commitment();
136        Ok(node_id)
137    }
138}
139
140impl MastForestContributor for ExternalNodeBuilder {
141    fn fingerprint_for_node(
142        &self,
143        _context: &impl MastNodeContext,
144        _hash_by_node_id: &impl LookupByIdx<MastNodeId, Word>,
145    ) -> Result<Word, MastForestError> {
146        Ok(self.digest)
147    }
148
149    fn remap_children(self, _remapping: &impl LookupByIdx<MastNodeId, MastNodeId>) -> Self {
150        // ExternalNode has no children to remap, so return self unchanged
151        self
152    }
153
154    fn with_digest(mut self, digest: Word) -> Self {
155        self.digest = digest;
156        self
157    }
158}
159
160#[cfg(any(test, feature = "arbitrary"))]
161impl proptest::prelude::Arbitrary for ExternalNodeBuilder {
162    type Parameters = ();
163    type Strategy = proptest::strategy::BoxedStrategy<Self>;
164
165    fn arbitrary_with(_params: Self::Parameters) -> Self::Strategy {
166        use proptest::prelude::*;
167
168        any::<[u64; 4]>()
169            .prop_map(|[a, b, c, d]| {
170                Word::new([
171                    Felt::new_unchecked(a),
172                    Felt::new_unchecked(b),
173                    Felt::new_unchecked(c),
174                    Felt::new_unchecked(d),
175                ])
176            })
177            .prop_map(Self::new)
178            .boxed()
179    }
180}
miden_core/mast/node/external.rs

miden_core/mast/node/
external.rs
