1. 引言
前序博客有：
这是由三部分组成的ZK范式系列文章的第二部分：
- 1）第1部分：何为 zkVM？
- 2）第2部分：zkVM 设计权衡
- 3）第3部分：zkVM 自定义 ISA（指令集架构）
在ZK范式系列之zkVM介绍（1） 中，深入探讨了零知识证明（zero-knowledge proof，ZKP）和零知识虚拟机（zero-knowledge virtual machine，zkVM）的基础知识，并全面了解了 zkVM 流程。本文重点关注塑造 zkVM 的复杂设计选择和权衡。
追求最佳的 zkVM 设计取决于实现微妙的平衡。
- 这不仅涉及核心性能指标——正确性、安全性、零知识、信任假设、效率、速度和简洁性。
- 还需要仔细考虑开发人员的经验、更广泛的采用潜力和整体系统复杂性。
认识到这个复杂环境中固有的权衡至关重要。本文旨在分享从Lita团队的研究和设计历程中获得的宝贵见解。希望引发关于优化 zkVM 性能和可用性的讨论，最终为更广泛的采用铺平道路并加速可验证计算的创新。
2. 揭秘 zkVM 设计：A Bird’s Eye View鸟瞰图
在深入研究设计权衡的复杂性之前，先探讨一下 zkVM 的基本设计方面及其在 zkVM 系统和可验证计算过程中的相互关联角色。
zkVM 设计总体视图为：
其中：
- 1）ISA ↔ 虚拟机
指令集架构 (ISA) 是由物理计算机或虚拟机实现的计算模型。它规定了编译器生成并由虚拟机执行的机器代码的格式，包括虚拟机的机制，如寄存器布局和内存模型。 - 2）编程语言支持 ↔ 编译器
选择要支持的编程语言决定了哪些高级语言可以被编译成机器代码。 - 3）算术化 ↔ VM、证明者、验证者
算术化是将计算问题转换为代数问题的过程。这涉及：- i) 约束系统：通过多项式约束对虚拟机执行正确性进行编码的系统。
- ii) 域：用于在算术中表示和操作数据的代数结构。
- 4）证明系统 ↔ 证明者、验证者
证明系统是一种密码学协议，用于生成和验证简洁的零知识证明，证明者“知道”由算术定义的代数问题的解决方案。证明系统由两个主要组件构成：- i) 交互式预言机证明 (Interactive Oracle Proof，IOP)：证明者通过与预言机的交互说服验证者相信事实真实性的过程。证明者将多项式发送给预言机，验证者向预言机查询特定点的evaluations评估，预言机提供诚实的答案。
- ii) 多项式承诺方案 (Polynomial Commitment Scheme，PCS)：一种用于承诺多项式并随后在特定点证明其evaalutions评估的密码学协议。
- 5）模块化与单体架构 ↔ 整个 zkVM 系统
zkVM 的设计可以是模块化的（由可插入组件构建），也可以是单片式的（封闭的集成解决方案）。
以下各节剖析了上述方面的关键设计选择背后的动机。
3. zkVM 应该使用什么指令集架构？
ISA 是物理计算机和虚拟机的重要组成部分，定义了它们实现的计算模型。
3.1 ISA 解决的关键问题
ISA 解决的关键问题有：
- 1）内存模型：定义有多少个地址空间、它们的大小以及它们的功能。如：
- 冯诺依曼架构：用于读取、写入和执行的单一地址空间
- 哈佛架构：数据（可读和可写）和代码（可执行）的独立地址空间
- 32 位 vs. 64 位 ISA：32 位地址允许 2 32 2^{32} 232 个不同的地址，而 64 位地址允许 2 64 2^{64} 264 个不同的地址。
- 2）指令集：指定模型定义的基本操作，构成所有程序的构建块。
- 3）寄存器：详细说明寄存器的数量、它们可以保存的数据类型以及它们的用途。
- 4）调用约定：概述函数调用的协议，包括参数传递、返回值和寄存器管理。
用于 zkVM 的 ISA 大致可以分为：
- 通用 ISA
- 和 zk 优化 ISA
其中：
- 1）指令复杂度
支持更多指令或执行更多工作的指令的 ISA 往往会导致证明和验证的每条指令复杂度更高。但是，它们也会减少解决问题所需的指令数量。 - 2）对成本的净影响
ISA 复杂性对证明和验证成本的净影响并不直接。特定计算的总体成本可以量化为：每条指令的成本 x 指令数量。
增加 ISA 复杂度往往会增加每条指令的成本，同时减少所需的指令数量。根据具体情况，增加或减少复杂度可能是有益的，也可能是有害的。
3.2 zkVM ISA：选择与影响
总体而言，ISA 的选择会影响 zkVM 的效率、速度和简洁性，以及指令的复杂性。具有更复杂指令的 ISA 会减少所需的指令数量，但会增加每条指令的复杂性。
- zk 优化的 ISA 提供了针对零知识证明量身定制的潜在性能优势，
- 而通用 ISA 则利用现有的编译器技术和优化，从而降低开发复杂性并缩短上市时间。
3.3 Valida 为何选择定制 ISA？
Valida 使用针对高性能零知识证明优化的自定义 ISA，这与为电子计算机设计的标准 ISA 不同。
使用自定义 ISA 的缺点是：
- 需要 Lita 构建自己的编译器工具链，使开发人员能够使用熟悉的语言（如 C）编写代码并生成等效的 Valida ISA 机器代码。
这是一项具有挑战性的工作，但Lita团队相信，新的领域特定 ISA 对于促进向无信任系统转变至关重要。
4. zkVM 应该支持哪些编程语言？
zkVM 的编程语言大致可以分为两个维度：
- 抽象级别
- 和 领域特定性。
其中抽象级别可分为：
- 低级语言：这些语言代表了一种低抽象的计算模型，要求程序员详细说明如何根据目标计算环境支持的原语执行计算。
- 高级语言：这些语言提供了更高的抽象模型，允许程序员指定所需的结果，而无需准确指定如何执行计算。
领域特定性可分为：
- 通用语言：这些语言专为广泛的应用而设计，并不适合任何特定领域。
- 领域特定语言（Domain-Specific Language，DSL）：这些语言是为特定的应用领域而设计的，针对目标用例优化特性和功能。
4.1 与领域特定语言结合的优势
一些 zkVM 项目与领域特定语言相关，该语言是 zkVM 编程唯一支持的高级语言，具有以下优势：
- 1）支持具有最少功能集的一种语言可简化实施。
- 2）语言特性可以根据 zkVM 的功能进行定制，从而增强实现的简易性。
- 3）高级语言可以进行优化以实现最高效的 zkVM 实现。
此类 zkVM 的示例包括：
- Cairo zkVM（与 Cairo 语言相关）
- Lurk zkVM（与 Lurk 语言相关）
- Polygon zkEVM（与 Solidity 相关）。
4.2 支持多种通用高级语言的优势
另外，一些 zkVM 项目支持多种通用高级语言，提供以下好处：
- 1）开发人员可以使用功能丰富、熟悉的语言。
2）开发人员可以利用成熟的编译器技术，降低开发成本，并且无需重新实现就可以实现复杂的编译器优化。
这种方法的著名例子包括 Valida、RISC Zero 和 Succinct SP1。
4.3 zkVM 编程语言：选择和影响
选择合适的语言来支持会极大地影响解决复杂问题的难易程度以及开发人员的采用率。本质上，这归结为可用性和可访问性。理想情况下，zkVM 将支持每种语言，从而使 ZKP 真正具有通用性。然而，实现这一雄心勃勃的目标需要采取战略方法。
这些考虑与一般编程类似。如，与 C 相比，Rust 的严格内存模型最大限度地减少了安全漏洞，但代价是增加了复杂性并可能降低效率。最终，最佳选择取决于项目的具体目标和开发者社区的需求。在这些因素之间取得平衡对于构建既强大又易于访问的 zkVM 至关重要。
5. zkVM 应该使用什么样的算术化策略？
算术化是用代数形式对计算声明（如虚拟机的机器指令）进行编码的过程。在 zkVM 中，此过程涉及execution trace执行轨迹的表示和表达执行正确性的多项式约束。
通常，算术化中的事实是来自ring环（通常是有限域）上的向量空间的元素集合。这些事实可以表示为系数形式或点-值形式的多项式。
本节将重点讨论两个主要方面：
- 约束系统
- 和 域。
5.1 约束系统
在 zkVM 中，执行轨迹记录了虚拟机在每个计算步骤的状态，并将其转换为有限域元素的矩阵或向量。然后，执行的正确性被编码为这些元素之间的多项式方程或“约束”，从而允许使用代数技术解决计算问题。
- 1）Rank-1 Constraint System (R1CS)
R1CS（Rank-1 Constraint System）约束可以从更高级别的“电路”规范开始自动生成和优化，如 Circom 等工具所示。然而，约束规范通常可能比witness见证大得多，因此需要进行预处理才能有效管理复杂性。这可能会导致证明系统的复杂性大大增加，如 Groth16 的电路特定可信设置或 Spartan 的“sparse matrix commitments稀疏矩阵承诺”等协议所证明的那样。 - 2）Algebraic Intermediate Representation (AIR)
另一方面，AIR 约束提供了一种统一的表示，允许verifier直接使用简洁的格式，无需进行预处理。尽管有这个优势，AIR 约束需要精心设计，限制了自动化工具的使用。AIR的统一性也使它们不太适合描述没有虚拟机中常见的重复结构的计算。 - 3）PLONKish
PLONKish 约束是一种折衷方案，具有部分统一的结构。PLONKish利用非统一的“copy constraints 复制约束”和“selectors 选择器”以统一的方式表达更通用的计算类型。虽然这些约束需要预处理，但与 R1CS 相比，该过程更简单且成本更低。大多数现代基于 AIR 的证明系统（包括 plonky3/Valida）都采用了这些更通用的约束类型来增强其表现力。
5.1.1 通用协议与专用协议
AIR、R1CS 和 PLONKish 等约束系统是通用的，这意味着它们可以编码任意计算。这种灵活性使它们适用于广泛的应用。
然而，算术化过程也可以包含特殊声明，这些声明对难以或成本高昂的事实进行编码，以多项式方程来表达。如，确保一个向量包含与另一个向量相同的条目（可能顺序不同）可能是一项复杂的任务。这些特殊声明可以使用专门的IOP 作为子协议。有效地结合这些专门的声明可以显著提高 zkVM 的效率和复杂性。
5.2 域
环是一种代数结构，其特点是加法和乘法运算满足一些代数基本定律。在环中：
- 加法需要满足交换律、结合律、zero-canceling零消和可逆律。
- 乘法需要满足结合律、单元律和加法分配律。
根据定义，域是乘法可逆的环，这意味着域的每个非零元素都有一个乘法逆元。有限域是只有有限多个不同值的域。
设计 ZK 证明协议通常需要选择一个或多个环或域，通常涉及扩域以提供额外的安全性。
- 1）基于椭圆曲线的协议：基于椭圆曲线的 ZK 证明协议特别受系数域选择的影响。每条椭圆曲线都由有限域上的多项式方程定义，形成一个椭圆曲线群。协议从该群中选择一个点来生成素数阶循环子群，通常同构于有限域 Fp。
此设置允许从 Fp 的加法群到椭圆曲线群的同态，从而便于使用系数来自 Fp 的多项式实现零知识协议。这些协议通常需要较大的域（如 255 位）来确保安全性，这会带来计算开销，但会简化大数运算。对于较小的域（如 32 位或 64 位），可使用扩域来实现必要的安全级别，如 Plonky2 和 Plonky3 等协议所示。 - 2）最新进展：最新进展使 ZK 证明协议能够在各种类型的域和环上运行，从而提高了灵活性和性能。如，新协议可以在二进制域（如 Binius）、任意有限域（如 Brakedown）甚至非域的环（如 Rinocchio）上运行。这些发展允许选择最适合特定用例的环。然而，在当前的研究中，适应常用的环（如 32 位和 64 位整数环）仍然是一项挑战。
5.3 zkVM 算术化策略：选择与影响
选择正确的约束系统对于优化 zkVM 的效率和复杂性至关重要。R1CS、AIR 和 PLONKish 等系统在预处理要求和对不同类型计算的适用性方面提供了各种优点和权衡。域（和环）的选择是 zkVM 设计的一个基本方面，直接影响零知识证明的效率和安全性。
由于 zkVM 设计中的算术化策略千差万别，因此归纳其结果具有挑战性。然而，一个指标的改进往往会恶化另一个指标。如，更简洁通常会增加证明的复杂性。小型、安全、易于验证的证明很难生成，而更容易生成的证明往往更大、更难验证或更不安全。因此，没有普遍适用的最佳策略——用例和优先级将始终驱动设计选型。
6. 哪种证明系统最适合 zkVM？
zkVM 中的证明系统，通常是 (zk)-SNARK 或 (zk)-STARK，由两个主要组件构成：
- 1）交互式预言证明 (Interactive Oracle Proof，IOP)：在此协议中，证明者将witness见证的列表示为多项式，并通过在验证者随机抽样的“挑战点”上提供对这些多项式的评估来证明见证满足约束。
- 2）多项式承诺方案 (Polynomial Commitment Scheme，PCS)：该密码学协议允许证明者用简洁的“承诺”表示多项式，然后证明这些承诺的多项式在选定的查询点处计算出特定值。
6.1 交互式预言证明IOP
值得注意的是，“IOP”和“Polynomial IOP”经常互换使用。在 zkVM 中，所有 IOP 都涉及 SNARK 中的多项式预言机。在此上下文中，此处对 IOP 的所有引用均指 PIOP。
IOP 是证明者和验证者之间进行的交互式协议。该协议的每一轮包括：
- 证明者向验证者发送多项式“预言”。这些预言是验证者可以查询的多项式的抽象表示。查询涉及验证者向预言发送一个点，预言会以该点的多项式评估作为响应。
- 验证者随机抽取一些“挑战”值并将其发送给证明者。这些挑战值应来自足够大的域以提供加密安全性（如，100+ 位）。挑战包括验证者查询预言机的点和论证中使用的其他随机值。
这个涉及多轮交换的交互过程确保了证明者关于witness正确性的断言受到验证者的严格检查。
交互式预言机证明流程示意图为：
6.1.1 构建 zk-SNARK
IOP 和 PCS 可以结合起来构建 zk-SNARK：zero-knowledge succinct non-interactive argument of knowledge 零知识简洁非交互式知识论证。
- 用承诺代替预言：证明者不再在 IOP 中发送抽象的预言，而是使用 PCS 来“承诺”多项式，并向验证者发送这些简洁的承诺。
- 使用 PCS 构建Evaluation Proofs评估证明：当验证者向多项式预言机查询其在某一点的评估时，证明者使用 PCS 构建评估证明并将其与评估一起发送给验证者。
- Fiat-Shamir 启发式：为了使论证非交互式，证明者应用了 Fiat-Shamir 启发式。证明者不会要求验证者抽取随机挑战值，而是根据承诺评估密码学哈希函数。此启发式将密码学哈希函数建模为“随机预言机”，这意味着哈希函数的输出无法与依赖于输入的随机值流区分开来。
6.1.2 IOP 和约束系统
IOP 旨在证明特定的约束系统，通常依赖于这些系统的特定特性。IOP与某些有限域和多项式特性兼容，如“FFT 友好”。
可以使用各种 IOP 来证明给定的约束系统，每种 IOP 都有不同的优点和缺点。对于每个常见的约束系统，都有已知的单变量和multilinear IOP 来证明它们。算术化与这些考虑因素无关，IOPs本质上不是多线性的或单变量的。
根据所涉及的多项式是否有一个或多个变量，IOP 分为：