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

miden_core/program/
mod.rs
