OpenVM supports an extensible instruction set, with different groups of opcodes supported by different VM extensions. This specification describes the overall architecture and default VM extensions which ship with OpenVM, which are:

• RV32IM: An extension supporting the 32-bit RISC-V ISA with multiplication.
• Native: An extension supporting native field arithmetic for proof recursion and aggregation.
• Keccak-256: An extension implementing the Keccak-256 hash function compatibly with RISC-V memory.
• SHA2-256: An extension implementing the SHA2-256 hash function compatibly with RISC-V memory.
• BigInt: An extension supporting 256-bit signed and unsigned integer arithmetic, including multiplication. This extension respects the RISC-V memory format.
• Algebra: An extension supporting modular arithmetic over arbitrary fields and their complex field extensions. This extension respects the RISC-V memory format.
• Elliptic curve: An extension for elliptic curve operations over Weierstrass curves, including addition and doubling. This can be used to implement multi-scalar multiplication and ECDSA scalar multiplication. This extension respects the RISC-V memory format.
• Pairing: An extension containing opcodes used to implement the optimal Ate pairing on the BN254 and BLS12-381 curves. This extension respects the RISC-V memory format.

In addition to these default extensions, developers are able to extend the ISA by defining their own custom VM extensions. For reader convenience, we provide a mapping between the code-level representation of opcodes in OpenVM and the opcodes below here.

Constants and Configuration Parameters

OpenVM depends on the following parameters, some of which are fixed and some of which are configurable:

We explain these parameters in subsequent sections.

Prime Field

The ISA globally depends on a prime field F. This field is currently fixed to Baby Bear, with modulus 15 * 2^27 + 1, but it may change in the future to another 31-bit field. Unless otherwise specified, we will identify the elements of F with the integers {0, ..., F::modulus() - 1}, where F::modulus() is the prime modulus of the field.

Virtual Machine State

The virtual machine is a state machine that is executed on a physical host machine. The state of the virtual machine consists of the following components:

Guest State:

• Program ROM (Read Only)
• Program Counter pc
• Data Memory (Read/Write)
• User Public Outputs

Host State:

• Input Stream
• Hint Stream
• Hint Spaces

The initial state of the virtual machine consists of:

• Program ROM - immutable throughout VM execution
• pc_0 - starting program counter
• Initial data memory
• No user public outputs
• Input stream
• Empty hint stream
• Empty hint spaces

We describe these components in more detail below.

Program ROM

OpenVM operates under the Harvard architecture, where program code is stored separately from data memory. The program code is loaded as read-only memory (ROM) in the VM state prior to execution, and it remains immutable throughout the execution.

Program code is a map from [0, 2^PC_BITS) to the space of instructions F^{NUM_OPERANDS + 1}, where

• PC_BITS = 30
• NUM_OPERANDS = 7.

Instructions will typically only exist at a subset of the indices in [0, 2^PC_BITS).

Instruction format

Instructions are encoded as a global opcode (field element) followed by NUM_OPERANDS = 7 operands (field elements):

opcode, a, b, c, d, e, f, g

An instruction does not need to use all operands, and trailing unused operands are suggested to be set to zero, but this won't be checked.

In the following sections, you will see operands like a, b, c, 1, e. 1 here means a fixed address space. In this case, d is suggested be set to 1, but this won't be checked.

Program Counter

There is a single special purpose register pc for the program counter of type F which stores the location of the instruction being executed. During execution, the program counter must always be a valid program address, meaning that it is an element in the range [0, 2^PC_BITS) where the program code is defined.

Data Memory

Data memory is a random access memory (RAM) which supports read and write operations. Memory is comprised of addressable cells which represent a single field element indexed by address space and pointer. The number of supported address spaces and the size of each address space are configurable constants.

• Valid address spaces not used for immediates lie in [1, 1 + 2^addr_space_height) for configuration constant addr_space_height.

• Valid pointers are field elements that lie in [0, 2^pointer_max_bits), for configuration constant pointer_max_bits. When accessing an address out of [0, 2^pointer_max_bits), the VM should panic.

• For the register address space (address space 1), valid pointers lie in [0, 128), corresponding to 32 registers with 4 byte limbs each. These configuration constants must satisfy addr_space_height, pointer_max_bits <= F::bits() - 2. We use the following notation to denote cells in memory:

• [a]_d denotes the single-cell value at pointer location a in address space d. This is a single field element.

• [a:N]_d denotes the slice [a..a + N]_d -- this is a length-N array of field elements.

Immediates

We reserve a special address space 0 for immediates. The framework enforces that address space 0 is never written to. Address space 0 is considered a read-only array with [a]_0 = a for any a in F.

Memory Accesses and Block Accesses

VM instructions can access (read or write) a contiguous list of cells (called a block) in a single address space. The block size must be in the set {1, 2, 4, 8, 16, 32}, and each address space has a minimum block size that is configurable. All block accesses must be at pointers that are a multiple of the minimum block size. For address spaces 1, 2, and 3, the minimum block size is 4, meaning all accesses must be at pointer addresses that are divisible by 4. However, RISC-V instructions like lb, lh, sb, and sh still work despite having minimum block size requirements equal to the size of the access (1 byte for lb/sb, 2 bytes for lh/sh) because these instructions are implemented by doing a block access of size 4. For the native address space (4), the minimum block size is 1, so accesses can start from any pointer address. For address spaces beyond 4, the minimum block size defaults to 1 but can be configured. Block accesses are not supported for address space 0.

Address Spaces

Different address spaces are used for different purposes in OpenVM. Memory cells in all address spaces are always field elements, but certain address spaces may impose the additional constraint that all elements fit into a maximum number of bits. The existing extensions reference the following set of address spaces, but user-defined extensions are free to introduce additional address spaces:

When adding a new user address space, the invariants of the memory cells in that address space must be declared, and all instructions must ensure that these invariants are preserved.

ℹ️ When adding a new instruction to the ISA, the instruction must declare its supported address spaces and respect the invariants of those address spaces. In particular, all instructions must respect the invariants of the address spaces above.

Inputs and Hints

To enable user input and non-determinism in OpenVM programs, the host state maintains the following three data structures during runtime execution:

• input_stream: a private non-interactive queue of vectors of field elements which is provided at the start of runtime execution
• hint_stream: a queue of values populated during runtime execution via phantom sub-instructions such as Rv32HintInput, NativeHintInput, and NativeHintBits.
• hint_space: a vector of vectors of field elements used to store hints during runtime execution via phantom sub-instructions such as NativeHintLoad. The outer hint_space vector is append-only, but each internal hint_space[hint_id] vector may be mutated, including deletions, by the host.
• kv_store: a read-only key-value store for hints. Executors(e.g. Rv32HintLoadByKey) can read data from kv_store at runtime. kv_store is designed for general purposes so both key and value are byte arrays. Encoding of key/value are decided by each executor. Users need to use the corresponding encoding when adding data to kv_store.

These data structures are not part of the guest state, and their state depends on host behavior that cannot be determined by the guest.

User Public Outputs

To make program outputs public, OpenVM allows the user to specify a list of field elements to make public. To populate this list, users can use:

• If continuations are enabled: REVEAL_RV32 (from the RV32IM extension)
• If continuations are disabled: PUBLISH (from the system extension)

The list is of length num_public_values, where num_public_values is a VM configuration parameter. By default, any element in the list that is never initialized is set to zero.

Instruction Execution

Starting from the initial VM state, the VM executes instructions according to the program ROM. Instruction execution is a transition function on the mutable parts of the VM state:

• Program Counter
• Data Memory
• User Public Outputs
• Input Stream
• Hint Stream
• Hint Spaces

which must satisfy the following conditions:

• Let from_pc be the program counter at the start of the instruction execution. The from_pc must be the address of a valid instruction in the program ROM.
• The execution must match the instruction from the program ROM.
• The execution has full read/write access to the data memory, except address space 0 must be read-only.
• User public outputs can be set at any index in [0, num_public_values). If continuations are disabled, a public value cannot be overwritten with a different value once it is set.
• Input stream can only be popped from the front as a queue.
• Full read/write access to the hint stream.
• Hint spaces can be read from at any index. Hint spaces may be mutated only by append.
• The program counter is set to a new to_pc at the end of the instruction execution. Instructions are only considered valid if to_pc is the address of a valid instruction in the program ROM.

ℹ️ Notes for extension developers: The specification of new instructions should carefully consider to_pc overflows, especially when you want to move pc with a positive offset.

Guest Instruction Execution

We define guest instruction execution to be the subset of instruction execution that only mutates the guest state:

• Program Counter
• Data Memory
• User Public Outputs

Guest instruction execution may still depend on read access to the host state. For example, instructions like HINT_STORE_RV32 (from the RV32IM extension) and HINT_STOREW, HINT_STOREW4 (from the native extension) can read from the hint_stream and write them to OpenVM memory to provide non-deterministic hints.

⚠️ Safeguards:

• All instructions should ensure that the modifications to the guest state are protected from non-deterministic host states, as the guest has no control over the host state. For example, the start address and length of modified guest memory must be derived from instruction operands or guest state (as opposed to being derived from host state).

Phantom Instructions

To facilitate hinting and debugging on the host, OpenVM supports the notion of phantom instructions. These are instructions which are identical to a no-op at the level of the OpenVM guest state, but which may be used to specify unconstrained behavior on the host. Use cases of phantom instructions include interacting with the input or hint streams or displaying debug information on the host machine.

Notes for extension developers: PhantomDiscriminant should be unique for each phantom instruction. If you want your new extension to be compatible with some extensions, you need select some compatible PhantomDiscriminant.

OpenVM Instruction Set

We now specify instructions supported by the default VM extensions shipping with OpenVM. Unless otherwise specified, instructions will set to_pc = from_pc + DEFAULT_PC_STEP. We will use the following notation:

• u32(x) where x: [F; 4] consists of 4 bytes will mean the casting from little-endian bytes in 2's complement to unsigned 32-bit integer.
• i32(x) where x: [F; 4] consists of 4 bytes will mean the casting from little-endian bytes in 2's complement to signed 32-bit integer.
• sign_extend means sign extension of bits in 2's complement.
• i32(c) where c is a field element will mean c.as_canonical_u32() if c.as_canonical_u32() < F::modulus() / 2 or c.as_canonical_u32() - F::modulus() as i32 otherwise.
• decompose(c) where c is a field element means c.as_canonical_u32().to_le_bytes().
• r32{0}(a) := i32([a:4]_1) means casting the value at [a:4]_1 to i32.

In the specification, operands marked with _ are not used and should be set to zero. Trailing unused operands should also be set to zero.

System Instructions

The opcodes below are supported by the OpenVM system and do not belong to any VM extension.

The behavior of the PHANTOM opcode is determined by the operand c. More specifically, the low 16-bits c.as_canonical_u32() & 0xffff are used as a discriminant to determine a phantom sub-instruction. Phantom sub-instructions supported by the system are listed below, and VM extensions can define additional phantom sub-instructions. Phantom sub-instructions are only allowed to use operands a,b and c_upper = c.as_canonical_u32() >> 16 and must always advance the program counter by DEFAULT_PC_STEP.

RV32IM Extension

The RV32IM extension introduces OpenVM opcodes which support 32-bit RISC-V via transpilation from a standard RV32IM ELF binary, specified here. These consist of opcodes corresponding 1-1 with RV32IM opcodes, as well as additional user IO opcodes and phantom sub-instructions to support input and debug printing on the host. We denote the OpenVM opcode corresponding to a RV32IM opcode by appending _RV32.

The RV32IM extension uses address space 0 for immediates, address space 1 for registers, and address space 2 for memory. As explained here, cells in address spaces 1 and 2 are constrained to be bytes, and all instructions preserve this constraint.

The ith RISC-V register is represented by the block [4 * i:4]_1 of 4 limbs in address space 1. All memory addresses in address space 1 behave uniformly, and in particular writes to the block [0:4]_1 corresponding to the RISC-V register x0 are allowed in the RV32IM extension. However, as detailed in RV32IM Transpilation, any OpenVM program transpiled from a RV32IM ELF will never contain such a write and conforms to the RV32IM specification.

ALU

In all ALU instructions, the operand d is fixed to be 1. The operand e must be either 0 or 1. When e = 0, the c operand is expected to be of the form F::from_canonical_u32(c_i16 as i24 as u24 as u32) where c_i16 is type i16. In other words we take signed 16-bits in two's complement, sign extend to 24-bits, consider the 24-bits as unsigned integer, and convert to field element. In the instructions below, [c:4]_0 should be interpreted as c_i16 as i32 sign extended to 32-bits.

Load/Store

For all load/store instructions, we assume the operand c is in [0, 2^16), and we fix address spaces d = 1. The address space e is 2 for load instructions, and can be 2, 3, or 4 for store instructions. The operand g must be a boolean. We let sign_extend(decompose(c)[0:2], g) denote the i32 defined by first taking the unsigned integer encoding of c as 16 bits, then sign extending it to 32 bits using the sign bit g, and considering the 32 bits as the 2's complement of an i32. We will use shorthand r32{c,g}(b) := i32([b:4]_1) + sign_extend(decompose(c)[0:2], g) as i32. This means performing signed 32-bit addition with the value of the register [b:4]_1. For consistency with other notation, we define the shorthand r32{c}(b) to mean r32{c,g}(b) where g is set to the most significant bit of c. Memory access to ptr: i32 in address space e is only valid if 0 <= ptr < 2^addr_max_bits and ptr is naturally aligned (i.e., ptr must be divisible by the data size in bytes), in which case it is an access to F::from_canonical_u32(ptr as u32). The data size is 1 for LOADB_RV32, LOADBU_RV32, STOREB_RV32, 2 for LOADH_RV32, LOADHU_RV32, STOREH_RV32, and 4 for LOADW_RV32, STOREW_RV32.

All load/store instructions always do block accesses of block size 4, even for LOADB_RV32 and STOREB_RV32.

Branch/Jump/Upper Immediate

For branch instructions, we fix d = e = 1. For jump instructions, we fix d = 1.

For branch and JAL_RV32 instructions, the instructions assume that the operand i32(c) is in [-2^24,2^24). The assignment pc += c is done as field elements. In valid programs, the from_pc is always in [0, 2^PC_BITS). We will only use base field F satisfying 2^PC_BITS + 2*2^24 < F::modulus() so to_pc = from_pc + c is only valid if i32(from_pc) + i32(c) is in [0, 2^PC_BITS).

For JALR_RV32, we treat c in [0, 2^16) as a raw encoding of 16-bits. The operand g must be a boolean. We let sign_extend(decompose(c)[0:2], g) denote the i32 defined by first taking the unsigned integer encoding of c as 16 bits, then sign extending it to 32 bits using the sign bit g, and considering the 32 bits as the 2's complement of an i32. Then it is added to the register value i32([b:4]_1), where 32-bit overflow is ignored. The instruction is only valid if the resulting i32 is in range [0, 2^PC_BITS). The result is then cast to u32 and then to F and assigned to pc.

For LUI_RV32, we are treating c in [0, 2^20) as a raw encoding of 20-bits. For AUIPC_RV32, we are treating c in [0, 2^24) as a raw encoding of 24-bits. The instruction does not need to interpret whether the register is signed or unsigned. For AUIPC_RV32, the addition is treated as unchecked u32 addition since that is the same as i32 addition at the bit level.

Note that AUIPC_RV32 does not have any condition for the register write.

RV32M Extension

For multiplication extension instructions, we fix d = 1. MUL_RV32 performs an 32-bit×32-bit multiplication and places the lower 32 bits in the destination cells. MULH_RV32, MULHU_RV32, and MULHSU_RV32 perform the same multiplication but return the upper 32 bits of the full 2×32-bit product, for signed×signed, unsigned×unsigned, and signed×unsigned multiplication respectively.

DIV_RV32 and DIVU_RV32 perform signed and unsigned integer division of 32-bits by 32-bits. REM_RV32 and REMU_RV32 provide the remainder of the corresponding division operation. Integer division is defined by dividend = q * divisor + r where 0 <= |r| < |divisor| and either sign(r) = sign(dividend) or r = 0.

Below x[n:m] denotes the bits from n to m inclusive of x.

User IO

In addition to opcodes which match 1-1 with the RV32IM opcodes, the following additional opcodes interact with address spaces outside of 1 and 2 to enable verification of programs with user input-output.

Phantom Sub-Instructions

The RV32IM extension defines the following phantom sub-instructions.

Native Extension

The native extension operates over native field elements and has instructions tailored for STARK proof recursion. It does not constrain memory elements to be bytes and most instructions only write to address space 4, with the notable exception of CASTF.

Base

In the instructions below, d,e must be either 0 or 4 except in CASTF, which may write to address space 2. Additional restrictions are applied on a per-instruction basis. In particular, the immediate address space 0 is allowed for non-vectorized reads but not allowed for writes. When using immediates, we interpret [a]_0 as the immediate value a.

Field Arithmetic

This instruction set does native field operations. Below, e,f must be either 0 or 4. When either e or f is zero, [b]_0 and [c]_0 should be interpreted as the immediates b and c, respectively.

Extension Field Arithmetic

This is only enabled when the native field is BabyBear. The quartic extension field is defined by the irreducible polynomial $x^4 - 11$, which matches Plonky3. All elements in the field extension can be represented as a vector [a_0,a_1,a_2,a_3] which represents the polynomial $a_0 + a_1x + a_2x^2 + a_3x^3$ over BabyBear.

The instructions read and write from address space 4 and do block access with block size 4.

Hashes

The instructions below do block accesses with block size 1 and CHUNK in address space 4.

The native extension uses the following Poseidon2 constants:

• PID: This identifier provides domain separation between different Poseidon2 constants. We use 0 to identify POSEIDON2_BABYBEAR_16_PARAMS, but the Mat4 used is Plonky3's with a Montgomery reduction.
• CHUNK: We use CHUNK = 8 for the native extension.
• WIDTH: We use WIDTH = 16 for the native extension.

The input (of size WIDTH) is read in two batches of size CHUNK, and, similarly, the output is written in either one or two batches of size CHUNK, depending on the output size of the corresponding opcode.

Proof Verification

We have the following special opcodes tailored to optimize FRI proof verification. They access address space 4.

Phantom Sub-Instructions

The native extension defines the following phantom sub-instructions.

Keccak Extension

The Keccak extension supports the Keccak256 hash function. The extension operates on address spaces 1 and 2, meaning all memory cells are constrained to be bytes.

SHA2-256 Extension

The SHA2-256 extension supports the SHA2-256 hash function. The extension operates on address spaces 1 and 2, meaning all memory cells are constrained to be bytes.

BigInt Extension

The BigInt extension supports operations on 256-bit signed and unsigned integers. The extension operates on address spaces 1 and 2, meaning all memory cells are constrained to be bytes. Pointers to the representation of the elements are read from address space 1 and the elements themselves are read/written from address space 2. Each instruction performs block accesses with block size 4 in address space 1 and block size 32 in address space 2.

Note: These instructions are not the same as instructions on 256-bit registers.

256-bit ALU

256-bit Branch

256-bit Multiplication

Multiplication performs 256-bit×256-bit multiplication and writes the lower 256-bits to memory. Below x[n:m] denotes the bits from n to m inclusive of x.

Algebra Extension

The algebra extension supports modular arithmetic over arbitrary fields and their complex field extensions. It is configured to specify a list of supported moduli. The configuration of each supported positive integer modulus N includes associated configuration parameters N::NUM_LIMBS and N::BLOCK_SIZE (defined below).

The instructions perform operations on unsigned big integers representing elements in the modulus. The extension operates on address spaces 1 and 2, meaning all memory cells are constrained to be bytes. Pointers to the representation of the elements are read from address space 1 and the elements themselves are read/written from address space 2.

An element in the ring of integers modulo Nis represented as an unsigned big integer with N::NUM_LIMBS limbs with each limb having LIMB_BITS = 8 bits. For each instruction, the input elements [r32{0}(b): N::NUM_LIMBS]_2, [r32{0}(c):N::NUM_LIMBS]_2 are assumed to be unsigned big integers in little-endian format with each limb having LIMB_BITS bits. However, the big integers are not required to be less than N. Under these conditions, the output element [r32{0}(a): N::NUM_LIMBS]_2 written to memory will be an unsigned big integer of the same format that is congruent modulo N to the respective operation applied to the two inputs.

For each instruction, the operand d is fixed to be 1 and e is fixed to be 2. Each instruction performs block accesses with block size 4 in address space 1 and block size N::BLOCK_SIZE in address space 2, where N::NUM_LIMBS is divisible by N::BLOCK_SIZE. Recall that N::BLOCK_SIZE must be a power of 2.

Modular Branching

The configuration of N is the same as above. For each instruction, the input elements [r32{0}(b): N::NUM_LIMBS]_2, [r32{0}(c): N::NUM_LIMBS]_2 are assumed to be unsigned big integers in little-endian format with each limb having LIMB_BITS bits.

Phantom Sub-Instructions

Complex Extension Field

A complex extension field Fp2 is the quadratic extension of a prime field Fp with irreducible polynomial X^2 + 1. An element in Fp2 is a pair c0: Fp, c1: Fp such that c0 + c1 u represents a point in Fp2 where u^2 = -1.

The complex extension field Fp2 is supported only if the modular arithmetic instructions for Fp::MODULUS is also supported. The memory layout of Fp2 is then that of two concatenated Fp elements, and the block size for memory accesses is the block size of Fp.

We use the following notation below:

r32_fp2(a) -> Fp2 {
    let c0 = [r32{0}(a): Fp::NUM_LIMBS]_2;
    let c1 = [r32{0}(a) + Fp::NUM_LIMBS: Fp::NUM_LIMBS]_2;
    return Fp2 { c0, c1 };
}

Elliptic Curve Extension

The elliptic curve extension supports arithmetic over elliptic curves C in Weierstrass form given by equation C: y^2 = x^3 + C::A * x + C::B where C::A and C::B are constants in the coordinate field. We note that the definitions of the curve arithmetic operations do not depend on C::B. The VM configuration will specify a list of supported curves. For each Weierstrass curve C there will be associated configuration parameters C::COORD_SIZE and C::BLOCK_SIZE ( defined below). The extension operates on address spaces 1 and 2, meaning all memory cells are constrained to be bytes.

An affine curve point EcPoint(x, y) is a pair of x,y where each element is an array of C::COORD_SIZE elements each with LIMB_BITS = 8 bits. When the coordinate field C::Fp of C is prime, the format of x,y is guaranteed to be the same as the format used in the modular arithmetic instructions. A curve point will be represented as 2 * C::COORD_SIZE contiguous cells in memory.

We use the following notation below:

r32_ec_point(a) -> EcPoint {
    let x = [r32{0}(a): C::COORD_SIZE]_2;
    let y = [r32{0}(a) + C::COORD_SIZE: C::COORD_SIZE]_2;
    return EcPoint(x, y);
}

Pairing Extension

The pairing extension supports opcodes tailored to accelerate pairing checks using the optimal Ate pairing over certain classes of pairing friendly elliptic curves. For a curve C to be supported, the VM must have enabled instructions for C::Fp and C::Fp2. The memory block size is C::Fp::BLOCK_SIZE for both reads and writes. The currently supported curves are BN254 and BLS12-381. The extension operates on address spaces 1 and 2, meaning all memory cells are constrained to be bytes.

Phantom Sub-Instructions

The pairing extension defines the following phantom sub-instructions.

Acknowledgements

The design of the native extension was inspired by Valida with changes suggested by Max Gillet for compatibility with existing ISAs.