miden_core/
program.rs

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

miden_core/
program.rs
