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