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