Enum miden_processor::Operation

pub enum Operation {
    Noop,
    Assert(u32),
    FmpAdd,
    FmpUpdate,
    SDepth,
    Caller,
    Clk,
    Join,
    Split,
    Loop,
    Call,
    Dyn,
    SysCall,
    Span,
    End,
    Repeat,
    Respan,
    Halt,
    Add,
    Neg,
    Mul,
    Inv,
    Incr,
    And,
    Or,
    Not,
    Eq,
    Eqz,
    Expacc,
    Ext2Mul,
    U32split,
    U32add,
    U32assert2(BaseElement),
    U32add3,
    U32sub,
    U32mul,
    U32madd,
    U32div,
    U32and,
    U32xor,
    Pad,
    Drop,
    Dup0,
    Dup1,
    Dup2,
    Dup3,
    Dup4,
    Dup5,
    Dup6,
    Dup7,
    Dup9,
    Dup11,
    Dup13,
    Dup15,
    Swap,
    SwapW,
    SwapW2,
    SwapW3,
    SwapDW,
    MovUp2,
    MovUp3,
    MovUp4,
    MovUp5,
    MovUp6,
    MovUp7,
    MovUp8,
    MovDn2,
    MovDn3,
    MovDn4,
    MovDn5,
    MovDn6,
    MovDn7,
    MovDn8,
    CSwap,
    CSwapW,
    Push(BaseElement),
    AdvPop,
    AdvPopW,
    MLoadW,
    MStoreW,
    MLoad,
    MStore,
    MStream,
    Pipe,
    HPerm,
    MpVerify,
    MrUpdate,
    FriE2F4,
    RCombBase,
}

A set of native VM operations.

These operations take exactly one cycle to execute.

Variants

Noop

Advances cycle counter, but does not change the state of user stack.

Assert(u32)

Pops the stack; if the popped value is not 1, execution fails.

The internal value specifies an error code associated with the error in case when the execution fails.

FmpAdd

Pops an element off the stack, adds the current value of the fmp register to it, and pushes the result back onto the stack.

FmpUpdate

Pops an element off the stack and adds it to the current value of fmp register.

SDepth

Pushes the current depth of the stack onto the stack.

Caller

Overwrites the top four stack items with the hash of a function which initiated the current SYSCALL. Thus, this operation can be executed only inside a SYSCALL code block.

Clk

Pushes the current value of the clock cycle onto the stack. This operation can be used to measure the number of cycles it has taken to execute the program up to the current instruction.

Join

Marks the beginning of a join block.

Split

Marks the beginning of a split block.

Loop

Marks the beginning of a loop block.

Call

Marks the beginning of a function call.

Dyn

Marks the beginning of a dynamic code block, where the target is specified by the stack.

SysCall

Marks the beginning of a kernel call.

Span

Marks the beginning of a span code block.

End

Marks the end of a program block.

Repeat

Indicates that body of an executing loop should be executed again.

Respan

Starts processing a new operation batch.

Halt

Indicates the end of the program. This is used primarily to pad the execution trace to the required length. Once HALT operation is executed, no other operations can be executed by the VM (HALT operation itself excepted).

Add

Pops two elements off the stack, adds them, and pushes the result back onto the stack.

Neg

Pops an element off the stack, negates it, and pushes the result back onto the stack.

Mul

Pops two elements off the stack, multiplies them, and pushes the result back onto the stack.

Inv

Pops an element off the stack, computes its multiplicative inverse, and pushes the result back onto the stack.

Incr

Pops an element off the stack, adds 1 to it, and pushes the result back onto the stack.

And

Pops two elements off the stack, multiplies them, and pushes the result back onto the stack.

If either of the elements is greater than 1, execution fails. This operation is equivalent to boolean AND.

Or

Pops two elements off the stack and subtracts their product from their sum.

If either of the elements is greater than 1, execution fails. This operation is equivalent to boolean OR.

Not

Pops an element off the stack and subtracts it from 1.

If the element is greater than one, the execution fails. This operation is equivalent to boolean NOT.

Eq

Pops two elements off the stack and compares them. If the elements are equal, pushes 1 onto the stack, otherwise pushes 0 onto the stack.

Eqz

Pops an element off the stack and compares it to 0. If the element is 0, pushes 1 onto the stack, otherwise pushes 0 onto the stack.

Expacc

Computes a single turn of exponent accumulation for the given inputs. This operation can be be used to compute a single turn of power of a field element.

The top 4 elements of the stack are expected to be arranged as follows (form the top):

• least significant bit of the exponent in the previous trace if there’s an expacc call, otherwise ZERO
• exponent of base number a for this turn
• accumulated power of base number a so far
• number which needs to be shifted to the right

At the end of the operation, exponent is replaced with its square, current value of power of base number a on exponent is incorporated into the accumulator and the number is shifted to the right by one bit.

Ext2Mul

Computes the product of two elements in the extension field of degree 2 and pushes the result back onto the stack as the third and fourth elements. Pushes 0 onto the stack as the first and second elements.

U32split

Pops an element off the stack, splits it into upper and lower 32-bit values, and pushes these values back onto the stack.

U32add

Pops two elements off the stack, adds them, and splits the result into upper and lower 32-bit values. Then pushes these values back onto the stack.

If either of these elements is greater than or equal to 2^32, the result of this operation is undefined.

U32assert2(BaseElement)

Pops two elements off the stack and checks if each of them represents a 32-bit value. If both of them are, they are pushed back onto the stack, otherwise an error is returned.

The internal value specifies an error code associated with the error in case when the assertion fails.

U32add3

Pops three elements off the stack, adds them together, and splits the result into upper and lower 32-bit values. Then pushes the result back onto the stack.

U32sub

Pops two elements off the stack and subtracts the first element from the second. Then, the result, together with a flag indicating whether subtraction underflowed is pushed onto the stack.

If their of the values is greater than or equal to 2^32, the result of this operation is undefined.

U32mul

Pops two elements off the stack, multiplies them, and splits the result into upper and lower 32-bit values. Then pushes these values back onto the stack.

If their of the values is greater than or equal to 2^32, the result of this operation is undefined.

U32madd

Pops two elements off the stack and multiplies them. Then pops the third element off the stack, and adds it to the result. Finally, splits the result into upper and lower 32-bit values, and pushes them onto the stack.

If any of the three values is greater than or equal to 2^32, the result of this operation is undefined.

U32div

Pops two elements off the stack and divides the second element by the first. Then pushes the integer result of the division, together with the remainder, onto the stack.

If their of the values is greater than or equal to 2^32, the result of this operation is undefined.

U32and

Pops two elements off the stack, computes their binary AND, and pushes the result back onto the stack.

If either of the elements is greater than or equal to 2^32, execution fails.

U32xor

Pops two elements off the stack, computes their binary XOR, and pushes the result back onto the stack.

If either of the elements is greater than or equal to 2^32, execution fails.

Pad

Pushes 0 onto the stack.

Drop

Removes to element from the stack.

Dup0

Pushes a copy of stack element 0 onto the stack.

Dup1

Pushes a copy of stack element 1 onto the stack.

Dup2

Pushes a copy of stack element 2 onto the stack.

Dup3

Pushes a copy of stack element 3 onto the stack.

Dup4

Pushes a copy of stack element 4 onto the stack.

Dup5

Pushes a copy of stack element 5 onto the stack.

Dup6

Pushes a copy of stack element 6 onto the stack.

Dup7

Pushes a copy of stack element 7 onto the stack.

Dup9

Pushes a copy of stack element 9 onto the stack.

Dup11

Pushes a copy of stack element 11 onto the stack.

Dup13

Pushes a copy of stack element 13 onto the stack.

Dup15

Pushes a copy of stack element 15 onto the stack.

Swap

Swaps stack elements 0 and 1.

SwapW

Swaps stack elements 0, 1, 2, and 3 with elements 4, 5, 6, and 7.

SwapW2

Swaps stack elements 0, 1, 2, and 3 with elements 8, 9, 10, and 11.

SwapW3

Swaps stack elements 0, 1, 2, and 3, with elements 12, 13, 14, and 15.

SwapDW

Swaps the top two words pair wise.

Input: [D, C, B, A, …] Output: [B, A, D, C, …]

MovUp2

Moves stack element 2 to the top of the stack.

MovUp3

Moves stack element 3 to the top of the stack.

MovUp4

Moves stack element 4 to the top of the stack.

MovUp5

Moves stack element 5 to the top of the stack.

MovUp6

Moves stack element 6 to the top of the stack.

MovUp7

Moves stack element 7 to the top of the stack.

MovUp8

Moves stack element 8 to the top of the stack.

MovDn2

Moves the top stack element to position 2 on the stack.

MovDn3

Moves the top stack element to position 3 on the stack.

MovDn4

Moves the top stack element to position 4 on the stack.

MovDn5

Moves the top stack element to position 5 on the stack.

MovDn6

Moves the top stack element to position 6 on the stack.

MovDn7

Moves the top stack element to position 7 on the stack.

MovDn8

Moves the top stack element to position 8 on the stack.

CSwap

Pops an element off the stack, and if the element is 1, swaps the top two remaining elements on the stack. If the popped element is 0, the stack remains unchanged.

If the popped element is neither 0 nor 1, execution fails.

CSwapW

Pops an element off the stack, and if the element is 1, swaps the remaining elements 0, 1, 2, and 3 with elements 4, 5, 6, and 7. If the popped element is 0, the stack remains unchanged.

If the popped element is neither 0 nor 1, execution fails.

Push(BaseElement)

Pushes the immediate value onto the stack.

AdvPop

Removes the next element from the advice stack and pushes it onto the operand stack.

AdvPopW

Removes a word (4 elements) from the advice stack and overwrites the top four operand stack elements with it.

MLoadW

Pops an element off the stack, interprets it as a memory address, and replaces the remaining 4 elements at the top of the stack with values located at the specified address.

MStoreW

Pops an element off the stack, interprets it as a memory address, and writes the remaining 4 elements at the top of the stack into memory at the specified address.

MLoad

Pops an element off the stack, interprets it as a memory address, and pushes the first element of the word located at the specified address to the stack.

MStore

Pops an element off the stack, interprets it as a memory address, and writes the remaining element at the top of the stack into the first element of the word located at the specified memory address. The remaining 3 elements of the word are not affected.

MStream

Loads two words from memory, and replaces the top 8 elements of the stack with them, element-wise, in stack order.

The operation works as follows:

• The memory address of the first word is retrieved from 13th stack element (position 12).
• Two consecutive words, starting at this address, are loaded from memory.
• The top 8 elements of the stack are overwritten with these words (element-wise, in stack order).
• Memory address (in position 12) is incremented by 2.
• All other stack elements remain the same.

Pipe

Pops two words from the advice stack, writes them to memory, and replaces the top 8 elements of the stack with them, element-wise, in stack order.

The operation works as follows:

• Two words are popped from the advice stack.
• The destination memory address for the first word is retrieved from the 13th stack element (position 12).
• The two words are written to memory consecutively, starting at this address.
• The top 8 elements of the stack are overwritten with these words (element-wise, in stack order).
• Memory address (in position 12) is incremented by 2.
• All other stack elements remain the same.

HPerm

Performs a Rescue Prime Optimized permutation on the top 3 words of the operand stack, where the top 2 words are the rate (words C and B), the deepest word is the capacity (word A), and the digest output is the middle word E.

Stack transition: [C, B, A, …] -> [F, E, D, …]

MpVerify

Verifies that a Merkle path from the specified node resolves to the specified root. This operation can be used to prove that the prover knows a path in the specified Merkle tree which starts with the specified node.

The stack is expected to be arranged as follows (from the top):

• value of the node, 4 elements.
• depth of the path, 1 element.
• index of the node, 1 element.
• root of the tree, 4 elements.

The Merkle path itself is expected to be provided by the prover non-deterministically (via merkle sets). If the prover is not able to provide the required path, the operation fails. The state of the stack does not change.

MrUpdate

Computes a new root of a Merkle tree where a node at the specified position is updated to the specified value.

The stack is expected to be arranged as follows (from the top):

• old value of the node, 4 element
• depth of the node, 1 element
• index of the node, 1 element
• current root of the tree, 4 elements
• new value of the node, 4 element

The Merkle path for the node is expected to be provided by the prover non-deterministically via the advice provider. At the end of the operation, the old node value is replaced with the new root value, that is computed based on the provided path. Everything else on the stack remains the same.

The tree will always be copied into a new instance, meaning the advice provider will keep track of both the old and new Merkle trees.

FriE2F4

TODO: add docs

RCombBase

Performs a single step of a random linear combination defining the DEEP composition polynomial i.e., the input to the FRI protocol. More precisely, the sum in question is: \sum_{i=0}^k{\alpha_i \cdot \left(\frac{T_i(x) - T_i(z)}{x - z} + \frac{T_i(x) - T_i(g \cdot z)}{x - g \cdot z} \right)}

and the following instruction computes the numerators $\alpha_i \cdot (T_i(x) - T_i(z))$ and $\alpha_i \cdot (T_i(x) - T_i(g \cdot z))$ and stores the values in two accumulators $r$ and $p$, respectively. This instruction is specialized to main trace columns i.e. the values $T_i(x)$ are base field elements.

Implementations

impl Operation

pub const OP_BITS: usize = 7usize

pub const fn op_code(&self) -> u8

Returns the opcode of this operation.

Opcode patterns have the following meanings:

• 00xxxxx operations do not shift the stack; constraint degree can be up to 2.
• 010xxxx operations shift the stack the left; constraint degree can be up to 2.
• 011xxxx operations shift the stack to the right; constraint degree can be up to 2.
• 100xxx-: operations consume 4 range checks; constraint degree can be up to 3. These are used to encode most u32 operations.
• 101xxx-: operations where constraint degree can be up to 3. These include control flow operations and some other operations requiring high degree constraints.
• 11xxx–: operations where constraint degree can be up to 5. These include control flow operations and some other operations requiring very high degree constraints.

pub fn imm_value(&self) -> Option<BaseElement>

Returns an immediate value carried by this operation.

pub fn is_control_op(&self) -> bool

Returns true if this operation is a control operation.

Trait Implementations

impl Clone for Operation

fn clone(&self) -> Operation

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Operation

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl Display for Operation

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl PartialEq for Operation

fn eq(&self, other: &Operation) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Copy for Operation

impl Eq for Operation

impl StructuralPartialEq for Operation