超立方体 IR：零知识证明系统的基础

在这篇文章中，我们将介绍我们正在进行的零知识证明（ZKP）专用硬件方面的工作。 在 Cysic，我们正在开发一种专为 ZKP 工作负载设计的定制证明加速芯片。 该芯片利用非传统的空间架构来最大化并行性并提高多项式计算的吞吐量。 此外，多个芯片可以高速互连，以创建可扩展的多核系统，从而显着提高性能和内存容量，以支持更大、更复杂的证明任务。

介绍

ZK 是一种密码学概念，它允许一方（证明者）向另一方（验证者）证明某个陈述是真实的，而无需泄露除该陈述本身真实性之外的任何其他信息。 这一原则是保护隐私技术和安全身份验证的基础。 在过去的十年中，我们目睹了 ZKP 技术的理论和实践方面的重大发展。 开发高性能 ZKP 证明系统的一个主要障碍是高性能代码缺乏可移植性。 这种缺乏可移植性表现在以下几个方面：

• 由于重写高性能后端的高成本，它阻碍了密码学社区快速采用新设计。
• 它阻止现有的证明系统快速适应不同的硬件，例如 CPU、GPU（包括 Nvidia 的 CUDA、Apple 的 Metal 和 AMD 的 ROCm），更重要的是，即将推出的 ZKP 专用加速芯片。
• 由于硬件公司需要承担调整每个证明系统软件后端的巨大成本，因此 ZKP 硬件加速器制造商很难推广其产品。

理想情况下，ZKP 社区应该拥有一个公共领域特定的中间表示（IR），类似于 AI 社区中的 TorchScript，作为证明系统开发团队和高性能硬件团队之间的桥梁。 在这里，我们介绍 HyperCube IR，这是一种为 ZKP 以及全同态加密（FHE）量身定制的极简格式。

设计原理

ZKP 过程中的工作负载无法完全用一组有限的基本内核的组合来表示（NTT 等特殊情况除外）。 因此，ZKP 需要一个可编程的 IR，而不是主要建立在枚举之上的运算符库（例如基于线性代数的 BLAS 库）。 例如，Plonkish 证明系统中的某些步骤完全取决于它们的约束多项式，这些多项式进一步受到启用自定义门类型集的影响。 另一个例子是使用 SumCheck 的证明系统，其中被求和的多项式通常涉及具有多个多线性多项式输入的可定制的多元低次多项式。 即使对于基于使用固定哈希函数的 Merkle 树的多项式承诺方案（PCS），在不同项目中，数据哈希顺序的实现方式也各不相同。 这些例子突出了 ZKP 专用 IR 中可编程性的关键重要性。

另一方面，像 LLVM 或 PTX 这样的通用处理器 IR 虽然高度灵活，但包含针对 CPU 或单个 GPU 的过多的低级细节。 这不仅增加了上游程序生成 IR 的复杂性，而且对其他类型的硬件（例如，那些针对 ZKP 专用芯片或并行计算系统的硬件）也提出了挑战，通常会产生适得其反的结果。 例如：

• 原生模运算：某些硬件原生支持模算术作为原始数据类型。 然而，LLVM/PTX 可能会将模运算分解为 32/64 位整数运算序列。 下游硬件编译器遇到了一项艰巨的任务，即对这些序列进行逆向工程，以将它们识别为高级模运算（例如，识别隐藏在 100 条指令中的 256 位模乘法），这是非常具有挑战性的。
• 并行架构优化：许多硬件平台采用大规模分层并行性和 ZKP/FHE 优化的高速缓存/互连架构。 这适用于多个级别：芯片上的内核之间、卡上的芯片之间、机器中的卡之间，甚至跨机器。 硬件设计人员通常利用 ZKP 计算模式（例如，NTT 或 SumCheck）中的规律性来优化其平台，以提高数据缓存和互连拓扑的利用率。 但是，如果在 ZKP 计算中使用 LLVM/PTX 表示，则这种规律性会被指针算术细节所掩盖，从而使这些优化失效。

因此，一个明确的结论是，ZKP IR 必须显式地暴露计算数据访问模式中的规律性，因为这代表了跨平台、性能关键的信息。 这可以通过将数据访问模式约束为一组定义明确的最小原始操作来实现，前提是 IR 保持足够的灵活性以满足可编程性要求。

这些权衡带来的收益是巨大的。 你想要的越多，你必须假设的就越多。 这些约束释放了跨软件和硬件的优化机会：

• 硬件中立性：IR 驻留在现有异构硬件可以有效实现的计算模型的交汇处。
• 编译器优化：编译器可以完全自动化数据布局管理，针对硬件和计算环境进行优化，同时启用内核融合机会。
• 释放高效的硬件架构：硬件可以采用空间高效的多核并行性、解耦访问执行（DAE）内存架构以及使用优化求解器静态调度的网络通信。

计算表示

ZKP 证明过程中所需的原始操作可以分为两类：

• 第一类：具有规则数据访问模式和大规模并行性的计算；
• 第二类：高度灵活、不规则的计算，总体工作量相对较小。

建立这种分类的目的在于提高设计高性能计算系统的成本效益：如果我们能够证明绝大多数的计算时间是由一小部分规则模式支配的，那么我们可以专注于优化这些模式，同时将剩余的边缘情况计算降级为现有的通用系统作为后备解决方案。 从这个角度来看，无论是设计可定制的芯片，还是使用现成的硬件构建高度并行的系统，识别这种分类都是至关重要的。

下面，我们首先介绍 ZKP 计算所需的原始操作的分类，然后通过示例说明它们在 ZKP 功能中的用法和覆盖完整性，这些示例以一种更数学化而不是以代码为中心的方式描述。 当我们识别这些原始操作时，我们会优先考虑最小化原始操作类型的数量，以涵盖大多数 ZKP 操作。 如果一个操作可以分解为更简单的原始操作的组合，则它本身不会被归类为原始操作。 虽然实际的硬件实现通常受益于将多个原始操作合并为一个步骤以提高效率（通常称为内核融合），但这被认为是内部编译器优化细节。 原始抽象接口在概念上应保持简单。

下面，我们列出第一类和第二类中的原始操作。 为了方便阅读，我们使用不同的颜色来表示不同的原始操作。

第一类

多维数组的点式运算

这个原始操作可以用数学方式描述如下：

(O1(x1,...,xN),...,OU(x1,...,xN))=f(p1(x1,...,xN),...,pS(x1,...,xN)),

其中

f:FqS→FqU 是一个具有

S 个输入和

U 个输出的函数，

(p1,...,pS) 是一个

N 维数组的集合，并且

(O1,...,OU) 是一个

N 维数组的集合。

这里的函数

f 可以是

• 一组 Fq 上的 S 元多项式，通常来源于
  • 约束多项式；
  • NTT 蝶形运算；
  • 对复杂多项式进行 SumCheck。
• 密码哈希函数，例如
  • 基于二进制的哈希函数（例如，Keccak/SHA），其中 Fq 元素被转换为二进制数据；
  • 原生 Fq 哈希函数（例如，Poseidon 系列），主要用于 Merkle 树的构造。

一个使用这个原始操作的例子是在 NTT 蝶形运算中，其中

(U1′(x1,...,xN),V1′(x1,...,xN)) 被计算为

(U1(x1,...,xN)+V1(x1,...,xN),T(x1,...,xN)(U1(x1,...,xN)−V1(x1,...,xN))).

规则数据移动：超立方体变换

这个原始操作可以被描述为

O(x1,...,xN)=p(expr1,...,exprM),

其中

expri 可以是常量 0 或 1,

x1 (直接索引) 或

1−xi (补码索引)。 一个使用这个原始操作的例子是在 NTT 计算的第一层，我们需要从输入中获取所有的偶数/奇数元素作为单独的数组，如

U1(x1,...,xN−1)=p0(x1,...,xN−1,0)

规则数据移动：一维循环移位

下一个原始操作可以被描述为以下等式：

O(x1,...,xN;y1,...,yM)=p(x1,...,xN;yi1,...,yiM),

其中

(yi1,...,yiM)=((y1,...,yM)+offset)mod2M, 并且

offset 是指定循环移位距离的整数。 这里输入

p 是一个

Fq 的

2M+N 元素数组，输出

O 是一个

Fq 的

2M+N 元素数组。 这个原始操作用于 Plonk 中的置换约束，如下所示。

数组连接

连接原始操作被描述为

O(x1,...,xN;y1,...,yM)=pbinary(y1,...,yM)(x1,...,xN),

其中

binary(y1,...,yM) 将一个布尔数组

(y1,...,y)M 转换为一个布尔字符串

y1y2⋯yM. 这里输入

p0,...,p2M−1 是

2m 个大小为

2N 的数组，将被连接，并且输出

O 是一个

Fq 的

2M+N 元素数组。 这个连接原始操作用于 NTT 操作的第一层。

不规则数据移动：分组收集

分组收集原始操作可以表示为

O(x1,...,xL;y1,...,yM;z1,...,zN′)=p(x1,..,xL;y1,...,yM;z1′,...,zN′),

其中它保持

binary(z1′,...,zN′′)=IndexTable(binary(y1,...,yM;z1,...,zN)).

函数

IndexTable 映射大小为

2M+N 的表格，其值范围从

0 到

2N′−1. 输入数组

p∈Fq 是要从中查找的源数组，而输出

O∈FqL+M+N 是目标数组。

第二类

灵活的小批量计算

第二类中只有一个原始操作来处理不规则计算。 该原始操作描述为

(O1,...,OU)=f(p1,...,pS),

其中

f 是一个 CPU 可执行的函数，比如 Fiat-Shamir 变换的哈希函数或 FRI-IOP 中的 Merkle 树路径验证。 使用这种原始操作的一个典型例子是 FRI 中的 Merkle 树构造，

(NewState, Challenges):=FiatShamir(OldState,LN,A,LN,B,LN,C,LN,D).

运行示例

在本部分中，我们将展示 ZKP 操作可以使用上面定义的原始操作来构建。

NTT DIF 操作

在 NTT DIF 操作中，输入

p0 是一个 Fq 中包含 2N 个元素的数组，输出 O 是一个 Fq 中包含 2M 个元素的数组，加上一个参数表，称为旋转因子（twiddle factors)。 NTT 计算的每一层对应于一个蝶形操作。 在此过程中，大小为

2N 的数组被拆分为两个大小为

2𝑁−1 的数组，然后进行蝶形操作。

蝶形操作本身可以表示为元素级操作，而超立方体变换与数组连接相结合，提供了这些操作中缺少的数据布局转换。

第一轮 NTT 操作被描述为以下四个等式：

U1(x1,...,xN−1)=p0(x1,...,xN−1,0),V1(x1,...,xN−1)=p0(x1,...,xN−1,1).

前两个等式可以使用超立方体变换来表示。 第三个等式，使用多维数组的点式运算表示，即

U1′(x1,...,xN−1=(U1(x1,...,xN−1)+V1(x1,...,xN−1) 和

V1′(x1,...,xN−1)=T(x1,...,xN−1)(U1(x1,...,xN−1)−V1(x1,...,xN−1)).

最后一个等式使用数组连接表示为

p1(x1,...,xN)=[U1′,V1′]xN(x1,...,xN−1).

值得一提的是，虽然从硬件执行的角度来看，上面说明的流程似乎不是最优的（特别是对于那些熟悉 GPU 编程的人）：例如，它创建了许多临时中间数组，仅仅是为了进行数据布局调整，而不是重写后续操作中的索引表达式。 但是，当合适时，这些临时数组并不难被特定于平台的编译器消除。

Merkle 树

Merkle 树计算用于多项式承诺方案（PCS）中，它接受

(p1,...,p4+8S) 个 Fq2N 中的元素，并输出 Merkle 根，以及通过 Fiat-Shamir 变换采样的路径。 在 Plonky2 中，它以矩阵形式的 witness 数据（维度为

2k 行和

M 列）为目标，首先将每一行 hashing 成一个固定大小的摘要（

4×64-bit 字段元素），然后从剩余的摘要单列生成一个传统的 Merkle 树。

首先，使用 Poseidon 哈希函数 H 对这 12 列进行哈希处理

H

(A1(x1,...,xN),B1(x1,...,xN),C1(x1,...,xN),D1(x1,...,xN))=H(p1(x1,,,.,xN),...,p12(x1,...,xN)),

这一步可以使用多维数组的点式运算来执行。 其次，我们可以哈希接下来的 8 列以获得

(A2(x1,...,xN),B2(x1,...,xN),C2(x1,...,xN),D2(x1,...,xN)) ，如

H(A1(x1,,,.,xN),...,D1(x1,,,.,xN),p13(x1,...,xN),P20(x1,...,xN)),

使用多维数组的点式运算。

哈希计算继续使用多维数组的点式运算，直到最后 8 列，

(AS(x1,...,xN),BS(x1,...,xN),CS(x1,...,xN),DS(x1,...,xN)) 的计算方式为

H(AS−1(x1,,,.,xN),...,DS−1(x1,,,.,xN),p5+8(S−1)(x1,...,xN),p12+8(S−1)(x1,...,xN)).

然后使用超立方体变换，我们可以将长度减半，如

L1,A,0(x2,...,xN)=AS(0,x2,...,xN),L1,A,1(x2,...,xN)=AS(1,x2,...,xN),

并且可以类似地计算

L1,B,0,L1,B,1,L1,C,0,L1,C,1,L1,D,0,L1,D,1 。 然后将这些值进行哈希处理以获得

(L1,A,L1,B,L1,C,L1,D) ，如

H(L1,A,0,L1,A,1,L1,B,0,L1,B,1,L1,C,0,L1,C,1,L1,D,0,L1,D,1)

哈希计算继续进行，直到我们计算

(LN,A,LN,B,LN,C,LN,D) 作为 Merkle 根。 最后，使用灵活的小批量计算来获得样本 Merkle 路径，如

(NewState,Challenges):=FiatShamir(OldState,LN,A,LN,B,LN,C,LN,D).

SumCheck（密集情形）

Sumcheck 通常用于 GKR 和 HyperPlonk 证明系统中。 对于数据并行电路中的 GRK 证明或对不规则电路使用 Plonkish 风格方法的 HyperPlonk，大多数计算可以表示为密集运算。 尽管完整的 SumCheck 过程由于其大量的轮数而不适合图示表示，但其计算构建块可以直观地分类如下：

• 加权折叠：首先，我们使用超立方体变换来计算

U(x1,...,xN−1):=p0(x1,...,xN−1,0),V(x1,...,xN−1):=p0(x1,...,xN−1,1).

然后使用多维数组的点式运算来得到

O(x1,...,xN−1):=α×U(x1,...,xN−1)+β×V(x1,...,xN−1).

• 多元多项式值的插值：首先，我们使用超立方体变换来计算

U(x1,...,xN−1):=p0(x1,...,xN−1,0),V(x1,...,xN−1):=p0(x1,...,xN−1,1).

然后使用多维数组的点式运算来得到

(O1(x1,...,xN−1),...,Od(x1,...,xN−1):=f(U(x1,...,xN−1),V(x1,...,xN−1)).

• 索引重排序：这在 Hyperplonk 中用于计算

，p(1，x1,...,xN)−p(x1,...,xN,0)×p(x1,...,xN,1).

上面的公式可以通过创建三个中间变量来实现，使用超立方体变换

，p′:=p(1，x1,...,xN),p″:=p(x1,...,xN,0),p‴:=p(x1,...,xN,1).

稀疏计算

一些证明系统使用稀疏多项式来表示不规则电路。 这些系统通过分组收集来跳过证明期间的零元素计算，分组收集将非零元素聚合到密集数组中，从而实现后续的密集风格计算。

例如，在 GKR 的 SumCheck 阶段，稀疏多项式

p 的加权折叠

O(x1,...,xN−1):=α×p(x1,...,xN−1,0)+β×p(x1,...,xN−1,1)

在一个大小为

2⌈log2⁡(O)⌉ 的密集数组上计算。 设

R=2⌈log2⁡(O)⌉, 我们有

[O](x1,...,xR):=α×A(x1,...,xR)+β×B(x1,...,xR),

其中

[O]，

A 和

B 都是密集数组。

[O] 表示稀疏多项式

O 的密集表示。

A 和

B 是通过 Grather 操作从

p 的密集表示 [p] 获得的辅助数组，即

A(x1,...,xR):=[p](y1,...,yK),

其中元组

(y1,...,yK)∈{0,1}K 被定义为唯一值，使得

binary(y1,...,yK)=IndexTable1(binary)(x1,...,xR) ，并且可以对多项式

B 进行类似的计算，使用

IndexTable2。 这里

IndexTable1 和

IndexTable2 是预先计算的 2R 元素数组，将稀疏索引映射到密集位置。

置换约束（Plonk）

在几乎每个 Plonkish 证明系统中，都需要证明两个数组包含相同的元素集合，这通常被转换为数组元素的乘积相等性证明。 此过程通常涉及循环访问模式：

• 前缀积计算：给定数组 [a0,a1,…,aN], 我们计算（互斥）前缀积为 [1,a0,a0a1,…,Πi<kai…]. 换句话说，我们从 p 中计算 O，使得：

O(x1,x2,...,xN):={1,如果 (x1,…,xN)=(0,…,0),p(x1′,x2′,…,xN′)×O(x1′,x2′,…,xN′),否则

其中

(x1′,...,xN′)∈{0,1}N 被定义为唯一值，使得

binary(x1′,...,xN′)=binary(x1,...,xN)−1. 可以使用对数数量级的轮递归计算数组

O 的大小：

• 步骤 1：计算

U(x2,...,xN):=p(0,x2,...,xN)V(x2,...,xN):=p(1,x2,...,xN)T(x2,...,xN):=U(x2,...,xN)×V(x2,...,xN)

• 步骤 2：递归计算大小减半的 T 的前缀积 C；我们得到 C，值为

C(x2,...,xN):={1,如果 (x2,...,xN)=(0,...,0)T(x2′,...,xN′)×C(x2′,...,xN′),否则

其中

(x2′,...,xN′)∈{0,1}N 是唯一值，使得

binary(x2′,...,xN′)=(binary(x2,...,xN)−1).

• 步骤 3：完成：

U′(x2,...,xN):=1×C(x2,...,xN)V′(x2,...,xN):=U(x2,...,xN)×C(x2,...,xN)O(x1,...,xN):=[U′,V′]x1(x2,...,xN)

• 数据旋转：对于像 g(x)−h(x)g(wc⋅x) 这样的单变量多项式表达式，其中 x 迭代集合 Ω={ωk|k∈N}，当在多维数组中存储 g 和 h 时，我们通过一阶旋转来实现循环访问：

U(x1,...,xN):=g(x1′,...,xN′),

其中

(x1′,...,xN′)∈{0,1}N 是唯一值，使得

binary(x1′,...,xN′)=(binary(x1,...,xN)+1)mod2N.

• 原文链接： hackmd.io/@Cysic/ByY3_L5...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～