miden_core/operations/mod.rs
1use core::fmt;
2
3use miden_crypto::field::PrimeField64;
4#[cfg(feature = "serde")]
5use serde::{Deserialize, Serialize};
6
7mod decorators;
8pub use decorators::{AssemblyOp, DebugOptions, Decorator, DecoratorList};
9pub use opcode_constants::*;
10
11use crate::{
12 Felt,
13 serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
14};
15
16// OPERATIONS OP CODES
17// ================================================================================================
18
19/// Opcode patterns have the following meanings:
20/// - 00xxxxx operations do not shift the stack; constraint degree can be up to 2.
21/// - 010xxxx operations shift the stack the left; constraint degree can be up to 2.
22/// - 011xxxx operations shift the stack to the right; constraint degree can be up to 2.
23/// - 100xxx-: operations consume 4 range checks; constraint degree can be up to 3. These are used
24/// to encode most u32 operations.
25/// - 101xxx-: operations where constraint degree can be up to 3. These include control flow
26/// operations and some other operations requiring high degree constraints.
27/// - 11xxx--: operations where constraint degree can be up to 5. These include control flow
28/// operations and some other operations requiring very high degree constraints.
29#[rustfmt::skip]
30mod opcode_constants {
31 pub const OPCODE_NOOP: u8 = 0b0000_0000;
32 pub const OPCODE_EQZ: u8 = 0b0000_0001;
33 pub const OPCODE_NEG: u8 = 0b0000_0010;
34 pub const OPCODE_INV: u8 = 0b0000_0011;
35 pub const OPCODE_INCR: u8 = 0b0000_0100;
36 pub const OPCODE_NOT: u8 = 0b0000_0101;
37 /* unused 0b0000_0110 */
38 pub const OPCODE_MLOAD: u8 = 0b0000_0111;
39 pub const OPCODE_SWAP: u8 = 0b0000_1000;
40 pub const OPCODE_CALLER: u8 = 0b0000_1001;
41 pub const OPCODE_MOVUP2: u8 = 0b0000_1010;
42 pub const OPCODE_MOVDN2: u8 = 0b0000_1011;
43 pub const OPCODE_MOVUP3: u8 = 0b0000_1100;
44 pub const OPCODE_MOVDN3: u8 = 0b0000_1101;
45 pub const OPCODE_ADVPOPW: u8 = 0b0000_1110;
46 pub const OPCODE_EXPACC: u8 = 0b0000_1111;
47
48 pub const OPCODE_MOVUP4: u8 = 0b0001_0000;
49 pub const OPCODE_MOVDN4: u8 = 0b0001_0001;
50 pub const OPCODE_MOVUP5: u8 = 0b0001_0010;
51 pub const OPCODE_MOVDN5: u8 = 0b0001_0011;
52 pub const OPCODE_MOVUP6: u8 = 0b0001_0100;
53 pub const OPCODE_MOVDN6: u8 = 0b0001_0101;
54 pub const OPCODE_MOVUP7: u8 = 0b0001_0110;
55 pub const OPCODE_MOVDN7: u8 = 0b0001_0111;
56 pub const OPCODE_SWAPW: u8 = 0b0001_1000;
57 pub const OPCODE_EXT2MUL: u8 = 0b0001_1001;
58 pub const OPCODE_MOVUP8: u8 = 0b0001_1010;
59 pub const OPCODE_MOVDN8: u8 = 0b0001_1011;
60 pub const OPCODE_SWAPW2: u8 = 0b0001_1100;
61 pub const OPCODE_SWAPW3: u8 = 0b0001_1101;
62 pub const OPCODE_SWAPDW: u8 = 0b0001_1110;
63 pub const OPCODE_EMIT: u8 = 0b0001_1111;
64
65 pub const OPCODE_ASSERT: u8 = 0b0010_0000;
66 pub const OPCODE_EQ: u8 = 0b0010_0001;
67 pub const OPCODE_ADD: u8 = 0b0010_0010;
68 pub const OPCODE_MUL: u8 = 0b0010_0011;
69 pub const OPCODE_AND: u8 = 0b0010_0100;
70 pub const OPCODE_OR: u8 = 0b0010_0101;
71 pub const OPCODE_U32AND: u8 = 0b0010_0110;
72 pub const OPCODE_U32XOR: u8 = 0b0010_0111;
73 pub const OPCODE_FRIE2F4: u8 = 0b0010_1000;
74 pub const OPCODE_DROP: u8 = 0b0010_1001;
75 pub const OPCODE_CSWAP: u8 = 0b0010_1010;
76 pub const OPCODE_CSWAPW: u8 = 0b0010_1011;
77 pub const OPCODE_MLOADW: u8 = 0b0010_1100;
78 pub const OPCODE_MSTORE: u8 = 0b0010_1101;
79 pub const OPCODE_MSTOREW: u8 = 0b0010_1110;
80 /* unused 0b0010_1111 */
81
82 pub const OPCODE_PAD: u8 = 0b0011_0000;
83 pub const OPCODE_DUP0: u8 = 0b0011_0001;
84 pub const OPCODE_DUP1: u8 = 0b0011_0010;
85 pub const OPCODE_DUP2: u8 = 0b0011_0011;
86 pub const OPCODE_DUP3: u8 = 0b0011_0100;
87 pub const OPCODE_DUP4: u8 = 0b0011_0101;
88 pub const OPCODE_DUP5: u8 = 0b0011_0110;
89 pub const OPCODE_DUP6: u8 = 0b0011_0111;
90 pub const OPCODE_DUP7: u8 = 0b0011_1000;
91 pub const OPCODE_DUP9: u8 = 0b0011_1001;
92 pub const OPCODE_DUP11: u8 = 0b0011_1010;
93 pub const OPCODE_DUP13: u8 = 0b0011_1011;
94 pub const OPCODE_DUP15: u8 = 0b0011_1100;
95 pub const OPCODE_ADVPOP: u8 = 0b0011_1101;
96 pub const OPCODE_SDEPTH: u8 = 0b0011_1110;
97 pub const OPCODE_CLK: u8 = 0b0011_1111;
98
99 pub const OPCODE_U32ADD: u8 = 0b0100_0000;
100 pub const OPCODE_U32SUB: u8 = 0b0100_0010;
101 pub const OPCODE_U32MUL: u8 = 0b0100_0100;
102 pub const OPCODE_U32DIV: u8 = 0b0100_0110;
103 pub const OPCODE_U32SPLIT: u8 = 0b0100_1000;
104 pub const OPCODE_U32ASSERT2: u8 = 0b0100_1010;
105 pub const OPCODE_U32ADD3: u8 = 0b0100_1100;
106 pub const OPCODE_U32MADD: u8 = 0b0100_1110;
107
108 pub const OPCODE_HPERM: u8 = 0b0101_0000;
109 pub const OPCODE_MPVERIFY: u8 = 0b0101_0001;
110 pub const OPCODE_PIPE: u8 = 0b0101_0010;
111 pub const OPCODE_MSTREAM: u8 = 0b0101_0011;
112 pub const OPCODE_SPLIT: u8 = 0b0101_0100;
113 pub const OPCODE_LOOP: u8 = 0b0101_0101;
114 pub const OPCODE_SPAN: u8 = 0b0101_0110;
115 pub const OPCODE_JOIN: u8 = 0b0101_0111;
116 pub const OPCODE_DYN: u8 = 0b0101_1000;
117 pub const OPCODE_HORNERBASE: u8 = 0b0101_1001;
118 pub const OPCODE_HORNEREXT: u8 = 0b0101_1010;
119 pub const OPCODE_PUSH: u8 = 0b0101_1011;
120 pub const OPCODE_DYNCALL: u8 = 0b0101_1100;
121 pub const OPCODE_EVALCIRCUIT: u8 = 0b0101_1101;
122 pub const OPCODE_LOGPRECOMPILE: u8 = 0b0101_1110;
123
124 pub const OPCODE_MRUPDATE: u8 = 0b0110_0000;
125 pub const OPCODE_CRYPTOSTREAM: u8 = 0b0110_0100;
126 pub const OPCODE_SYSCALL: u8 = 0b0110_1000;
127 pub const OPCODE_CALL: u8 = 0b0110_1100;
128 pub const OPCODE_END: u8 = 0b0111_0000;
129 pub const OPCODE_REPEAT: u8 = 0b0111_0100;
130 pub const OPCODE_RESPAN: u8 = 0b0111_1000;
131 pub const OPCODE_HALT: u8 = 0b0111_1100;
132}
133
134// OPERATIONS
135// ================================================================================================
136
137/// A set of native VM operations which take exactly one cycle to execute.
138#[derive(Copy, Clone, Debug, Eq, PartialEq)]
139#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
140#[repr(u8)]
141pub enum Operation {
142 // ----- system operations -------------------------------------------------------------------
143 /// Advances cycle counter, but does not change the state of user stack.
144 Noop = OPCODE_NOOP,
145
146 /// Pops the stack; if the popped value is not 1, execution fails.
147 ///
148 /// The internal value specifies an error code associated with the error in case when the
149 /// execution fails.
150 Assert(Felt) = OPCODE_ASSERT,
151
152 /// Pushes the current depth of the stack onto the stack.
153 SDepth = OPCODE_SDEPTH,
154
155 /// Overwrites the top four stack items with the hash of a function which initiated the current
156 /// SYSCALL. Thus, this operation can be executed only inside a SYSCALL code block.
157 Caller = OPCODE_CALLER,
158
159 /// Pushes the current value of the clock cycle onto the stack. This operation can be used to
160 /// measure the number of cycles it has taken to execute the program up to the current
161 /// instruction.
162 Clk = OPCODE_CLK,
163
164 /// Emits an event to the host.
165 ///
166 /// Semantics:
167 /// - Reads the event id from the top of the stack (as a `Felt`) without consuming it; the
168 /// caller is responsible for pushing and later dropping the id.
169 /// - User-defined events are conventionally derived from strings via
170 /// `hash_string_to_word(name)[0]` (Blake3-based) and may be emitted via immediate forms in
171 /// assembly (`emit.event("...")` or `emit.CONST` where `CONST=event("...")`).
172 /// - System events are still identified by specific 32-bit codes; the VM attempts to interpret
173 /// the stack `Felt` as `u32` to dispatch known system events, and otherwise forwards the
174 /// event to the host.
175 ///
176 /// This operation does not change the state of the user stack aside from reading the value.
177 Emit = OPCODE_EMIT,
178
179 // ----- flow control operations -------------------------------------------------------------
180 /// Marks the beginning of a join block.
181 Join = OPCODE_JOIN,
182
183 /// Marks the beginning of a split block.
184 Split = OPCODE_SPLIT,
185
186 /// Marks the beginning of a loop block.
187 Loop = OPCODE_LOOP,
188
189 /// Marks the beginning of a function call.
190 Call = OPCODE_CALL,
191
192 /// Marks the beginning of a dynamic code block, where the target is specified by the stack.
193 Dyn = OPCODE_DYN,
194
195 /// Marks the beginning of a dynamic function call, where the target is specified by the stack.
196 Dyncall = OPCODE_DYNCALL,
197
198 /// Marks the beginning of a kernel call.
199 SysCall = OPCODE_SYSCALL,
200
201 /// Marks the beginning of a span code block.
202 Span = OPCODE_SPAN,
203
204 /// Marks the end of a program block.
205 End = OPCODE_END,
206
207 /// Indicates that body of an executing loop should be executed again.
208 Repeat = OPCODE_REPEAT,
209
210 /// Starts processing a new operation batch.
211 Respan = OPCODE_RESPAN,
212
213 /// Indicates the end of the program. This is used primarily to pad the execution trace to
214 /// the required length. Once HALT operation is executed, no other operations can be executed
215 /// by the VM (HALT operation itself excepted).
216 Halt = OPCODE_HALT,
217
218 // ----- field operations --------------------------------------------------------------------
219 /// Pops two elements off the stack, adds them, and pushes the result back onto the stack.
220 Add = OPCODE_ADD,
221
222 /// Pops an element off the stack, negates it, and pushes the result back onto the stack.
223 Neg = OPCODE_NEG,
224
225 /// Pops two elements off the stack, multiplies them, and pushes the result back onto the
226 /// stack.
227 Mul = OPCODE_MUL,
228
229 /// Pops an element off the stack, computes its multiplicative inverse, and pushes the result
230 /// back onto the stack.
231 Inv = OPCODE_INV,
232
233 /// Pops an element off the stack, adds 1 to it, and pushes the result back onto the stack.
234 Incr = OPCODE_INCR,
235
236 /// Pops two elements off the stack, multiplies them, and pushes the result back onto the
237 /// stack.
238 ///
239 /// If either of the elements is greater than 1, execution fails. This operation is equivalent
240 /// to boolean AND.
241 And = OPCODE_AND,
242
243 /// Pops two elements off the stack and subtracts their product from their sum.
244 ///
245 /// If either of the elements is greater than 1, execution fails. This operation is equivalent
246 /// to boolean OR.
247 Or = OPCODE_OR,
248
249 /// Pops an element off the stack and subtracts it from 1.
250 ///
251 /// If the element is greater than one, the execution fails. This operation is equivalent to
252 /// boolean NOT.
253 Not = OPCODE_NOT,
254
255 /// Pops two elements off the stack and compares them. If the elements are equal, pushes 1
256 /// onto the stack, otherwise pushes 0 onto the stack.
257 Eq = OPCODE_EQ,
258
259 /// Pops an element off the stack and compares it to 0. If the element is 0, pushes 1 onto
260 /// the stack, otherwise pushes 0 onto the stack.
261 Eqz = OPCODE_EQZ,
262
263 /// Computes a single turn of exponent accumulation for the given inputs. This operation can be
264 /// be used to compute a single turn of power of a field element.
265 ///
266 /// The top 4 elements of the stack are expected to be arranged as follows (form the top):
267 /// - least significant bit of the exponent in the previous trace if there's an expacc call,
268 /// otherwise ZERO
269 /// - exponent of base number `a` for this turn
270 /// - accumulated power of base number `a` so far
271 /// - number which needs to be shifted to the right
272 ///
273 /// At the end of the operation, exponent is replaced with its square, current value of power
274 /// of base number `a` on exponent is incorporated into the accumulator and the number is
275 /// shifted to the right by one bit.
276 Expacc = OPCODE_EXPACC,
277
278 // ----- ext2 operations ---------------------------------------------------------------------
279 /// Computes the product of two elements in the extension field of degree 2 and pushes the
280 /// result back onto the stack as the third and fourth elements. Pushes 0 onto the stack as
281 /// the first and second elements.
282 ///
283 /// The extension field is defined as 𝔽ₚ\[x\]/(x² - x + 2), i.e. using the
284 /// irreducible quadratic polynomial x² - x + 2 over the base field.
285 Ext2Mul = OPCODE_EXT2MUL,
286
287 // ----- u32 operations ----------------------------------------------------------------------
288 /// Pops an element off the stack, splits it into upper and lower 32-bit values, and pushes
289 /// these values back onto the stack.
290 U32split = OPCODE_U32SPLIT,
291
292 /// Pops two elements off the stack, adds them, and splits the result into upper and lower
293 /// 32-bit values. Then pushes these values back onto the stack.
294 ///
295 /// If either of these elements is greater than or equal to 2^32, the result of this
296 /// operation is undefined.
297 U32add = OPCODE_U32ADD,
298
299 /// Pops two elements off the stack and checks if each of them represents a 32-bit value.
300 /// If both of them are, they are pushed back onto the stack, otherwise an error is returned.
301 ///
302 /// The internal value specifies an error code associated with the error in case when the
303 /// assertion fails.
304 U32assert2(Felt) = OPCODE_U32ASSERT2,
305
306 /// Pops three elements off the stack, adds them together, and splits the result into upper
307 /// and lower 32-bit values. Then pushes the result back onto the stack.
308 U32add3 = OPCODE_U32ADD3,
309
310 /// Pops two elements off the stack and subtracts the first element from the second. Then,
311 /// the result, together with a flag indicating whether subtraction underflowed is pushed
312 /// onto the stack.
313 ///
314 /// If their of the values is greater than or equal to 2^32, the result of this operation is
315 /// undefined.
316 U32sub = OPCODE_U32SUB,
317
318 /// Pops two elements off the stack, multiplies them, and splits the result into upper and
319 /// lower 32-bit values. Then pushes these values back onto the stack.
320 ///
321 /// If their of the values is greater than or equal to 2^32, the result of this operation is
322 /// undefined.
323 U32mul = OPCODE_U32MUL,
324
325 /// Pops two elements off the stack and multiplies them. Then pops the third element off the
326 /// stack, and adds it to the result. Finally, splits the result into upper and lower 32-bit
327 /// values, and pushes them onto the stack.
328 ///
329 /// If any of the three values is greater than or equal to 2^32, the result of this operation
330 /// is undefined.
331 U32madd = OPCODE_U32MADD,
332
333 /// Pops two elements off the stack and divides the second element by the first. Then pushes
334 /// the integer result of the division, together with the remainder, onto the stack.
335 ///
336 /// If their of the values is greater than or equal to 2^32, the result of this operation is
337 /// undefined.
338 U32div = OPCODE_U32DIV,
339
340 /// Pops two elements off the stack, computes their binary AND, and pushes the result back
341 /// onto the stack.
342 ///
343 /// If either of the elements is greater than or equal to 2^32, execution fails.
344 U32and = OPCODE_U32AND,
345
346 /// Pops two elements off the stack, computes their binary XOR, and pushes the result back
347 /// onto the stack.
348 ///
349 /// If either of the elements is greater than or equal to 2^32, execution fails.
350 U32xor = OPCODE_U32XOR,
351
352 // ----- stack manipulation ------------------------------------------------------------------
353 /// Pushes 0 onto the stack.
354 Pad = OPCODE_PAD,
355
356 /// Removes to element from the stack.
357 Drop = OPCODE_DROP,
358
359 /// Pushes a copy of stack element 0 onto the stack.
360 Dup0 = OPCODE_DUP0,
361
362 /// Pushes a copy of stack element 1 onto the stack.
363 Dup1 = OPCODE_DUP1,
364
365 /// Pushes a copy of stack element 2 onto the stack.
366 Dup2 = OPCODE_DUP2,
367
368 /// Pushes a copy of stack element 3 onto the stack.
369 Dup3 = OPCODE_DUP3,
370
371 /// Pushes a copy of stack element 4 onto the stack.
372 Dup4 = OPCODE_DUP4,
373
374 /// Pushes a copy of stack element 5 onto the stack.
375 Dup5 = OPCODE_DUP5,
376
377 /// Pushes a copy of stack element 6 onto the stack.
378 Dup6 = OPCODE_DUP6,
379
380 /// Pushes a copy of stack element 7 onto the stack.
381 Dup7 = OPCODE_DUP7,
382
383 /// Pushes a copy of stack element 9 onto the stack.
384 Dup9 = OPCODE_DUP9,
385
386 /// Pushes a copy of stack element 11 onto the stack.
387 Dup11 = OPCODE_DUP11,
388
389 /// Pushes a copy of stack element 13 onto the stack.
390 Dup13 = OPCODE_DUP13,
391
392 /// Pushes a copy of stack element 15 onto the stack.
393 Dup15 = OPCODE_DUP15,
394
395 /// Swaps stack elements 0 and 1.
396 Swap = OPCODE_SWAP,
397
398 /// Swaps stack elements 0, 1, 2, and 3 with elements 4, 5, 6, and 7.
399 SwapW = OPCODE_SWAPW,
400
401 /// Swaps stack elements 0, 1, 2, and 3 with elements 8, 9, 10, and 11.
402 SwapW2 = OPCODE_SWAPW2,
403
404 /// Swaps stack elements 0, 1, 2, and 3, with elements 12, 13, 14, and 15.
405 SwapW3 = OPCODE_SWAPW3,
406
407 /// Swaps the top two words pair wise.
408 ///
409 /// Input: [D, C, B, A, ...]
410 /// Output: [B, A, D, C, ...]
411 SwapDW = OPCODE_SWAPDW,
412
413 /// Moves stack element 2 to the top of the stack.
414 MovUp2 = OPCODE_MOVUP2,
415
416 /// Moves stack element 3 to the top of the stack.
417 MovUp3 = OPCODE_MOVUP3,
418
419 /// Moves stack element 4 to the top of the stack.
420 MovUp4 = OPCODE_MOVUP4,
421
422 /// Moves stack element 5 to the top of the stack.
423 MovUp5 = OPCODE_MOVUP5,
424
425 /// Moves stack element 6 to the top of the stack.
426 MovUp6 = OPCODE_MOVUP6,
427
428 /// Moves stack element 7 to the top of the stack.
429 MovUp7 = OPCODE_MOVUP7,
430
431 /// Moves stack element 8 to the top of the stack.
432 MovUp8 = OPCODE_MOVUP8,
433
434 /// Moves the top stack element to position 2 on the stack.
435 MovDn2 = OPCODE_MOVDN2,
436
437 /// Moves the top stack element to position 3 on the stack.
438 MovDn3 = OPCODE_MOVDN3,
439
440 /// Moves the top stack element to position 4 on the stack.
441 MovDn4 = OPCODE_MOVDN4,
442
443 /// Moves the top stack element to position 5 on the stack.
444 MovDn5 = OPCODE_MOVDN5,
445
446 /// Moves the top stack element to position 6 on the stack.
447 MovDn6 = OPCODE_MOVDN6,
448
449 /// Moves the top stack element to position 7 on the stack.
450 MovDn7 = OPCODE_MOVDN7,
451
452 /// Moves the top stack element to position 8 on the stack.
453 MovDn8 = OPCODE_MOVDN8,
454
455 /// Pops an element off the stack, and if the element is 1, swaps the top two remaining
456 /// elements on the stack. If the popped element is 0, the stack remains unchanged.
457 ///
458 /// If the popped element is neither 0 nor 1, execution fails.
459 CSwap = OPCODE_CSWAP,
460
461 /// Pops an element off the stack, and if the element is 1, swaps the remaining elements
462 /// 0, 1, 2, and 3 with elements 4, 5, 6, and 7. If the popped element is 0, the stack
463 /// remains unchanged.
464 ///
465 /// If the popped element is neither 0 nor 1, execution fails.
466 CSwapW = OPCODE_CSWAPW,
467
468 // ----- input / output ----------------------------------------------------------------------
469 /// Pushes the immediate value onto the stack.
470 Push(Felt) = OPCODE_PUSH,
471
472 /// Removes the next element from the advice stack and pushes it onto the operand stack.
473 AdvPop = OPCODE_ADVPOP,
474
475 /// Removes a word (4 elements) from the advice stack and overwrites the top four operand
476 /// stack elements with it.
477 AdvPopW = OPCODE_ADVPOPW,
478
479 /// Pops an element off the stack, interprets it as a memory address, and replaces the
480 /// remaining 4 elements at the top of the stack with values located at the specified address.
481 MLoadW = OPCODE_MLOADW,
482
483 /// Pops an element off the stack, interprets it as a memory address, and writes the remaining
484 /// 4 elements at the top of the stack into memory at the specified address.
485 MStoreW = OPCODE_MSTOREW,
486
487 /// Pops an element off the stack, interprets it as a memory address, and pushes the first
488 /// element of the word located at the specified address to the stack.
489 MLoad = OPCODE_MLOAD,
490
491 /// Pops an element off the stack, interprets it as a memory address, and writes the remaining
492 /// element at the top of the stack into the first element of the word located at the specified
493 /// memory address. The remaining 3 elements of the word are not affected.
494 MStore = OPCODE_MSTORE,
495
496 /// Loads two words from memory, and replaces the top 8 elements of the stack with them,
497 /// element-wise, in stack order.
498 ///
499 /// The operation works as follows:
500 /// - The memory address of the first word is retrieved from 13th stack element (position 12).
501 /// - Two consecutive words, starting at this address, are loaded from memory.
502 /// - The top 8 elements of the stack are overwritten with these words (element-wise, in stack
503 /// order).
504 /// - Memory address (in position 12) is incremented by 2.
505 /// - All other stack elements remain the same.
506 MStream = OPCODE_MSTREAM,
507
508 /// Pops two words from the advice stack, writes them to memory, and replaces the top 8
509 /// elements of the stack with them, element-wise, in stack order.
510 ///
511 /// The operation works as follows:
512 /// - Two words are popped from the advice stack.
513 /// - The destination memory address for the first word is retrieved from the 13th stack element
514 /// (position 12).
515 /// - The two words are written to memory consecutively, starting at this address.
516 /// - The top 8 elements of the stack are overwritten with these words (element-wise, in stack
517 /// order).
518 /// - Memory address (in position 12) is incremented by 2.
519 /// - All other stack elements remain the same.
520 Pipe = OPCODE_PIPE,
521
522 /// Encrypts data from source memory to destination memory using the Poseidon2 sponge keystream.
523 ///
524 /// Two consecutive words (8 elements) are loaded from source memory, each element is added
525 /// to the corresponding element in the rate (top 8 stack elements), and the resulting
526 /// ciphertext is written to destination memory and replaces the rate. Source and destination
527 /// addresses are incremented by 8.
528 ///
529 /// Stack transition:
530 /// ```text
531 /// [rate(8), cap(4), src, dst, ...]
532 /// ↓
533 /// [ct(8), cap(4), src+8, dst+8, ...]
534 /// ```
535 /// where `ct = mem[src..src+8] + rate`, where addition is element-wise.
536 ///
537 /// After this operation, `hperm` should be applied to refresh the keystream for the next block.
538 CryptoStream = OPCODE_CRYPTOSTREAM,
539
540 // ----- cryptographic operations ------------------------------------------------------------
541 /// Performs a Poseidon2 permutation on the top 3 words of the operand stack,
542 /// where the top 2 words are the rate (words C and B), the deepest word is the capacity (word
543 /// A), and the digest output is the middle word E.
544 ///
545 /// Stack transition:
546 /// [C, B, A, ...] -> [F, E, D, ...]
547 HPerm = OPCODE_HPERM,
548
549 /// Verifies that a Merkle path from the specified node resolves to the specified root. This
550 /// operation can be used to prove that the prover knows a path in the specified Merkle tree
551 /// which starts with the specified node.
552 ///
553 /// The stack is expected to be arranged as follows (from the top):
554 /// - value of the node, 4 elements.
555 /// - depth of the path, 1 element.
556 /// - index of the node, 1 element.
557 /// - root of the tree, 4 elements.
558 ///
559 /// The Merkle path itself is expected to be provided by the prover non-deterministically (via
560 /// merkle sets). If the prover is not able to provide the required path, the operation fails.
561 /// The state of the stack does not change.
562 ///
563 /// The internal value specifies an error code associated with the error in case when the
564 /// assertion fails.
565 MpVerify(Felt) = OPCODE_MPVERIFY,
566
567 /// Computes a new root of a Merkle tree where a node at the specified position is updated to
568 /// the specified value.
569 ///
570 /// The stack is expected to be arranged as follows (from the top):
571 /// - old value of the node, 4 element
572 /// - depth of the node, 1 element
573 /// - index of the node, 1 element
574 /// - current root of the tree, 4 elements
575 /// - new value of the node, 4 element
576 ///
577 /// The Merkle path for the node is expected to be provided by the prover non-deterministically
578 /// via the advice provider. At the end of the operation, the old node value is replaced with
579 /// the new root value, that is computed based on the provided path. Everything else on the
580 /// stack remains the same.
581 ///
582 /// The tree will always be copied into a new instance, meaning the advice provider will keep
583 /// track of both the old and new Merkle trees.
584 MrUpdate = OPCODE_MRUPDATE,
585
586 /// Performs FRI (Fast Reed-Solomon Interactive Oracle Proofs) layer folding by a factor of 4
587 /// for FRI protocol executed in a degree 2 extension of the base field.
588 ///
589 /// This operation:
590 /// - Folds 4 query values (v0, v1), (v2, v3), (v4, v5), (v6, v7) into a single value (ne0, ne1)
591 /// - Computes new value of the domain generator power: poe' = poe^4
592 /// - Increments layer pointer (cptr) by 2
593 /// - Checks that the previous folding was done correctly
594 /// - Shifts the stack to move an item from the overflow table to stack position 15
595 ///
596 /// Stack transition:
597 /// Input: [v7, v6, v5, v4, v3, v2, v1, v0, f_pos, d_seg, poe, pe1, pe0, a1, a0, cptr, ...]
598 /// Output: [t1, t0, s1, s0, df3, df2, df1, df0, poe^2, f_tau, cptr+2, poe^4, f_pos, ne1, ne0,
599 /// eptr, ...] where eptr is moved from the stack overflow table and is the address of the
600 /// final FRI layer.
601 FriE2F4 = OPCODE_FRIE2F4,
602
603 /// Performs 8 steps of the Horner evaluation method on a polynomial with coefficients over
604 /// the base field, i.e., it computes
605 ///
606 /// acc' = (((acc_tmp * alpha + c3) * alpha + c2) * alpha + c1) * alpha + c0
607 ///
608 /// where
609 ///
610 /// acc_tmp := (((acc * alpha + c7) * alpha + c6) * alpha + c5) * alpha + c4
611 ///
612 ///
613 /// In other words, the intsruction computes the evaluation at alpha of the polynomial
614 ///
615 /// P(X) := c7 * X^7 + c6 * X^6 + ... + c1 * X + c0
616 HornerBase = OPCODE_HORNERBASE,
617
618 /// Performs 4 steps of the Horner evaluation method on a polynomial with coefficients over
619 /// the extension field, i.e., it computes
620 ///
621 /// acc' = (((acc * alpha + c3) * alpha + c2) * alpha + c1) * alpha + c0
622 ///
623 /// In other words, the intsruction computes the evaluation at alpha of the polynomial
624 ///
625 /// P(X) := c3 * X^3 + c2 * X^2 + c1 * X + c0
626 HornerExt = OPCODE_HORNEREXT,
627
628 /// Evaluates an arithmetic circuit given a pointer to its description in memory, the number
629 /// of arithmetic gates, and the sum of the input and constant gates.
630 EvalCircuit = OPCODE_EVALCIRCUIT,
631
632 /// Logs a precompile event. This instruction is used to signal that a precompile computation
633 /// was requested.
634 LogPrecompile = OPCODE_LOGPRECOMPILE,
635}
636
637impl Operation {
638 pub const OP_BITS: usize = 7;
639
640 /// Returns the opcode of this operation.
641 #[rustfmt::skip]
642 pub fn op_code(&self) -> u8 {
643 // SAFETY: This is safe because we have given this enum a primitive representation with
644 // #[repr(u8)], with the first field of the underlying union-of-structs the discriminant.
645 //
646 // See the section on "accessing the numeric value of the discriminant"
647 // here: https://doc.rust-lang.org/std/mem/fn.discriminant.html
648 unsafe { *<*const _>::from(self).cast::<u8>() }
649 }
650
651 /// Returns an immediate value carried by this operation.
652 // Proptest generators for operations in crate::mast::node::basic_block_node::tests discriminate
653 // on this flag, please update them when you modify the semantics of this method.
654 pub fn imm_value(&self) -> Option<Felt> {
655 match *self {
656 Self::Push(imm) => Some(imm),
657 _ => None,
658 }
659 }
660
661 /// Returns true if this operation writes any data to the decoder hasher registers.
662 ///
663 /// In other words, if so, then the user op helper registers are not available.
664 pub fn populates_decoder_hasher_registers(&self) -> bool {
665 matches!(
666 self,
667 Self::End
668 | Self::Join
669 | Self::Split
670 | Self::Loop
671 | Self::Repeat
672 | Self::Respan
673 | Self::Span
674 | Self::Halt
675 | Self::Call
676 | Self::SysCall
677 )
678 }
679}
680
681impl crate::prettier::PrettyPrint for Operation {
682 fn render(&self) -> crate::prettier::Document {
683 crate::prettier::display(self)
684 }
685}
686
687impl fmt::Display for Operation {
688 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
689 match self {
690 // ----- system operations ------------------------------------------------------------
691 Self::Noop => write!(f, "noop"),
692 Self::Assert(err_code) => write!(f, "assert({err_code})"),
693
694 Self::SDepth => write!(f, "sdepth"),
695 Self::Caller => write!(f, "caller"),
696
697 Self::Clk => write!(f, "clk"),
698
699 // ----- flow control operations ------------------------------------------------------
700 Self::Join => write!(f, "join"),
701 Self::Split => write!(f, "split"),
702 Self::Loop => write!(f, "loop"),
703 Self::Call => writeln!(f, "call"),
704 Self::Dyncall => writeln!(f, "dyncall"),
705 Self::SysCall => writeln!(f, "syscall"),
706 Self::Dyn => writeln!(f, "dyn"),
707 Self::Span => write!(f, "span"),
708 Self::End => write!(f, "end"),
709 Self::Repeat => write!(f, "repeat"),
710 Self::Respan => write!(f, "respan"),
711 Self::Halt => write!(f, "halt"),
712
713 // ----- field operations -------------------------------------------------------------
714 Self::Add => write!(f, "add"),
715 Self::Neg => write!(f, "neg"),
716 Self::Mul => write!(f, "mul"),
717 Self::Inv => write!(f, "inv"),
718 Self::Incr => write!(f, "incr"),
719
720 Self::And => write!(f, "and"),
721 Self::Or => write!(f, "or"),
722 Self::Not => write!(f, "not"),
723
724 Self::Eq => write!(f, "eq"),
725 Self::Eqz => write!(f, "eqz"),
726
727 Self::Expacc => write!(f, "expacc"),
728
729 // ----- ext2 operations --------------------------------------------------------------
730 Self::Ext2Mul => write!(f, "ext2mul"),
731
732 // ----- u32 operations ---------------------------------------------------------------
733 Self::U32assert2(err_code) => write!(f, "u32assert2({err_code})"),
734 Self::U32split => write!(f, "u32split"),
735 Self::U32add => write!(f, "u32add"),
736 Self::U32add3 => write!(f, "u32add3"),
737 Self::U32sub => write!(f, "u32sub"),
738 Self::U32mul => write!(f, "u32mul"),
739 Self::U32madd => write!(f, "u32madd"),
740 Self::U32div => write!(f, "u32div"),
741
742 Self::U32and => write!(f, "u32and"),
743 Self::U32xor => write!(f, "u32xor"),
744
745 // ----- stack manipulation -----------------------------------------------------------
746 Self::Drop => write!(f, "drop"),
747 Self::Pad => write!(f, "pad"),
748
749 Self::Dup0 => write!(f, "dup0"),
750 Self::Dup1 => write!(f, "dup1"),
751 Self::Dup2 => write!(f, "dup2"),
752 Self::Dup3 => write!(f, "dup3"),
753 Self::Dup4 => write!(f, "dup4"),
754 Self::Dup5 => write!(f, "dup5"),
755 Self::Dup6 => write!(f, "dup6"),
756 Self::Dup7 => write!(f, "dup7"),
757 Self::Dup9 => write!(f, "dup9"),
758 Self::Dup11 => write!(f, "dup11"),
759 Self::Dup13 => write!(f, "dup13"),
760 Self::Dup15 => write!(f, "dup15"),
761
762 Self::Swap => write!(f, "swap"),
763 Self::SwapW => write!(f, "swapw"),
764 Self::SwapW2 => write!(f, "swapw2"),
765 Self::SwapW3 => write!(f, "swapw3"),
766 Self::SwapDW => write!(f, "swapdw"),
767
768 Self::MovUp2 => write!(f, "movup2"),
769 Self::MovUp3 => write!(f, "movup3"),
770 Self::MovUp4 => write!(f, "movup4"),
771 Self::MovUp5 => write!(f, "movup5"),
772 Self::MovUp6 => write!(f, "movup6"),
773 Self::MovUp7 => write!(f, "movup7"),
774 Self::MovUp8 => write!(f, "movup8"),
775
776 Self::MovDn2 => write!(f, "movdn2"),
777 Self::MovDn3 => write!(f, "movdn3"),
778 Self::MovDn4 => write!(f, "movdn4"),
779 Self::MovDn5 => write!(f, "movdn5"),
780 Self::MovDn6 => write!(f, "movdn6"),
781 Self::MovDn7 => write!(f, "movdn7"),
782 Self::MovDn8 => write!(f, "movdn8"),
783
784 Self::CSwap => write!(f, "cswap"),
785 Self::CSwapW => write!(f, "cswapw"),
786
787 // ----- input / output ---------------------------------------------------------------
788 Self::Push(value) => write!(f, "push({value})"),
789
790 Self::AdvPop => write!(f, "advpop"),
791 Self::AdvPopW => write!(f, "advpopw"),
792
793 Self::MLoadW => write!(f, "mloadw"),
794 Self::MStoreW => write!(f, "mstorew"),
795
796 Self::MLoad => write!(f, "mload"),
797 Self::MStore => write!(f, "mstore"),
798
799 Self::MStream => write!(f, "mstream"),
800 Self::Pipe => write!(f, "pipe"),
801 Self::CryptoStream => write!(f, "crypto_stream"),
802
803 Self::Emit => write!(f, "emit"),
804
805 // ----- cryptographic operations -----------------------------------------------------
806 Self::HPerm => write!(f, "hperm"),
807 Self::MpVerify(err_code) => write!(f, "mpverify({err_code})"),
808 Self::MrUpdate => write!(f, "mrupdate"),
809
810 // ----- STARK proof verification -----------------------------------------------------
811 Self::FriE2F4 => write!(f, "frie2f4"),
812 Self::HornerBase => write!(f, "horner_eval_base"),
813 Self::HornerExt => write!(f, "horner_eval_ext"),
814 Self::EvalCircuit => write!(f, "eval_circuit"),
815 Self::LogPrecompile => write!(f, "log_precompile"),
816 }
817 }
818}
819
820impl Serializable for Operation {
821 fn write_into<W: ByteWriter>(&self, target: &mut W) {
822 target.write_u8(self.op_code());
823
824 // For operations that have extra data, encode it in `data`.
825 match self {
826 Operation::Assert(err_code)
827 | Operation::MpVerify(err_code)
828 | Operation::U32assert2(err_code) => {
829 err_code.write_into(target);
830 },
831 Operation::Push(value) => value.as_canonical_u64().write_into(target),
832
833 // Note: we explicitly write out all the operations so that whenever we make a
834 // modification to the `Operation` enum, we get a compile error here. This
835 // should help us remember to properly encode/decode each operation variant.
836 Operation::Noop
837 | Operation::SDepth
838 | Operation::Caller
839 | Operation::Clk
840 | Operation::Join
841 | Operation::Split
842 | Operation::Loop
843 | Operation::Call
844 | Operation::Dyn
845 | Operation::Dyncall
846 | Operation::SysCall
847 | Operation::Span
848 | Operation::End
849 | Operation::Repeat
850 | Operation::Respan
851 | Operation::Halt
852 | Operation::Add
853 | Operation::Neg
854 | Operation::Mul
855 | Operation::Inv
856 | Operation::Incr
857 | Operation::And
858 | Operation::Or
859 | Operation::Not
860 | Operation::Eq
861 | Operation::Eqz
862 | Operation::Expacc
863 | Operation::Ext2Mul
864 | Operation::U32split
865 | Operation::U32add
866 | Operation::U32add3
867 | Operation::U32sub
868 | Operation::U32mul
869 | Operation::U32madd
870 | Operation::U32div
871 | Operation::U32and
872 | Operation::U32xor
873 | Operation::Pad
874 | Operation::Drop
875 | Operation::Dup0
876 | Operation::Dup1
877 | Operation::Dup2
878 | Operation::Dup3
879 | Operation::Dup4
880 | Operation::Dup5
881 | Operation::Dup6
882 | Operation::Dup7
883 | Operation::Dup9
884 | Operation::Dup11
885 | Operation::Dup13
886 | Operation::Dup15
887 | Operation::Swap
888 | Operation::SwapW
889 | Operation::SwapW2
890 | Operation::SwapW3
891 | Operation::SwapDW
892 | Operation::Emit
893 | Operation::MovUp2
894 | Operation::MovUp3
895 | Operation::MovUp4
896 | Operation::MovUp5
897 | Operation::MovUp6
898 | Operation::MovUp7
899 | Operation::MovUp8
900 | Operation::MovDn2
901 | Operation::MovDn3
902 | Operation::MovDn4
903 | Operation::MovDn5
904 | Operation::MovDn6
905 | Operation::MovDn7
906 | Operation::MovDn8
907 | Operation::CSwap
908 | Operation::CSwapW
909 | Operation::AdvPop
910 | Operation::AdvPopW
911 | Operation::MLoadW
912 | Operation::MStoreW
913 | Operation::MLoad
914 | Operation::MStore
915 | Operation::MStream
916 | Operation::Pipe
917 | Operation::CryptoStream
918 | Operation::HPerm
919 | Operation::MrUpdate
920 | Operation::FriE2F4
921 | Operation::HornerBase
922 | Operation::HornerExt
923 | Operation::EvalCircuit
924 | Operation::LogPrecompile => (),
925 }
926 }
927}
928
929impl Deserializable for Operation {
930 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
931 let op_code = source.read_u8()?;
932
933 let operation = match op_code {
934 OPCODE_NOOP => Self::Noop,
935 OPCODE_EQZ => Self::Eqz,
936 OPCODE_NEG => Self::Neg,
937 OPCODE_INV => Self::Inv,
938 OPCODE_INCR => Self::Incr,
939 OPCODE_NOT => Self::Not,
940 OPCODE_MLOAD => Self::MLoad,
941 OPCODE_SWAP => Self::Swap,
942 OPCODE_CALLER => Self::Caller,
943 OPCODE_MOVUP2 => Self::MovUp2,
944 OPCODE_MOVDN2 => Self::MovDn2,
945 OPCODE_MOVUP3 => Self::MovUp3,
946 OPCODE_MOVDN3 => Self::MovDn3,
947 OPCODE_ADVPOPW => Self::AdvPopW,
948 OPCODE_EXPACC => Self::Expacc,
949
950 OPCODE_MOVUP4 => Self::MovUp4,
951 OPCODE_MOVDN4 => Self::MovDn4,
952 OPCODE_MOVUP5 => Self::MovUp5,
953 OPCODE_MOVDN5 => Self::MovDn5,
954 OPCODE_MOVUP6 => Self::MovUp6,
955 OPCODE_MOVDN6 => Self::MovDn6,
956 OPCODE_MOVUP7 => Self::MovUp7,
957 OPCODE_MOVDN7 => Self::MovDn7,
958 OPCODE_SWAPW => Self::SwapW,
959 OPCODE_EXT2MUL => Self::Ext2Mul,
960 OPCODE_MOVUP8 => Self::MovUp8,
961 OPCODE_MOVDN8 => Self::MovDn8,
962 OPCODE_SWAPW2 => Self::SwapW2,
963 OPCODE_SWAPW3 => Self::SwapW3,
964 OPCODE_SWAPDW => Self::SwapDW,
965 OPCODE_EMIT => Self::Emit,
966
967 OPCODE_ASSERT => Self::Assert(Felt::read_from(source)?),
968 OPCODE_EQ => Self::Eq,
969 OPCODE_ADD => Self::Add,
970 OPCODE_MUL => Self::Mul,
971 OPCODE_AND => Self::And,
972 OPCODE_OR => Self::Or,
973 OPCODE_U32AND => Self::U32and,
974 OPCODE_U32XOR => Self::U32xor,
975 OPCODE_FRIE2F4 => Self::FriE2F4,
976 OPCODE_DROP => Self::Drop,
977 OPCODE_CSWAP => Self::CSwap,
978 OPCODE_CSWAPW => Self::CSwapW,
979 OPCODE_MLOADW => Self::MLoadW,
980 OPCODE_MSTORE => Self::MStore,
981 OPCODE_MSTOREW => Self::MStoreW,
982
983 OPCODE_PAD => Self::Pad,
984 OPCODE_DUP0 => Self::Dup0,
985 OPCODE_DUP1 => Self::Dup1,
986 OPCODE_DUP2 => Self::Dup2,
987 OPCODE_DUP3 => Self::Dup3,
988 OPCODE_DUP4 => Self::Dup4,
989 OPCODE_DUP5 => Self::Dup5,
990 OPCODE_DUP6 => Self::Dup6,
991 OPCODE_DUP7 => Self::Dup7,
992 OPCODE_DUP9 => Self::Dup9,
993 OPCODE_DUP11 => Self::Dup11,
994 OPCODE_DUP13 => Self::Dup13,
995 OPCODE_DUP15 => Self::Dup15,
996 OPCODE_ADVPOP => Self::AdvPop,
997 OPCODE_SDEPTH => Self::SDepth,
998 OPCODE_CLK => Self::Clk,
999
1000 OPCODE_U32ADD => Self::U32add,
1001 OPCODE_U32SUB => Self::U32sub,
1002 OPCODE_U32MUL => Self::U32mul,
1003 OPCODE_U32DIV => Self::U32div,
1004 OPCODE_U32SPLIT => Self::U32split,
1005 OPCODE_U32ASSERT2 => Self::U32assert2(Felt::read_from(source)?),
1006 OPCODE_U32ADD3 => Self::U32add3,
1007 OPCODE_U32MADD => Self::U32madd,
1008
1009 OPCODE_HPERM => Self::HPerm,
1010 OPCODE_MPVERIFY => Self::MpVerify(Felt::read_from(source)?),
1011 OPCODE_PIPE => Self::Pipe,
1012 OPCODE_MSTREAM => Self::MStream,
1013 OPCODE_CRYPTOSTREAM => Self::CryptoStream,
1014 OPCODE_SPLIT => Self::Split,
1015 OPCODE_LOOP => Self::Loop,
1016 OPCODE_SPAN => Self::Span,
1017 OPCODE_JOIN => Self::Join,
1018 OPCODE_DYN => Self::Dyn,
1019 OPCODE_DYNCALL => Self::Dyncall,
1020 OPCODE_HORNERBASE => Self::HornerBase,
1021 OPCODE_HORNEREXT => Self::HornerExt,
1022 OPCODE_LOGPRECOMPILE => Self::LogPrecompile,
1023 OPCODE_EVALCIRCUIT => Self::EvalCircuit,
1024
1025 OPCODE_MRUPDATE => Self::MrUpdate,
1026 OPCODE_PUSH => Self::Push(Felt::read_from(source)?),
1027 OPCODE_SYSCALL => Self::SysCall,
1028 OPCODE_CALL => Self::Call,
1029 OPCODE_END => Self::End,
1030 OPCODE_REPEAT => Self::Repeat,
1031 OPCODE_RESPAN => Self::Respan,
1032 OPCODE_HALT => Self::Halt,
1033 _ => {
1034 return Err(DeserializationError::InvalidValue(format!(
1035 "Invalid opcode '{op_code}'"
1036 )));
1037 },
1038 };
1039
1040 Ok(operation)
1041 }
1042
1043 /// Returns the minimum serialized size: 1 byte opcode.
1044 ///
1045 /// Some operations have additional payload (e.g., Push has 8 bytes for Felt),
1046 /// but the minimum is just the opcode byte.
1047 fn min_serialized_size() -> usize {
1048 1
1049 }
1050}