seo网站推广seo,个人业务网站带后台,海南网站公司,北京中高端网站建设公司1. 引言
本文主要参考#xff1a;
2023年9月ZKSummit10 Wei Dai 1k(x) Terry Chung 1k(x)分享视频 ZK10: Analysis of zkVM Designs - Wei Dai Terry Chung
当前有各种zkVM#xff0c;其设计思想各有不同#xff0c;且各有取舍#xff0c;本文重点对现有各z…1. 引言
本文主要参考
2023年9月ZKSummit10 Wei Dai 1k(x) Terry Chung 1k(x)分享视频 ZK10: Analysis of zkVM Designs - Wei Dai Terry Chung
当前有各种zkVM其设计思想各有不同且各有取舍本文重点对现有各zkVM设计进行分析。 zkVMs寒武纪大爆发
2020年之前的zkVM方案均是学术性的不具备实用性具体有 TinyRAM2013年vnTinyRAMBuffetGeppettoSpice等 2021年之后开始有商业化的zkVM方案特别是近两年来各种zkVM方案开始大爆发有 Cairo-VMRisc-ZerozkSyncVMpolygon zkEVMScroll zkEVMDelphinus zkWasmValidaTriton VMpowdr risc-vFluent zkWasmJoltpolygon Miden等
本文内容框架为
何为zkVMs为何需要zkVMszkVM设计性能分析 ISA性能分析Arithmetization性能分析Proof system性能分析 结论及开放性问题
2. 何为zkVMs为何需要zkVMs
2.1 为何需要zkVMs
zk Circuits vs. zkVMs
编程语言zk Circuits通常采用Circom、HDL等面向领域编程语言编写而zkVMs采用Rust、WASM、Risc-V、LLVM等高级通用语言编写。易用性及生态难于用zk Circuits来表达具有很多分支的复杂逻辑而zkVMs的程序有大量现有可靠的软件。性能zk Circuits性能较高因其对特定计算的约束进行了手动调优而zkVMs性能要慢约10~100倍。本文重点关注的是如何提升zkVMs的性能。
2.2 何为VMs
虚拟机采用指令集架构Instruction set architectureISA即
具有固定语义的一组有限数量的指令集。 虚拟机Virtual MachineVM的主要结构有
程序由指令序列组成。虚拟机每次仅读取程序中的一条指令。内存虚拟机主要工作为 1读取输入2对内存RAM读写3修改本地机器状态内部机器状态为Stack和或Registers。4写输出5中止执行
现有的VM/zkVM架构以及内部机器状态内存模型选型情况为
2.2.1 VM选择——Harvard架构 vs. Von Neumann架构
前序博客见
哈佛架构 VS 冯·诺依曼架构
在做zkVM设计时对应虚拟机VM架构通常需考虑在哈佛架构 和 冯·诺依曼架构 之间二选一
哈佛架构程序和内存分属不同区域。 优点为 无program loader仅lookup table需要额外的cycles。 缺点为 无JITper program setup需对每个程序做setup 冯·诺依曼架构程序在内存中。 优点为 通用更接近现代CPUs 缺点为 必须约束所取指令的正确性需要program loader来将程序加载到内存中 意味着需要更多cycles 2.2.2 VM内部机器状态内存模型选择——Stack, Register, vs. Direct Memory
虚拟机内部机器状态内存模型通常有3种选择
1Stack Machine通过访问stack top来进行数据移动指令更简单。如 EVMMiden-asmWasm 2Register Machine指令比Stack Machine要短但更复杂不过数据移动操作要少的多。如 RISC-V 3Direct Memory Machine无需数据移动zero data movement但有更多的读写操作。如 LLVM-IR 三种虚拟机内部机器状态内存模型的性能对比为
2.3 何为zkVMs
zkVM的目的在于
给定初始程序、初始程序输入、初始内部机器状态证明以上VM的有效执行。
zkVMs主要分为四大阶段 1Setup阶段根据参数如最大trace行数、固定列数、哈希函数等获得Proving key和Verification key。 2生成Witness阶段Executor根据程序和程序输入生成execution trace即witnesses。该execution trace中包含了 该程序的执行以及帮助约束该执行有效性的额外信息。 在生成Witness阶段还包括将程序切分以供后续并行证明的工作。 3Proving阶段根据execution trace和Proving key生成proof。 4Verification阶段根据proof和Verification key生成验证是否通过的结果Y/N。 3. zkVM设计性能分析
传统虚拟机中其效率分析的核心思想为
VM效率 约等于 程序中的指令数 x 执行单条指令用时 即 T ≈ P中指令数 × time instruction T\approx \text{P中指令数 }\times \frac{\text{time}}{\text{instruction}} T≈P中指令数 ×instructiontime
当使用zkVM证明某固定、抽象程序P时借鉴相同的思想
zkVM效率 约等于 程序中的指令数 x 单条指令的约束复杂度 x 单个约束证明用时 即zkVM证明用时 T T T以如下公式来表示 T ≈ P中指令数 × time instruction ≈ P中指令数 × Constraint complexity instruction × time Constraint complexity \begin{aligned}T \approx \text{P中指令数 }\times \frac{\text{time}}{\text{instruction}} \\ \approx\text{P中指令数 }\times \frac{\text{Constraint complexity}}{\text{instruction}} \times \frac{\text{time}}{\text{Constraint complexity}}\end{aligned} T≈P中指令数 ×instructiontime≈P中指令数 ×instructionConstraint complexity×Constraint complexitytime
其中的“约束”为
衡量某类proof system复杂度的单位。
取决于所采用的proof system类型具体的“约束复杂度”是指如
R1CS约束数具有固定配置的Plonk电路中的cells数具有固定depth的GKR电路中的wires数
为此在对zkVM做性能分析时将“程序中的指令数 x 单条指令的约束复杂度 x 单个约束证明用时”拆分成3个维度来分析其中
1程序中的指令数对应为ISAInstruction set architecture性能分析。2单条指令的约束复杂度对应为Arithmetization性能分析。3单个约束证明用时对应为Proof system性能分析。
3.1 ISA性能分析
ISAInstruction 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性能取决于所采用的机器内部状态内存模型
1Stack machines具有大量stack操作数据移动操作高达50%~60%。2Register machines 当寄存器压力低时其性能好。当寄存器压力高时~30%需要大量的数据移动。 3Direct 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 checkProduct 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有
Risc0MidenCairoValidaNockTritonVMzkSync VMPolygon zkEVM
这些STARK zkVMs的性能分析对比情况为【关键数据见最后2列】 现有的基于SNARK方案的zkVMs采用的都是基于Halo2的方案具体有
zkWasmPowdr的Risc-vScroll的zkEVM
这些SNARK zkVMs性能对比为
3.2.2.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 t t个segment时总的复杂度为
证明所有 t t t个具有 n n n-stepsegments复杂度证明所有 t − 1 t-1 t−1个 recursive proofs的复杂度
相应的关键路径为
1个segment proof log ( t ) \log(t) log(t)个recursive proofs 如Risc0中有多达50%的开销用于对“continuation” state进行序列化。
对比SNARKsPlonk、Folding/Accumulation、STARKs等方案的recursion threshold开销为
3.3 Proof system性能分析
Proof system性能分析关注的是
单个约束证明用时。
对于多项式承诺方案PCSPolynomial 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工具来对比各个方案的性能。 参考资料
[1] 2023年9月ZKSummit10 Wei Dai 1k(x) Terry Chung 1k(x)分享视频ZK10: Analysis of zkVM Designs - Wei Dai Terry Chung【1k(x)为早期密码学投资基金】
