miden_core/program/
kernel.rs

1use alloc::{string::ToString, vec::Vec};
2
3use miden_crypto::Word;
4#[cfg(feature = "serde")]
5use serde::{Deserialize, Serialize};
6
7use crate::serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
8
9// KERNEL
10// ================================================================================================
11
12/// A list of exported kernel procedure hashes defining a VM kernel.
13///
14/// The internally-stored list always has a consistent order, regardless of the order of procedure
15/// list used to instantiate a kernel.
16#[derive(Debug, Clone, Default, PartialEq, Eq)]
17#[cfg_attr(feature = "serde", derive(Serialize))]
18#[cfg_attr(feature = "serde", serde(transparent))]
19#[cfg_attr(
20    all(feature = "arbitrary", test),
21    miden_test_serde_macros::serde_test(binary_serde(true))
22)]
23pub struct Kernel(Vec<Word>);
24
25impl Kernel {
26    /// The maximum number of procedures which can be exported from a Kernel.
27    pub const MAX_NUM_PROCEDURES: usize = u8::MAX as usize;
28
29    /// Returns a new [Kernel] instantiated with the specified procedure hashes.
30    ///
31    /// Hashes are canonicalized into a consistent internal order.
32    ///
33    /// # Errors
34    /// Returns an error if:
35    /// - `proc_hashes` contains duplicates.
36    /// - `proc_hashes.len()` exceeds [`MAX_NUM_PROCEDURES`](Self::MAX_NUM_PROCEDURES).
37    pub fn new(proc_hashes: &[Word]) -> Result<Self, KernelError> {
38        Self::from_hashes(proc_hashes.to_vec())
39    }
40
41    /// Returns a new [Kernel] from owned procedure hashes.
42    ///
43    /// Hashes are canonicalized into a consistent internal order.
44    ///
45    /// # Errors
46    /// Returns an error if:
47    /// - `hashes` contains duplicates.
48    /// - `hashes.len()` exceeds [`MAX_NUM_PROCEDURES`](Self::MAX_NUM_PROCEDURES).
49    pub fn from_hashes(mut hashes: Vec<Word>) -> Result<Self, KernelError> {
50        if hashes.len() > Self::MAX_NUM_PROCEDURES {
51            return Err(KernelError::TooManyProcedures(Self::MAX_NUM_PROCEDURES, hashes.len()));
52        }
53
54        // Canonical ordering is a separate kernel invariant (not just a dedup side effect), so
55        // we sort first and then validate uniqueness over the canonical representation.
56        hashes.sort_by_key(Word::as_bytes); // ensure consistent order
57        let duplicated = hashes.windows(2).any(|data| data[0] == data[1]);
58
59        if duplicated {
60            Err(KernelError::DuplicatedProcedures)
61        } else {
62            Ok(Self(hashes))
63        }
64    }
65
66    /// Creates a kernel from raw hashes without enforcing constructor invariants.
67    ///
68    /// This is only intended for tests that need intentionally malformed kernels.
69    #[cfg(test)]
70    pub(crate) fn from_hashes_unchecked(hashes: Vec<Word>) -> Self {
71        Self(hashes)
72    }
73
74    /// Returns true if this kernel does not contain any procedures.
75    pub fn is_empty(&self) -> bool {
76        self.0.is_empty()
77    }
78
79    /// Returns true if a procedure with the specified hash belongs to this kernel.
80    ///
81    /// Note: the kernel is constructed from exported kernel procedures only.
82    pub fn contains_proc(&self, proc_hash: Word) -> bool {
83        // Note: we can't use `binary_search()` here because the hashes were sorted using a
84        // different key that the `binary_search` algorithm uses.
85        self.0.contains(&proc_hash)
86    }
87
88    /// Returns a list of procedure hashes contained in this kernel.
89    pub fn proc_hashes(&self) -> &[Word] {
90        &self.0
91    }
92}
93
94// this is required by AIR as public inputs will be serialized with the proof
95impl Serializable for Kernel {
96    fn write_into<W: ByteWriter>(&self, target: &mut W) {
97        // expect is OK here because the number of procedures is enforced by the constructor
98        target.write_u8(self.0.len().try_into().expect("too many kernel procedures"));
99        target.write_many(&self.0)
100    }
101}
102
103impl Deserializable for Kernel {
104    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
105        let len = source.read_u8()? as usize;
106        let kernel = source.read_many_iter::<Word>(len)?.collect::<Result<_, _>>()?;
107        Self::from_hashes(kernel).map_err(|err| DeserializationError::InvalidValue(err.to_string()))
108    }
109}
110
111#[cfg(feature = "serde")]
112impl<'de> Deserialize<'de> for Kernel {
113    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
114    where
115        D: serde::Deserializer<'de>,
116    {
117        let kernel = Vec::<Word>::deserialize(deserializer)?;
118        Self::from_hashes(kernel).map_err(serde::de::Error::custom)
119    }
120}
121
122// KERNEL ERROR
123// ================================================================================================
124
125#[derive(Debug, Clone, PartialEq, Eq, thiserror::Error)]
126pub enum KernelError {
127    #[error("kernel cannot have duplicated procedures")]
128    DuplicatedProcedures,
129    #[error("kernel can have at most {0} procedures, received {1}")]
130    TooManyProcedures(usize, usize),
131}
132
133#[cfg(test)]
134mod tests {
135    use alloc::vec::Vec;
136
137    use super::Kernel;
138    use crate::{
139        Felt, Word,
140        serde::{ByteWriter, Deserializable, Serializable, SliceReader},
141    };
142
143    #[test]
144    fn kernel_read_from_rejects_duplicate_procedure_hashes() {
145        let a: Word = [
146            Felt::new_unchecked(1),
147            Felt::new_unchecked(2),
148            Felt::new_unchecked(3),
149            Felt::new_unchecked(4),
150        ]
151        .into();
152        let b: Word = [
153            Felt::new_unchecked(5),
154            Felt::new_unchecked(6),
155            Felt::new_unchecked(7),
156            Felt::new_unchecked(8),
157        ]
158        .into();
159
160        assert!(
161            Kernel::new(&[a, a]).is_err(),
162            "test precondition: Kernel::new must reject duplicates"
163        );
164
165        // Manually serialize a Kernel that contains duplicates. This cannot be constructed via
166        // `Kernel::new`, but it can be produced via the binary format.
167        let mut bytes = Vec::new();
168        bytes.write_u8(3);
169        b.write_into(&mut bytes);
170        a.write_into(&mut bytes);
171        a.write_into(&mut bytes);
172
173        let mut reader = SliceReader::new(&bytes);
174        let result = Kernel::read_from(&mut reader);
175
176        assert!(
177            result.is_err(),
178            "expected Kernel::read_from to reject duplicate procedure hashes"
179        );
180    }
181
182    #[cfg(feature = "serde")]
183    #[test]
184    fn kernel_serde_deserialisation_rejects_duplicate_procedure_hashes() {
185        let a: Word = [
186            Felt::new_unchecked(1),
187            Felt::new_unchecked(2),
188            Felt::new_unchecked(3),
189            Felt::new_unchecked(4),
190        ]
191        .into();
192
193        assert!(
194            Kernel::new(&[a, a]).is_err(),
195            "test precondition: Kernel::new must reject duplicates"
196        );
197
198        // Kernel deserialization should reject duplicates.
199        let json = serde_json::to_string(&vec![a, a]).unwrap();
200        let result: Result<Kernel, _> = serde_json::from_str(&json);
201        assert!(
202            result.is_err(),
203            "expected serde deserialization to reject duplicate procedure hashes"
204        );
205    }
206
207    #[cfg(feature = "serde")]
208    #[test]
209    fn kernel_serde_deserialisation_rejects_too_many_procedure_hashes() {
210        let proc_hashes: Vec<Word> = (0u64..=255)
211            .map(|n| {
212                [
213                    Felt::new_unchecked(n),
214                    Felt::new_unchecked(n + 1),
215                    Felt::new_unchecked(n + 2),
216                    Felt::new_unchecked(n + 3),
217                ]
218                .into()
219            })
220            .collect();
221
222        let json = serde_json::to_string(&proc_hashes).unwrap();
223        let result: Result<Kernel, _> = serde_json::from_str(&json);
224        assert!(
225            result.is_err(),
226            "expected serde deserialization to reject more than MAX_NUM_PROCEDURES hashes"
227        );
228    }
229}
miden_core/program/kernel.rs

miden_core/program/
kernel.rs
