驱动 Binius 的域

原文： https://blog.lambdaclass.com/the-fields-powering-binius/

译者：Kurt Pan

通用零知识证明虚拟机 (zkVM) 的发展使得可验证应用程序的编写变得更加容易，使得开发人员可以编写高级代码，然后将其编译为 RISC-V 或其他指令集架构 (ISA)，并在虚拟机上运行。然后虚拟机使用诸如 STARK 或 Groth16 之类的证明系统生成简洁的执行证明。证明系统的最新进展使得证明时间得以缩短，我们正朝着实时证明以太坊区块的目标迈进。Binius 是一个证明系统，其开发重点是如何创建一种硬件友好的技术。了解硬件的工作原理后，一个定制的、具有快速数学运算的证明系统可以带来显著的改进。Petra 是第一个使用 Binius 的虚拟机。那么Binius 有何特别之处？它是如何工作的呢？

• https://www.binius.xyz/
• https://github.com/PetraProver/PetraVM

在本文中，我们将回顾 Binius 协议背后的基本数学原理，该协议利用了布尔超立方体  。我们将重点介绍二进制塔的基本描述和域元素的表示，以及利用域元素与电路级运算的自然关系进行域元素的加法和乘法运算。在本文中，我们将介绍二进制塔的诞生并成为一个具有技术趣味的对象的几个基石工作，即：

• Diamond 和 Posen 于 2023 年发表的论文 "Succint Arguments over Towers of Binary Fields"
• David Cantor 于 1989 年发表的开创性论文  "On Arithmetical Algorithms over Finite Fields"
• Wiedemann 1987 年的论文  "An Iterated Quadratic Extension of GF(2)"

更多背景资料请参阅我们之前关于 Binius 第 1 部分和 Binius 第 2 部分的帖子

• https://blog.lambdaclass.com/snarks-on-binary-fields-binius/
• https://blog.lambdaclass.com/binius-part-2/

域扩张和域元素的表示

在下面的讨论中，我们将  定义为具有两个元素的域。该域的次数为  的有限域扩张可以刻画为商环

其中  是任意次数为  的不可约多项式  ：该域恰好包含  个元素，且由多项式除以  后的所有余数组成。换句话说，它由次数最多为  且系数为  的多项式组成。此外，该扩张域可以看作是基域  上维度为  的向量空间，这是一个非常好的性质。集合

通常称为单项式基，固定此基后，即可建立同构，该同构将多项式与其  坐标等同起来。域元素的加法和乘法，当被视为多项式时，是以  为模进行的。

示例

考虑多项式

作为  中的一个元素。 是不可约的；如果它有一个非平凡因子 ，那么 ，并且由于 ，这将迫使  的根成为  的根。由于  在基域中没有根，因此我们得出结论， 是不可约的，且

确实是  的二次扩张；这意味着它可以被视为基域上的二维向量空间。该向量空间的标准基为

并且其所有元素都可以表示为  元素的线性组合：

下表列出了  在  上的坐标表示

扩张中的域运算是将  中的环运算应用到商域上，并考虑非平凡关系 。有时可以直观地解释为：现在  成为域扩张  中  的根。

我们观察到，上一个例子中  的不可约性很简单，因为  的次数足够低：如果  则  在  上不可约当且仅当  在  中没有根（这是域论中的一个定理）。

定义（二次扩张）：通过不可约二次多项式的商定义的域扩张称为二次扩张。

定义（域塔）：只要存在域  且 ，我们称  是  的扩张（通常记为 ），称  是  的扩张。将这些扩张连接在一起得到一个扩张塔，记为 。

事实证明，乍一看，域扩张的连接可能显得陌生且过于复杂，但最终会产生非常好的结果。

扩展示例： 的两种构造

让我们研究一下 16 元素域的两种不同实现，看看域是如何构造的。

第一种构造：将  表示为一个四次多项式的商：

要构造 ，我们需要在二进制域  上找到一个四次不可约多项式。其中一个这样的多项式是：

要验证此多项式在  上不可约，需要检查它在  中没有根，且不能分解为两个二次不可约多项式的乘积。

1.  中无根：

   由于  在  中没有根，因此它没有形如  的线性因子，其中 。

2. 不可分解为两个二次不可约多项式：

   在  上唯一的二次不可约多项式是 。如果  可约，它必定能写成 ，其中 。

   展开得：

   将其与  的系数比较：

   由于我们得到  且 ，矛盾。因此  不能分解为两个二次不可约多项式。

•  的系数：
•  的系数：
•  的系数：（一致）
• 常数项：

由于  在  上为四次不可约多项式，商环

是一个包含  个元素的域。该域的元素可以表示为次数不超过 3 且系数在  中的多项式；其中，加法在系数上逐项模 2 进行，乘法则是多项式相乘后再对  取模得到。该模运算通过反复使用关系  来实现。

例如，要计算  与  的乘积：

通过模 2 加法，我们可以抵消  项；利用定义关系，将高于 4 的幂替换：

再次模 2 加法后，得到 。

我们将看到，尽管这种乘法机制易于理解，但效率很低。我们希望找到一种不同的表示方式，以便快速高效地进行乘法运算。

第二种构造： 作为二次扩张序列

在此方法中，我们通过构造位于顶部的  的域塔来构造该域；我们利用二次扩张，以及当多项式次数不超过 3 时，其不可约性可通过根的检验来判断。

步骤 1：将  作为  的扩张：

同前面一样，我们使用不可约多项式  扩张 。由于扩展就是引入  的根 ，我们可以简单地表示为：

该域的四个元素为 ，且满足 。

步骤 2：将  作为  的扩张：

由于  有 4 个元素，我们需要在  上找到一个二次不可约多项式，以构造  并使 ；考虑多项式：

为了检验其不可约性，需要检查其在  中是否有根：

由于  是二次多项式且在  中无根，因此它在  上不可约。引入其根  可得：

并满足关系：

• （来自第一步扩张）
• （来自第二步扩张）

每一步都通过与一个二次不可约多项式取商来定义，即每一步都是二次扩张。更重要的是， 中的每个元素均可表示为基

的线性组合，系数在  中。

关于坐标表示：

让我们计算  相对于  及基域  的坐标。 的元素可写为

其中 。由于每个  各有 4 种取值，共有  个元素；回忆  对  的基为 ， 对  的基为 。

域论中有一条著名定理：在域塔中，上层域的基由下层扩张基元素的乘积构成。但需要注意顺序：有序基不仅要给出一个线性无关并生成的子集，还要明确这些元素在基中的顺序，以便使用坐标系。下面按照从左到右的习惯顺序，计算  中的元素：

例如，取元素 ，用坐标  表示。若将  用  表示，则只需将  和  的坐标连接即可得到  在  上的坐标。

例如，元素  在  中可写为 ，因此坐标为

又 ，，因此

我们再重复一次：选择基时，同时选择基元素的顺序；即使元素相同，不同顺序也会形成不同的基。在本文中我们按照从左到右，依次对应扩张的顺序来排列基元素。这并非唯一方式；事实上，逆序在计算机科学界也很常用。

Wiedemann 塔和Diamond & Posen 的工作

我们刚才在  的例子中看到的是Wiedemann塔的一个实例：一个域扩张序列，其中每个扩张都是前一个扩张的二次扩张，其表示方式是，扩张的基可以通过引入在那个时间点某个不可约多项式序列的根来获得。在刚才看到的例子中，基很简单

域元素仅仅是这些符号的  线性组合：我们通常将它们视为两个变量在  上的多项式，其中所有变量最多都以一次方的形式出现。在密码学领域，这些多项式通常被称为“多线性”。这类域扩张和多项式是 Ben Diamond 和 Jim Posen 工作的核心，他们提出了一种方案，可以在特征 2 中实现零知识协议，从而依靠电路级算术运算实现更高效的性能：BINIUS。他们工作中定义的二进制塔类似于迭代二次扩张序列，其灵感来自 Wiedemann 的工作。为了匹配他们的符号集 ，然后递归定义

其中 ；Wiedemann 证明了这个多项式在  上确实不可约，因此它将  定义为  的二次扩张。简要写下几个扩张

我们通常将  称为  的第  层或扩张；这样的域恰好包含  个元素。在这一层中，元素被描述为  个变量  上的多项式，每个  的幂最多为 1，也就是说，它们是多线性单项式在  上的线性组合。为了简单起见，还有一种非常方便的方法来指向特定的单项式，它与非负整数的二进制展开有关。

为了更清楚地说明这一点，假设我们需要找到第  个基元素，并将其称为 。为此，我们只需以 2 为底展开 ：

然后设置

例如，要获得 Wiedemann 塔中的第 10 个基元素，首先以 2 为底展开：

（在计算机科学中，通常从最高有效位开始，而且元素计数通常从 0 开始），然后构建

我们确认这种特定的基排序是一种字典序，这一事实将带来多种便利：

• 首先，它让我们能够目测某个元素是否属于  的特定子域；当与层  元素关联的坐标向量的后半部分为零时，我们就知道它属于 。
• 该事实表明，塔式结构通过在坐标向量的后半部分填充零，将  嵌入到  中。从计算角度看，将子域中的元素视为该域扩张中的元素“零成本”。

这些特性使得 Wiedemann 塔非常适合编码和芯片级实现：在任意扩张中，我们无法数学上保证能确定某元素属于哪个子域。然而由于这些域的高度结构化，这个问题往往可以快速解决。或者更确切地说：我们可以轻松表征扩张的子域。

域运算与乘法问题

这类塔的一个有趣方面是坐标在常规域运算下的表现。

加法

在  中的加法（即在坐标上执行的运算）与位异或操作直接等价。有限扩张  中两个元素的加法，就是将它们的坐标对应位模 2 相加。由于模 2 加法等同于异或，这在大多数处理器架构中是一种非常快速高效的按位运算。

乘法

现在问题就出现了。根据元素的表示方式，域元素的乘法可以有不同的实现方式。我们先从最直接的方法说起。

朴素乘法：多项式乘积与约简

在域扩张中，一种比较直接的乘法方法是：首先将元素看作多项式，接着对多项式相乘，最后根据定义扩张的不可约多项式进行模约简。

为了说明，考虑 ，并设

将其看作  上的一次多项式，系数来自 ：

然后用  和  替换：

在特征 2 的域中，，于是

所以在  中，

读者可能已经猜到了——这需要大量的工作。我们希望有一个更高效的域元素乘法算法，能够从高度结构化的扩张塔中汲取灵感。

系统地进行域元素乘法的一种方法是使用类似 Karatsuba 的技术。

Wiedemann 塔中的类似 Karatsuba 的乘法

Karatsuba 算法的主要目的是，当应用于有限域扩展（如 Wiedemann 塔的各层）中的元素乘法时，通过增加域加法和子域乘法的数量来减少较大域中的域乘法数量，方法是利用加法（通过 XOR 完成）在计算上便宜的事实。

具体来说，为了在一个子域上乘以两个一次多项式，一个简单的方法需要在子域中进行四次乘法运算。而 Karatsuba 的方法仅用子域中的三次乘法和少量加法运算就实现了这一点。当这种看似微小的减少在塔式扩展的多层级上递归应用时，其复杂度将变得显著，最终达到亚二次渐近复杂度。

让我们首先描述 Karatsuba 公式，该公式用于计算  中两个元素的乘积（它们是  中次数最多为 1 的多项式，系数为  ），先说明乘法是什么样子，然后再进行观察：

假设我们需要相乘

用  表示  。乘法遵循分配律，所以我们要求的乘积是

• 步骤 1：计算子域  中的三个中间乘积。

这就是 Karatsuba 技巧减少乘法的地方。我们不再计算涉及  的四个乘积，而是计算三个乘法：

并注意到，在特征二中，这三个乘积足以产生  中的系数，因为

我们通常将  称为＂中间项＂。这三个乘法和两个加法是在  中执行的。

• 步骤2：使用定义不可约多项式来约简乘积。

至此，乘积由下式给出：

现在关系  将产生所需乘积的最终表达式：

这是元素的最终约简为标准多项式表示的结果。这里有一点需要特别指出。这个计算是如何进行的？

• 如前所述，系数  和  在子域  中计算。
• 为了计算更大的线性组合，我们必须计算乘积

首先。问题在于，当将  视为  上的向量空间时，与  相乘即为自同构，因此，一旦我们查看Wiedemann塔中方便层级的元素，就可以通过矩阵乘法获得上述乘积 （这就是子域相互连接的方式带来好处的地方）。具体来说，我们首先将  解释为上域  的一个元素。 在坐标系中，这一事实可以通过用零填充坐标  来表示，以获得其坐标  ：

如果我们考虑  ，那么与  的乘积可以在坐标系中通过矩阵乘法来执行：

其中  是一个矩阵，其行是  的基元素与  的乘积在  上的坐标。

• 最后的加法在顶部域  中执行；在坐标中，这只是通过 XOR 完成。

到目前为止的简要总结：

• 层次结构的串联：多线性基（Diamond 和 Posen 隐式采用）的关键思想是，元素在  中的表示仅仅是其在  中的系数的串联。这意味着只需拆分元素的位串即可将其“解包”为其子元素。这是一个“免费”操作，除了索引操作之外无需任何计算。

• 递归应用：Karatsuba 算法完美地映射到这种递归结构。这正是该算法高效运行的设计方式。

• 加法的按位异或：所有加法都只是对坐标向量进行按位异或 (⊕)。这在现代处理器上速度极快，可以在一个周期内对整个机器字执行异或运算。

• 定义的约简：不可约多项式（, , ）是  中的简单三项式或二项式。约简步骤（例如 ）转化为系数向量的线性变换，只需几次异或运算和重新索引即可完成。

• 小系数：由于域为 ，所有系数 () 均为个位（0 或 1）。这简化了  函数中的基数乘法，使其极其高效。

一个手工扩张示例

让我们使用上述算法手工计算中两个元素的乘积，分别是

在继续之前，为了避免递归深入时的繁琐，我们可以实际一点，先构造“乘以 ”映射的矩阵。该矩阵为

它有助于构建完整的乘法表；要将任意元素  乘以 ，我们只需计算