miden_core/program/
kernel.rs

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

miden_core/program/
kernel.rs
