miden_core/program/
mod.rs

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

miden_core/program/
mod.rs
