miden_core/sys_events.rs
1use core::fmt;
2
3use crate::EventId;
4
5// SYSTEM EVENTS
6// ================================================================================================
7
8#[rustfmt::skip]
9mod constants {
10 pub const EVENT_MERKLE_NODE_MERGE: u8 = 0;
11 pub const EVENT_MERKLE_NODE_TO_STACK: u8 = 1;
12 pub const EVENT_MAP_VALUE_TO_STACK: u8 = 2;
13 pub const EVENT_MAP_VALUE_TO_STACK_N: u8 = 3;
14 pub const EVENT_HAS_MAP_KEY: u8 = 4;
15 pub const EVENT_EXT2_INV: u8 = 5;
16 pub const EVENT_U32_CLZ: u8 = 6;
17 pub const EVENT_U32_CTZ: u8 = 7;
18 pub const EVENT_U32_CLO: u8 = 8;
19 pub const EVENT_U32_CTO: u8 = 9;
20 pub const EVENT_ILOG2: u8 = 10;
21 pub const EVENT_MEM_TO_MAP: u8 = 11;
22 pub const EVENT_HDWORD_TO_MAP: u8 = 12;
23 pub const EVENT_HDWORD_TO_MAP_WITH_DOMAIN: u8 = 13;
24 pub const EVENT_HQWORD_TO_MAP: u8 = 14;
25 pub const EVENT_HPERM_TO_MAP: u8 = 15;
26}
27use constants::*;
28
29/// Defines a set of actions which can be initiated from the VM to inject new data into the advice
30/// provider.
31///
32/// These actions can affect all 3 components of the advice provider: Merkle store, advice stack,
33/// and advice map.
34///
35/// All actions, except for `MerkleNodeMerge`, `Ext2Inv` and `UpdateMerkleNode` can be invoked
36/// directly from Miden assembly via dedicated instructions.
37#[derive(Copy, Clone, Debug, Eq, PartialEq)]
38#[repr(u8)]
39pub enum SystemEvent {
40 // MERKLE STORE EVENTS
41 // --------------------------------------------------------------------------------------------
42 /// Creates a new Merkle tree in the advice provider by combining Merkle trees with the
43 /// specified roots. The root of the new tree is defined as `Hash(LEFT_ROOT, RIGHT_ROOT)`.
44 ///
45 /// Inputs:
46 /// Operand stack: [RIGHT_ROOT, LEFT_ROOT, ...]
47 /// Merkle store: {RIGHT_ROOT, LEFT_ROOT}
48 ///
49 /// Outputs:
50 /// Operand stack: [RIGHT_ROOT, LEFT_ROOT, ...]
51 /// Merkle store: {RIGHT_ROOT, LEFT_ROOT, hash(LEFT_ROOT, RIGHT_ROOT)}
52 ///
53 /// After the operation, both the original trees and the new tree remains in the advice
54 /// provider (i.e., the input trees are not removed).
55 MerkleNodeMerge = EVENT_MERKLE_NODE_MERGE,
56
57 // ADVICE STACK SYSTEM EVENTS
58 // --------------------------------------------------------------------------------------------
59 /// Pushes a node of the Merkle tree specified by the values on the top of the operand stack
60 /// onto the advice stack.
61 ///
62 /// Inputs:
63 /// Operand stack: [depth, index, TREE_ROOT, ...]
64 /// Advice stack: [...]
65 /// Merkle store: {TREE_ROOT<-NODE}
66 ///
67 /// Outputs:
68 /// Operand stack: [depth, index, TREE_ROOT, ...]
69 /// Advice stack: [NODE, ...]
70 /// Merkle store: {TREE_ROOT<-NODE}
71 MerkleNodeToStack = EVENT_MERKLE_NODE_TO_STACK,
72
73 /// Pushes a list of field elements onto the advice stack. The list is looked up in the advice
74 /// map using the specified word from the operand stack as the key.
75 ///
76 /// Inputs:
77 /// Operand stack: [KEY, ...]
78 /// Advice stack: [...]
79 /// Advice map: {KEY: values}
80 ///
81 /// Outputs:
82 /// Operand stack: [KEY, ...]
83 /// Advice stack: [values, ...]
84 /// Advice map: {KEY: values}
85 MapValueToStack = EVENT_MAP_VALUE_TO_STACK,
86
87 /// Pushes a list of field elements onto the advice stack, and then the number of elements
88 /// pushed. The list is looked up in the advice map using the specified word from the operand
89 /// stack as the key.
90 ///
91 /// Inputs:
92 /// Operand stack: [KEY, ...]
93 /// Advice stack: [...]
94 /// Advice map: {KEY: values}
95 ///
96 /// Outputs:
97 /// Operand stack: [KEY, ...]
98 /// Advice stack: [num_values, values, ...]
99 /// Advice map: {KEY: values}
100 MapValueToStackN = EVENT_MAP_VALUE_TO_STACK_N,
101
102 /// Pushes a flag onto the advice stack whether advice map has an entry with specified key.
103 ///
104 /// If the advice map has the entry with the key equal to the key placed at the top of the
105 /// operand stack, `1` will be pushed to the advice stack and `0` otherwise.
106 ///
107 /// Inputs:
108 /// Operand stack: [KEY, ...]
109 /// Advice stack: [...]
110 ///
111 /// Outputs:
112 /// Operand stack: [KEY, ...]
113 /// Advice stack: [has_mapkey, ...]
114 HasMapKey = EVENT_HAS_MAP_KEY,
115
116 /// Given an element in a quadratic extension field on the top of the stack (i.e., a0, b1),
117 /// computes its multiplicative inverse and push the result onto the advice stack.
118 ///
119 /// Inputs:
120 /// Operand stack: [a1, a0, ...]
121 /// Advice stack: [...]
122 ///
123 /// Outputs:
124 /// Operand stack: [a1, a0, ...]
125 /// Advice stack: [b0, b1...]
126 ///
127 /// Where (b0, b1) is the multiplicative inverse of the extension field element (a0, a1) at the
128 /// top of the stack.
129 Ext2Inv = EVENT_EXT2_INV,
130
131 /// Pushes the number of the leading zeros of the top stack element onto the advice stack.
132 ///
133 /// Inputs:
134 /// Operand stack: [n, ...]
135 /// Advice stack: [...]
136 ///
137 /// Outputs:
138 /// Operand stack: [n, ...]
139 /// Advice stack: [leading_zeros, ...]
140 U32Clz = EVENT_U32_CLZ,
141
142 /// Pushes the number of the trailing zeros of the top stack element onto the advice stack.
143 ///
144 /// Inputs:
145 /// Operand stack: [n, ...]
146 /// Advice stack: [...]
147 ///
148 /// Outputs:
149 /// Operand stack: [n, ...]
150 /// Advice stack: [trailing_zeros, ...]
151 U32Ctz = EVENT_U32_CTZ,
152
153 /// Pushes the number of the leading ones of the top stack element onto the advice stack.
154 ///
155 /// Inputs:
156 /// Operand stack: [n, ...]
157 /// Advice stack: [...]
158 ///
159 /// Outputs:
160 /// Operand stack: [n, ...]
161 /// Advice stack: [leading_ones, ...]
162 U32Clo = EVENT_U32_CLO,
163
164 /// Pushes the number of the trailing ones of the top stack element onto the advice stack.
165 ///
166 /// Inputs:
167 /// Operand stack: [n, ...]
168 /// Advice stack: [...]
169 ///
170 /// Outputs:
171 /// Operand stack: [n, ...]
172 /// Advice stack: [trailing_ones, ...]
173 U32Cto = EVENT_U32_CTO,
174
175 /// Pushes the base 2 logarithm of the top stack element, rounded down.
176 /// Inputs:
177 /// Operand stack: [n, ...]
178 /// Advice stack: [...]
179 ///
180 /// Outputs:
181 /// Operand stack: [n, ...]
182 /// Advice stack: [ilog2(n), ...]
183 ILog2 = EVENT_ILOG2,
184
185 // ADVICE MAP SYSTEM EVENTS
186 // --------------------------------------------------------------------------------------------
187 /// Reads words from memory at the specified range and inserts them into the advice map under
188 /// the key `KEY` located at the top of the stack.
189 ///
190 /// Inputs:
191 /// Operand stack: [KEY, start_addr, end_addr, ...]
192 /// Advice map: {...}
193 ///
194 /// Outputs:
195 /// Operand stack: [KEY, start_addr, end_addr, ...]
196 /// Advice map: {KEY: values}
197 ///
198 /// Where `values` are the elements located in memory[start_addr..end_addr].
199 MemToMap = EVENT_MEM_TO_MAP,
200
201 /// Reads two word from the operand stack and inserts them into the advice map under the key
202 /// defined by the hash of these words.
203 ///
204 /// Inputs:
205 /// Operand stack: [B, A, ...]
206 /// Advice map: {...}
207 ///
208 /// Outputs:
209 /// Operand stack: [B, A, ...]
210 /// Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
211 ///
212 /// Where KEY is computed as hash(A || B, domain=0)
213 HdwordToMap = EVENT_HDWORD_TO_MAP,
214
215 /// Reads two words from the operand stack and inserts them into the advice map under the key
216 /// defined by the hash of these words (using `d` as the domain).
217 ///
218 /// Inputs:
219 /// Operand stack: [B, A, d, ...]
220 /// Advice map: {...}
221 ///
222 /// Outputs:
223 /// Operand stack: [B, A, d, ...]
224 /// Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
225 ///
226 /// Where KEY is computed as hash(A || B, d).
227 HdwordToMapWithDomain = EVENT_HDWORD_TO_MAP_WITH_DOMAIN,
228
229 /// Reads four words from the operand stack and inserts them into the advice map under the key
230 /// defined by the hash of these words.
231 ///
232 /// Inputs:
233 /// Operand stack: [D, C, B, A, ...]
234 /// Advice map: {...}
235 ///
236 /// Outputs:
237 /// Operand stack: [D, C, B, A, ...]
238 /// Advice map: {KEY: [A', B', C', D'])}
239 ///
240 /// Where:
241 /// - KEY is the hash computed as hash(hash(hash(A || B) || C) || D) with domain=0.
242 /// - A' (and other words with `'`) is the A word with the reversed element order: A = [a3, a2,
243 /// a1, a0], A' = [a0, a1, a2, a3].
244 HqwordToMap = EVENT_HQWORD_TO_MAP,
245
246 /// Reads three words from the operand stack and inserts the top two words into the advice map
247 /// under the key defined by applying an RPO permutation to all three words.
248 ///
249 /// Inputs:
250 /// Operand stack: [B, A, C, ...]
251 /// Advice map: {...}
252 ///
253 /// Outputs:
254 /// Operand stack: [B, A, C, ...]
255 /// Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
256 ///
257 /// Where KEY is computed by extracting the digest elements from hperm([C, A, B]). For example,
258 /// if C is [0, d, 0, 0], KEY will be set as hash(A || B, d).
259 HpermToMap = EVENT_HPERM_TO_MAP,
260}
261
262impl TryFrom<EventId> for SystemEvent {
263 type Error = EventId;
264
265 fn try_from(event_id: EventId) -> Result<Self, Self::Error> {
266 let value: u8 = event_id.as_felt().as_int().try_into().map_err(|_| event_id)?;
267
268 match value {
269 EVENT_MERKLE_NODE_MERGE => Ok(SystemEvent::MerkleNodeMerge),
270 EVENT_MERKLE_NODE_TO_STACK => Ok(SystemEvent::MerkleNodeToStack),
271 EVENT_MAP_VALUE_TO_STACK => Ok(SystemEvent::MapValueToStack),
272 EVENT_MAP_VALUE_TO_STACK_N => Ok(SystemEvent::MapValueToStackN),
273 EVENT_HAS_MAP_KEY => Ok(SystemEvent::HasMapKey),
274 EVENT_EXT2_INV => Ok(SystemEvent::Ext2Inv),
275 EVENT_U32_CLZ => Ok(SystemEvent::U32Clz),
276 EVENT_U32_CTZ => Ok(SystemEvent::U32Ctz),
277 EVENT_U32_CLO => Ok(SystemEvent::U32Clo),
278 EVENT_U32_CTO => Ok(SystemEvent::U32Cto),
279 EVENT_ILOG2 => Ok(SystemEvent::ILog2),
280 EVENT_MEM_TO_MAP => Ok(SystemEvent::MemToMap),
281 EVENT_HDWORD_TO_MAP => Ok(SystemEvent::HdwordToMap),
282 EVENT_HDWORD_TO_MAP_WITH_DOMAIN => Ok(SystemEvent::HdwordToMapWithDomain),
283 EVENT_HQWORD_TO_MAP => Ok(SystemEvent::HqwordToMap),
284 EVENT_HPERM_TO_MAP => Ok(SystemEvent::HpermToMap),
285 _ => Err(event_id),
286 }
287 }
288}
289
290impl From<SystemEvent> for EventId {
291 fn from(system_event: SystemEvent) -> Self {
292 Self::from_u64(system_event as u64)
293 }
294}
295
296impl crate::prettier::PrettyPrint for SystemEvent {
297 fn render(&self) -> crate::prettier::Document {
298 crate::prettier::display(self)
299 }
300}
301
302impl fmt::Display for SystemEvent {
303 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
304 match self {
305 Self::MerkleNodeMerge => write!(f, "merkle_node_merge"),
306 Self::MerkleNodeToStack => write!(f, "merkle_node_to_stack"),
307 Self::MapValueToStack => write!(f, "map_value_to_stack"),
308 Self::MapValueToStackN => write!(f, "map_value_to_stack_with_len"),
309 Self::HasMapKey => write!(f, "has_key_in_map"),
310 Self::Ext2Inv => write!(f, "ext2_inv"),
311 Self::U32Clz => write!(f, "u32clz"),
312 Self::U32Ctz => write!(f, "u32ctz"),
313 Self::U32Clo => write!(f, "u32clo"),
314 Self::U32Cto => write!(f, "u32cto"),
315 Self::ILog2 => write!(f, "ilog2"),
316 Self::MemToMap => write!(f, "mem_to_map"),
317 Self::HdwordToMap => write!(f, "hdword_to_map"),
318 Self::HdwordToMapWithDomain => write!(f, "hdword_to_map_with_domain"),
319 Self::HqwordToMap => write!(f, "hqword_to_map"),
320 Self::HpermToMap => write!(f, "hperm_to_map"),
321 }
322 }
323}
324
325#[cfg(test)]
326mod test {
327 use super::*;
328
329 #[test]
330 fn test_try_from() {
331 /// Last variant of the `SystemEvent` enum, used to derive the number of cases.
332 const LAST_EVENT: SystemEvent = SystemEvent::HpermToMap;
333 let last_event_id = LAST_EVENT as u8;
334
335 // Check that the event IDs are contiguous
336 for id in 0..=last_event_id {
337 let event_id = EventId::from_u64(id as u64);
338 assert!(event_id.is_reserved());
339 let event = SystemEvent::try_from(event_id).unwrap();
340 assert_eq!(id, event as u8)
341 }
342
343 // Creating from an the next index results in an error.
344 let invalid_event_id = EventId::from_u64((last_event_id + 1) as u64);
345 SystemEvent::try_from(invalid_event_id).unwrap_err();
346
347 // This dummy match statement ensures a compile-time error is raised after adding a new
348 // SystemEvent variant. If so the following must also be done
349 // - create a new constant with the next available value
350 // - update try_from with the new constant
351 // - add a case to `fmt`
352 match LAST_EVENT {
353 SystemEvent::MerkleNodeMerge
354 | SystemEvent::MerkleNodeToStack
355 | SystemEvent::MapValueToStack
356 | SystemEvent::MapValueToStackN
357 | SystemEvent::HasMapKey
358 | SystemEvent::Ext2Inv
359 | SystemEvent::U32Clz
360 | SystemEvent::U32Ctz
361 | SystemEvent::U32Clo
362 | SystemEvent::U32Cto
363 | SystemEvent::ILog2
364 | SystemEvent::MemToMap
365 | SystemEvent::HdwordToMap
366 | SystemEvent::HdwordToMapWithDomain
367 | SystemEvent::HqwordToMap
368 | SystemEvent::HpermToMap => {},
369 };
370 }
371}