We want to make it practical to compile conventional code to a zkVM with reasonable performance. No zkVM today is optimized for this goal. We desire a VM with neither registers nor a dedicated stack, and one that has a small field size with low-degree constraints. We also want efficient compilation from LLVM IR to the set of VM instructions.
We want to make it practical to compile conventional code to a zkVM with reasonable performance. No zkVM today is optimized for this goal. We desire a VM with neither registers nor a dedicated stack, and one that has a small field size with low-degree constraints. We also want efficient compilation from LLVM IR to the set of VM instructions.
The zkVM consists of a CPU and several coprocessors, which are connected with communication buses:
graph TD;
CPU* --- Memory*;
CPU* --- Memory*;
CPU* --- Memory*;
CPU* --- Tip5*;
CPU* --- Logic;
CPU* --- u32_mul;
CPU* --- u32_add_sub;
CPU* --- Bls12;
CPU* --- Keccak-f;
Memory* --- Pager*;
* Part of the core (non-optional) configuration
Communication buses are implemented using permutation arguments (either grand product or multi-set checks), and may be multiplexed for efficiency when only one of a subset of buses will be used in a given cycle.
There are multiple VM configurations. The “Core” configuration is always present, and provides instructions for basic control flow and memory access. Additional configurations, such as “Field Arithmetic” or “Additional Jump” build upon the core configuration and offer additional instructions.
Instructions are encoded in groups of 6 field elements. The first element in the group contains the opcode, followed by three elements representing the operands and two immediate value flags:
opcode, opa, opb, opc, immb, immc.
Our VM operates under the Harvard architecture, where progrom code is stored separately from main memory. Code is addressed by any field element, starting from 0. The program counter pc stores the location (a field element) of the instruction that is being executed.
Memory is comprised of word-addressable cells. A given cell contains 4 field elements, each of which are typically used to store a single byte (arbitrary field elements can also be stored). All core and ALU-related instructions operate on cells (i.e. any operand address is word aligned – a multiple of 4). In the VM compiler, the address of newly added local variables in the stack is word aligned.
For example, a U32 is represented in memory by its byte decomposition (4 elements). To initialize a U32 from an immediate value, we use the SETL16 instruction (see the complete instruction list below), which sets the first two bytes in memory. To initialize a U32 value greater than 16 bits, we can also call the SETH16 instruction to set the upper two bytes.
Our VM cannot represent operand values that are greater than the prime p, and cannot distinguish between 0 and p. Therefore, any immediate values greater than or equal to p need to be expanded into smaller values.
Our zkVM does not operate on general purpose registers. Instead, instructions refer to variables local to the call frame, i.e. relative to the current frame pointer fp.
The following notation is used throughout this document:
Operand values: opa, opb, opc denote the value encoded in the operand a, b, or c of the current instruction.
CPU registers: fp, pc denote the value of the current frame pointer and program counter, respectively.
Relative addressing: [a] denote the cell value at address a offset from fp, i.e. fp + a. Variables local to the call frame are denoted in this form. Note that we are omitting fp in the expression here, but that the first dereference of an operand is always relative to the frame pointer.
Absolute addressing: [[a]] denotes the cell value at absolute address [a]. Heap-allocated values are denoted in this form.
To refer to relative or absolute element values, we use the notation [a]elem or [[a]]elem respectively.
Each instruction contains 5 field element operands, a, b, c, d, e. Often, d and e are binary flags indicating whther operands a and b are immediate values or relative offets.
Listed below are the instructions offered in each configuration.
Note that field arithmetic instructions only operate on the first element in a cell, which represents a field element instead of a single byte.
Note: These will not be supported in the initial version.
Note:
Fixed configurable stack size (e.g. 8MB), growing in opposite direction of the heap.
Allocate-only malloc (no de-allocation using free)
We will closely follow RISC-V assembly, making modifications as necessary. The most important difference between our zkVM assembly and RV32IM is that instead of registers x0-31, we only have two special-purpose registers fp and pc. However, we have (up to 231−1) local variables, addressed relative to the current frame point fp.
We follow the RISC-V convention and grows the stack downwards. For a function call, the arguments are pushed onto the stack in reverse order. We only allow statically sized allocation on the stack, unlike traditional architectures where alloca can be used to allocate dynamically. All dynamic allocation will be compiled to heap allocations. Instead of using a frame pointer that points at the begining of the frame, we use a stack pointer which points at the first free stack cell.
Note that:
Functions arguments are stored at fp + 12, fp + 16, …
Return FP (the value of FP before the call) is stored at fp+8
Return value is stored at fp + 4
Return address is stored at fp
Local variables are stored at fp - 4, fp - 8, …
Memcpy will require rougly 2 cycles per word. We can follow this memcpy implementation on RISC-V.
define i32 @main() {
%1 = alloca i32, align 4
%2 = alloca i32, align 4
%3 = alloca i32, align 4
store i32 24, i32* %1, align 4
store i32 7, i32* %2, align 4
%4 = load i32, i32* %1, align 4
%5 = load i32, i32* %2, align 4
%6 = mul nsw i32 %4, %5
store i32 %6, i32* %3, align 4
%7 = load i32, i32* %1, align 4
ret i32 %7
}
main:
sub -4(fp), 0(fp), 0(fp) # Setup the 0 local variable at fp - 4
add -8(fp), -4(fp), 24, # Set [fp - 8] to 24
add -12(fp), -4(fp), 7, # Set [fp - 12] to 7
mul -16(fp), 8(fp), 12(fp) # Set [fp - 16] to 24 * 7
add 4(fp), -8(fp), 0 # Set return value at [fp + 4] to [fp - 8]
ret
define i32 @main() {
%1 = alloca i32, align 4
store i32 0, i32* %1, align 4
%2 = call i32 @mul(i32 938253, i32 7)
ret i32 %2
}
define i32 @mul2(i32 %0, i32 %1) {
%3 = alloca i32, align 4
%4 = alloca i32, align 4
store i32 %0, i32* %3, align 4
store i32 %1, i32* %4, align 4
%5 = load i32, i32* %3, align 4
%6 = load i32, i32* %4, align 4
%7 = mul nsw i32 %5, %6
ret i32 %7
}
main:
imm32 -4(fp), 938253
imm32 -8(fp), 7
call mul2
# call translates to
# jal 0(fp), -16, mul2 " store pc + 1 to [fp], add -16 to fp, set pc to mul2
# addifp 16
ret
mul2:
mul 4(fp), 8(fp), 12(fp)
ret
The stack at the time of executing mul inside mul (line 11) looks like:
Columns opcode, opa, opb, opc, opd, ope are specified by the program code (see the “Instruction Trace” section below).
Trace cells are also allocated to hold buffered read memory values for addra and addrb, and buffered write values for addrc . We read and write 4 elements from memory at a time to the main trace. These elements are only constrained when the immediate value flags are not set (see the “Instruction Decoding” section below):
The memory table is sorted by (addr, clk)
TODO: Replace this trace table and associated constraints with more efficient nondeterministic methods
There are also 5 helper value cells: ℎ0 through ℎ4.
Trace cells are also allocated for each selector. In each cycle, the opcode is decoded into the following selector flags, which are grouped by type (not configuration) below for convenience. All flags are binary values, except for the instruction code.
We are writing a compiler from LLVM IR to our ISA.
This is a STARK-based zkVM. We are using Plonky3 to implement the polynomial IOP and PCS.
We plan to use the 32-bit field defined by p = 2^31 - 1, which should give very good performance on GPUs or with most vector instruction sets.
Our VM has no general purpose registers, since memory is cheap.
We will use a conventional R/W memory.
The CPU can do up to three memory operations per cycle, to support binary operations involving two reads and one write.
If we used a single-trace model, we could support this by adding columns for 6 memory operations in each row of our trace: 3 for the chronological memory log and 3 for the (address, timestamp) ordered memory log.Instead, we make the memory a separate table (i.e. a separate STARK which gets connected with a permutation argument). We also use multi-table support to implement other coprocessors that are wasteful to include in the main CPU, as their operations may not be used during most cycles (e.g. Keccak).
TODO: Explain the permutation-based continuation implementation.
Initially, we will support lookups only against prover-supplied tables. The main use case is range checks. To perform a 16-bit range check, for example, we would have the prover send a table containing [0 .. 2^16 - 1] in order. (If the trace was not already 2^16, we would pad it. If it was longer than 2^16, the prover would include some duplicates.) We would then use constraints to enforce that this table starts at 0, ends at 2^16 - 1, and increments by 0 or 1.
Preprocessed tables can also be useful, particularly for bitwise operations like xor. However, we will not support them initially because they require non-succinct preprocessing.
Fast floating point arithmetic doesn’t seem important for our anticipated use cases, so we will convert float operations to integer ones during compilation.
This open-source project aims to construct a robust, versatile system optimized for wide-ranging use cases, performance, and development productivity. We seek varied perspectives, innovative ideas, and unwavering dedication to quality.
Your contribution can take many forms, each equally valuable. Here are a few ways you can get involved:
Code Contribution: You can directly contribute to the source code. This could range from fixing bugs and improving documentation, to developing new features.
Adding Coprocessors: Valida zkVM is designed to be flexible and extensible. If you have an idea for a new coprocessor that could enhance zkVM’s functionality, we encourage you to design and implement it.
Contributing to Plonky3: As part of our ongoing efforts, we are working on the Plonky3 backend. Whether you have experience in this area or are interested in learning more, your contribution can significantly help us expedite our progress.
Code Review and Bug Reporting: Reviewing our codebase and reporting any issues you find is a great way to contribute to the project.
Documentation: Comprehensive and clear documentation is the backbone of any successful open-source project. If you have a knack for writing or explaining complex concepts in a simple way, your skills would be greatly valued.
We are looking forward to your contributions and are ready to provide guidance and support to anyone who wants to get involved. Please visit our GitHub page to get started and feel free to reach out with any questions or ideas.