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

miden_core/program/
mod.rs
