RISC-V ELF Transpilation to OpenVM Executable

The OpenVM framework supports transpilation of a RISC-V ELF consisting of the RV32IM instruction set as well as custom RISC-V instructions specified by VM extensions into an OpenVM executable.

Transpiler Framework

The transpiler is a function that converts a RISC-V ELF into an OpenVM executable, where an OpenVM executable is defined as the following pieces of data:

• Program ROM
• Starting program counter pc_0
• Initial data memory

The OpenVM executable forms a part of the initial VM state.

We define a RISC-V machine code block to be a 32-bit aligned contiguous sequence of bits in the RISC-V program memory, where the bit length is variable and a multiple of 32. The code block may contain instructions from standard or non-standard RISC-V ISA extensions, but it may also contain arbitrary bits.

The transpiler is configured upon construction with the set of VM extensions to support. In order to be supported by the transpiler, a VM extension must specify a set of RISC-V machine code blocks and rules for mapping each code block to a sequences of potentially multiple OpenVM instructions.

The transpilation rules must satisfy:

• A read or write to the RISC-V program counter corresponds to a read or write to the program counter of the same value in OpenVM. This includes the implicit read of the program counter to fetch the instruction from program code, as well as any implicit pc += 4 advancement in some RISC-V instructions. In transpilations where a single RISC-V code block is mapped to multiple OpenVM instructions (e.g., Kernel Code), the intermediate OpenVM instructions may change the value of the program counter to a program address that is not the start of a RISC-V instruction. It is required that at the end of the RISC-V code block, the program counter is set to the start of a valid RISC-V instruction in the RISC-V machine code.
• A RISC-V 32-bit register x{i} read or write access corresponds to an OpenVM memory access at [4 * i: 4]_1 except for writes to x0, see below. The 32-bits of x{i} are represented as 4 little-endian bytes in OpenVM memory.
  • A RISC-V code block must never map to any OpenVM instruction that changes the value of [0:4]_1 in OpenVM memory.
• A RISC-V 32-bit user memory access of the jth byte in word i corresponds to an OpenVM memory access at [4 * i + j]_2.
• If the RISC-V code block is a standard instruction from the RISC-V Instruction Set Manual Volume I: Unprivileged ISA (pdf), then the transpilation rule must map the RISC-V instruction to an OpenVM instruction that follows the RISC-V specification after applying the above correspondences to register and memory accesses.

The above requirements, together with the invariants of the OpenVM ISA, imply that transpilation will only be valid for programs where:

• The program code does not have program address greater than or equal to 2^PC_BITS.
• The program does not access memory outside the range [0, 2^addr_max_bits): programs that attempt such accesses will fail to execute.

A transpiler configuration is only considered valid if there are no two transpilation rules that may map the same RISC-V code block to different OpenVM instructions.

• When defining a new VM extension with transpiler support, the associated RISC-V code blocks should be chosen to avoid conflicts with RISC-V code blocks from other pre-existing VM extensions that the new VM extension expects to be compatible with.

Register x0 Handling

As specified in Section 2.1 of RISC-V Instruction Set Manual Volume I: Unprivileged ISA (pdf), register x0 is hardwired to zero and must never be written to.

The OpenVM ISA treats [0:4]_1 as normal read/write memory and makes no guarantees on memory accesses to this location. The transpiler must never transpile a RISC-V code block to any OpenVM instruction that changes the value of [0:4]_1 in OpenVM memory. For compatibility with the RISC-V ISA, the transpiler must always transpile a RISC-V instruction to an OpenVM instruction that matches the RISC-V specification. In particular, any RISC-V instruction that has rd=x0 must be transpiled to either the NOP OpenVM instruction if it has no side effects or to an OpenVM instruction that executes the expected side effect and does not change the value of [0:4]_1.

Transpiler Specification for Default VM Extensions

This section specifies the behavior of the transpiler for the default VM extensions with the custom RISC-V instructions specified here. We use the following notation:

• Let ind(rd) denote 4 * (register index), which is in 0..128. In particular, it fits in one field element.
• We use itof for the function that takes 12-bits (or 21-bits in case of J-type) to a signed integer and then mapping to the corresponding field element. So 0b11…11 goes to -1 in F.
• We use sign_extend_24 to convert a 12-bit integer into a 24-bit integer via sign extension. We use this in conjunction with utof, which converts 24 bits into an unsigned integer and then maps it to the corresponding field element. Note that each 24-bit unsigned integer fits in one field element.
• We use sign_extend_16 for the analogous conversion into a 16-bit integer via sign extension.
• We use zero_extend_24 to convert an unsigned integer with at most 24 bits into a 24-bit unsigned integer by zero extension. This is used in conjunction with utof to convert unsigned integers to field elements.
• We use sign_of(imm) to get the sign bit of the immediate imm.
• The notation imm[0:4] means the lowest 5 bits of the immediate.
• For a phantom instruction ins, disc(ins) is the discriminant specified in the ISA specification.
• For a phantom instruction ins and a 16-bit c_upper, phantom_c(c_upper, ins) = c_upper << 16 | disc(ins) is the corresponding 32-bit operand c for PHANTOM.

We now specify the transpilation for system instructions and the default set of VM extensions.

System Instructions

RV32IM Extension

Transpilation from RV32IM to OpenVM assembly follows the mapping below, which is generally a 1-1 translation between RV32IM instructions and OpenVM instructions. The main exception relates to handling of the x0 register, which discards writes and has value 0 in all reads. We handle writes to x0 in transpilation as follows:

• Instructions that write to x0 with no side effects are transpiled to the PHANTOM instruction with c = 0x00 (Nop).
• Instructions that write to a register which might be x0 with side effects (JAL, JALR) are transpiled to the corresponding custom instruction whose write behavior is controlled by a flag specifying whether the target register is x0.

Because [0:4]_1 is initialized to 0 and never written to, this guarantees that reads from x0 yield 0 and enforces that any OpenVM program transpiled from RV32IM conforms to the RV32IM specification for x0.

System Level Extensions to RV32IM

Standard RV32IM Instructions

OpenVM Intrinsic VM Extensions

The following sections specify the transpilation of the default set of intrinsic extensions to OpenVM. In order to preserve correctness of handling of x0, the transpilation must respect the constraint that any instruction that writes to a register must:

• Transpile to Nop if the register is x0 and there are no side effects.
• Transpile to an OpenVM assembly instruction that does not write to [0:4]_1 and processes side effects if the register is x0 and there are side effects.

Each VM extension's behavior is specified below.

Keccak Extension

SHA2-256 Extension

BigInt Extension

Algebra Extension

Modular Arithmetic

Complex Extension Field Arithmetic

Elliptic Curve Extension

Pairing Extension

OpenVM Kernel Code Transpilation

This section specifies the transpilation of custom RISC-V kernel code to OpenVM instructions. This transpilation differs from the ones described above in that a custom RISC-V code block of more than 32-bits is used to specify a single OpenVM instruction, and a single 32-bit RISC-V instruction is also used to specify multiple (nonexistent) instructions.

We use the following 32-bit RISC-V code blocks in conjunction with other arbitrary code blocks to transpile custom RISC-V kernel code to OpenVM instructions.

We have 3 special 32-bit code blocks:

Note that the vri code block does not conform to RISC-V instruction naming conventions and is only used after lfii as described below. The vri code is the 32-bit big-endian encoding of 2^31 + 116.

Overview

We specify a format in which an arbitrary sequence of OpenVM instructions can be serialized into a 32-bit aligned code block which can be inserted into the RISC-V ELF. The transpiler is then able to recognize this code block and transpile it (effectively deserializing) back into the original OpenVM instructions.

To do this, suppose we have a sequence of OpenVM instructions [i_1, ..., i_l]. These will be serialized into the concatenation of the code blocks:

lfii [i_1 encoding]
lfii [i_2 encoding]
...
lfii [i_l encoding]
gi [gap encoding]

This will be an overall code block of 32 * m bits, where m > l, which will be transpiled to only l OpenVM instructions. The instructions are encoded as described below. If the starting program address of the RISC-V code block is a (in bytes), then the OpenVM instructions i_1, ..., i_l will be at addresses [a, a + 4, ..., a + 4 * (l - 1)] in the OpenVM program ROM. The addresses [a + 4 * l, ..., a + 4 * (m - 1)] will be left empty in the OpenVM program ROM to maintain compatibility with RISC-V program addresses. The gap between l and m is encoded by the gap encoding.

OpenVM Instruction Encoding

An OpenVM instruction is encoded to a RISC-V code block as follows. We identify the 31-bit field F with {0, ..., p - 1} where p is the prime modulus. We encode u32 as 32-bits in little-endian format.

Let the instruction be opcode operand_1 operand_2 ... operand_n where each opcode and operand is a field element. Then to encode it into a 32-bit aligned code block, we first write lfii, followed by the number of operands n (as u32), followed by opcode (as u32). We then encode each operand simply by its canonical 32-bit representation.

Gap Encoding

The transpiler also allows for the transpilation of gaps, i.e., addresses in the RISC-V program memory that do not map to OpenVM instructions. The purpose of this is to maintain the validity of pc offsets when using the above encoding of OpenVM instructions.

A gap is encoded by first writing gi, then the number of instructions to be skipped (i.e. the length of the gap) as u32. Note that the number of instructions to be skipped is not the same as the number of bytes to be skipped -- on a 32-bit architecture, these will differ by a factor of 4.

The gap code block is used to signify the end of a block of kernel code.

Kernel Code Assumptions

The above transpilation procedure allows the insertion of arbitrary serialized OpenVM instructions into the RISC-V ELF as kernel code. To maintain the guarantees of the transpiler framework, the kernel code must satisfy the following safety assumptions:

• All code exiting the code block must jump to a valid RISC-V instruction in the machine code
• Code from outside of the kernel code block must not jump into the middle of a kernel code block
• Kernel code must not write to [0:4]_1 in OpenVM memory
• Kernel code must only write bytes to address space 2 in OpenVM memory