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