miden_core/program/
mod.rs

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

miden_core/program/
mod.rs
