LambdaWorks，或者我们如何决定创建我们的zkSNARKs库和一个STARK证明器

介绍

我们认为目前大多数 ZK 库还不够易于使用。它们大多假定用户具有深厚的密码学背景，这使得新手很难从中学习，即使他面前有所有代码。我们还发现，一些常用的库对于初学者来说文档不足或示例难以理解。除此之外，一些库没有遵循对于构建可靠的生产系统至关重要的先进工程实践。有很多像 Cairo、Noir 这样的项目没有这些问题，但它们是成熟的编程语言。我们想要一个工具来构建像那些语言、新的证明系统或任何我们需要的东西。

因此，我们决定开始构建我们的 LambdaWorks 库，并牢记以下目标：

1. 用 Rust 实现，支持 WASM，并在其他主流语言中提供 FFI API
2. 易于使用的 API
3. 包含最著名的证明系统（Groth16、Plonk、STARKs、Plonky2，可能还有 Halo2）以及递归/IVC (Nova, Supernova)
4. 允许硬件加速，例如 GPU 和 FPGA 集成
5. 清晰的文档，提供从初学者到高级用户的各种教程

鉴于 STARKs 的重要性和应用，我们决定从实现 STARKs 的证明器开始构建我们的库。我们必须实现有限域算术和基本的密码学内容，例如 Merkle 树和哈希函数。我们将继续学习椭圆曲线和 SNARKs。

STARKs

STARKs（可扩展的、透明的知识论证）是密码学原语，是达到目的的便捷手段。我们追求的目标是计算完整性，即证明计算已正确执行（根据一组指令）。例如，我们想要证明我们正确计算了一个序列的前 5000 个值，或者我们运行了一个给定的机器学习算法，或者我们在区块链中处理了 4000 个交易。STARKs 为我们提供了计算完整性的简短证明。STARKs 给我们的优势是，检查证明比执行朴素验证（验证者重新执行程序）要快得多。

有很多有趣的资源可以学习 STARKs 的基础知识，例如 Starkware's STARK 101、Anatomy of a STARK、Ministark，以及 Starkware 关于算术化的博客（第一部分 和 第二部分）。

STARK 协议包含以下步骤：

• 算术化
• 转换为多项式方程。
• FRI，它有两个步骤：承诺和解承诺。

算术化

执行轨迹是一个包含 $w$ 列（寄存器）和 $T$ 行的表格，代表系统的每个状态。一个轨迹看起来像这样：

我们将每一列（寄存器）解释为多项式在域上的求值（我们称之为轨迹求值域）。例如，我们可以说 $f1(x)f1(x)$ 是表示第 1 列的多项式，因此：

f1(0)=x1,0f1(0)=x1,0

f1(1)=x1,1f1(1)=x1,1

⋮⋮

f1(T)=x1,Tf1(T)=x1,T

为了使事情更容易和更快，我们将使用大小为 $2n2n$ 的乘法子群 $Zp⋆Zp⋆$ 作为轨迹求值域，使得 $2n≥T2n≥T$。该群有一个生成器 ωω，它跨越子群中的所有元素。子群可以用 ωω 的幂表示，{1,ω,ω2,ω3,...,ωN}{1,ω,ω2,ω3,...,ωN}。我们的轨迹多项式满足

f1(1)=x1,0f1(1)=x1,0

f1(ω)=x1,1f1(ω)=x1,1

⋮⋮

f1(ωT−1)=x1,Tf1(ωT−1)=x1,T

执行轨迹中的元素满足由计算和边界条件给出的某些关系。我们称这些关系为约束。它们可以大致分为两组：

• 边界约束。
• 转移约束。

边界约束非常简单：它们指定给定时间寄存器的值。例如，当我们初始化计算时，每个寄存器都有一个给定的值。在斐波那契数列的情况下，

a0=a1=1a0=a1=1

如果我们的轨迹由表示序列的单列组成，则前两个元素等于 1：

x1,0=1x1,0=1

x1,1=1x1,1=1

我们可以将约束转换为多项式关系。我们知道 $x1,0=f1(1)x1,0=f1(1)$ 和 $x1,1=f1(ω)x1,1=f1(ω)$。如果约束成立，例如在 $x=ωx=ω$ 时，则单项式 $x−ωx−ω$ 除 $f1(x)−1f1(x)−1$。这意味着 $f(x)−1f(x)−1$ 除以 $x−ωx−ω$ 的结果是一个多项式，

QBC,1(x)=f1(x)−1x−ωQBC,1(x)=f1(x)−1x−ω

类似地，

QBC,0(x)=f1(x)−1x−1QBC,0(x)=f1(x)−1x−1

这种方法的一个缺点是，如果我们有 $n$ 个边界约束，我们会得到 $n$ 个多项式。一种优化方法是插值边界约束并获得一个新多项式。在这种情况下，

fBC(1)=1fBC(1)=1

fBC(ω)=1fBC(ω)=1

结合所有内容，我们得到

QBC(x)=f(x)−fBC(x)ZBC(x)QBC(x)=f(x)−fBC(x)ZBC(x)

其中 $ZBC(x)ZBC(x)$ 是在强制边界条件的点上消失的多项式：

ZBC(x)=(x−1)(x−ω)ZBC(x)=(x−1)(x−ω)

转移约束是可以在各种计算点应用的，不同行之间的关系。在斐波那契数列的情况下，我们有 $an+2=an+1+anan+2=an+1+an$，对于每个 $n=0,1,...T−2n=0,1,...T−2$。就轨迹多项式而言，

f1(ω2x)−f1(ωx)−f1(x)=0f1(ω2x)−f1(ωx)−f1(x)=0

如果满足约束，则以下函数应该是一个多项式，

QT(x)=f1(ω2x)−f1(ωx)−f1(x)ZT(x)QT(x)=f1(ω2x)−f1(ωx)−f1(x)ZT(x)

其中 $ZT(x)ZT(x)$ 是在强制执行转移约束的地方消失的多项式，

ZT(x)=∏T−2k=0(x−ωk)ZT(x)=∏k=0T−2(x−ωk)

转移约束通常表示为连接执行轨迹中两个连续行的多元多项式。例如，如果我们用 $x$ 表示给定的行，而 $y$ 是下一行，则约束可能是这样的

P(x,y)=y−x2=0P(x,y)=y−x2=0

如果我们用轨迹多项式组合约束多项式，我们有 $x=t(x)x=t(x)$，$y=t(ωx)y=t(ωx)$，所以

t(ωx)−t(x)2=0t(ωx)−t(x)2=0

如果我们正确地进行了计算，那么 $QBC(x)QBC(x)$ 和 $QT(x)QT(x)$ 应该是多项式；如果不是，它们是有理函数（两个多项式的商）。我们可以通过取一个随机线性组合来减少证明它们每个都是多项式

CP(x)=αBCQBC(x)+αTQT(x)CP(x)=αBCQBC(x)+αTQT(x)

如果 $QBC(x)QBC(x)$ 和 $QT(x)QT(x)$ 都是多项式，那么 $CP(x)CP(x)$ 也是。但如果它们中至少有一个是有理函数，那么 $CP(x)CP(x)$ 不太可能是多项式。

鉴于证明 $CP(x)CP(x)$ 是一个多项式很困难，我们将证明它接近一个低次多项式。为此，我们将 $CP(x)CP(x)$ 投影到一个新的函数上，该函数的次数较小。我们将继续进行投影，直到我们得到一个常数多项式。关键在于投影操作Respects这个距离。如果原始函数远离低次多项式，那么投影也将远离它。在跳转到这个过程（称为 FRI）之前，我们必须承诺到轨迹多项式。

承诺到轨迹

我们需要在更大的域上评估轨迹多项式；域的大小是 $β2nβ2n$，其中 $ββ$ 是 blowup 因子。为了避免问题，我们通过将元素乘以 $h$ 来移动域，其中 $h$ 属于陪集。低次扩展域（简称域）由下式给出

D={h,hη,hη2,...,hη2n−1}D={h,hη,hη2,...,hη2n−1}

这里 ηη 是阶数为 $β2nβ2n$ 的子群的生成器，这样它就不会与 ωω 混淆（尽管我们可以通过取 $ω=ηβω=ηβ$ 来关联它们）。

我们在这个大域上评估轨迹多项式，并获得表示每次求值的向量：

[f1(h),f1(hη),...,f1(hη2n−1)][f1(h),f1(hη),...,f1(hη2n−1)]

[f2(h),f2(hη),...,f2(hη2n−1)][f2(h),f2(hη),...,f2(hη2n−1)]

[fw(h),fw(hη),...,fw(hη2n−1)][fw(h),fw(hη),...,fw(hη2n−1)]

为了承诺到这些求值，我们构建 Merkle 树，prover 将 Merkle 树的根发送给 verifiers。为了使事情更容易，轨迹的低次扩展的每一行的元素被分组到单个叶子中。

承诺到组合多项式

我们使用相同的域 $D={h,hη,hη2,...,hη2n−1}D={h,hη,hη2,...,hη2n−1}$ 来评估组合多项式。然后，我们可以从这些求值创建一棵 Merkle 树，并将根发送给 verifier。

关联执行轨迹的 LDE 和组合多项式

在某个时刻，verifier 将要求 prover 在某个点 $z$ 处给出组合多项式的值，即 $CP(z)CP(z)$。Verifier 需要确保组合多项式是由将多项式约束应用于轨迹多项式而产生的。给定值 $z∈Dz∈D$（在 DEEP 中，$z$ 的值是在域外采样的），prover 需要在给定点发送轨迹多项式的值，以便 verifier 可以检查计算。例如，在斐波那契的情况（为了简单起见，我们将忽略所有其他约束），

P(u,v,w)=w−v−u=0P(u,v,w)=w−v−u=0

P(t(x),t(ωx),t(ω2x))=t(ω2x)−t(ωx)−t(x)=0P(t(x),t(ωx),t(ω2x))=t(ω2x)−t(ωx)−t(x)=0

要创建组合多项式，我们必须将先前的多项式除以相应的消失多项式。因此，如果我们选择 $x=zx=z$，我们有

Q(z)=t(ω2z)−t(ωz)−t(z)ZD(z)Q(z)=t(ω2z)−t(ωz)−t(z)ZD(z)

Prover 需要发送这三个值。注意 $z=hηkz=hηk$，所以 prover 需要发送值 $t(ω2hηk)t(ω2hηk)$，$t(ωhηk)t(ωhηk)$，$t(hηk)t(hηk)$，他们在 Merkle 树中被 $ββ$ 个元素分隔开。Verifier 取这三个值，评估消失多项式，并检查

Q(z)=CP(z)Q(z)=CP(z)

这样，verifier 相信组合多项式通过约束多项式与执行轨迹相关。

FRI 协议

Prover 必须证明 $CP(x)CP(x)$ 接近于低次多项式。为此，他会随机折叠多项式，从而降低次数，直到得到一个常数多项式（在优化中，获得一个常数多项式是不必要的，因为 prover 可以发送一个多项式的所有系数，并让 verifier 检查它）。FRI 协议有两个步骤：承诺和解承诺。

承诺

Prover 取 $CP(x)CP(x)$ 并按以下方式拆分它：

g(x2)=CP(x)+CP(−x)2g(x2)=CP(x)+CP(−x)2

xh(x2)=CP(x)−CP(−x)2xh(x2)=CP(x)−CP(−x)2

以便

CP(x)=g(x2)+xh(x2)CP(x)=g(x2)+xh(x2)

Verifier 选择一个随机值 α0α0，并且 prover 形成多项式，

P1(x)=g(x2)+α0h(x2)P1(x)=g(x2)+α0h(x2)

新的域 $D1={h2,h2η2,...,h2ηm}D1={h2,h2η2,...,h2ηm}$ 的大小是 $DD$ 的一半。

Prover 可以通过在 $D1D1$ 上评估 $P1(x)P1(x)$ 来执行低次扩展，然后通过创建 Merkle 树并发送根来承诺到它。他可以通过在每一步将次数减半，继续执行该过程。对于步骤 $k$，我们有

Pk(y2)=Pk−1(y)+Pk−1(−y)2+αk−1(Pk−1(y)−Pk−1(−y)2)Pk(y2)=Pk−1(y)+Pk−1(−y)2+αk−1(Pk−1(y)−Pk−1(−y)2)

和

Dk={h2k−1,(hη)2k−1,...,(ηlh)2k−1}Dk={h2k−1,(hη)2k−1,...,(ηlh)2k−1}

Prover 在 $DkDk$ 上评估 $Pk(x)Pk(x)$ 并承诺到它，发送 Merkle 根。

解承诺

Verifier 随机选择一个属于 $DD$ 的点 $q$。Prover 需要说服他，轨迹多项式和组合多项式是相关的（我们之前已经介绍过），并且连续 FRI 层的元素也是相关的。对于每一层，prover 需要向 verifier 发送两个元素，$Pk(z)Pk(z)$ 和 $Pk(−z)Pk(−z)$。他还必须证明这些元素属于相应的 Merkle 树，因此还需要每个元素的身份验证路径。

Verifier 可以通过执行共线性检查来检查 FRI 层的正确性。给定 $Pk(z)Pk(z)$，$Pk(−z)Pk(−z)$ 和 $Pk+1(z2)Pk+1(z2)$，verifier 可以计算

gk+1(z2)=Pk(z)+Pk(−z)2gk+1(z2)=Pk(z)+Pk(−z)2

hk+1(z2)=Pk(z)−Pk(−z)2zhk+1(z2)=Pk(z)−Pk(−z)2z

并获得下一层的值

uk+1=gk+1(z2)+αkhk+1(z2)uk+1=gk+1(z2)+αkhk+1(z2)

如果 prover 正确地进行了计算，那么

uk+1=Pk+1(z2)uk+1=Pk+1(z2)

FRI 的一个玩具示例

我们将使用一个简单的示例来了解 FRI 上的一切是如何工作的。我们选择 $p=17p=17$，它的乘法群的阶数为 $16=2^416=24$，并设置 $η=3η=3$，这是一个本原单位根（即，$3^{16}=13^{16}=1$ 并且对于 $0<k<160<k<16$ 有 $3^k≠13k≠1$）。我们的组合多项式是 $P0(x)=x3+x2+1P0(x)=x3+x2+1$。LDE 的域简单地是 $D0=Z17⋆={1,2,3,4,5,6,...,16}D0=Z17⋆={1,2,3,4,5,6,...,16}$。下表包含 $P0(x)P0(x)$ 的LDE：

假设 verifier 采样 $β0=3β0=3$。Prover 对 $P0(x)P0(x)$ 执行随机折叠，

g1(x2)=1+x2g1(x2)=1+x2

xh1(x2)=x3xh1(x2)=x3

所以

P1(x2)=1+(1+β0)x2P1(x2)=1+(1+β0)x2

为了使事情更简单，

P1(y)=1+4yP1(y)=1+4y

与 $y=x2y=x2$。新的域是通过对 $D0D0$ 的元素进行平方而获得的。$P1(y)P1(y)$ 的 LDE 是

Verifier 采样 $β1=2β1=2$，并且 prover 折叠 $P1(y)P1(y)$ 以获得 $P2(z)P2(z)$，

P2(z)=1+4β1=9P2(z)=1+4β1=9

这是一个常数多项式。域 $D2={1,13,16,4}D2={1,13,16,4}$。LDE 中的所有元素都评估为 9，因此不需要表格。

多项式 $P0(x)P0(x)$，$P1(x)P1(x)$ 和 $P2(x)P2(x)$ 的评估分别使用 Merkle 树进行承诺并发送给 verifier。

假设 verifier 在 LDE 中选择索引 4 以检查 FRI 层的正确性。Prover 需要向他发送以下内容：

• $P0(13)=4P0(13)=4$ 和 $P0(−13)=P0(4)=13P0(−13)=P0(4)=13$ 及其身份验证路径。
• $P1(16)=14P1(16)=14$ 和 $P1(−16)=P1(1)=5P1(−16)=P1(1)=5$ 及其身份验证路径。
• $P2(4)=9P2(4)=9$。

我们可以看到，对于第一层，prover 传递位置 4 和 12 的值，然后传递 4 和 1（这是 index+|D1|/2index+|D1|/2，其中 |D1||D1| 是 D1D1 中的元素数，但由于 8 超过了最大值，因此我们环绕）。

Verifier 进行以下计算，

u=P0(13)+P0(4)2+β0(P0(13)−P0(4)2×13)u=P0(13)+P0(4)2+β0(P0(13)−P0(4)2×13)

回想一下，除以 $t$ 只是乘以 $t^{-1}t^{-1}$。在 22 的情况下，我们有 $2^{-1}=92^{-1}=9$，因为 $2×9=18≡1(mod17)2×9=18≡1(mod17)$。因此，

u=2−1(4+13)+3×9−1(4−13)u=2−1(4+13)+3×9−1(4−13)

第一项是 00，而第二项是 $48≡14(mod17)48≡14(mod17)$，所以

u=14u=14.

接下来，他检查

u=P1(16)u=P1(16)

两者都是 1414，因此第一层是正确的。

Verifier 继续到下一层。他需要计算

u=P1(16)+P1(1)2+β1(P1(16)−P1(1)2×16)u=P1(16)+P1(1)2+β1(P1(16)−P1(1)2×16)

如果我们进行计算，

u=22+2(92×16)u=22+2(92×16)

但这只是

u=1+(−9)=1+8=9u=1+(−9)=1+8=9

现在，

P2(4)=9=uP2(4)=9=u

因此所有层都已检查。你应该尝试选择一个索引并表明所有计算都匹配。

总结

STARKs 是强大的密码学原语，允许一方证明计算的完整性。为了生成证明，我们获得了程序的执行轨迹，并将轨迹的每一列解释为多项式在“nice”域上的求值。执行轨迹的行通过低次多项式相关联，这决定了约束。当我们用轨迹多项式组合约束多项式时，我们在执行轨迹上强制执行约束。然后我们可以通过它们有效域上的消失多项式来除以它们（强制执行每个约束的地方）；如果约束成立，则除法是精确的并产生一个多项式。STARKs 没有证明结果是一个多项式，而是表明结果接近于低次多项式。FRI 随机折叠该函数，在每一步将次数减半；关键是这种折叠保留了与低次多项式的距离。该协议包含两个阶段：承诺，其中证明者将自己绑定到多项式在其相应域上的评估，以及解承诺，其中他生成允许验证者检查计算的证明。在即将发布的文章中，我们将介绍一些优化和示例。

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