zkVM专辑 | 揭秘zkVM的设计

文摘 2024-07-09 12:28 新加坡

1. 鸟瞰图

在深入研究设计权衡的复杂性之前，让我们先探讨一下 zkVM 的基本设计方面及其在 zkVM 系统和可验证计算过程中的相互关联角色。

指令集架构 ↔ 虚拟机

指令集架构 (ISA) 是由物理计算机或虚拟机实现的计算模型。它规定了编译器生成并由虚拟机执行的机器代码的格式，包括虚拟机的机制，例如寄存器布局和内存模型。

编程语言支持 ↔ 编译器

选择要支持的编程语言决定了哪些高级语言可以编译成机器代码。

算术化 ↔ 虚拟机、证明者、验证者

算术化是将计算问题转换为代数问题的过程。这涉及：

约束系统：通过多项式约束对虚拟机执行正确性进行编码的系统。
域：用于在算术中表示和操作数据的代数结构。

证明系统 ↔ 证明者、验证者

证明系统是一种加密协议，用于生成和验证简洁的零知识证明，证明者“知道”由算术定义的代数问题的解决方案。它由两个主要组件构成：

i) 交互式预言机证明 (IOP)：证明者通过与预言机的交互说服验证者相信事实真实性的过程。证明者将多项式发送给预言机，验证者向预言机查询特定点的评估，预言机提供诚实的答案。

ii) 多项式承诺方案 (PCS)：一种用于承诺多项式并在特定点证明其评估的加密协议。

模块化与单体架构 ↔ 整个 zkVM 系统

zkVM 的设计可以是模块化的（由可插入组件构建），也可以是单片的（封闭的集成解决方案）。

以下各节剖析了上述方面的关键设计选择背后的动机。

2. zkVM 应该使用什么指令集架构？

指令集架构 (ISA) 是物理计算机和虚拟机的重要组成部分，定义了它们实现的计算模型。

指令集架构 (ISA) 解决的关键问题

i. 内存模型：定义有多少个地址空间、它们的大小以及它们的功能。例如：

冯诺依曼架构：用于读取、写入和执行的单一地址空间
哈佛架构：数据（可读和可写）和代码（可执行）的独立地址空间
32 位与 64 位 ISA：32 位地址允许 2^32 个不同的地址，而 64 位地址允许 2^64 个不同的地址。

ii. 指令集：指定模型定义的基本操作，构成所有程序的构建块。

iii. 寄存器：详细说明寄存器的数量、它们可以保存的数据类型以及它们的用途。

iiii. 调用约定：概述函数调用的协议，包括参数传递、返回值和寄存器管理。

用于 zkVM 的指令集架构 (ISA) 大致可以分为通用 ISA 和 zk 优化 ISA，基于以下几个方面考量：

指令复杂度

支持更多指令或执行更多工作的指令的 ISA 往往会导致证明和验证的每条指令复杂度更高。但是，它们也会减少解决问题所需的指令数量。

对成本的净影响

指令集架构 (ISA) 复杂性对证明和验证成本的净影响并不直接。特定计算的总体成本可以量化为：每条指令的成本 x 指令数量。

增加 ISA 复杂度往往会增加每条指令的成本，同时减少所需的指令数量。根据具体情况，增加或减少复杂度可能是有益的，也可能是有害的。

zkVM ISA：选择与影响

总体而言，指令集架构 (ISA) 的选择会影响 zkVM 的效率、速度和简洁性，以及指令的复杂性。具有更复杂指令的指令集架构 (ISA) 会减少所需的指令数量，但会增加每条指令的复杂性。zk 优化的指令集架构 (ISA) 提供了针对零知识证明量身定制的潜在性能优势，而通用指令集架构 (ISA) 则利用现有的编译器技术和优化，从而降低开发复杂性并缩短上市时间。

3. zkVM 应该支持哪些编程语言？

zkVM 的编程语言大致可以分为两个维度：抽象级别和领域特定性。

抽象级别

低级语言：这些语言代表了一种低抽象的计算模型，要求程序员详细说明如何根据目标计算环境支持的原语执行计算。
高级语言：这些语言提供了更高的抽象模型，允许程序员指定所需的结果，而无需准确指定如何执行计算。

领域特定性

通用语言：这些语言专为广泛的应用而设计，并不适合任何特定领域。
领域特定语言：这些语言是为特定的应用领域而设计的，针对目标用例优化特性和功能。

与领域特定语言结合的优势

一些 zkVM 项目与领域特定语言相关，该语言是 zkVM 编程唯一支持的高级语言，具有以下优势：

支持具有最少功能集的一种语言可简化实施。
语言特性可以根据 zkVM 的功能进行定制，从而增强实现的简易性。
高级语言可以进行优化以实现最高效的 zkVM 实现。

此类 zkVM 的示例包括：Cairo zkVM（与 Cairo 语言相关）、Lurk zkVM（与 Lurk 语言相关）、Polygon zkEVM（与 Solidity 相关）和 Aleo zkVM（与 Leo 语言有关）。

支持多种通用高级语言的优势

一些 zkVM 项目支持多种通用高级语言，提供以下好处：

开发人员可以使用功能丰富、熟悉的语言。
开发人员可以利用成熟的编译器技术，降低开发成本，并且无需重新实现就可以实现复杂的编译器优化。

zkVM 编程语言：选择和影响

选择合适的语言来支持会极大地影响解决复杂问题的难易程度以及开发人员的采用率。本质上，这归结为可用性和可访问性。理想情况下，zkVM 将支持每种语言，从而使 ZKP 真正具有通用性。然而，实现这一雄心勃勃的目标需要采取战略方法。

这些考虑与一般编程类似。例如，与 C 相比，Rust 的严格内存模型最大限度地减少了安全漏洞，但代价是增加了复杂性并可能降低效率。最终，最佳选择取决于项目的具体目标和开发者社区的需求。在这些因素之间取得平衡对于构建既强大又易于访问的 zkVM 至关重要。

4. zkVM 应该使用什么样的算术策略？

算术化是用代数形式对计算语句（如虚拟机的机器指令）进行编码的过程。在 zkVM 中，此过程涉及执行轨迹的表示和表达执行正确性的多项式约束。

通常，算术化中的事实是来自环（通常是有限域）上的向量空间的元素集合。这些事实可以表示为系数形式或点求值形式的多项式。

我们将重点讨论两个主要方面：约束系统和字段。

4.1 约束系统

在 zkVM 中，执行轨迹记录了虚拟机在每个计算步骤的状态，并将其转换为有限域元素的矩阵或向量。然后，执行的正确性被编码为这些元素之间的多项式方程或“约束”，从而允许使用代数技术解决计算问题。

i. R1CS

R1CS（等级 1 约束系统）约束可以从更高级别的“电路”规范开始自动生成和优化，如 Circom 等工具所示。然而，约束规范通常可能比见证大得多，因此需要进行预处理才能有效管理复杂性。这可能会导致证明系统的复杂性大大增加，如 Groth16 的电路特定可信设置或 Spartan 的“稀疏矩阵承诺”等协议所证明的那样。

ii. AIR

另一方面，AIR 约束提供了一种统一的表示形式，允许验证器直接使用简洁的格式，无需进行预处理。尽管有这个优势，但 AIR 约束需要精心设计，限制了自动化工具的使用。它们的统一性也使它们不太适合描述没有虚拟机中常见的重复结构的计算。

ii. PLONKish

PLONKish 约束是一种折衷方案，具有部分统一的结构。它们利用非统一的“复制约束”和“选择器”以统一的方式表达更通用的计算类型。虽然这些约束需要预处理，但与 R1CS 相比，该过程更简单且成本更低。大多数现代基于 AIR 的证明系统（包括 plonky3/Valida）都采用了这些更通用的约束类型来增强其表现力。

通用协议与专用协议

AIR、R1CS 和 PLONKish 等约束系统具有通用性，这意味着它们可以对任意计算进行编码。这种灵活性使它们适用于广泛的应用。

然而，算术化过程也可以包含特殊语句，这些语句对难以或成本高昂的事实进行编码，以多项式方程来表达。例如，确保一个向量包含与另一个向量相同的条目（可能顺序不同）可能是一项复杂的任务。这些特殊语句可以使用专门的。

IOP 作为子协议。有效地结合这些专门的语句可以显著提高 zkVM 的效率和复杂性。

4.2 字段

环是一种代数结构，其特点是加法和乘法运算满足一些代数基本定律。在环中，加法需要满足交换律、结合律、零消和可逆律。环中的乘法需要满足结合律、单元律和加法分配律。根据定义，域是乘法可逆的环，这意味着域的每个非零元素都有一个乘法逆元。有限域是只有有限多个不同值的域。

设计 ZK 证明协议通常需要选择一个或多个环或字段，通常涉及扩展字段以提供额外的安全性。

基于椭圆曲线的协议：基于椭圆曲线的 ZK 证明协议特别受系数域选择的影响。每条椭圆曲线都由有限域上的多项式方程定义，形成一个椭圆曲线群。协议从该群中选择一个点来生成素数阶循环子群，通常同构于有限域 Fp。

这种设置允许从 Fp 的加法群到椭圆曲线群的同态，从而便于使用系数来自 Fp 的多项式实现零知识协议。这些协议通常需要较大的字段（例如 255 位）来确保安全性，这会带来计算开销，但会简化大数运算。对于较小的字段（例如 32 位或 64 位），可使用扩展字段来实现必要的安全级别，如 Plonky2 和 Plonky3 等协议所示。

最新进展：最新进展使 ZK 证明协议能够在各种类型的字段和环上运行，从而提高了灵活性和性能。例如，新协议可以在二进制字段（例如 Binius）、任意有限字段（例如 Brakedown）甚至非字段的环（例如 Rinocchio）上运行。这些发展允许选择最适合特定用例的环。然而，在当前的研究中，适应常用的环（如 32 位和 64 位整数环）仍然是一项挑战。

zkVM 算术化策略：选择与影响

选择正确的约束系统对于优化 zkVM 的效率和复杂性至关重要。R1CS、AIR 和 PLONKish 等系统在预处理要求和对不同类型计算的适用性方面提供了各种优点和权衡。字段（和环）的选择是 zkVM 设计的一个基本方面，直接影响零知识证明的效率和安全性。

由于 zkVM 设计中的算法策略千差万别，因此归纳其结果具有挑战性。然而，一个指标的改进往往会恶化另一个指标。例如，更简洁通常会增加证明的复杂性。小而安全、易于验证的证明很难生成，而更容易生成的证明往往更大、更难验证或更不安全。因此，没有普遍适用的最佳策略；用例和优先级将始终驱动设计选择。

5. 哪种证明系统最适合 zkVM？

zkVM 中的证明系统，通常是 (zk)-SNARK 或 (zk)-STARK，由两个主要组件构成：

交互式预言证明 (IOP)：在此协议中，证明者将见证的列表示为多项式，并通过在验证者随机抽样的“挑战点”上提供对这些多项式的评估来证明见证满足约束。
多项式承诺方案 (PCS)：该加密协议允许证明者用简洁的“承诺”表示多项式，然后证明这些承诺的多项式在选定的查询点处计算出特定值。

5.1 交互式预言证明

值得注意的是，“IOP”和“多项式 IOP”经常互换使用。在 zkVM 中，所有 IOP 都涉及 SNARK 中的多项式预言机。在此上下文中，此处对 IOP 的所有引用均指 PIOP。

IOP 是证明者和验证者之间进行的交互式协议。该协议的每一轮包括：

证明者向验证者发送多项式“预言”。这些预言是验证者可以查询的多项式的抽象表示。查询涉及验证者向预言发送一个点，预言会以该点的多项式评估作为响应。
验证者随机抽取一些“挑战”值并将其发送给证明者。这些挑战值应来自足够大的字段以提供加密安全性（例如 100+ 位）。挑战包括验证者查询预言机的点以及论证中使用的其他随机值。

这个涉及多轮交换的交互过程确保了证明者关于证人正确性的断言受到验证者的严格检查。

构建 zk-SNARK

IOP 和 PCS 可以结合起来构建 zk-SNARK：零知识简洁非交互式知识论证。

用承诺代替预言：证明者不再在 IOP 中发送抽象的预言，而是使用 PCS 来“承诺”多项式，并向验证者发送这些简洁的承诺。
使用 PCS 构建评估证明：当验证者查询多项式预言机在某一点的评估时，证明者使用 PCS 构建评估证明并将其与评估一起发送给验证者。
Fiat-Shamir 启发式：为了使论证非交互式，证明者应用了 Fiat-Shamir 启发式。证明者不会要求验证者抽取随机质询值，而是根据承诺评估加密哈希函数。此启发式将加密哈希函数建模为“随机预言机”，这意味着哈希函数的输出无法与依赖于输入的随机值流区分开来。

IOPs 和约束系统

IOPs 旨在证明特定的约束系统，通常依赖于这些系统的特定特性。它们与某些有限域和多项式特性兼容，例如“FFT 友好”。

可以使用各种 IOPs 来证明给定的约束系统，每种 IOPs 都有不同的优点和缺点。对于每个常见的约束系统，都有已知的单变量和多线性 IOPs 来证明它们。算法与这些考虑因素无关；它们本质上不是多线性的或单变量的。

根据所涉及的多项式是否有一个或多个变量，IOPs 分为单变量类型和多线性类型。

单变量 IOPs

次数小于 N 的单变量多项式唯一地对应于长度为 N 的迹向量 t，即 t [ i ] = p ( x i )，其中 D = x ii = 1 N 是域 𝔽 的一组指定元素（D通常是乘法子群）。

多线性 IOPs

多线性多项式是 n 个变量的多项式，每个变量的次数最多为 1。它们唯一地对应于长度为N = 2 n的迹向量t，要求t [ i ] = p ( ϵ 1 , …, ϵ n )，其中 [ ϵ 1 , …, ϵ n ] 是整数i的二进制表示。

选择单变量 IOPs 还是多线性 IOPs，决定了可以使用哪种多项式承诺方案。从历史上看，单变量 IOP 更为常见，部分原因是已知的具有恒定大小证明的多项式承诺方案只有单变量方案。然而，多线性多项式承诺方案近年来取得了重大进展。

可分性论证与基于求和检查的方法

为了证明多项式方程在大集合中的每个点（即执行跟踪的每一行）都成立，单变量 IOPs 通常使用可分性论证，而多线性 IOPs 则使用求和检查协议。每种方法都依赖于不同的代数技术，这些技术在不同的设置之间不能直接转换，从而导致重要的性能差异。

求和校验协议（多线性 IOPs）

求和校验协议通常更快、更灵活。证明者只需要执行一些字段操作，主要是计算向量的线性组合，这些操作与见证大小 NN 成线性比例。除了编码见证本身的预言之外，这种方法不需要向验证者发送其他预言。

可分性论证（单变量 IOPs）

另一方面，单变量 IOPs 中使用的可分性论证通常涉及计算 FFT（快速傅里叶变换），这需要 Nlog⁡(N)Nlog(N) 个场运算。此外，证明者必须向验证者发送辅助多项式的预言，这使得该过程的计算量更大。

5.2 多项式承诺方案

承诺方案是一种加密协议，其中证明者创建数据的简洁指纹（承诺）并证明有关它的事实，而无需透露数据本身。多项式承诺方案将其扩展到多项式，允许证明者承诺多项式，然后在特定点证明其评估。

多项式承诺方案大致可分为几类。虽然这种分类并不详尽，但它提供了不同类型的 PCS 的全面概述。

i. 系数环

PCSs 使用多项式进行操作，其系数取自特定环，通常是有限域。系数环的选择会影响多项式约束系统的复杂性，较大的域会简化约束，但会增加计算开销。

例如，Cairo zkVM 设计其源语言和 ISA 以与 PCS 最自然的系数环保持一致。

ii. 单变量与多线性

单变量 PCS：致力于单变量多项式，不能用于多线性协议。提供恒定大小的证明（例如 KZG）。

多线性 PCS：致力于多线性多项式，可用于单变量协议。提供更高效的编码和线性证明复杂性。

iii. 单次 vs. 批量

单次 PCS：致力于单一多项式并证明单点评估。

批量 PCS：提交多个多项式并同时证明多个点评估，在复杂的 SNARK 协议中很有用。

iiii. 基于椭圆曲线与基于哈希

基于椭圆曲线的 PCS：涉及通过从向量空间到椭圆曲线群的同态进行承诺，如 KZG 等方案所示。主要优点是可以减少证明量。

基于哈希的 PCS：利用哈希（例如基于 FRI 的 PCS），降低证明复杂度和有限域运算。通常，KZG PCS 的验证复杂度低于基于 FRI 的 PCS，而后者的验证复杂度又低于内积参数。

性能注意事项

zk-SNARK 的简洁性涉及三个关键指标：证明大小、验证者时间复杂度和验证者空间复杂度，这三个指标对于验证第 1 层区块链上的 SNARK 证明至关重要。第 1 层区块链由于其高度重复的计算而具有严格的资源限制，因此需要严格限制交易大小和计算复杂度。

证明大小、验证器时间复杂度和验证器空间复杂度可以是常数、次线性或线性的。例如，KZG PCS 提供恒定指标，但需要可信设置。虽然 KZG PCS 是简洁的理想选择，但它们需要大量设置，而证明复杂度较低的 PCS 通常会产生更大、更难验证的证明。基于 FRI 的 PCS 虽然证明复杂度较低，但与 KZG PCS 相比，其证明更大、更难验证。

zkVM 证明系统：选择与影响

zkVM 中 IOPs 的设计和选择涉及计算效率、证明大小和复杂性的权衡，影响证明系统的整体性能。单变量和多线性 IOP 之间的选择会显著影响所使用的多项式承诺方案。由于 KZG 等恒定大小证明方案，单变量 IOP 传统上更为常见，而多线性 IOP 因其高效编码和线性证明复杂性而越来越受欢迎。单变量 IOP 通常依赖于可分性参数，这需要大量计算，而多线性 IOP 使用和校验协议，以更少的要求提供更快、更灵活的操作。

如果优先考虑的是低证明复杂度、不需要可信设置过程和可管理的证明大小，那么基于多线性哈希的 PCS 目前是理想的选择。相反，如果主要关注的是最小化证明大小和验证复杂度，并且可信设置过程是可以接受的，那么 KZG PCS 更合适。随着研究的进展和新进展的出现，这些评估可能会不断发展，需要不断重新评估和调整。

6. zkVM 应该是模块化还是单片化？

zkVM 的设计可以采用两种基本方式：模块化或单片化。

模块化与单片式 zkVM：选择与影响

模块化 zkVM 提供广泛的定制功能，允许添加针对特定用例定制的指令，从而减少指令数量并减少证明者的工作量。然而，这种灵活性是以增加复杂性和维护费用为代价的。相比之下，单片 zkVM 由于其集中式、封闭式架构而更易于管理和维护，但它们的灵活性较低，并且仅限于集中式指令。

在模块化和单片式 zkVM 之间做出选择，取决于项目的目标以及在定制化和易于管理之间所需的平衡。

PS：本文大部分来自于对于专业网站的搜集整理撰稿。

ZKT 纯GPU锄头，第一梯队，仅限大算力合作！

ZKT Aleo-ASIC芯片机整机预售中，台积电代工！

2024年全球ZK峰会 Aleo-ASIC 最有竞争力品牌！

感兴趣的小伙伴扫码联系，仅限大客户和渠道！

全网最全Aleo中文WiKi

zkVM专辑 | 什么是 zkVM？