二元域上的 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 的域。它们的形式为 $F_{2^n}$ 对于某个 $n$。最简单的二元域是 $F_2$，其元素只有 ${0,1}$，运算以 $2$ 为模进行。加法对应于按位异或，乘法对应于按位与。鉴于 $2^n$ 不是素数，我们需要做一些工作才能将其转换为域。首先，我们将考虑 $F_2$ 上的多项式，即系数为 $0$ 或 $1$ 的多项式，例如 $p(x)=x^7+x^5+x^2+1$。然后，我们选择一个 $F2$ 上的不可约多项式 $m(x)$，并通过取任何多项式除以 $m(x)$ 的余数来考虑等价类。例如，多项式 $m(x)=x^2+x+1$ 是不可约的；余数始终是至多一次的多项式 $r(x)=ax+b$，其中 $a$ 和 $b$ 要么为零要么为一。结果域是 $F{2^2}$，它包含 $4$ 个元素， $0+0x$, $1+0x$, $0+x$, $1+1x$，我们可以将其表示为 $00$, $10$, $01$ 和 $11$。我们总是可以用长度为 $n$ 的位串明确地表示 $F_{2^n}$ 中的一个元素。此处 可以找到 $F_2$ 上的不可约多项式列表。

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

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

1. 从 $\tau_0=F_2$ 开始。
2. 设置 $\tau_1=F_2[x_0]/(x_0^2+x_0+1)$
3. 继续 $\tau_k=F2[x{k-1}]/(x{k-1}^2+x{k-1}x_{k-2}+1)$

我们有 $\tau_0 \subset \tau_1 \subset \tau_2 \subset \cdots \subset \tau_m$。

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

1. 对于 $\tau_0$，这很简单，因为我们有 $0$ 或 $1$。
2. 对于 $\tau_1$，元素为 $0+0x_0$, $1+0x_0$, $0+1x_0$, $1+1x_0$。我们可以将 $\tau_0$ 的元素识别为前两个，$00$ 和 $10$。
3. 对于 $\tau_2$，我们有 $0+0x_0+0x_1+0x_0x_1$, $1+0x_0+0x_1+0x_0x_1$, $0+1x_0+0x_1+0x_0x_1$, $1+1x_0+0x_1+0x_0x_1$, $1+0x_0+1x_1+0x_0x_1$, $0+1x_0+1x_1+0x_0x_1$, $1+1x_0+1x_1+0x_0x_1$, 等等，我们可以将其识别为大小为 4 的所有位串。$\tau_1$ 的元素可以看作是 $\tau_2$ 中形式为 $b_0b_100$ 的元素。这种对元素进行排序的方式对应于字典排序。

还值得注意的是，给定一个来自 $\tau_k$ 的元素 $b_0b_1b2...b{2^{k-1}}$，我们可以将其分成两半，它们满足 $b{lo}+X{k-1}b{hi}$，其中 $b{hi}$ 和 $b{lo}$ 来自 $\tau{k-1}$。加法只是异或，从硬件的角度来看，这有很多优点，包括我们不必担心进位。可以使用我们看到的分解以递归方式进行乘法。如果我们有 $a_{hi}xk+a{lo}$ 和 $b_{hi}xk+b{lo}$，我们会得到

$a{hi}b{hi}xk^2+(a{hi}b{lo}+a{lo}b_{hi})xk+a{lo}b_{lo}$

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

编码理论

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

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

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

给定一个在 $F$ 上具有生成矩阵 $M$ 的 $[n,k,d]$ 线性码 $C$ 和一个在 $F$ 上的向量空间 $V$， $C$ 的扩展码 $C'$ 是映射 $Mx$ 的图像，其中 $x$ 在 $V^k$ 中。

多项式承诺方案

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

证明者从一个向量 $(t_0,t_1,...t_n)$ 开始，他将其解释为在 ${0,1}^{\log n}$ 上拉格朗日基中的系数。然后，他将系数组织成一个 $m_0 \times m_1$ 的矩阵 $T$，其中行 $row_i$ 并编码 $row_i$ 以获得 $u_i$（有 $m_0$ 行长度为 $\rho^{-1}m_1$）。我们将包含 $u_i$ 作为行的矩阵称为 $U$。使用每一列作为叶子构建一个 Merkle 树，并将根输出作为承诺。

验证者选择一个评估点 $r=(r_0,r1,\dots,r{\log(n)-1})$，证明者将提供 $s$ 作为多项式在 $r$ 上的评估。要生成评估证明，

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

该证明包括评估 $s$、Merkle 根 $root$、向量 - 矩阵乘积 $R \cdot T$、 $i$ 列及其相应的身份验证路径。

要检查证明：

1. 验证者检查 Merkle 树是否包含这些列。
2. 验证者计算 $R \cdot T$ 的编码，并检查 $U$ 的所选列与 $R$ 的乘积是否对应于 $R \cdot T$ 编码的列。
3. 验证者使用 $R \cdot T$ 和 $r$ 的前 $\log(m_1)$ 分量的张量积来检查 $s$ 是否是正确的评估。

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

结论

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

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