miden_core/program/
kernel.rs

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

miden_core/program/
kernel.rs
