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

miden_core/program/
mod.rs
