zkVM 课程第二周作业

[dyxushuai]

思考题

1. NO Memory, NO Cpu 的VM架构如何帮助加速电路
2. 如何在VM中支持Cpu Profiler和Memory Profiler
3. Register Based ISA 和 Stack Based ISA 对电路效率的影响，为什么

[baidang201]

1 NO Memory, NO CPU架构加速电路的机制：
直接约束转换
所有操作直接转换为数学约束
避免了模拟内存和CPU的开销
减少了中间状态的存储需求
优化特点
消除了内存访问的约束
简化了控制流验证
降低了状态转换的复杂度

2 VM中实现Profiler的方法：
CPU Profiler实现
在操作码执行时添加计数器约束
记录每类指令的执行频率
通过witness追踪执行路径
支持热点分析
Memory Profiler实现
跟踪数据流动
记录数据访问模式
分析内存使用效率
识别优化机会

3 Register Based vs Stack Based ISA对电路效率的影响：
Register Based ISA
优点:
指令数量较少
更容易优化
寄存器分配灵活
缺点:
需要额外的寄存器选择约束
状态空间较大

Stack Based ISA
优点:
指令格式简单
约束生成直观
状态转换清晰
缺点:
可能需要更多push/pop操作
栈操作产生额外约束
影响原因
约束数量与指令复杂度相关
状态表示方式影响约束结构
不同操作的约束生成效率不同

[wcc19840827]

1. NO Memory, NO Cpu 的VM架构如何帮助加速电路

这种VM架构通常采用 (Lasso) lookup table 或者 precompile专用电路

• lookup table: 用查表证明代替 执行指令与电路约束的过程
• precompile: 使用预先编译好的专用电路, 大大减少指令的数量, 简化电路的复杂度
• 汇编级指令: 手写的电路通常比编译器翻译出的更高效 (不然就没必要手写)

2. 如何在VM中支持Cpu Profiler和Memory Profiler

• Cpu : 用 register 或者 stack 记录指令执行过程中的状态转换. 增加一个PC(程序计数器),将指令的消耗作为立即数累加到PC上.
• Memory: 用page给内存分页, 加速读写, 更有利于产生merkel prove. 增加一个计数器, 记录内存分页调入和调出操作的开销.

3. Register Based ISA 和 Stack Based ISA 对电路效率的影响，为什么

• Register Based ISA: 使用寄存器来存储操作数和中间结果, 支持随机读写, 能支持更复杂的指令操作
• Stack Based ISA: 只能对栈顶做操作, 单条指令结构更简化, 但完成相同的操作可能需要更多的指令, trace更多, 证明也更费时

[EgoSay]

NO Memory, NO Cpu 的VM架构如何帮助加速电路

在传统的 VM 里，内存 RAM 和 CPU 负责执行指令，访问数据，进行运算, 但 ZKVM 里，一切计算都要被“证明”是正确的, 所以这里的主要问题在于：

• 内存访问成本很高：每次访问 RAM，证明方都需要提供“证明”来保证这个数据是从正确的地址读取的，并且没有被篡改。这通常需要Merkle 证明或者Plonk-style 约束，非常昂贵。
• CPU 指令的模拟很贵：传统 CPU 的 ALU（算术逻辑单元）可以直接做整数运算，但 ZK 里，每个计算都要转换成约束（比如 R1CS 或 AIR），特别是布尔逻辑、除法、模运算这种操作，在 ZK 里更是天生昂贵。

优化实现思路:

(1）去掉 RAM，改用 Execution Trace

• 传统 VM 需要在 RAM 里读写数据，而 ZKVM 可以直接把计算轨迹（Execution Trace）存成电路的一部分, 意味着所有的计算步骤都可以预先固定，并且不需要复杂的 RAM 访问验证。
• 参考示例：Cairo vm

（2）去掉 CPU，改用 Arithmetic Circuits

• 传统 VM 里，CPU 执行指令时，可能涉及布尔逻辑、除法、模运算这种操作, 开销可能很大，可以采用基于算术电路（Arithmetic Circuits）的模型，直接在电路层面做计算，而不是模拟 CPU 指令流。
• 参考示例：https://dev.risczero.com/reference-docs/about-arithmetic-circuits

如何在VM中支持Cpu Profiler和Memory Profiler

• CPU Profiler：基于 Execution Trace 统计指令开销，在执行时收集每条指令的执行次数、寄存器变更、调用深度, 计算约束开销
• Memory Profiler：如果 ZKVM 仍然支持“模拟内存”（如 zkEVM），可以在电路里记录每次内存访问，对于像 Cairo 这种无 RAM 的 VM，我们可以通过 Execution Trace 分析数据流

Register Based ISA 和 Stack Based ISA 对电路效率的影响，为什么

采用 Register-Based ISA 寄存器架构的话， 操作数存放在固定数量的寄存器里（R0, R1, R2...）, 指令寻址更简单, 可以直接读取 R0, R1，而不用维护栈指针，减少电路约束数量

例如，加法 ADD R1, R2, R3 ， 在 ZK 里，这只需要一个 q_add 约束：

ADD R1, R2, R3  =>  q_add ⋅ (R1 - (R2 + R3)) = 0

而 Stack Based ISA 栈架构需要额外的 PUSH / POP 约束，导致更多约束成本。

再一个就是，栈的访问成本高，访问 stack[n] 需要存储 n 个历史状态（Merkle 证明或 Trace 记录），会引入额外的哈希计算，增加证明成本。

栈架构（Stack-Based ISA）虽然在 ZK 证明里通常比寄存器架构（Register-Based ISA）开销更大，不过它也有一些其他优点:

• 栈架构的指令不需要指定寄存器，因为所有操作都默认对栈顶元素进行, 所以指令长度更短，使得字节码编译更简单，解析更快，占用空间更小
• 由于不涉及固定的寄存器数量，栈架构的代码可以直接在不同的 CPU / VM 之间运行，不会因为寄存器布局不同而受影响,更容易跨平台
• 适用于字节码解释执行（Bytecode Interpretation）, 而在在寄存器架构里，字节码需要转换成寄存器操作，而寄存器的数量是有限的，通常需要额外的寄存器分配优化（Register Allocation）

总结:

架构类型	优点
寄存器架构（Register-Based ISA）	指令执行高效，ZK 证明成本低
栈架构（Stack-Based ISA）	代码简洁、跨平台、适用于沙盒

• 如果你的 VM 需要跨平台、解释执行, 比如想兼容 EVM，那可能需要用栈架构，并优化其 ZK 证明。

• 如果你想设计一个高效的 ZK 原生 VM，那寄存器架构可能更合适

[linqining]

1.NO Memory, NO Cpu 的VM架构如何帮助加速电路
基于memory和cpu架构的实现，由于基于cpu实现的，相应的实现需要模拟cpu架构的运行操作，如第一课的jolt 实现，需要模拟cpu的读取指令加载指令和执行指令的循环，需要实现所有的指令集
基于NO Memory, NO Cpu 的VM架构，如sp1, 实现思路不是面向底层硬件，而是面向ISA,是比面向cpu和memory架构更为抽象的一层实现，可以生成的证明和trace相应会更小，执行效率更高，其次，由于面向isa架构，读取elf文件对于某些函数可以做编译优化，特定符号的函数替换为更高效的专用电路,最后，可以发挥isa的优势，使用条件编译，以提高性能。

2.如何在VM中支持Cpu Profiler和Memory Profiler
参考https://trapdoortech.medium.com/zero-knowledge-proof-introduction-to-sp1-zkvm-source-code-d26f88f90ce4
在程序运行时记录ExecutionState并输出。

3.Register Based ISA 和 Stack Based ISA 对电路效率的影响，为什么

1. Register Based ISA 相比于Stack Based ISA 的特性优势主要有，更小的内存访问和更少的指令集，但是编译的文件会更大，综合而言，Register Based ISA 执行效率更高，对于电路而言，意味着更高执行效率，
2. 其次从电路约束实现来讲，由于stack的操作比寄存器更为复杂，Stack Based ISA用Push 、Pop 来传送数据，电路需要多实现对应的约束，从而降低电路的执行效率，
3. 从电路实现原理看https://trapdoortech.medium.com/zero-knowledge-proof-introduction-to-sp1-zkvm-source-code-d26f88f90ce4，Register Based ISA 和 Stack Based ISA 的内存约束都是通过内存一致性实现，我认为这个实现方式两者效率一致。

[deepld]

1. NO Memory, NO Cpu 的VM架构如何帮助加速电路

• NO CPU：传统架构需要复杂的数学运算和逻辑推导，NO cpu 不需要模拟CPU所有的控制单元、计算单元，将操作直接转换为数学约束，不需要先转换为中间状态；无需实现所有的指令集。
• NO Memory: 不需要担心内存访问约束，无需担心来源的正确性；通过优化电路来减少内存访问量的需求。
• zk计算就是为了执行有限状态机，使用NO Memory, NO Cpu 架构，减少传统计算机的资源需求，提升ZK证明的效率和可扩展性，可以在硬件级别加速或者在电路级别（比如：Precompile）进行加速；可以并行执行任务。

2. 如何在VM中支持Cpu Profiler和Memory Profiler
   Profiler是toolchain的重要部分

• CPU：增加记录每个指令的metric，分析执行频率和开销，用来分析电路中执行较慢的部分；通过路径追踪，发现热点和瓶颈。
• Memory：zkvm通常已经将连续内存memroy切成page，方便提升merkel proof的性能，可以考虑用内存池管理这些page，追踪分配和释放情况。

3. Register Based ISA 和 Stack Based ISA 对电路效率的影响，为什么

• Register Based：指令数较少，所有的数据load到寄存器中来计算，只需要减少的存储空间，减少电路中需要的门数量，生成proof的成本较低；但因为必须先load到寄存器，增加电路的控制复杂度。
• Stack Based ISA：用Push/Pop 来传送数据，只能栈顶操作。简洁和灵活，其栈操作模型能够更容易转换成电路计算，减少指令和数据的复杂性；但所有操作都依赖于栈的数据传递，访问成本较高。栈是线性结构，无法像寄存器那样并行操作来提升性能。

[jzhchu]

问题1

在计算机执行程序时，首先会将二进制可执行文件（Executable File）读取到Memory（比如RAM）中，再由CPU按照“取指-解码-执行”的循环来工作。具体而言，CPU根据程序计数器（PC, Program Counter）指向的地址，从Memory中读取一条指令并加载到CPU的指令寄存器中。然后CPU对指令进行解码，确认指令类型（如加法、跳转、访问内存等），在确认对应的寄存器或者功能单元，如算术逻辑单元ALU。最后，由CPU对解码的指令进行执行，如果是算术运算，则在ALU中进行，访问内存如加载/存储，则访问内存，从指定地址中读取或写入，跳转则修改PC。执行完毕后，CPU会更新PC，指向下一条指令的地址。
在Jolt实现zkVM时，按照上述逻辑，将程序执行的证明过程分为了三部分，分别为通过R1CS约束证明取指过程正确，使用offline memory checking证明解码过程以及访问Memory过程的正确性，使用Lasso lookup table证明执行过程。这种基于通用计算机架构下CPU执行方式进行证明的zkVM，理论上可以支持任意指令的执行，且可以保证过程的正确性，但是牺牲了效率性，因为对于每条指令的解码、寄存器更新、内存寻址、读写顺序等都要进行完整的电路化描述，这带来了大量的约束，提高了电路复杂度。
而在No Memory, No CPU的VM架构中，不再模拟CPU的执行过程，而是把指令视作一个相对简单的状态机或者函数，为指令集中的每个指令构建零知识电路，例如RISC0使用RISC-V指令集，对程序编译后的ELF文件进行证明，让解码、执行的逻辑通过查表的方式实现。这种方式不需要构建一个完整的CPU解码执行的流水线，可以大幅度的减少电路的约束数量。
此外，No Memory架构去除或精简了RAM的寻址、读写、对齐等复杂操作。比如控制Memory的读写方式，只允许以线性方式或者固定的方式进行读写，从而无需模拟地址加法、内存布局、页表映射等CPU机制，比如Cairo VM采用一种“Nondeterministic read-only memory”的方式，通过承诺机制替代随机访问验证。这种方式使得zkVM在构建零知识电路时，只需要保证输入、输出的顺序和内容符合预期，无需实现繁琐的随机访问和地址映射。通过对内存机制的精简，使zkVM也不必在电路级别进行复杂的寻址、边界检查，可以让电路规模显著减小。

问题2

由于在zkVM中，程序不是在CPU上运行，而是将指令抽象为电路，通过SNARK/STARK等证明系统完成证明，因此导致无法使用CPU Profiler和Memory Profiler观察运行时的指令执行、函数调用栈以及内存分配、访问情况等。针对这种情况，可以对Profiler度量的内容单独进行设计。
比如统计指令执行量和不同函数的调用频次，可以增加一组计数器，在zkVM执行固定指令集（如RISC-V）时，执行每条指令，对应的计数器加一，通过这种方式可以统计指令执行量和调用频次等信息。对于Memory的数据读写次数，也可以通过增加计数器的方式，针对读写相关的指令进行累计。而内存分配大小，需要根据不同的zkVM单独设定，目前大部分zkVM不支持复杂的内存分配，而是以stack和segment的形式出现，所以只需统计分配操作的次数即可。
而针对运行时间、指令运行效率的问题，可以通过添加log的方式，每当执行指令时，都产生一条执行日志，记录当前的CPU和内存使用情况，通过这种方式可以统计指令的运行时间和对宿主机的CPU和内存的占用情况等。

问题3

Register Based 和 Stack Based 是指令集的两种架构，这两种架构会直接影响到指令集设计的复杂度和执行的效率。寄存器式的ISA会显式的指定操作数在哪些寄存器里，结果写回哪个寄存器等，需要一个或多个memory存放当前所有寄存器的值，而且指令中会有一部分编码用于标识目标/源寄存器的编号。如ADD R1, R2, R3表示将R2+R3的结果存放在R1中，在RISC-V中编码为0x003100B3。而栈式ISA没有显式的寄存器编号，指令仅仅是操作栈顶的若干元素，例如执行ADD指令，会把栈顶的两个元素弹出，进行加法运算后，将结果压回栈顶。
对于zkVM而言，stack-based ISA通常意味着零知识友好，因为栈式ISA的指令通常是0操作数或1操作数（如PUSH），解码器只需要解码指令本身，而不需要解码多个寄存器的操作数，因此在构建零知识证明的约束过程中，可以显著减少电路的复杂度。此外，栈式机器不需要做Memory的通用寻址，只需要对栈顶元素进行操作，因此电路只需要处理栈顶pop/push数据的一致性即可。
但是register-based ISA也存在高效之处，首先register-based ISA的指令数量更少，register-based ISA中的一条指令可能需要stack-based ISA中的多条指令完成，例如ADD R1, R2, R3在栈式ISA中需要如下指令

PUSH R2 
PUSH R3 
ADD
POP R1

所以，通常而言寄存器式的指令总数更少，即使单条指令的电路部分会更大，但是总体可能依然更优。此外，如果电路要实现steam或者batch处理，寄存器式的ISA对并行数据流更加友好，因为每个寄存器对应一份数据，可以直接对多个寄存器并行执行某些操作，而栈式要想做并行，需要把栈内容拆分，管理一堆子栈或另行做调度，往往比较麻烦。
综上所述，在zkVM的指令集选择上，二者各有优劣。在指令解码方面，栈式ISA只需区分极少数的指令，因此解码电路规模相比于寄存器式的ISA更小。在读写操作方面，栈式ISA只需维护栈顶指针+栈内容，每次PUSH/POP时更新栈顶指针和元素即可，而寄存器式的ISA需要处理memory的寻址、存取等问题。但是同一程序的指令数量方面，寄存器式的ISA更占优势，寄存器式的ISA单条指令实现的功能更多。在并行化处理方面，寄存器式的ISA也比栈式ISA更有优势，因此考虑到利用FPGA或GPU进行硬件加速时，寄存器式的ISA更加友好。
因此，两种模式的ISA各具优点，对zkVM的电路效率也有不同的影响。

[soga061]

1. NO Memory, NO CPU 的 VM 架构如何帮助加速电路

这种 VM 架构通过去除内存和 CPU 抽象，简化了电路结构，从而加快了证明速度。它通常采用两种方式：

• Lookup table（如 Lasso）：将复杂指令的执行转化为查表操作，通过查找预先计算好的输入输出对来完成计算，避免在电路中模拟指令逻辑。
• Precompile 专用电路：针对某些特定操作（如哈希、签名等）提前编写好专用电路模块，避免使用通用电路执行，提高效率。

这类 VM 通常没有程序计数器、内存读写等传统结构，电路形式固定，结构简单，更适合用于 SNARK/STARK 系统。

---

2. 汇编级指令的作用

手写的汇编级指令电路通常比编译器自动生成的电路更高效。因为编译器生成的电路存在冗余和不必要的中间步骤，而手写可以直接控制每一步操作和变量的使用，减少约束数量，提高执行效率。

---

3. 如何在这样的 VM 中支持 CPU Profiler 和 Memory Profiler

CPU Profiler：使用一个寄存器或栈变量记录每条指令的执行开销。增加一个程序计数器（PC），每条指令携带一个常数值表示自己的资源消耗，执行时将其累加到 PC 中。

Memory Profiler：将内存划分为 page，每次访问记录所在页。通过增加一个计数器记录分页调入和调出操作的次数，便于衡量内存访问的资源消耗。这种分页方式也方便后续生成 Merkle 证明。

---

4. Register-based ISA 与 Stack-based ISA 对电路效率的影响

Register-based ISA 使用寄存器存储操作数和中间结果，支持随机访问，可以表达复杂的操作，但对应的电路结构更复杂，需要更多的约束，且 memory checking 成本较高。

Stack-based ISA 只能操作栈顶元素，指令形式更简单，电路结构更规整，但为了完成相同的功能，需要更多指令，trace 更长，证明时间更高。

因此，Register-based ISA 更适合表达复杂逻辑但电路成本高，Stack-based ISA 更适合简单线性逻辑但需要更长执行路径。