1. 引言
当前有各种zkVM，其设计思想各有不同，且各有取舍，本文重点对现有各zkVM设计进行分析。
zkVMs寒武纪大爆发：
2020年之前的zkVM方案均是学术性的，不具备实用性，具体有：
TinyRAM（2013年）
vnTinyRAM
Buffet
Geppetto
Spice等
2021年之后开始有商业化的zkVM方案，特别是近两年来各种zkVM方案开始大爆发，有：
Cairo-VM
Risc-Zero
zkSyncVM
polygon zkEVM
Scroll zkEVM
Delphinus zkWasm
Valida
Triton VM
powdr risc-v
Fluent zkWasm
Jolt
polygon Miden等
2. 何为zkVMs？为何需要zkVMs？
2.1 何为VMs？
虚拟机采用指令集架构（Instruction set architecture，ISA），即：
具有固定语义的一组有限数量的指令集。
虚拟机（Virtual Machine，VM）的主要结构有：
程序：由指令序列组成。虚拟机每次仅读取程序中的一条指令。
内存
虚拟机：主要工作为：
1）读取输入
2）对内存（RAM）读写
3）修改本地机器状态：内部机器状态为：Stack和（或）Registers。
4）写输出
5）中止执行
现有的VM/zkVM架构，以及内部机器状态内存模型，选型情况为：
2.1.1 VM选择——Harvard架构 vs. Von Neumann架构
在做zkVM设计时，对应虚拟机（VM）架构通常需考虑在哈佛架构和冯·诺依曼架构之间二选一：
哈佛架构：程序和内存分属不同区域。
优点：
无program loader
仅lookup table需要额外的cycles。
缺点：
无JIT
per program setup（需对每个程序做setup）
冯·诺依曼架构：程序在内存中。
优点：
通用，更接近现代CPUs
缺点：
必须约束所取指令的正确性
需要program loader（来将程序加载到内存中）， 意味着需要更多cycles
2.1.2 VM内部机器状态内存模型选择——Stack, Register, vs. Direct Memory
虚拟机内部机器状态内存模型，通常有3种选择：
1）Stack Machine：通过访问stack top来进行数据移动，指令更简单。如：
EVM
Miden-asm
Wasm
2）Register Machine：指令比Stack Machine要短，但更复杂，不过数据移动操作要少的多。如：
RISC-V
3）Direct Memory Machine：无需数据移动（zero data movement），但有更多的读写操作。如：
LLVM-IR
三种虚拟机内部机器状态内存模型的性能对比为：
2.2 何为zkVMs？
zkVM的目的在于：
给定初始程序、初始程序输入、初始内部机器状态，证明以上VM的有效执行。
zkVMs主要分为四大阶段：
1）Setup阶段：根据参数（如最大trace行数、固定列数、哈希函数等），获得Proving key和Verification key。
2）生成Witness阶段：（Executor）根据程序和程序输入，生成execution trace（即witnesses）。该execution trace中包含了：
该程序的执行
以及，帮助约束该执行有效性的额外信息。
在生成Witness阶段，还包括将程序切分以供后续并行证明的工作。
3）Proving阶段：根据execution trace和Proving key，生成proof。
4）Verification阶段：根据proof和Verification key，生成验证是否通过的结果Y/N。
2.3 为何需要zkVMs？
zk Circuits vs. zkVMs：
编程语言：zk Circuits通常采用Circom、HDL等面向领域编程语言编写；而zkVMs采用Rust、WASM、Risc-V、LLVM等高级通用语言编写。
易用性及生态：难于用zk Circuits来表达具有很多分支的复杂逻辑；而zkVMs的程序有大量现有可靠的软件。
性能：zk Circuits性能较高，因其对特定计算的约束进行了手动调优；而zkVMs性能要慢约10~100倍。本文重点关注的是如何提升zkVMs的性能。
3. zkVM设计性能分析
传统虚拟机中，其效率分析的核心思想为：
VM效率 约等于 （程序中的指令数 x 执行单条指令用时），即：
当使用zkVM证明某固定、抽象程序P时，借鉴相同的思想：
zkVM效率 约等于 （程序中的指令数 x 单条指令的约束复杂度 x 单个约束证明用时），即：zkVM证明用时T以如下公式来表示：
其中的“约束”为：
衡量某类proof system复杂度的单位。
取决于所采用的proof system类型，具体的“约束复杂度”是指，如：
R1CS约束数
具有固定配置的Plonk电路中的cells数
具有固定depth的GKR电路中的wires数
为此，在对zkVM做性能分析时，将“（程序中的指令数 x 单条指令的约束复杂度 x 单个约束证明用时）”拆分成3个维度来分析，其中：
1）程序中的指令数：对应为ISA（Instruction set architecture）指令集性能分析。
2）单条指令的约束复杂度：对应为Arithmetization算术性能分析。
3）单个约束证明用时：对应为Proof system零知识证明系统性能分析。
3.1 ISA指令集性能分析
ISA（Instruction set architecture）指令集性能分析，主要关注的是程序中的指令数。
传统ISA和“ZK ISA”是针对不同的场景进行了优化：
传统ISA为：
内存局限性：处理器具有内存上限。
程序size（如压缩）：无法有太多通用寄存器。
执行速度
"ZK ISA"为：
每个cycle，一条指令：具有指令上限。
指令大小的影响小：指令可包含更多信息，如引用更多寄存器或本地变量。
证明速度或性能。
以在软件中实现SHA256 one-round压缩函数 所需的指令数，为例，不同虚拟机对比情况为：
其中：
前三种（EVM、Miden-asm、Wasm）为stack machine，具有相对更多的local data movement操作。
RISC-V为register machine，具有少得多的local data movement操作。
LLVM-IR为direct memory模式，具有虚拟寄存器，从而具有zero data movement。
由此可知，实际的ISA性能，取决于所采用的机器内部状态内存模型：
1）Stack machines：具有大量stack操作（数据移动操作）（高达50%~60%）。
2）Register machines：当寄存器压力低时，其性能好。当寄存器压力高时（~30%），需要大量的数据移动。
3）Direct memory machines：消除了local data movement，即无需数据移动。Caveat（警告）：可能会导致更复杂的arithmetization
3.2 Arithmetization算术性能分析
Arithmetization算术性能分析，关注的是：
单条指令的约束复杂度。
实际在对Arithmetization性能分析时，主要分为2大块：
Segment性能分析
“Recursion复杂度”+“Continuation复杂度” 性能分析。
3.2.1 Segment性能分析
算术化是指将对程序执行segment的约束，转换为：
Permutation check、
Gate check、
lookup、
Copy check
等组合，然后进一步转换为2大类子约束表达：
Zero check
Product check
取决于具体所采用的PolyIOP方案，后续的方案以及影响性能的关键运算也有所不同：
单变量PolyIOP：相关方案有Plonk、STARK、Plookup等，对应为Quotient check，影响性能的关键运算为FFT。
多变量PolyIOP：相关方案有GKR、HyperPlonk、Jolt/Lasso、ProtoStar等，对应为Sum check，影响性能的关键运算为MLE。
以基于STARK的zkVM为例，将程序正确执行的execution trace切分为多个segment。其Prover的证明用时由：
派生多项式，以及对多项式进行承诺
所主导。根据RISC0、Triton、Plonky2所提供的数据：
经典的STARK Provers有60%~80%的证明时长用于派生和commit多项式。
3.2.1.1 STARK VMs vs. SNARK VMs
当前基于STARK方案的zkVM有：
Risc0
Miden
Cairo
Valida
Nock
TritonVM
zkSync VM
Polygon zkEVM
这些STARK zkVMs的性能分析对比情况为：【关键数据见最后2列】
现有的基于SNARK方案的zkVMs，采用的都是基于Halo2的方案，具体有：
zkWasm
Powdr的Risc-v
Scroll的zkEVM
这些SNARK zkVMs性能对比为：
3.2.1.2 segment性能提升措施
为提升Arithmetization segment性能，其目标应为：
尽可能使，单个指令的committed cells，数量最少。
具体措施有：
1）移除重复的cells。仅对每个指令的“state change”进行commit。
对“non-local” 数据/计算，采用permutation/lookups。
powdr risc-v中的寄存器（编码在列中），占约50%的列。
2）采用表达性更好的IOP arguments：
fixed lookup tables可改进bitwise运算性能。
改进关键IOP原语的性能，如在单个table中查找 M M M个列集合，采用更好的lookup argument会具有更好的性能：
3）具有“flexible area”的co-processors，有助于改进单个指令开销。
3.2.2 “Recursion复杂度”和“Continuation复杂度” 性能分析
当将1个完整的execution trace切分为t个segment时，总的复杂度为：
证明所有t个（具有n-step）segments复杂度
证明所有t-1个 recursive proofs的复杂度
相应的关键路径为：
1个segment proof
log(t)个recursive proofs
如Risc0中，有多达50%的开销用于对“continuation” state进行序列化。
对比SNARKs（Plonk）、Folding/Accumulation、STARKs等方案的recursion threshold开销为：
3.3 Proof system零知识证明系统性能分析
Proof system零知识证明系统性能分析，关注的是：
单个约束证明用时。
对于多项式承诺方案（PCS，Polynomial Commitment Scheme），基于FRI的PCS性能要由于基于MSM的多项式承诺方案性能：【其中y轴表示的是每秒承诺的域元素数】
4.结论及开放性问题
关于ISA指令集的开放性问题有：
如何将现有工具应用到zk-efficient ISA中？
可进一步消除data movement么？如对memcpy进行direct argument？
关于Arithmetization算术化的开放性问题有：
降低单个指令的复杂度
降低递归（recursion）复杂度
“doubly-fast”哈希函数（如Poseidon2、Tip5、XHash{8,12}、Monolith等）
降低"continuation"复杂度
关于proof system/PCS的开放性问题有：
FFT、MLE、PCS应封装为库，项目方可受益于这些原语的更好实现。
更好的bench工具，来对比各个方案的性能。
PS：本文大部分翻译整理自ZKSummit10 ZK10: Analysis of zkVM Designs - Wei Dai & Terry Chung【1k(x)为早期密码学投资基金】
ZKT 纯GPU锄头，第一梯队，仅限大算力合作！
ZKT Aleo-ASIC，芯片和芯片机预售中，台积电代工！
2024年全球ZK峰会 Aleo-ASIC 最有竞争力品牌！
感兴趣的小伙伴扫码联系，仅限大客户和渠道！
全网最全Aleo中文WiKi
重点解析Aleo基金会执行董事Alex在“ZK硬件加速的未来”中的发言！
Aleo最新十年区块产出奖励模型推演（Testnet Beta）
测试网Beta激励 | Aleo全网算力超过1亿算力，近期要点解读！
Aleo主网倒计时 | Aleo最新Puzzle谜题算法深度解析！
Aleo主网倒计时 | 测试网Beta发布，距离主网还有多远？
重磅分析！以太坊真的会开倒车转回“PoW”么？还是会效仿Aleo模式？
Aleo主网倒计时 | Aleo Systems 公司 CEO Alex Pruden 卸任感言
重磅！Aleo初始经济模型重大更新！主网上线时间是否有变化？
ALEO 问答集锦 | 关于质押者、证明者和验证者官方最新解答
ALEO 问答集锦 | Aleo积分到底有什么用？区块奖励重大变化？
重磅分析！为什么说FPGA或者ZK通用服务器在Aleo项目上机会是零？
