Design Principles
Last updated
Last updated
ZK WorldVM adopts the AI Intelligent Instruction Set Computer (AISC) architecture, which is characterized by a smaller instruction set compared to the Complex Instruction Set Computer (CISC) architecture. The contrast between RISC and CISC architectures can be explored further in Comparison of RISC and CISC.
AI intelligent instruction set reduces the number of constraint polynomials
In ZKVM, there is a very critical constraint, CSTC (CPU State Transition Constraint); it is mainly used to constrain the validity of virtual machine state changes before and after instruction execution.
There are many registers in a virtual machine. When the virtual machine executes an instruction, the state of some registers will change. In order to ensure the correctness of the virtual machine execution, we need to constrain the following:
changes in the state of the registers involved in the execution of the instruction are valid;
The state of registers that do not participate in instruction execution remains unchanged. Let's look at a simple example to explain constraints on register state changes:
We briefly introduced the changes of some registers after the virtual machine executes three instructions; taking the PC register as an example, the update logic of the three instructions is as follows:
SubarkADD：pci+1= pci+ 1
• MOV: pci+1= pci+ 2
• JMP: pci+1= 2
When considering constraints, we cannot predict which instruction a virtual machine will execute at any given time. . Therefore, we have to design a constraint that can handle all instructions, this constraint is called CPU state Transition constraints (CSTC). In the simple example above, the PC update logic can be designed as follows:
pci+1= sel_jmpi·imm_value +（1−sel_jmp）·(pci+ 1 + op1_imm)
We represent all CPU state transitions with this constraint form. The inclusion of each new instruction by the AI-smart instruction set introduces an additional selector, which increases the complexity of the constraints. To manage this complexity, we limit the instruction size to 19, including built-in. . .
Despite having a simplified instruction set architecture, Turing-completeness still needs to be maintained to ensure that we can perform any computation using these simple instructions. Combine these instructions with the following
In Prophet Mechanism, we have developed ZK World-lang, a Turing-complete language that supports loop and recursive operations.
Most operations will use a fraction of the instruction set
. Under the CISC architecture, a large number of instruction sets are defined. In practice, however, only a small subset of instructions are used for most computations. From a constraint perspective, this represents a significant inefficiency.
. This is because the constraint logic for all instructions must be included in the constraint system (CSTC), and in the worst case, each instruction corresponds to a constraint factor. This complexity leads to a large number of polynomial and higher-order constraints, making the entire constraint The system is challenging.
In many cases it is better to use the existing instruction set rather than introduce a new instruction when performing certain calculations, although this approach may increase the size of the program (depending on the opcode), it can be verified in Add redundant data during the process to facilitate FFT. However, for complex calculations that require a large number of instructions, there are other solutions. These include introducing builtins and our Prophet module, which will be discussed in more detail in later chapters. For now, it is important to note that they can significantly reduce the number of instructions required to perform these complex calculations, as shown in Figure 2.
In ZKVM, we not only have to constrain the state of the registers associated with the instruction to be updated correctly, but we also have to ensure that the state of the registers that are not involved in the current instruction remains unchanged whereas register-based virtual machines offer certain advantages, having more registers from Verification point of view is not necessarily better. One of the following tradeoffs must be considered:
How many registers will be sufficient for most calculations?
For some calculations, is the increased number of memory accesses acceptable when there are not enough registers?
If the number of registers is small enough that memory accesses do not need to be bounded, this would be an ideal scenario for verification efficiency. The design of the Cairo VM exemplifies this approach, with no general-purpose registers and all instruction operands coming from memory. To avoid consistency checks on memory, a write-once model is used, which means that memory cannot be rewritten at the execution level, avoiding the need for checks.
However, the downside of the write-once model is that it is not friendly to Dapp developers, and the limitations of the memory model require developers to pay extra attention to memory usage. The traditional memory model is a read-write model.
As shown in Figure 3, we choose an optimal solution that considers both ZK-friendly and developer-friendly perspectives, and we consider the minimum value when it comes to the number of registers.
The calculation type that can be supported on ZK WorldVM is U32 integer calculation. Through some boundary conditions, such as the number of loops, loop termination conditions, etc., we have determined that 9 general-purpose registers can support most of the U32 calculations. In addition, the integer calculations of U64 and U256 can be realized by U32 libraryZK WorldVM also using two special registers (PC and PSP)
If the number of registers is insufficient, we need to use memory for caching, which requires instructions related to memory access (MLOAD, MSTORE). Note that to facilitate FFT, verifiers often add redundant data to the trace to satisfy the size of the trace to a power of 2. These redundant data can be replaced with valid data, as shown in FIG. 4 .
ZK World-VM uses a simplified instruction set, which limits its ability to support certain complex calculations. The traditional approach to this problem is to use existing instructions to implement such computations. However, this approach can consume a lot of opcodes, and there is an upper limit to the size of traces. Therefore, to accommodate more computations in trace, each opcode should occupy fewer trace units. Alternatively, one can take inspiration from the design of the EVM and use precompiled contracts to support complex computations. In this mode, there is no need to use EVM instructions to implement computations; instead, we can add corresponding precompiled contracts, which can be written in any high-level language, such as Rust or Go. However, this approach significantly increases the workload of the proof, requiring a separate trace table for complex computations, and performing constraint proofs only on the output of that computation and its inputs recorded in the CPU trace.
It is desirable to support complex computations with a small number of opcodes without increasing the complexity of the proof. To achieve this, we devised a method called "Prophet", as shown in Figure 8, which follows a method of prophecy and confirmation. This approach fits well with the overall design of the ZK World VM.
For complex calculations, the results of complex calculations are first calculated locally by someone else (usually proving himself), without any restrictions. The virtual machine then performs a validity check on the result of the calculation before continuing with other calculations. This verification process is implemented using instructions and included in the verification process. . For example, consider the task of computing the square root of a root. When implementing Newton's method requires more than 20 instructions, verifying that a result is indeed the square root of a free root can be done succinctly.
ZKVM, for example, only needs to multiply the result with itself to obtain the product, and then verify that the product is equal to the radical, this process requires only two instructions and a second algorithm, how to calculate the square root does not care about the ZK circuit and the user calculation process is wrapped in the prophet. Segmentation sums do not need to be verified by the ZK circuit. The ZK circuit only needs to verify the concise logical result · result = root, by using ZK WorldVM to execute these two algorithms and generate ZK proofs, the second algorithm is 10 times faster than the first traditional algorithm.
To ensure that ZK WorldVM remains developer-friendly at the language level, it currently does not support developers writing their own oracle implementations, instead the oracle library is officially maintained and updated. . Additionally, for security reasons, memory access during Prophet execution is read-only. It is worth noting that not all complex calculations are suitable for this model. Computationally complex but effective verifications, such as square roots and cube roots, are more suitable for this method, and there are also some calculations that are not complex but still ZK-unfriendly, such as bit operations, range checks, hashing and other calculations. These types of calculations do not fit into the Prophet's design, instead we use precompiled methods to support them.
Similar to precompiled contract functions in EVM. We call this approach "builtin protein". In the next chapters, we will detail the types of protein construction and the way of constraints.
The memory design is influenced by Prophet, in order to ensure that the memory tracking table can be written out by Prophet without using instructions, the memory space needs to be divided into several segments. Prophet segments are write-once bound
