Operation constraints
In addition to the constraints described in the previous section, we need to impose constraints to check that each VM operation is executed correctly.
For this purpose the VM exposes a set of operation-specific flags. These flags are set to DUP
operation is executed, and to
To describe how operation-specific constraints work, let’s use an example with DUP
operation. This operation pushes a copy of the top stack item onto the stack. The constraints we need to impose for this operation are as follows:
The first constraint enforces that the top stack item in the next row is the same as the top stack item in the current row. The second constraint enforces that all stack items (starting from item
Let’s write similar constraints for DUP1
operation, which pushes a copy of the second stack item onto the stack:
It is easy to notice that while the first constraint changed, the second constraint remained the same - i.e., we are still just shifting the stack to the right.
In fact, for most operations it makes sense to make a distinction between constraints unique to the operation vs. more general constraints which enforce correct behavior for the stack items not affected by the operation. In the subsequent sections we describe in detail only the former constraints, and provide high-level descriptions of the more general constraints. Specifically, we indicate how the operation affects the rest of the stack (e.g., shifts right starting from position
Operation flags¶
As mentioned above, operation flags are used as selectors to enforce operation-specific constraints. That is, they turn on relevant constraints for a given operation. In total, the VM provides
Operation flags are mutually exclusive. That is, if one flag is set to
To compute values of operation flags we use op bits registers located in the decoder. These registers contain binary representations of operation codes (opcodes). Each opcode consists of
For example, the value of the flag for NOOP
, which is encoded as 0000000
, is computed as follows:
While the value of the DROP
operation, which is encoded as 0101001
is computed as follows:
As can be seen from above, the degree for both of these flags is
We organize the operations into
# of ops | degree | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
0 | x | x | x | x | x | x | 0 | 0 | 64 | 7 |
1 | 0 | 0 | x | x | x | - | 0 | 0 | 8 | 6 |
1 | 0 | 1 | x | x | x | x | 1 | 0 | 16 | 5 |
1 | 1 | x | x | x | - | - | 0 | 1 | 8 | 4 |
In the above:
- Operation flags for operations in the first group (with prefix
0
), are computed using all op bits, and thus their degree is . - Operation flags for operations in the second group (with prefix
100
), are computed using only the first op bits, and thus their degree is . - Operation flags for operations in the third group (with prefix
101
), are computed using all op bits. We use the extra register (which is set to ) to reduce the degree by . Thus, the degree of op flags in this group is . - Operation flags for operations in the fourth group (with prefix
11
), are computed using only the first op bits. We use the extra register (which is set to ) to reduce the degree by . Thus, the degree of op flags in this group is .
How operations are distributed between these
No stack shift operations¶
This group contains
Operation | Opcode value | Binary encoding | Operation group | Flag degree |
---|---|---|---|---|
NOOP |
000_0000 |
System ops | ||
EQZ |
000_0001 |
Field ops | ||
NEG |
000_0010 |
Field ops | ||
INV |
000_0011 |
Field ops | ||
INCR |
000_0100 |
Field ops | ||
NOT |
000_0101 |
Field ops | ||
FMPADD |
000_0110 |
System ops | ||
MLOAD |
000_0111 |
I/O ops | ||
SWAP |
000_1000 |
Stack ops | ||
CALLER |
000_1001 |
System ops | ||
MOVUP2 |
000_1010 |
Stack ops | ||
MOVDN2 |
000_1011 |
Stack ops | ||
MOVUP3 |
000_1100 |
Stack ops | ||
MOVDN3 |
000_1101 |
Stack ops | ||
ADVPOPW |
000_1110 |
I/O ops | ||
EXPACC |
000_1111 |
Field ops | ||
MOVUP4 |
001_0000 |
Stack ops | ||
MOVDN4 |
001_0001 |
Stack ops | ||
MOVUP5 |
001_0010 |
Stack ops | ||
MOVDN5 |
001_0011 |
Stack ops | ||
MOVUP6 |
001_0100 |
Stack ops | ||
MOVDN6 |
001_0101 |
Stack ops | ||
MOVUP7 |
001_0110 |
Stack ops | ||
MOVDN7 |
001_0111 |
Stack ops | ||
SWAPW |
001_1000 |
Stack ops | ||
EXT2MUL |
001_1001 |
Field ops | ||
MOVUP8 |
001_1010 |
Stack ops | ||
MOVDN8 |
001_1011 |
Stack ops | ||
SWAPW2 |
001_1100 |
Stack ops | ||
SWAPW3 |
001_1101 |
Stack ops | ||
SWAPDW |
001_1110 |
Stack ops | ||
<unused> |
001_1111 |
Left stack shift operations¶
This group contains
Operation | Opcode value | Binary encoding | Operation group | Flag degree |
---|---|---|---|---|
ASSERT |
010_0000 |
System ops | ||
EQ |
010_0001 |
Field ops | ||
ADD |
010_0010 |
Field ops | ||
MUL |
010_0011 |
Field ops | ||
AND |
010_0100 |
Field ops | ||
OR |
010_0101 |
Field ops | ||
U32AND |
010_0110 |
u32 ops | ||
U32XOR |
010_0111 |
u32 ops | ||
FRIE2F4 |
010_1000 |
Crypto ops | ||
DROP |
010_1001 |
Stack ops | ||
CSWAP |
010_1010 |
Stack ops | ||
CSWAPW |
010_1011 |
Stack ops | ||
MLOADW |
010_1100 |
I/O ops | ||
MSTORE |
010_1101 |
I/O ops | ||
MSTOREW |
010_1110 |
I/O ops | ||
FMPUPDATE |
010_1111 |
System ops |
Right stack shift operations¶
This group contains
Operation | Opcode value | Binary encoding | Operation group | Flag degree |
---|---|---|---|---|
PAD |
011_0000 |
Stack ops | ||
DUP |
011_0001 |
Stack ops | ||
DUP1 |
011_0010 |
Stack ops | ||
DUP2 |
011_0011 |
Stack ops | ||
DUP3 |
011_0100 |
Stack ops | ||
DUP4 |
011_0101 |
Stack ops | ||
DUP5 |
011_0110 |
Stack ops | ||
DUP6 |
011_0111 |
Stack ops | ||
DUP7 |
011_1000 |
Stack ops | ||
DUP9 |
011_1001 |
Stack ops | ||
DUP11 |
011_1010 |
Stack ops | ||
DUP13 |
011_1011 |
Stack ops | ||
DUP15 |
011_1100 |
Stack ops | ||
ADVPOP |
011_1101 |
I/O ops | ||
SDEPTH |
011_1110 |
I/O ops | ||
CLK |
011_1111 |
System ops |
u32 operations¶
This group contains 100
to serve as a selector for the range check constraints. The value of this flag is computed as follows:
The degree of this flag is
As mentioned previously, the last bit of the opcode is not used in computation of the flag for these operations. We force this bit to always be set to
Putting these operations into a group with flag degree U32SPLIT
operation have degree U32ADD3
and U32MADD
shift the stack to the left. Thus, having these two operations in this group and putting them under the common prefix 10011
allows us to create a common flag for these operations of degree
High-degree operations¶
This group contains operations which require constraints with degree up to
Operation | Opcode value | Binary encoding | Operation group | Flag degree |
---|---|---|---|---|
HPERM |
101_0000 |
Crypto ops | ||
MPVERIFY |
101_0001 |
Crypto ops | ||
PIPE |
101_0010 |
I/O ops | ||
MSTREAM |
101_0011 |
I/O ops | ||
SPLIT |
101_0100 |
Flow control ops | ||
LOOP |
101_0101 |
Flow control ops | ||
SPAN |
101_0110 |
Flow control ops | ||
JOIN |
101_0111 |
Flow control ops | ||
DYN |
101_1000 |
Flow control ops | ||
<unused> |
101_1001 |
|||
<unused> |
101_1010 |
|||
<unused> |
101_1011 |
|||
<unused> |
101_1100 |
|||
<unused> |
101_1101 |
|||
<unused> |
101_1110 |
|||
<unused> |
101_1111 |
Note that the SPLIT
and LOOP
operations are grouped together under the common prefix 101010
, and thus can have a common flag of degree
Also, we need to make sure that extra
register
Very high-degree operations¶
This group contains operations which require constraints with degree up to
Operation | Opcode value | Binary encoding | Operation group | Flag degree |
---|---|---|---|---|
MRUPDATE |
110_0000 |
Crypto ops | ||
PUSH |
110_0100 |
I/O ops | ||
SYSCALL |
110_1000 |
Flow control ops | ||
CALL |
110_1100 |
Flow control ops | ||
END |
111_0000 |
Flow control ops | ||
REPEAT |
111_0100 |
Flow control ops | ||
RESPAN |
111_1000 |
Flow control ops | ||
HALT |
111_1100 |
Flow control ops |
As mentioned previously, the last two bits of the opcode are not used in computation of the flag for these operations. We force these bits to always be set to
Also, we need to make sure that extra
register
Composite flags¶
Using the operation flags defined above, we can compute several composite flags which are used by various constraints in the VM.
Shift right flag¶
The right-shift flag indicates that an operation shifts the stack to the right. This flag is computed as follows:
In the above, 011
. We also need to add in flags for other operations which shift the stack to the right but are not a part of the above group (e.g., PUSH
operation).
Shift left flag¶
The left-shift flag indicates that a given operation shifts the stack to the left. To simplify the description of this flag, we will first compute the following intermediate variables:
A flag which is set to
A flag which is set to
Using the above variables, we compute left-shift flag as follows:
In the above:
* 010
.
* LOOP
block, and to
Thus, similarly to the right-shift flag, we compute the value of the left-shift flag based on the prefix of the operation group which contains most left shift operations, and add in flag values for other operations which shift the stack to the left but are not a part of this group.
Control flow flag¶
The control flow flag
However, this can be computed more efficiently via the common operation prefixes for the two groups of control flow operations as follows.