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

miden_core/program/
kernel.rs
