二元域上的 SNARK：Binius - 第 1 部分

介绍

ZK-SNARKs (zero-knowledge, succinct, non-interactive arguments of knowledge) 和 STARKs (scalable, transparent arguments of knowledge) 由于它们在分布式私有计算和区块链扩展中的应用而受到广泛关注。多年来，由于新的证明系统、新的查找参数和更小的域，我们已经看到了几个性能改进。最大的挑战之一与程序的算术化有关，即将给定的程序转换为多项式关系系统。这代表了相当大的开销，因为我们必须用有限域中的元素来表示变量，例如位。在椭圆曲线上的 SNARK 的情况下，该域由使用的椭圆曲线给出，这意味着为了表示简单的位运算，我们必须使用（至少）256 位字段元素。在 STARK 的情况下，我们可以使用更小的字段（例如 mini Goldilocks 或 Mersenne 31），这给出了更小的开销，但随后我们必须在扩展域上工作才能实现密码安全性。典型的哈希函数涉及大量的按位运算，这使得它们的算术化成本很高（因此证明涉及计算哈希的事情）。这导致了 SNARK 友好的哈希函数的使用，例如 Poseidon 或 Tip5。

Ulvetanna 最近的一系列工作 提出了使用带有 brakedown 多项式承诺方案的二元域来获得新的 SNARK，它可以更自然地表示按位运算。它还具有硬件友好和内存占用更小的优点。这篇文章将解释一些关键概念，例如二元域和 brakedown 承诺方案。我们稍后将使用这些概念来理解 Binius 的工作原理。

二元域

二元域是特征为 2 的域。它们的形式为 F2nF2n 对于某个 nn。最简单的二元域是 F2F2，其元素只有 {0,1}{0,1}，运算以 22 为模进行。加法对应于按位异或，乘法对应于按位与。鉴于 2n2n 不是素数，我们需要做一些工作才能将其转换为域。首先，我们将考虑 F2F2 上的多项式，即系数为 00 或 11 的多项式，例如 p(x)=x7+x5+x2+1p(x)=x7+x5+x2+1。然后，我们选择一个 F2F2 上的不可约多项式 m(x)m(x)，并通过取任何多项式除以 m(x)m(x) 的余数来考虑等价类。例如，多项式 m(x)=x2+x+1m(x)=x2+x+1 是不可约的；余数始终是至多一次的多项式 r(x)=ax+br(x)=ax+b，其中 aa 和 bb 要么为零要么为一。结果域是 F22F22，它包含 44 个元素，0+0x0+0x, 1+0x1+0x, 0+x0+x, 1+1x1+1x，我们可以将其表示为 0000, 1010, 0101 和 1111。我们总是可以用长度为 nn 的位串明确地表示 F2nF2n 中的一个元素。此处 可以找到 F2F2 上的不可约多项式列表。

多项式 m(x)=x3+x+1m(x)=x3+x+1 也是不可约的，因此我们可以使用它来构建不同的扩展 F23F23，其中包含其他 88 个元素。构造 F23F23 的另一种方法是使用扩展塔。Binius 使用 Wiedemann 提出的构造。

我们可以使用多线性拉格朗日多项式作为扩展塔的基础。这样做的好处是，通过填充零系数可以很容易地将一个扩展嵌入到其他扩展中。该构造以归纳方式进行：

1. 从 τ0=F2τ0=F2 开始。
2. 设置 τ1=F2[x0]/(x20+x0+1)τ1=F2[x0]/(x02+x0+1)
3. 继续 τk=F2[xk−1]/(x2k−1+xk−1xk−2+1)τk=F2[xk−1]/(xk−12+xk−1xk−2+1)

我们有 τ0⊂τ1⊂τ2⊂⋯⊂τmτ0⊂τ1⊂τ2⊂⋯⊂τm。

让我们看一下这些元素，看看它是如何工作的：

1. 对于 τ0τ0，这很简单，因为我们有 00 或 11。
2. 对于 τ1τ1，元素为 0+0x00+0x0, 1+0x01+0x0, 0+1x00+1x0, 1+1x01+1x0。我们可以将 τ0τ0 的元素识别为前两个，0000 和 1010。
3. 对于 τ2τ2，我们有 0+0x0+0x1+0x0x10+0x0+0x1+0x0x1, 1+0x0+0x1+0x0x11+0x0+0x1+0x0x1, 0+1x0+0x1+0x0x10+1x0+0x1+0x0x1, 1+1x0+0x1+0x0x11+1x0+0x1+0x0x1, 1+0x0+1x1+0x0x11+0x0+1x1+0x0x1, 0+1x0+1x1+0x0x10+1x0+1x1+0x0x1, 1+1x0+1x1+0x0x11+1x0+1x1+0x0x1, 等等，我们可以将其识别为大小为 4 的所有位串。τ1τ1 的元素可以看作是 τ2τ2 中形式为 b0b100b0b100 的元素。这种对元素进行排序的方式对应于字典排序。

还值得注意的是，给定一个来自 τkτk 的元素 b0b1b2...b2k−1b0b1b2...b2k−1，我们可以将其分成两半，它们满足 blo+Xk−1bhiblo+Xk−1bhi，其中 bhibhi 和 bloblo 来自 τk−1τk−1。加法只是异或，从硬件的角度来看，这有很多优点，包括我们不必担心进位。可以使用我们看到的分解以递归方式进行乘法。如果我们有 ahixk+aloahixk+alo 和 bhixk+blobhixk+blo，我们会得到

ahibhix2k+(ahiblo+alobhi)xk+alobloahibhixk2+(ahiblo+alobhi)xk+aloblo

但我们知道 x2k=xk−1xk+1xk2=xk−1xk+1。然后我们必须计算 τk−1τk−1 中的乘积，我们可以应用相同的策略，直到我们可以解决它们，要么是因为它是一个微不足道的操作（F2F2 上的操作），要么是因为我们有一个查找表来获取这些值。还有一些有效的乘法技术可以将一个域中的元素乘以子域中的元素。例如，来自 τk+jτk+j 的元素可以乘以 τkτk 中的元素，只需 2j2j 次乘法。

编码理论

字母表 AA 上块 nn 的代码是 AnAn 的子集，即具有属于 AA 的 nn 个元素的向量。两个代码之间的汉明距离是它们不同的分量数。

字段 FF 上的一个 [k,n,d][k,n,d] 代码是 FnFn 的一个 kk 维线性子空间，使得两个不同元素之间的距离至少为 dd。 Reed-Solomon 码是这些类型的代码的示例。给定一个大小为 kk 的向量 (a0,a1,...,ak−1)(a0,a1,...,ak−1)，其 Reed-Solomon 编码包括将每个 akak 解释为 k−1k−1 次多项式的求值，然后在 nn 个点上求值该多项式（我们在使用 STARK 时使用了这种编码）。如果前 kk 个元素对应于原始向量，则该代码称为系统的。比率 ρ=k/nρ=k/n 是代码的速率（我们使用它的倒数，即膨胀因子）。在这种情况下，距离是 n−k+1n−k+1，因为 k−1k−1 次多项式最多可以在 k−1k−1 个点上重合。

块长度的 mm 倍交织码可以看作是在字母表 AmAm 上定义的尺寸为 nn 的线性码。我们可以将该码视为具有 AmAm 中元素的行。

给定一个在 FF 上具有生成矩阵 MM 的 [n,k,d][n,k,d] 线性码 CC 和一个在 FF 上的向量空间 VV，CC 的扩展码 C′C′ 是映射 MxMx 的图像，其中 xx 在 VkVk 中。

多项式承诺方案

多项式的系数和代码字段大小 FF 可以尽可能小，但它们应该相同。可以通过从扩展域 EE 中采样元素来添加安全性。

证明者从一个向量 (t0,t1,...tn)(t0,t1,...tn) 开始，他将其解释为在 0,1logn0,1log⁡n 上拉格朗日基中的系数。然后，他将系数组织成一个 m0×m1m0×m1 的矩阵 TT，其中行 rowirowi 并编码 rowirowi 以获得 uiui（有 m0m0 行长度为 ρ−1m1ρ−1m1）。我们将包含 uiui 作为行的矩阵称为 UU。使用每一列作为叶子构建一个 Merkle 树，并将根输出作为承诺。

验证者选择一个评估点 r=(r0,r1,…,rlog(n)−1)r=(r0,r1,…,rlog⁡(n)−1)，证明者将提供 ss 作为多项式在 rr 上的评估。要生成评估证明，

1. 证明者发送向量 - 矩阵乘积 R.TR.T，其中 RR 是 rr 的最后 log(m0)log⁡(m0) 分量的张量积。
2. 验证者采样 ii 个查询（取决于安全级别），每次选择 UU 的一列。
3. 证明者发送请求的列及其相应的身份验证路径。

该证明包括评估 ss、Merkle 根 rootroot、向量 - 矩阵乘积 R.TR.T、ii 列及其相应的身份验证路径。

要检查证明：

1. 验证者检查 Merkle 树是否包含这些列。
2. 验证者计算 R.TR.T 的编码，并检查 UU 的所选列与 RR 的乘积是否对应于 R.TR.T 编码的列。
3. 验证者使用 R.TR.T 和 rr 的前 log(m1)log⁡(m1) 分量的张量积来检查 ss 是否是正确的评估。

构建承诺方案的关键概念是打包。给定 τkτk 的 m 个元素，我们可以将它们分组为 τk+jτk+j 的 m/2jm/2j 个元素。类似地，这些行可以打包成 τrτr 的元素。修改多项式承诺，使验证者测试列块而不是单列。

结论

在这篇文章中，我们介绍了 Binius 背后的基本概念。该构造利用了使用扩展塔构建的二元域，这导致了硬件友好的操作。该构造还允许我们连接几个元素并将它们解释为扩展域的元素。承诺方案基于 brakedown，它使用 Merkle 树和 Reed-Solomon 编码。该方案导致比 FRI 更大的证明和更长的验证时间，但证明者的时间显着减少。但是，就证明者时间而言，好处通常超过更长验证时间的好处。此外，使用递归证明可以进一步减少证明大小，或者我们可以使用最终的 SNARK，例如 Groth16 或 Plonk，来实现更小的证明以发布到 L1。在接下来的文章中，我们将更深入地研究承诺方案和 SNARK 的不同协议。

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