二进制域上的SNARK：Binius - 第二部分

介绍

这篇文章是我们关于 Binius （一种基于二元域的新证明系统）讨论的延续。在继续之前，如果你不熟悉某些概念，请参阅第一部分，或者阅读我们的文章，了解我们为什么认为这个证明系统可以帮助推动行业发展。

在本文中，我们将重点介绍级联码（这使我们能够扩展小域的多项式承诺方案）以及用于检查多元多项式上的语句的不同协议。

级联码

在之前的文章中，我们介绍了小域的多项式承诺方案。为了开发通用的承诺方案，我们首先需要介绍 packing 方案和级联码。请记住，在这种设置中，我们正在使用域塔，$\tau_0 \subset \tau_1 \subset \cdots \subset \tau_t$。我们使用一个 $[n_0, k_0, d_0]$ 线性外码，以及一个 $[n_i, k_i, di]$ 线性内码。外码基于 $\tau{i+k}$，而内码基于 $\tau_i$。

整个构造依赖于从一个域中 packing 几个元素，并将它们解释为来自扩展域的元素。我们可以将来自 $\taui$ 的 $2k$ 个元素视为来自 $\tau{i+k}$ 的单个元素（我们可以将其视为 $\tau_i$ 向量空间，因为我们可以将复数视为实数上的二维向量空间）。

级联码的编码过程如下：

1. 将 $\taui$ 上的初始消息 packing 成 $\tau{i+k}$ 的元素。例如，我们有来自 $\tau_0$ 的四个比特变量 $0, 1, 1, 1$，我们可以将它们分组为来自 $\tau_2$ 的一个元素 $0111$。
2. 使用外码对外码对打包的消息进行编码。例如，我们可以使用 Reed-Solomon 编码。
3. 将码字中的每个符号 unpacking 为 $\tau_i$ 上的消息。
4. 使用内码进行编码并连接元素。此编码可能是微不足道的，也就是说，应用恒等码。

我们面临的一个问题是我们必须使用扩展码。我们在不同的域之间存在相互作用：表示多项式系数的域、代码字母表的域、中间域以及我们用于密码安全的扩展域（这里是 $\tau_t$）。为了使用扩展码，我们定义了一个结构，其中包含来自矩形数组(具有 $2^{\tau-i} \times 2^k$ 个元素)中 $\taui$ 的元素。每行包含 $2^k$ 个元素，可以解释为 $\tau{i+k}$ 元素。类似地，一列中的 $2^{\tau-i}$ 个元素可以解释为 $\tau_t$ 中的单个元素。该结构具有双重视图：作为维度为 $2^k$ 的 $\taut$ 上的向量空间（查看列）或作为维度为 $2^{t-i}$ 的 $\tau{i+k}$ 上的向量空间。数组与来自 $\tau_i$ 的元素的乘法被解释为逐元素乘法。如果我们要乘以 $\tau_t$ 上的元素，我们取每一列（它是来自 $\taut$ 的单个元素）并执行每一列与该元素的乘法。以类似的方式，我们可以通过将每一行相乘来乘以 $\tau{i+k}$ 中的元素。

基于块级别编码的多项式承诺方案的步骤是：

1. Commit(pp)：将多项式的系数排列成一个 $m_0 \times m_1$ 矩阵，其条目位于 $\taui$ 中。取 $2\kappa$ 的块对元素进行分组，并将它们解释为 $\tau{i+k}$ 中的元素，并按行应用扩展编码，获得一个大小为 $m_0 \times n$ 的矩阵，其元素位于 $\tau$ 上。从列构建一个 Merkle 树，并将根作为承诺输出。
2. Prove(pp,ss)：证明者将系数排列成一个 $m_0 \times m_1$ 矩阵 $t$，其条目位于 $\taui$ 中。他计算并清楚地发送 $t' = \otimes{i=l_1}(1-r_i, r_i).T$ 给验证者。验证者对 $\rho$ 索引 $j_0, j1, ... j{\rho-1}$ 进行采样。 证明者发送编码矩阵 $U$ 的列及其随附的 Merkle 路径。
3. Verify($\pi, r, s$)：验证者检查 $t' \otimes_{i=0}^{l_1}.(1-r_i, ri) = s$。然后，验证者将 $t'$ 解释为大小为 $2k$ 的块，并应用扩展码，unpacking 所有元素以获得 $u'$。验证者检查提供的所有列是否都包含在 Merkle 树中，并检查 $\otimes{i=l_1}(1-r_i, r_i).u$。

证明的大小可以从 $t'$ （来自 $\tau_t$ 的 $m1$ 个元素）、列（由来自 $\tau{i+k}$ 的 $\rho m_0$ 个元素组成）加上 $\rho$ 列的身份验证路径来计算。 假设摘要大小为 $256$ 位，我们有 $2\tau m_1 + 2^{i+k} \rho m_0 + 28 \rho \log_2 n$ 位。

协议

Binius 包含一个关键多项式谓词列表，基于 HyperPlonk 提出的那些：

1. 查询
2. 求和
3. 零
4. 乘积
5. 多重集
6. 排序
7. 查找

几乎所有的协议都归结为 sumcheck。 有关 sumcheck 协议的基础知识，请参阅我们之前的文章或 Thaler 的书。

例如，zerocheck 协议可用于证明在 HyperPlonk 中强制执行了 gate 约束。在该协议中，我们有一个多线性多项式 $M$（它编码了 trace）和选择器多线性多项式 $S_1$、$S_2$、$S_3$，这样，对于 ${0,1}^n$ 中的每个点，我们有

$0 = S_1(M_0 + M_1) + S_2 M_0 M_1 + S_3 G(M_0, M_1) - M_2 + I$

其中 $M_0(x) = M(0,0,x)$，$M_1(x) = M(0,1,x)$，$M_2(x) = M(1,0,x)$。

我们如何证明多元多项式 $P = S_1(M_0 + M_1) + S_2 M_0 M_1 + S_3 G(M_0, M_1) - M2 + I$ 对于 ${0,1}^n$ 中的每个值都等于零？我们让验证者提供来自 $F^n$ 的随机点 $r{zc}$ 并构建多元多项式

$P'(x) = eq(r_{zc}, x)P(x)$

其中 $eq(x,y) = \prod (x_i y_i + (1-x_i)(1-y_i))$，我们为 $P'(x)$ 运行 sumcheck 协议，以 $0$ 作为总和值。验证者只需要在 $x=r_s$ 处对 $P'(x)$ 进行一次评估。

将 sumcheck 与 $P'(x)$ 一起使用涉及到非多线性的多元多项式；这意味着证明者必须在每一轮发送一个最多为 $d$ 次的多项式。HyperPlonk 对此情况进行了优化：证明者发送对次数最多为 $d$ 的单变量多项式的承诺，并提供对单个点的评估（而不是至少 3 个点）。

由于大多数协议最终都以 sumcheck 结束，我们可以使用随机线性组合对多项式进行批处理，并将所有检查减少为单个 sumcheck。Binius 的存储库 包含零、求和和评估检查的实现。

Binius 建议使用 Plonkish 算术化； 与 HyperPlonk 的主要区别在于，trace 包含属于不同子域的元素。 因此，gate 约束将表达不同子域上的关系。 如果满足以下条件，则执行有效

1. 所有 gate 约束都成立。
2. 所有全局复制约束都得到满足。
3. 每个 witness 变量都位于其规定的子域内。

前两个条件适用于 Plonk 的任何变体； 最后一个条件是引入的，因为我们使用扩展塔。

结论

在本文中，我们介绍了如何扩展第一部分中开发的承诺方案以使用打包域。 我们可以以双重方式查看域元素数组，按列或按行 packing 元素。 本文稍后介绍了一些关键协议，以证明多项式上的谓词，例如评估、求和和乘积检查； 这些都归结为执行多个可以方便地批处理的 sumcheck。 这些与一些算术化方案（例如 Plonkish）一起可以使用来产生 SNARK。 HyperPlonk 和 Binius 之间的主要区别在于，Binius 中的 trace 元素可能属于不同的子域。 然而，这并没有增加新的检查。 相反，这可以取代 HyperPlonk 中可能存在的额外检查。 这些子域检查由小域多项式承诺方案的安全属性保证。

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