miden_core/sys_events.rs
1use core::fmt;
2
3use crate::{EventId, EventName};
4
5// SYSTEM EVENTS
6// ================================================================================================
7
8/// Defines a set of actions which can be initiated from the VM to inject new data into the advice
9/// provider.
10///
11/// These actions can affect all 3 components of the advice provider: Merkle store, advice stack,
12/// and advice map.
13///
14/// All actions, except for `MerkleNodeMerge`, `Ext2Inv` and `UpdateMerkleNode` can be invoked
15/// directly from Miden assembly via dedicated instructions.
16///
17/// System event IDs are derived from blake3-hashing their names (prefixed with "sys::").
18///
19/// The enum variant order matches the indices in SYSTEM_EVENT_LOOKUP, allowing efficient const
20/// lookup via `to_event_id()`. The discriminants are implicitly 0, 1, 2, ... 15.
21#[derive(Copy, Clone, Debug, Eq, PartialEq)]
22#[repr(u8)]
23pub enum SystemEvent {
24 // MERKLE STORE EVENTS
25 // --------------------------------------------------------------------------------------------
26 /// Creates a new Merkle tree in the advice provider by combining Merkle trees with the
27 /// specified roots. The root of the new tree is defined as `Hash(LEFT_ROOT, RIGHT_ROOT)`.
28 ///
29 /// Inputs:
30 /// Operand stack: [RIGHT_ROOT, LEFT_ROOT, ...]
31 /// Merkle store: {RIGHT_ROOT, LEFT_ROOT}
32 ///
33 /// Outputs:
34 /// Operand stack: [RIGHT_ROOT, LEFT_ROOT, ...]
35 /// Merkle store: {RIGHT_ROOT, LEFT_ROOT, hash(LEFT_ROOT, RIGHT_ROOT)}
36 ///
37 /// After the operation, both the original trees and the new tree remains in the advice
38 /// provider (i.e., the input trees are not removed).
39 MerkleNodeMerge,
40
41 // ADVICE STACK SYSTEM EVENTS
42 // --------------------------------------------------------------------------------------------
43 /// Pushes a node of the Merkle tree specified by the values on the top of the operand stack
44 /// onto the advice stack.
45 ///
46 /// Inputs:
47 /// Operand stack: [depth, index, TREE_ROOT, ...]
48 /// Advice stack: [...]
49 /// Merkle store: {TREE_ROOT<-NODE}
50 ///
51 /// Outputs:
52 /// Operand stack: [depth, index, TREE_ROOT, ...]
53 /// Advice stack: [NODE, ...]
54 /// Merkle store: {TREE_ROOT<-NODE}
55 MerkleNodeToStack,
56
57 /// Pushes a list of field elements onto the advice stack. The list is looked up in the advice
58 /// map using the specified word from the operand stack as the key.
59 ///
60 /// Inputs:
61 /// Operand stack: [KEY, ...]
62 /// Advice stack: [...]
63 /// Advice map: {KEY: values}
64 ///
65 /// Outputs:
66 /// Operand stack: [KEY, ...]
67 /// Advice stack: [values, ...]
68 /// Advice map: {KEY: values}
69 MapValueToStack,
70
71 /// Pushes a list of field elements onto the advice stack, and then the number of elements
72 /// pushed. The list is looked up in the advice map using the specified word from the operand
73 /// stack as the key.
74 ///
75 /// Inputs:
76 /// Operand stack: [KEY, ...]
77 /// Advice stack: [...]
78 /// Advice map: {KEY: values}
79 ///
80 /// Outputs:
81 /// Operand stack: [KEY, ...]
82 /// Advice stack: [num_values, values, ...]
83 /// Advice map: {KEY: values}
84 MapValueToStackN,
85
86 /// Pushes a flag onto the advice stack whether advice map has an entry with specified key.
87 ///
88 /// If the advice map has the entry with the key equal to the key placed at the top of the
89 /// operand stack, `1` will be pushed to the advice stack and `0` otherwise.
90 ///
91 /// Inputs:
92 /// Operand stack: [KEY, ...]
93 /// Advice stack: [...]
94 ///
95 /// Outputs:
96 /// Operand stack: [KEY, ...]
97 /// Advice stack: [has_mapkey, ...]
98 HasMapKey,
99
100 /// Given an element in a quadratic extension field on the top of the stack (i.e., a0, b1),
101 /// computes its multiplicative inverse and push the result onto the advice stack.
102 ///
103 /// Inputs:
104 /// Operand stack: [a1, a0, ...]
105 /// Advice stack: [...]
106 ///
107 /// Outputs:
108 /// Operand stack: [a1, a0, ...]
109 /// Advice stack: [b0, b1...]
110 ///
111 /// Where (b0, b1) is the multiplicative inverse of the extension field element (a0, a1) at the
112 /// top of the stack.
113 Ext2Inv,
114
115 /// Pushes the number of the leading zeros of the top stack element onto the advice stack.
116 ///
117 /// Inputs:
118 /// Operand stack: [n, ...]
119 /// Advice stack: [...]
120 ///
121 /// Outputs:
122 /// Operand stack: [n, ...]
123 /// Advice stack: [leading_zeros, ...]
124 U32Clz,
125
126 /// Pushes the number of the trailing zeros of the top stack element onto the advice stack.
127 ///
128 /// Inputs:
129 /// Operand stack: [n, ...]
130 /// Advice stack: [...]
131 ///
132 /// Outputs:
133 /// Operand stack: [n, ...]
134 /// Advice stack: [trailing_zeros, ...]
135 U32Ctz,
136
137 /// Pushes the number of the leading ones of the top stack element onto the advice stack.
138 ///
139 /// Inputs:
140 /// Operand stack: [n, ...]
141 /// Advice stack: [...]
142 ///
143 /// Outputs:
144 /// Operand stack: [n, ...]
145 /// Advice stack: [leading_ones, ...]
146 U32Clo,
147
148 /// Pushes the number of the trailing ones of the top stack element onto the advice stack.
149 ///
150 /// Inputs:
151 /// Operand stack: [n, ...]
152 /// Advice stack: [...]
153 ///
154 /// Outputs:
155 /// Operand stack: [n, ...]
156 /// Advice stack: [trailing_ones, ...]
157 U32Cto,
158
159 /// Pushes the base 2 logarithm of the top stack element, rounded down.
160 /// Inputs:
161 /// Operand stack: [n, ...]
162 /// Advice stack: [...]
163 ///
164 /// Outputs:
165 /// Operand stack: [n, ...]
166 /// Advice stack: [ilog2(n), ...]
167 ILog2,
168
169 // ADVICE MAP SYSTEM EVENTS
170 // --------------------------------------------------------------------------------------------
171 /// Reads words from memory at the specified range and inserts them into the advice map under
172 /// the key `KEY` located at the top of the stack.
173 ///
174 /// Inputs:
175 /// Operand stack: [KEY, start_addr, end_addr, ...]
176 /// Advice map: {...}
177 ///
178 /// Outputs:
179 /// Operand stack: [KEY, start_addr, end_addr, ...]
180 /// Advice map: {KEY: values}
181 ///
182 /// Where `values` are the elements located in memory[start_addr..end_addr].
183 MemToMap,
184
185 /// Reads two word from the operand stack and inserts them into the advice map under the key
186 /// defined by the hash of these words.
187 ///
188 /// Inputs:
189 /// Operand stack: [B, A, ...]
190 /// Advice map: {...}
191 ///
192 /// Outputs:
193 /// Operand stack: [B, A, ...]
194 /// Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
195 ///
196 /// Where KEY is computed as hash(A || B, domain=0)
197 HdwordToMap,
198
199 /// Reads two words from the operand stack and inserts them into the advice map under the key
200 /// defined by the hash of these words (using `d` as the domain).
201 ///
202 /// Inputs:
203 /// Operand stack: [B, A, d, ...]
204 /// Advice map: {...}
205 ///
206 /// Outputs:
207 /// Operand stack: [B, A, d, ...]
208 /// Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
209 ///
210 /// Where KEY is computed as hash(A || B, d).
211 HdwordToMapWithDomain,
212
213 /// Reads four words from the operand stack and inserts them into the advice map under the key
214 /// defined by the hash of these words.
215 ///
216 /// Inputs:
217 /// Operand stack: [D, C, B, A, ...]
218 /// Advice map: {...}
219 ///
220 /// Outputs:
221 /// Operand stack: [D, C, B, A, ...]
222 /// Advice map: {KEY: [A', B', C', D'])}
223 ///
224 /// Where:
225 /// - KEY is the hash computed as hash(hash(hash(A || B) || C) || D) with domain=0.
226 /// - A' (and other words with `'`) is the A word with the reversed element order: A = [a3, a2,
227 /// a1, a0], A' = [a0, a1, a2, a3].
228 HqwordToMap,
229
230 /// Reads three words from the operand stack and inserts the top two words into the advice map
231 /// under the key defined by applying an RPO permutation to all three words.
232 ///
233 /// Inputs:
234 /// Operand stack: [B, A, C, ...]
235 /// Advice map: {...}
236 ///
237 /// Outputs:
238 /// Operand stack: [B, A, C, ...]
239 /// Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
240 ///
241 /// Where KEY is computed by extracting the digest elements from hperm([C, A, B]). For example,
242 /// if C is [0, d, 0, 0], KEY will be set as hash(A || B, d).
243 HpermToMap,
244}
245
246impl SystemEvent {
247 /// Attempts to convert an EventId into a SystemEvent by looking it up in the const table.
248 ///
249 /// Returns `Some(SystemEvent)` if the ID matches a known system event, `None` otherwise.
250 /// This uses a const lookup table with hardcoded EventIds, avoiding runtime hash computation.
251 pub const fn from_event_id(event_id: EventId) -> Option<Self> {
252 let lookup = Self::LOOKUP;
253 let mut i = 0;
254 while i < lookup.len() {
255 if lookup[i].id.as_u64() == event_id.as_u64() {
256 return Some(lookup[i].event);
257 }
258 i += 1;
259 }
260 None
261 }
262
263 /// Attempts to convert a name into a SystemEvent by looking it up in the const table.
264 ///
265 /// Returns `Some(SystemEvent)` if the name matches a known system event, `None` otherwise.
266 /// This uses const string comparison against the lookup table.
267 pub const fn from_name(name: &str) -> Option<Self> {
268 let lookup = Self::LOOKUP;
269 let mut i = 0;
270 while i < lookup.len() {
271 if str_eq(name, lookup[i].name) {
272 return Some(lookup[i].event);
273 }
274 i += 1;
275 }
276 None
277 }
278
279 /// Returns the human-readable name of this system event as an [`EventName`].
280 ///
281 /// System event names are prefixed with `sys::` to distinguish them from user-defined events.
282 pub const fn event_name(&self) -> EventName {
283 EventName::new(Self::LOOKUP[*self as usize].name)
284 }
285
286 /// Returns the [`EventId`] for this system event.
287 ///
288 /// The ID is looked up from the const LOOKUP table using the enum's discriminant
289 /// as the index. The discriminants are explicitly set to match the array indices.
290 pub const fn event_id(&self) -> EventId {
291 Self::LOOKUP[*self as usize].id
292 }
293
294 /// Returns an array of all system event variants.
295 pub const fn all() -> [Self; Self::COUNT] {
296 [
297 Self::MerkleNodeMerge,
298 Self::MerkleNodeToStack,
299 Self::MapValueToStack,
300 Self::MapValueToStackN,
301 Self::HasMapKey,
302 Self::Ext2Inv,
303 Self::U32Clz,
304 Self::U32Ctz,
305 Self::U32Clo,
306 Self::U32Cto,
307 Self::ILog2,
308 Self::MemToMap,
309 Self::HdwordToMap,
310 Self::HdwordToMapWithDomain,
311 Self::HqwordToMap,
312 Self::HpermToMap,
313 ]
314 }
315}
316
317impl From<SystemEvent> for EventName {
318 fn from(system_event: SystemEvent) -> Self {
319 system_event.event_name()
320 }
321}
322
323impl crate::prettier::PrettyPrint for SystemEvent {
324 fn render(&self) -> crate::prettier::Document {
325 crate::prettier::display(self)
326 }
327}
328
329impl fmt::Display for SystemEvent {
330 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
331 const PREFIX_LEN: usize = "sys::".len();
332
333 let (_prefix, rest) = Self::LOOKUP[*self as usize].name.split_at(PREFIX_LEN);
334 write!(f, "{rest}")
335 }
336}
337
338// LOOKUP TABLE
339// ================================================================================================
340
341/// An entry in the system event lookup table, containing all metadata for a system event.
342#[derive(Copy, Clone, Debug)]
343pub(crate) struct SystemEventEntry {
344 /// The unique event ID (hash of the name)
345 pub id: EventId,
346 /// The system event variant
347 pub event: SystemEvent,
348 /// The full event name string (e.g., "sys::merkle_node_merge")
349 pub name: &'static str,
350}
351
352impl SystemEvent {
353 /// The total number of system events.
354 pub const COUNT: usize = 16;
355
356 /// Lookup table mapping system events to their metadata.
357 ///
358 /// The enum variant order matches the indices in this table, allowing efficient const
359 /// lookup via array indexing using discriminants.
360 const LOOKUP: [SystemEventEntry; Self::COUNT] = [
361 SystemEventEntry {
362 id: EventId::from_u64(7243907139105902342),
363 event: SystemEvent::MerkleNodeMerge,
364 name: "sys::merkle_node_merge",
365 },
366 SystemEventEntry {
367 id: EventId::from_u64(6873007751276594108),
368 event: SystemEvent::MerkleNodeToStack,
369 name: "sys::merkle_node_to_stack",
370 },
371 SystemEventEntry {
372 id: EventId::from_u64(17843484659000820118),
373 event: SystemEvent::MapValueToStack,
374 name: "sys::map_value_to_stack",
375 },
376 SystemEventEntry {
377 id: EventId::from_u64(7354377147644073171),
378 event: SystemEvent::MapValueToStackN,
379 name: "sys::map_value_to_stack_n",
380 },
381 SystemEventEntry {
382 id: EventId::from_u64(5642583036089175977),
383 event: SystemEvent::HasMapKey,
384 name: "sys::has_map_key",
385 },
386 SystemEventEntry {
387 id: EventId::from_u64(9660728691489438960),
388 event: SystemEvent::Ext2Inv,
389 name: "sys::ext2_inv",
390 },
391 SystemEventEntry {
392 id: EventId::from_u64(1503707361178382932),
393 event: SystemEvent::U32Clz,
394 name: "sys::u32_clz",
395 },
396 SystemEventEntry {
397 id: EventId::from_u64(10656887096526143429),
398 event: SystemEvent::U32Ctz,
399 name: "sys::u32_ctz",
400 },
401 SystemEventEntry {
402 id: EventId::from_u64(12846584985739176048),
403 event: SystemEvent::U32Clo,
404 name: "sys::u32_clo",
405 },
406 SystemEventEntry {
407 id: EventId::from_u64(6773574803673468616),
408 event: SystemEvent::U32Cto,
409 name: "sys::u32_cto",
410 },
411 SystemEventEntry {
412 id: EventId::from_u64(7444351342957461231),
413 event: SystemEvent::ILog2,
414 name: "sys::ilog2",
415 },
416 SystemEventEntry {
417 id: EventId::from_u64(5768534446586058686),
418 event: SystemEvent::MemToMap,
419 name: "sys::mem_to_map",
420 },
421 SystemEventEntry {
422 id: EventId::from_u64(5988159172915333521),
423 event: SystemEvent::HdwordToMap,
424 name: "sys::hdword_to_map",
425 },
426 SystemEventEntry {
427 id: EventId::from_u64(6143777601072385586),
428 event: SystemEvent::HdwordToMapWithDomain,
429 name: "sys::hdword_to_map_with_domain",
430 },
431 SystemEventEntry {
432 id: EventId::from_u64(11723176702659679401),
433 event: SystemEvent::HqwordToMap,
434 name: "sys::hqword_to_map",
435 },
436 SystemEventEntry {
437 id: EventId::from_u64(6190830263511605775),
438 event: SystemEvent::HpermToMap,
439 name: "sys::hperm_to_map",
440 },
441 ];
442}
443
444// HELPERS
445// ================================================================================================
446
447/// Const-compatible string equality check.
448const fn str_eq(a: &str, b: &str) -> bool {
449 let a_bytes = a.as_bytes();
450 let b_bytes = b.as_bytes();
451
452 if a_bytes.len() != b_bytes.len() {
453 return false;
454 }
455
456 let mut i = 0;
457 while i < a_bytes.len() {
458 if a_bytes[i] != b_bytes[i] {
459 return false;
460 }
461 i += 1;
462 }
463 true
464}
465
466#[cfg(test)]
467mod test {
468 use super::*;
469
470 #[test]
471 fn test_system_events() {
472 // Comprehensive test verifying consistency between SystemEvent::all() and
473 // SystemEvent::LOOKUP. This ensures all() and LOOKUP are in sync, lookup table has
474 // correct IDs/names, and all variants are covered.
475
476 // Verify lengths match COUNT
477 assert_eq!(SystemEvent::all().len(), SystemEvent::COUNT);
478 assert_eq!(SystemEvent::LOOKUP.len(), SystemEvent::COUNT);
479
480 // Iterate through both all() and LOOKUP together, checking all invariants
481 for (i, (event, entry)) in
482 SystemEvent::all().iter().zip(SystemEvent::LOOKUP.iter()).enumerate()
483 {
484 // Verify LOOKUP entry matches the event at the same index
485 assert_eq!(
486 entry.event, *event,
487 "LOOKUP[{}].event ({:?}) doesn't match all()[{}] ({:?})",
488 i, entry.event, i, event
489 );
490
491 // Verify LOOKUP entry ID matches the computed ID
492 let computed_id = event.event_id();
493 assert_eq!(
494 entry.id,
495 computed_id,
496 "LOOKUP[{}].id is EventId::from_u64({}), but {:?}.to_event_id() returns EventId::from_u64({})",
497 i,
498 entry.id.as_u64(),
499 event,
500 computed_id.as_u64()
501 );
502
503 // Verify name has correct "sys::" prefix
504 assert!(
505 entry.name.starts_with("sys::"),
506 "SystemEvent name should start with 'sys::': {}",
507 entry.name
508 );
509
510 // Verify from_event_id lookup works
511 let looked_up =
512 SystemEvent::from_event_id(entry.id).expect("SystemEvent should be found by ID");
513 assert_eq!(looked_up, *event);
514
515 // Verify from_name lookup works
516 let looked_up_by_name =
517 SystemEvent::from_name(entry.name).expect("SystemEvent should be found by name");
518 assert_eq!(looked_up_by_name, *event);
519
520 // Verify EventName conversion works
521 let event_name = event.event_name();
522 assert_eq!(event_name.as_str(), entry.name);
523 assert!(SystemEvent::from_name(event_name.as_str()).is_some());
524 let event_name_from_into: EventName = (*event).into();
525 assert_eq!(event_name_from_into.as_str(), entry.name);
526 assert!(SystemEvent::from_name(event_name_from_into.as_str()).is_some());
527
528 // Exhaustive match to ensure compile-time error when adding new variants
529 match event {
530 SystemEvent::MerkleNodeMerge
531 | SystemEvent::MerkleNodeToStack
532 | SystemEvent::MapValueToStack
533 | SystemEvent::MapValueToStackN
534 | SystemEvent::HasMapKey
535 | SystemEvent::Ext2Inv
536 | SystemEvent::U32Clz
537 | SystemEvent::U32Ctz
538 | SystemEvent::U32Clo
539 | SystemEvent::U32Cto
540 | SystemEvent::ILog2
541 | SystemEvent::MemToMap
542 | SystemEvent::HdwordToMap
543 | SystemEvent::HdwordToMapWithDomain
544 | SystemEvent::HqwordToMap
545 | SystemEvent::HpermToMap => {},
546 }
547 }
548 }
549}