miden_core/
program.rs

1use alloc::{sync::Arc, vec::Vec};
2use core::fmt;
3
4use miden_crypto::{Felt, WORD_SIZE, Word};
5use winter_math::FieldElement;
6use winter_utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
7
8use super::Kernel;
9use crate::{
10    AdviceMap,
11    mast::{MastForest, MastNode, MastNodeId},
12    utils::ToElements,
13};
14
15// PROGRAM
16// ===============================================================================================
17
18/// An executable program for Miden VM.
19///
20/// A program consists of a MAST forest, an entrypoint defining the MAST node at which the program
21/// execution begins, and a definition of the kernel against which the program must be executed
22/// (the kernel can be an empty kernel).
23#[derive(Clone, Debug, PartialEq, Eq)]
24pub struct Program {
25    mast_forest: Arc<MastForest>,
26    /// The "entrypoint" is the node where execution of the program begins.
27    entrypoint: MastNodeId,
28    kernel: Kernel,
29}
30
31/// Constructors
32impl Program {
33    /// Construct a new [`Program`] from the given MAST forest and entrypoint. The kernel is assumed
34    /// to be empty.
35    ///
36    /// # Panics:
37    /// - if `mast_forest` doesn't contain the specified entrypoint.
38    /// - if the specified entrypoint is not a procedure root in the `mast_forest`.
39    pub fn new(mast_forest: Arc<MastForest>, entrypoint: MastNodeId) -> Self {
40        Self::with_kernel(mast_forest, entrypoint, Kernel::default())
41    }
42
43    /// Construct a new [`Program`] from the given MAST forest, entrypoint, and kernel.
44    ///
45    /// # Panics:
46    /// - if `mast_forest` doesn't contain the specified entrypoint.
47    /// - if the specified entrypoint is not a procedure root in the `mast_forest`.
48    pub fn with_kernel(
49        mast_forest: Arc<MastForest>,
50        entrypoint: MastNodeId,
51        kernel: Kernel,
52    ) -> Self {
53        assert!(mast_forest.get_node_by_id(entrypoint).is_some(), "invalid entrypoint");
54        assert!(mast_forest.is_procedure_root(entrypoint), "entrypoint not a procedure");
55
56        Self { mast_forest, entrypoint, kernel }
57    }
58
59    /// Produces a new program with the existing [`MastForest`] and where all key/values in the
60    /// provided advice map are added to the internal advice map.
61    pub fn with_advice_map(self, advice_map: AdviceMap) -> Self {
62        let mut mast_forest = (*self.mast_forest).clone();
63        mast_forest.advice_map_mut().extend(advice_map);
64        Self {
65            mast_forest: Arc::new(mast_forest),
66            ..self
67        }
68    }
69}
70
71// ------------------------------------------------------------------------------------------------
72/// Public accessors
73impl Program {
74    /// Returns the hash of the program's entrypoint.
75    ///
76    /// Equivalently, returns the hash of the root of the entrypoint procedure.
77    pub fn hash(&self) -> Word {
78        self.mast_forest[self.entrypoint].digest()
79    }
80
81    /// Returns the entrypoint associated with this program.
82    pub fn entrypoint(&self) -> MastNodeId {
83        self.entrypoint
84    }
85
86    /// Returns a reference to the underlying [`MastForest`].
87    pub fn mast_forest(&self) -> &Arc<MastForest> {
88        &self.mast_forest
89    }
90
91    /// Returns the kernel associated with this program.
92    pub fn kernel(&self) -> &Kernel {
93        &self.kernel
94    }
95
96    /// Returns the [`MastNode`] associated with the provided [`MastNodeId`] if valid, or else
97    /// `None`.
98    ///
99    /// This is the fallible version of indexing (e.g. `program[node_id]`).
100    #[inline(always)]
101    pub fn get_node_by_id(&self, node_id: MastNodeId) -> Option<&MastNode> {
102        self.mast_forest.get_node_by_id(node_id)
103    }
104
105    /// Returns the [`MastNodeId`] of the procedure root associated with a given digest, if any.
106    #[inline(always)]
107    pub fn find_procedure_root(&self, digest: Word) -> Option<MastNodeId> {
108        self.mast_forest.find_procedure_root(digest)
109    }
110
111    /// Returns the number of procedures in this program.
112    pub fn num_procedures(&self) -> u32 {
113        self.mast_forest.num_procedures()
114    }
115}
116
117// ------------------------------------------------------------------------------------------------
118/// Serialization
119#[cfg(feature = "std")]
120impl Program {
121    /// Writes this [Program] to the provided file path.
122    pub fn write_to_file<P>(&self, path: P) -> std::io::Result<()>
123    where
124        P: AsRef<std::path::Path>,
125    {
126        let path = path.as_ref();
127        if let Some(dir) = path.parent() {
128            std::fs::create_dir_all(dir)?;
129        }
130
131        // NOTE: We're protecting against unwinds here due to i/o errors that will get turned into
132        // panics if writing to the underlying file fails. This is because ByteWriter does not have
133        // fallible APIs, thus WriteAdapter has to panic if writes fail. This could be fixed, but
134        // that has to happen upstream in winterfell
135        std::panic::catch_unwind(|| match std::fs::File::create(path) {
136            Ok(ref mut file) => {
137                self.write_into(file);
138                Ok(())
139            },
140            Err(err) => Err(err),
141        })
142        .map_err(|p| {
143            match p.downcast::<std::io::Error>() {
144                // SAFETY: It is guaranteed to be safe to read Box<std::io::Error>
145                Ok(err) => unsafe { core::ptr::read(&*err) },
146                // Propagate unknown panics
147                Err(err) => std::panic::resume_unwind(err),
148            }
149        })?
150    }
151}
152
153impl Serializable for Program {
154    fn write_into<W: ByteWriter>(&self, target: &mut W) {
155        self.mast_forest.write_into(target);
156        self.kernel.write_into(target);
157        target.write_u32(self.entrypoint.as_u32());
158    }
159}
160
161impl Deserializable for Program {
162    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
163        let mast_forest = Arc::new(source.read()?);
164        let kernel = source.read()?;
165        let entrypoint = MastNodeId::from_u32_safe(source.read_u32()?, &mast_forest)?;
166
167        if !mast_forest.is_procedure_root(entrypoint) {
168            return Err(DeserializationError::InvalidValue(format!(
169                "entrypoint {entrypoint} is not a procedure"
170            )));
171        }
172
173        Ok(Self::with_kernel(mast_forest, entrypoint, kernel))
174    }
175}
176
177// ------------------------------------------------------------------------------------------------
178// Pretty-printing
179
180impl crate::prettier::PrettyPrint for Program {
181    fn render(&self) -> crate::prettier::Document {
182        use crate::prettier::*;
183        let entrypoint = self.mast_forest[self.entrypoint()].to_pretty_print(&self.mast_forest);
184
185        indent(4, const_text("begin") + nl() + entrypoint.render()) + nl() + const_text("end")
186    }
187}
188
189impl fmt::Display for Program {
190    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
191        use crate::prettier::PrettyPrint;
192        self.pretty_print(f)
193    }
194}
195
196// PROGRAM INFO
197// ===============================================================================================
198
199/// A program information set consisting of its MAST root and set of kernel procedure roots used
200/// for its compilation.
201///
202/// This will be used as public inputs of the proof so we bind its verification to the kernel and
203/// root used to execute the program. This way, we extend the correctness of the proof to the
204/// security guarantees provided by the kernel. We also allow the user to easily prove the
205/// membership of a given kernel procedure for a given proof, without compromising its
206/// zero-knowledge properties.
207#[derive(Debug, Clone, Default, PartialEq, Eq)]
208pub struct ProgramInfo {
209    program_hash: Word,
210    kernel: Kernel,
211}
212
213impl ProgramInfo {
214    /// Creates a new instance of a program info.
215    pub const fn new(program_hash: Word, kernel: Kernel) -> Self {
216        Self { program_hash, kernel }
217    }
218
219    /// Returns the program hash computed from its code block root.
220    pub const fn program_hash(&self) -> &Word {
221        &self.program_hash
222    }
223
224    /// Returns the program kernel used during the compilation.
225    pub const fn kernel(&self) -> &Kernel {
226        &self.kernel
227    }
228
229    /// Returns the list of procedures of the kernel used during the compilation.
230    pub fn kernel_procedures(&self) -> &[Word] {
231        self.kernel.proc_hashes()
232    }
233}
234
235impl From<Program> for ProgramInfo {
236    fn from(program: Program) -> Self {
237        let program_hash = program.hash();
238        let kernel = program.kernel().clone();
239
240        Self { program_hash, kernel }
241    }
242}
243
244// ------------------------------------------------------------------------------------------------
245// Serialization
246
247impl Serializable for ProgramInfo {
248    fn write_into<W: ByteWriter>(&self, target: &mut W) {
249        self.program_hash.write_into(target);
250        self.kernel.write_into(target);
251    }
252}
253
254impl Deserializable for ProgramInfo {
255    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
256        let program_hash = source.read()?;
257        let kernel = source.read()?;
258        Ok(Self { program_hash, kernel })
259    }
260}
261
262// ------------------------------------------------------------------------------------------------
263// ToElements implementation
264
265impl ToElements for ProgramInfo {
266    fn to_elements(&self) -> Vec<Felt> {
267        let num_kernel_proc_elements = self.kernel.proc_hashes().len() * WORD_SIZE;
268        let mut result = Vec::with_capacity(2 * WORD_SIZE + num_kernel_proc_elements);
269
270        // append program hash elements where we pad with zero so as to make the fixed length
271        // public inputs section of the public inputs of length a multiple of 8 i.e., double-word
272        // aligned
273        result.extend_from_slice(self.program_hash.as_elements());
274        result.extend_from_slice(&[Felt::ZERO; 4]);
275
276        // append kernel procedure hash elements
277        // we reverse the digests in order to make reducing them using auxiliary randomness easier
278        // we also pad them to the next multiple of 8
279        for proc_hash in self.kernel.proc_hashes() {
280            let mut proc_hash_elements = proc_hash.as_elements().to_vec();
281            pad_next_mul_8(&mut proc_hash_elements);
282            proc_hash_elements.reverse();
283            result.extend_from_slice(&proc_hash_elements);
284        }
285        result
286    }
287}
288
289// HELPER
290// ===============================================================================================
291
292/// Pads a vector of field elements using zeros to the next multiple of 8.
293fn pad_next_mul_8(input: &mut Vec<Felt>) {
294    let output_len = input.len().next_multiple_of(8);
295    input.resize(output_len, Felt::ZERO);
296}
miden_core/program.rs

miden_core/
program.rs
