# Field operations

In this section we describe the AIR constraints for Miden VM field operations (i.e., arithmetic operations over field elements).

## ADD¶

Assume $$a$$ and $$b$$ are the elements at the top of the stack. The ADD operation computes $$c \leftarrow (a + b)$$. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_0' - (s_0 + s_1) = 0 \text{ | degree} = 1$

The effect on the rest of the stack is: * Left shift starting from position $$2$$.

## NEG¶

Assume $$a$$ is the element at the top of the stack. The NEG operation computes $$b \leftarrow (-a)$$. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_0' + s_0 = 0 \text{ | degree} = 1$

The effect on the rest of the stack is: * No change starting from position $$1$$.

## MUL¶

Assume $$a$$ and $$b$$ are the elements at the top of the stack. The MUL operation computes $$c \leftarrow (a \cdot b)$$. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_0' - s_0 \cdot s_1 = 0 \text{ | degree} = 2$

The effect on the rest of the stack is: * Left shift starting from position $$2$$.

## INV¶

Assume $$a$$ is the element at the top of the stack. The INV operation computes $$b \leftarrow (a^{-1})$$. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$1 - s_0' \cdot s_0 = 0 \text{ | degree} = 2$

Note that the above constraint can be satisfied only if the value in $$s_0 \neq 0$$.

The effect on the rest of the stack is: * No change starting from position $$1$$.

## INCR¶

Assume $$a$$ is the element at the top of the stack. The INCR operation computes $$b \leftarrow (a+1)$$. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_0' - (s_0 + 1) = 0 \text{ | degree} = 1$

The effect on the rest of the stack is: * No change starting from position $$1$$.

## NOT¶

Assume $$a$$ is a binary value at the top of the stack. The NOT operation computes $$b \leftarrow (\lnot a)$$. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_0^2 - s_0 = 0 \text{ | degree} = 2$
$s_0' - (1 - s_0) = 0 \text{ | degree} = 1$

The first constraint ensures that the value in $$s_0$$ is binary, and the second constraint ensures the correctness of the boolean NOT operation.

The effect on the rest of the stack is: * No change starting from position $$1$$.

## AND¶

Assume $$a$$ and $$b$$ are binary values at the top of the stack. The AND operation computes $$c \leftarrow (a \land b)$$. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_i^2 - s_i = 0 \text{ for } i \in \{0, 1\} \text{ | degree} = 2$
$s_0' - s_0 \cdot s_1 = 0 \text{ | degree} = 2$

The first two constraints ensure that the value in $$s_0$$ and $$s_1$$ are binary, and the third constraint ensures the correctness of the boolean AND operation.

The effect on the rest of the stack is: * Left shift starting from position $$2$$.

## OR¶

Assume $$a$$ and $$b$$ are binary values at the top of the stack. The OR operation computes $$c \leftarrow (a \lor b)$$ The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_i^2 - s_i = 0 \text{ for } i \in \{0, 1\} \text{ | degree} = 2$
$s_{0}' - (s_{1} + s_{0} - s_{1} \cdot s_{0}) = 0 \text{ | degree} = 2$

The first two constraints ensure that the value in $$s_0$$ and $$s_1$$ are binary, and the third constraint ensures the correctness of the boolean OR operation.

The effect on the rest of the stack is: * Left shift starting from position $$2$$.

## EQ¶

Assume $$a$$ and $$b$$ are the elements at the top of the stack. The EQ operation computes $$c$$ such that $$c = 1$$ if $$a = b$$, and $$0$$ otherwise. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_0' \cdot (s_0 - s_1) = 0 \text{ | degree} = 2$
$s_0' - (1 - (s_0 - s_1) \cdot h_0) = 0 \text{ | degree} = 2$

To satisfy the above constraints, the prover must populate the value of helper register $$h_0$$ as follows:

• If $$s_0 \neq s_1$$, set $$h_0 = \frac{1}{s_0 - s_1}$$.
• Otherwise, set $$h_0$$ to any value (e.g., $$0$$).

The effect on the rest of the stack is: * Left shift starting from position $$2$$.

## EQZ¶

Assume $$a$$ is the element at the top of the stack. The EQZ operation computes $$b$$ such that $$b = 1$$ if $$a = 0$$, and $$0$$ otherwise. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

$s_0' \cdot s_0 = 0 \text{ | degree} = 2$
$s_0' - (1 - s_0 \cdot h_0) = 0 \text{ | degree} = 2$

To satisfy the above constraints, the prover must populate the value of helper register $$h_0$$ as follows: * If $$s_0 \neq 0$$, set $$h_0 = \frac{1}{s_0}$$. * Otherwise, set $$h_0$$ to any value (e.g., $$0$$).

The effect on the rest of the stack is:

• No change starting from position $$1$$.

## EXPACC¶

The EXPACC operation pops top $$4$$ elements from the top of the stack, performs a single round of exponent aggregation, and pushes the resulting $$4$$ values onto the stack. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

bit should be a binary.

$s_0'^{2} - s_0' = 0 \text{ | degree} = 2$

The exp in the next frame should be the square of the exp in the current frame.

$s_1' - s_1^{2} = 0 \text{ | degree} = 2$

The value val in the helper register is computed correctly using the bit and exp in next and current frame respectively.

$h_0 - ((s_1 - 1) * s_0' + 1) = 0 \text{ | degree} = 2$

The acc in the next frame is the product of val and acc in the current frame.

$s_2' - s_2 * h_0 = 0 \text{ | degree} = 2$

b in the next frame is the right shift of b in the current frame.

$s_3' - (s_3 * 2 + s_0') = 0 \text{ | degree} = 1$

The effect on the rest of the stack is:

• No change starting from position $$4$$.

## EXT2MUL¶

The EXT2MUL operation pops top $$4$$ values from the top of the stack, performs multiplication between the two extension field elements, and pushes the resulting $$4$$ values onto the stack. The diagram below illustrates this graphically.

Stack transition for this operation must satisfy the following constraints:

The first stack element should be unchanged in the next frame.

$s_0' - s_0 = 0 \text{ | degree} = 1$

The second stack element should be unchanged in the next frame.

$s_1' - s_1 = 0 \text{ | degree} = 1$

The third stack element should satisfy the following constraint.

$s_2' - (s_0 + s_1) \cdot (s_2 + s_3) + s_0 \cdot s_2 = 0 \text{ | degree} = 2$

The fourth stack element should satisfy the following constraint.

$s_3' - s_1 \cdot s_3 + 2 \cdot s_0 \cdot s_2 = 0 \text{ | degree} = 2$

The effect on the rest of the stack is:

• No change starting from position $$4$$.

Last update: January 16, 2024
Authors: kmurphypolygon (99.63%), Alejandro (0.37%)