Binius：在二进制域上的高效证明

Binius: 在二进制域上高效的证明

这篇文章主要是面向对2019年时代的加密技术有一定了解的读者，尤其是对SNARKs和STARKs有基础知识的读者。如果你不了解这部分内容，我建议你先阅读这些文章。特别感谢Justin Drake、Jim Posen、Benjamin Diamond和Radi Cojbasic的反馈和审阅。

在过去两年中，STARKs 已成为有效生成易于验证的复杂声明加密证明（例如，证明以太坊区块有效）的一项关键且不可或缺的技术。一个关键原因是小域大小：根据椭圆曲线的SNARKs要求以256位整数进行运算以确保安全，STARKs则允许使用更小的域，这使得计算过程更高效：最初是Goldilocks域（64位整数），然后是Mersenne31和BabyBear（都是31位）。由于这些效率提升，Plonky2在证明许多类型计算时，使用Goldilocks比其前身快了数百倍。

一个自然的问题是：我们能否将这一趋势推向逻辑极限，构建更快的证明系统，通过直接在零和一上进行操作？这正是Binius所尝试的，采用了一些数学技巧，使其与三年前的SNARKs和STARKs显著不同。本文将探讨小域如何使证明生成变得更高效、为何二进制域是独一无二的强大以及Binius用于使二进制域证明如此有效的技巧。

目录

• 回顾：有限域
• 回顾：算术化
• Plonky2：从256位SNARKs和STARKs到64位...仅STARKs
• 从小素数到二进制
• 从单变量多项式到超立方体
• 简单Binius - 一个示例
• 二进制域
• 完整Binius
• 综合总结
• 我们没有涵盖什么？

回顾：有限域 加密证明系统的一项关键任务是必须在处理大量数据时保持数值较小。如果你能将一项有关大型程序的声明压缩成涉及少量数值的数学方程，然而这些数值与原始程序一样大，那么你就没有获得任何收益。为了在保持数值小的条件下进行复杂的算术运算，加密学家通常使用模运算。我们选择某个素数“模数”p。操作符 % 的意思是“取余数”：15 % 7=1，53 % 10=3，等等（注意：答案总是非负的，因此例如 −1 % 10=9）。

我们重新定义：

x+y⇒(x+y) % p

x∗y⇒(x∗y) % p

xy⇒(xy) % p

x−y⇒(x−y) % p

x/y⇒(x∗yp−2) % p

上述规则都是自洽的。例如，如果 p=7，则：

• 5+3=1（因为 8 % 7=1）
• 1−3=5（因为 −2 % 7=5）
• 2⋅5=3
• 3/5=2（因为 (3⋅55) % 7=9375 % 7=2）

这种结构的更一般术语是有限域。有限域是一种数学结构，遵循通常的算术规律，但值的数量有限，因此每个值可以用固定的大小进行表示。

模运算（或素域）是最常见的一种有限域类型，但还有另一种类型：扩展域。你可能已经见过扩展域：复数。我们“想象”一个新元素，我们标记为 i，并声明它满足 i2=−1。然后，你可以采用常规数字和 i 的任意组合，进行数学运算： (3i+2)∗(2i+4)= 6i2+12i+4i+8=16i+2。我们同样可以取素域的扩展。随着我们开始在更小的域上工作，素域的扩展变得越来越重要以保持安全，而二进制域（Binius 使用的）完全依赖于扩展才能具有实用价值。

回顾：算术化 SNARKs 和 STARKs 证明计算机程序中的事物的方式是通过算术化：你将要证明的关于某个程序的声明转换为涉及多项式的数学方程。方程的有效解决方案对应于程序的有效执行。举个简单的例子，假设我计算了第100个斐波那契数，我想向你证明它的值。我要创建一个多项式 F ，它编码了斐波那契数：因此 F(0)=F(1)=1， F(2)=2， F(3)=3， F(4)=5，等等，直到100步。我需要证明的条件是 F(x+2)=F(x)+F(x+1)，适用于范围 x={0,1...98}。如果我能提供有效的 F 和 H，使得满足这个方程，则 F 必须在该范围内满足 F(x+2)−F(x+1)−F(x)。如果我还验证 F 满足 F(0)=F(1)=1，则 F(100) 必须实际上是第100个斐波那契数。如果你想证明更复杂的事情，则可以将“简单”的关系 F(x+2)=F(x)+F(x+1) 替换为一个更复杂的方程式，基本上是“F(x+1) 是使用 F(x) 的状态初始化一个虚拟机并运行一步计算的输出”。你还可以将数字100替换为更大的数字，例如100000000，以容纳更多步骤。

所有的 SNARKs 和 STARKs 都是基于使用一个简单的方程式在多项式（或有时向量和矩阵）上表示大量个体值之间关系的这一思想。并不是所有的证明都以上述方式检查相邻计算步骤之间的等效性：PLONK 就不是这样的，R1CS 也不是。但是，许多效率最优的证明确实如此，因为多次执行相同的检查（或相同的几次检查）可以更容易地减少开销。

Plonky2：从256位SNARKs和STARKs到64位...仅STARKs

五年前，各种类型的零知识证明的合理总结如下。有两种类型的证明：（椭圆曲线基础的）SNARKs 和（哈希基础的）STARKs。从技术上讲，STARKs 是 SNARKs 的一种，但实际上“SNARK”通常用来仅指椭圆曲线基础的种类，而“STARK”则指哈希基础的构造。SNARKs 小，因此你可以非常快速地验证它们并轻松地将其放置在链上。STARKs 大，但它们不需要可信设置，并且具有抗量子能力。

这里的一项历史关键点是，通过广泛使用椭圆曲线基础的SNARKs的引入，使得STARKs直到2018年才变得足够高效， thanks to FRI，在此之前Zcash已经运行了超过一年。椭圆曲线基础的SNARKs有一个关键限制：如果要使用椭圆曲线基础的SNARKs，则必须在椭圆曲线上的点数目进行整数运算。这是一个很大的数字，通常接近2256，例如，对于bn128曲线而言，就是。然而，实际的计算是使用小数：如果你考虑使用你最喜欢的语言编写的“真实”程序，它正在处理的许多内容都是计数器、for循环中的索引、程序中的位置、表示True或False的单独位和其他几乎总是只有几位数的内容。

即使你的“原始”数据由“小”数字组成，证明过程仍然需要计算商、扩展、随机线性组合以及数据的其他变换，这导致平均下与域的完整大小相等或更大的对象数量。这产生了一个关键的低效：为了证明在n个小值上进行计算，你不得不对此些值进行更大的计算。起初，STARKs从SNARKs继承了256位域的习惯，从而遭受了相同的低效。

2022年，Plonky2 发布。Plonky2的主要创新是在较小素数下进行模代数：264−232+1=18446744069414584321。现在，每次加法或乘法都始终可以在 CPU 上通过几条指令完成，对所有数据进行哈希处理的速度是之前的4倍。然而，这有一个问题：这种方法仅适用于 STARK。如果你尝试使用这样小的椭圆曲线进行 SNARK，椭圆曲线将不再安全。

为了继续保持安全，Plonky2还需要引入扩展域。检查算术方程的一项关键技术是“随机点采样”：如果你想检查 H(x)∗Z(x) 实际上等于 F(x+2)−F(x+1)−F(x)，你可以选择一些随机坐标 r，提供多项式承诺开证，证明 H(r)、Z(r)、F(r)、F(r+1) 和 F(r+2)，然后实际检查 H(r)∗Z(r) 是否等于 F(r+2)−F(r+1)−F(r)。如果攻击者可以提前猜测坐标，攻击者可以欺骗证明系统——因此必须随机。但是，这也意味着坐标必须从一个足够大的集合中被抽取，这样攻击者无法通过随机机会来猜测。如果模数接近 2256，显然是这样。但对于264−232+1，就没有那么简单，若降低到231−1，这绝对不是这样。尝试伪造证明二十亿次直到幸运的机会完全在攻击者的能力范围内。

为了阻止这一点，我们从扩展域中采样 r。例如，你可以定义 y，其中 y3=5，并得出 1、y和 y2 的组合。这使得坐标的总数反弹回大约 293。证明者计算的多项式的绝大部分不进入这个扩展域；它们只是使用整数模231−1，因此你仍然可以获得使用小域的所有效率。但随机点检查和FRI计算则深入这个更大的域，以获取所需的安全性。

从小素数到二进制

计算机通过将较大的数字表示为零和一的序列，并在这些位上构建“电路”来计算加法和乘法等操作。计算机特别优化用于计算16位、32位和64位整数。像264−232+1和231−1这样的模数选择不仅因其符合这些边界，还因为它们与这些边界良好对齐：你可以通过进行常规的32位乘法来进行模264−232+1的乘法，并在几处进行位移和复制输出；这篇文章很好地解释了其中的一些技巧。

然而，更好的方式是直接在二进制中进行计算。如果加法可以“只是”XOR，而不需要担心将某个一位的溢出“进位”到下一位怎么办？如果乘法在同样的方式上更可并行化又如何？而且所有这些优势还可以在仅用一个比特表示True/False值的基础上获得。

捕捉直接进行二进制计算的这些优势正是Binius的目标。以下是Binius团队在zkSummit的演示的一张表格，展示了效率收益：

尽管“尺寸”大致相同，但32位二进制域运算的计算资源消耗比31位Mersenne域的运算少5倍。

从单变量多项式到超立方体 假设我们相信这个理由，并希望对位（零和一）进行一切操作。我们如何实际承诺一个代表十亿个位的多项式？在这里，我们面临两个实际问题：

1. 要生成大量值，必须在多项式的评估中可以访问这些值：在上述斐波那契示例中，F(0)、F(1)...F(100)，在更大计算中，索引的范围将达到数百万。而且我们所使用的域需要包含数字，其大小可以达到此类规模。

2. 证明我们在 Merkel 树中的某个值的承诺（因为所有 STARKs 都这样做）需要进行Reed-Solomon编码：将 n 个值扩展到例如 8n 个值，使用冗余以阻止恶意证明者通过伪造计算中间的某个值来欺骗。这还需要一个大得足够的域：为了将百万个值扩展到800万，你需要800万个不同的点来评估该多项式。

Binius中的一个关键想法是分别解决这两个问题，并通过将相同的数据用两种不同的方法表示来做到这一点。首先，是多项式本身。基于椭圆曲线的SNARKs、2019年时代的STARKs、Plonky2及其他系统通常处理单一变量的多项式：F(x)。而Binius则受到Spartan协议的启发，处理多变量多项式：F(x1,x2...xk)。实际上，我们在“超立方体”评估上的整个计算轨迹进行表示，其中每个xi都是0或1。例如，如果我们想表示一个斐波那契数列，并且我们的域仍然足够大以进行表示，我们可以将前十六个数可视化如下：

即，F(0,0,0,0)将是1，F(1,0,0,0)也将是1，F(0,1,0,0)将是2，依此类推，直到我们得到F(1,1,1,1)=987。给定这样的评估超立方体，能够产生这些评估的确切一个多项式是多线性的（每个变量的程度为1）。因此，我们可以将这一组评估视为表示多项式；我们实际上从不需要繁琐地计算系数。

这个例子当然只是为了说明：实际上，采用超立方体的整个要点是让我们能够使用单个位。使用 Binius 计算斐波那契数的“本土”方式将是使用高维立方体，并使用每组例如16个位来存储一个数字。这需要一些巧妙的方法来在个位上实现整数加法，但是使用Binius这并不太难实现。

现在，我们进入擦除编码。STARKs 的工作方式为：你获取 n 个值，将它们进行 Reed-Solomon 扩展，扩展到更大的值（通常是 8n，通常在 2n 到 32n之间），然后随机选择一些来自该扩展的Merkle分支并对其执行某种检查。超立方体在每个维度上都有长度 2。因此，直接扩展它并不实际：没有足够的“空间”从16个值中采样Merkl 分支。那么我们该怎样做呢？我们假装超立方体是个方形！

简单Binius - 一个示例

参见这里以了解该协议的Python实现。

我们来通过一个示例，通过常规整数作为我们的域（在真实实现中将是二进制域元素）来演示。首先，我们获取要承诺的超立方体，并将其编码为一个方形：

现在，我们对方形进行Reed-Solomon扩展。也就是说，我们将每一行视作在 x = {0, 1, 2, 3} 下评估的一个三次多项式，并在 x = {4, 5, 6, 7} 下评估相同的多项式：

注意，数字增涨很快！这就是为什么在实际实现中，我们总是针对有限域使用此方法，而不是常规数字：例如，如果我们使用模11的整数，则第一行的扩展仅为[3, 10, 0, 6]。

如果你想亲自尝试扩展并验证此处的数字，你可以使用我的简单Reed-Solomon扩展代码。

接下来，我们将此扩展视为列，并构建列的Merkle树。Merkle树的根为我们的承诺。

现在，假设证明者想要证明在某个点 r={r0,r1,r2,r3} 下该多项式的评估。有一点需要注意，在 Binius 中使其比其他多项式承诺方案稍显脆弱：证明者不应在承诺Merkle 根之前知道或猜测 s（换句话说，r 应该是一个依赖于Merkle根的伪随机值）。这使得该方案对于“数据库查询”无用（例如，“好的，你给我了Merkle根，现在向我证明P(0,0,1,0)！”）。但我们实际使用的零知识证明协议通常不需要“数据库查询”；它们只需要在随机评估点检查多项式。因此，这一限制对于我们的目的来说是可以接受的。

假设我们选择 r={1,2,3,4}（此时该多项式的评估结果为−137；你可以通过这段代码进行验证）。现在，我们进入实际制作证明的过程。我们将 r 分为两部分：第一部分 {1,2} 表示一行内的列的线性组合，第二部分 {3,4} 表示行的线性组合。我们计算一个“张量积”，对于列部分也是如此：

⨂i=01(1−ri,ri)

对于行部分：

⨂i=23(1−ri,ri)

这意味着：从每个集合中获取一个值的所有可能乘积列表。在行情况下，我们得到：

[(1−r2)∗(1−r3),r2∗(1−r3),(1−r2)∗r3,r2∗r3]

使用 r={1,2,3,4}（因此 r2=3 和 r3=4）：

[(1−3)∗(1−4),3∗(1−4),(1−3)∗4,3∗4]=[6,−9,−8,12]

现在，我们通过取现有行的线性组合计算出一个新“行” t′，即，我们取：

[3,1,4,1]∗6 +[5,9,2,6]∗(−9) +[5,3,5,8]∗(−8) +[9,7,9,3]∗12=[41,−15,74,−76]

你可以将这里发生的情况视为局部评估。也就是说，如果我们对完整的张量积 ⨂i=03(1−ri,ri) 和所有值的向量进行乘法运算，你将获得评估 P(1,2,3,4)=−137。这里我们只在使用一半的评估坐标来计算 局部 张量积，并且将 N 值的网格缩减为一行 N 值。如果你将这一行提供给其他人，他们可以使用 另一半 评估坐标的张量积来完成其余计算。

证明者向验证者提供此新行 t′以及从一些随机抽样的列中获得的 Merkle 证明。这是 O(N) 数据。在我们的示例中，证明者只需提供最后一列；在现实中，证明者需要提供十几列以实现足够的安全性。

现在，我们利用Reed-Solomon代码的线性关系。我们使用的关键属性是：对Reed-Solomon扩展进行线性组合的结果与线性组合的Reed-Solomon扩展相同。当你拥有两种线性操作时，这种“顺序独立性”通常会发生。

验证者正是这样做的。他们计算 t′ 的扩展，并计算证明者之前计算的相同列的线性组合（但仅限于证明者提供的列），并验证这两个过程是否得到相同的答案。

在这种情况下，扩展 t′、以及计算相同的线性组合（[6,−9,−8,12]）的列，都给出相同的答案：−10746。这证明Merkle根是“合乎信心”构造的（或者至少“足够接近”），并且与t′匹配：至少大部分列彼此兼容，并且与 t′ 匹配。

但是验证者还需要检查一项内容：即检查在 {r0..r3} 的多项式评估。到目前为止，验证者的步骤实际上并未依赖于证明者声称的值。因此我们该如何完成这一检查。我们从“评估点的列部分”取得张量积：

⨂i=01(1−ri,ri)

在我们的示例中，r={1,2,3,4}（因此选择列的那一半为{1,2}），这等于：

[(1−1)∗(1−2),1∗(1−2),(1−1)∗2,1∗2]=[0,−1,0,2]

现在我们取这一 t′ 的线性组合：

0∗41+(−1)∗(−15)+0∗74+2∗(−76)=−137

这恰好等于你直接计算多项式评估的答案。

以上是“简单”Binius协议的近乎完整描述。这已经具有一些有趣的优势；例如，由于数据被拆分为行和列，你只需使用一半大小的域。但这仍然无法充分实现二进制计算的全部优势。为此，我们需要完整的 Binius 协议。但首先，我们需要更深入理解二进制域。

二进制域 最小的可能域是模2运算，其小到可以直接写出加法和乘法表：

通过进行扩展，我们可以生成更大的二进制域：如果我们从 F2（模2的整数）开始，定义 x，使得 x2=x+1，得到以下加法和乘法表：

事实证明，我们可以通过重复这个构建将二进制域扩展到任意大小。与通过实数构建复数不同，在那里你只能添加一个新元素 i，但无法再添加其他。（四元数确实存在，但它们在数学上是奇怪的，例如 ab≠ba），在有限域中，你可以不断添加新的扩展。具体来说，我们定义元素如下：

• x0 满足 x02=x0+1
• x1 满足 x12=x1x0+1
• x2 满足 x22=x2x1+1
• x3 满足 x32=x3x2+1

依此类推。这通常被称为塔构造，因每个后续扩展可以被视为向塔中添加一个新层。虽然构建二进制域的方法并非唯一，但有一些独特优势，Binius将其利用到了。

我们可以将这些数字表示为位的列表，例如 1100101010001111。第一个位表示1的倍数，第二个位表示 x0 的倍数，接下来的位表示：x1、x1∗x0、x2、x2∗x0，等等。这种编码的好处是你可以将其分解为：

1100101010001111=11001010+10001111∗x3 =1100+1010∗x2+1000∗x3+1111∗x2x3 =11+10∗x2+10∗x2x1+10∗x3+11∗x2x3+11∗x1x2x3+x0x1x2x3

这是一种相对不常见的表示法，但我倾向于将二进制域元素表示为整数，采用更高位对应左边的比特表示方式。也就是，1=1，x0=01=2，1+x0=11=3，1+x0+x2=11001000=19，等等。1100101010001111 在这种表示法下为61779。

二进制域的加法仅为XOR（顺便说一下，减法也是如此）；请注意，这意味着 x+x=0 对于任意的 x。乘以两个元素 x∗y，有个相对简单的递归算法：将每个数字分割为两个部分：

x=Lx+Rx∗xk y=Ly+Ry∗xk

然后分割乘法：

x∗y=(Lx∗Ly)+(Lx∗Ry)∗xk+(Rx∗Ly)∗xk+(Rx∗Ry)∗xk2

最后一项是唯一一个稍微棘手的部分，因为你必须应用减少规则，用 xk2 替换 Rx∗Ry∗xk2为 Rx∗Ry∗(xk−1∗xk+1)。还有更有效的方法来进行乘法，类似于Karatsuba算法和快速傅里叶变换，但我会将这些留给感兴趣的读者去研究。

在二进制域中除法是通过组合乘法和求逆实现的：35=3∗15。“简单但慢”的求逆方法是应用广义费马小定理：1x=x22k−2对于任意 k，满足 22k>x。在这种情况下，15=514=14，因此 35=3∗14=9。还有一种复杂但更高效的求逆算法，你可以在这里找到：这里。你可以使用这里的代码进行二进制域的加法、乘法和除法练习。

关于这种类型的二进制域的美妙之处在于，它结合了“常规”整数和模运算的一些最佳部分。类似于常规整数，二进制域元素是无限的：你可以无限扩展到任意远。但如同模运算一样，如果你在特定大小限制范围内执行操作，所有的答案也会保持在相同的限制内。例如，如果你按42的连续幂进行操作，得到：

1,42,199,215,245,249,180,91...

并且经过255步，你会再次到达42255=1。而且，像“常规整数”和模运算一样，它们遵循通常的数学规律：a∗b=b∗a，a∗(b+c)=a∗b+a∗c，即使是一些奇怪的新规律，例如 a2+b2=(a+b)2（正常的 2ab 项是缺失的，因为在二进制域中1+1=0）。

最后，二进制域与位的协作非常方便：如果你用适合于 2k 位的数字进行数学计算，那么所有的输出也会适合于 2k 位。这避免了例如以太坊的EIP-4844所拥有的麻烦，其中单个“块”必须是模某个数的数字，因此对二进制数据进行编码需要丢弃一个比特的空间，在应用层面上进行额外检查，以确保每个元素存储的值小于2248。这也意味着在计算机上进行二进制域的算术运算是超级快速的——无论是在 CPU上，还是理论上最优化的FPGA和ASIC设计中。

这就意味着我们可以像我们上面做的 Reed-Solomon 编码那样做到，以完全避免整数的“膨胀”，正如我们在示例中看到的，并采用方式，与计算机擅长的计算方式极为“原生”。二进制域的“分裂”特性——我们如何进行1100101010001111=11001010+10001111∗x3，然后根据需要分割任意多或少，这也对实现诸多灵活性至关重要。

完整Binius

请参见这里以了解该协议的 Python 实现。

现在，我们可以讨论“完整 Binius”，调整“简单 Binius”以（i）在二进制域上工作，并（ii）允许我们承诺单个位。这个协议很复杂，因为它不断在不同的位矩阵表示之间切换；我花的时间超过了通常理解一个加密协议所需的时间。不过，一旦你理解了二进制域，好消息是 Binius 的逻辑并没有依赖于任何“更困难的数学”。这并不是椭圆曲线对，它涉及的代数几何越来越复杂；在这里，二进制域就是全部需要的。

让我们再次看看完整的框架：

现在，你应该熟悉大多数组件。将超立方体“扁平化”成网格，将评估点的行组合和列组合计算为张量的想法，以及检查“先进行Reed-Solomon扩展再计算行组合，以及后计算再进行Reed-Solomon扩展”的等价性，都是简单 Binius 中的内容。

“完整 Binius”中的新内容大概有三点：

• 超立方体和方形中的单个值必须是比特（0 或 1）
• 扩展过程通过将比特分组到列中并假设它们是较大域元素来扩展比特
• 在行组合步骤之后，有一个逐元素的“分解为比特”步骤，它将扩展转换回比特我们将依次讨论两个内容。首先是新的扩展方案。Reed-Solomon 编码有一个基本的限制，即如果你要将 n 个值扩展到 k∗n 个值，则需要在具有 k∗n 个不同值的域中工作。使用 F2（即比特），你无法做到这一点。因此，我们所做的就是将相邻的 F2 元素“打包”成更大的值。在这里的示例中，我们一次打包两个比特到 {0,1,2,3} 中的元素，因为我们的扩展只有四个评估点，这对我们来说已经足够了。在“真实”的证明中，我们可能将 16 个比特同时打包在一起。然后我们对这些打包的值执行 Reed-Solomon 编码，并再次将其解包为比特。

现在是行组合。为了使“在随机点评估”检查具有密码学安全性，我们需要将该点从一个相当大的空间中抽样，这个空间的大小远远大于超立方体本身。因此，虽然在超立方体 内部 的点是比特，但超立方体 外部 的评估则大得多。在我们上面的示例中，“行组合”最终为 [11,4,6,1]。

这提出了一个问题：我们知道如何将 比特 成对组合成一个更大的值，然后对其执行 Reed-Solomon 扩展，但如何将更大值的成对进行相同的操作呢？

Binius 的窍门是逐位进行：我们查看每个值的单个比特（例如，对于我们标记为“11”的值，那是 [1,1,0,1]），然后我们逐行展开。也就是说，我们在每个元素的 1 行上执行扩展程序，然后是在 x0 行上，然后是在“x1”行上，然后是在 x0∗x1 行上，以此类推（在我们的玩具示例中我们就停在这里，但在真实的实现中我们会扩展到 128 行（最后一行为 x6∗...∗x0））。

总结：

• 我们获取超立方体中的比特，将其转换为一个网格
• 然后，我们将每行上的相邻比特组作为更大的域元素进行处理，并对它们进行算术运算，以对行进行 Reed-Solomon 扩展
• 然后，我们对每列的比特进行行组合，得到每行输出的（对于大于 4x4 的平方，远小于的）比特列
• 然后，我们将输出视为矩阵，并将 该 矩阵的比特再次视为行

这为什么有效呢？在“普通”的数学中，如果你开始通过数字切割一个数，通常可以以任意顺序进行线性运算并获得相同结果的能力就不再有效。例如，如果我从数字 345 开始，先乘以 8 再乘以 3，我得到 8280，如果将这两个操作反转，我也会得到 8280。但如果我在两个步骤之间插入一个“按位切分”的操作，它就会崩溃：如果你先做 8x，然后 3x，你得到：

345→×82760→[2,7,6,0]→×3[6,21,18,0]

但如果你先做 3x，然后 8x，你得到：

345→×31035→[1,0,3,5]→×8[8,0,24,40]

但在使用 tower 结构构建的二元域中，这种情况 是 有效的。其原因与它们的可分性有关：如果你将一个大的值乘以一个小的值，那么每个部分发生的情况将保持在各自的部分内。如果我们将 1100101010001111 乘以 11，这相当于首先将 1100101010001111 分解为 11+10∗x2+10∗x2x1+10∗x3+11∗x2x3+11∗x1x2x3，然后分别乘以 11。

综合起来，总体上，零知识证明系统通过对多项式的陈述工作，而这些多项式同时表示底层评估的陈述：就像我们在 Fibonacci 示例中看到的那样，F(X+2)−F(X+1)−F(X)=Z(X)∗H(X) 同时检查 Fibonacci 计算的所有步骤。我们通过在一个随机点证明评估来检查多项式的陈述：给定对 F 的承诺，你可以随机选择例如 1892470，要求在该点（和相邻点）上对 F、Z 和 H 的评估进行证明，检查这些证明，然后检查 F(1892472)−F(1892471)−F(1892470) = Z(1892470)∗H(1892470)。这个在随机点的检查相当于检查整个多项式：如果多项式方程 不 匹配，恰好在某个随机坐标上匹配的机会非常小。在实践中，主要的效率来源于这样的事实：在真实程序中，我们处理的大多数数字都是微小的：循环中的索引、真/假值、计数器等。但当我们使用 Reed-Solomon 编码来“扩展”数据，以提供 Merkle 证明基础的检查所需的冗余时，大多数“额外”值最终会占据域的全大小，即使原始值很小。为了应对这一点，我们希望将域设得尽可能小。Plonky2 使我们从 256 位数字降到 64 位数字，然后 Plonky3 进一步降至 31 位。但即使这样也是亚最优的。使用二元域，我们可以在 单个比特 上工作。这使得编码“密集”：如果你实际使用的数据有 n 个比特，那么你的编码将也有 n 个比特，扩展将有 8 * n 个比特，没有额外的开销。现在，让我们第三次查看图表：

在 Binius 中，我们承诺一个 多线性多项式 ：一个超立方体 P(x0,x1...xk)，每个单独的评估 P(0,0...0)、P(0,0...1) 一直到 P(1,1,...1) 都包含我们关心的数据。为了证明在某个点的评估，我们“重新解释”相同的数据为一个平方。然后，我们使用 Reed-Solomon 编码对每 行 进行扩展，使用比特组来为数据提供随机 Merkle 分支查询的冗余。然后我们计算行的随机线性组合，系数设计得使得新的组合行实际包含我们关心的评估。然后将这个新创建的行（再次被重新解释为 128 行比特）和几个随机选出的包含 Merkle 分支的列传递给验证者。这是 O(N) 数据：新的行有 O(N) 的大小，每个（常数数量的）被传递列都有 O(N) 的大小。然后，验证者会进行“扩展的行组合”（或者说一些扩展的列），以及“行组合的扩展”，并验证这两个是否匹配。然后，他们计算一个 列 组合，并检查其返回的值是否为证明者所主张的值。而这就是我们的证明系统（或者说是 多项式承诺方案 ，这是证明系统的重要构建块）。

我们_没有_讨论什么？

• 扩展行的高效算法，这对于实际提升验证者的计算效率至关重要，使其达到 O(N)。使用朴素的拉格朗日插值，我们只能得到 O(N23)。为此，我们使用二元域上的快速傅里叶变换，在这里描述（尽管确切的实现会有所不同，因为这个帖子使用的是一种基于递归扩展的效率较低的构造）。
• 算术化。单变量多项式非常方便，因为可以像 F(X+2)−F(X+1)−F(X)=Z(X)∗H(X) 一样进行操作，以关联计算中的相邻步骤。在超立方体中，“下一个步骤”的解释并不像“X+1”那样简洁。你可以进行 X∗k 并在 k 的幂次间跳转，但这种跳转行为将会牺牲 Binius 的许多关键优势。Binius 论文引入了对此的解决方案（例如，见第 4.3 节），但这本身也是一个“深兔子洞”。
• 如何安全地进行特定值检查。Fibonacci 示例需要检查关键的边界条件：F(0)=F(1)=1，以及 F(100) 的值。但使用“原始” Binius，在已知评估点进行检查是不安全的。有相当简单的方法可以使用所谓的求和检查协议将已知评估检查转换为未知评估检查；但我们在这里没有探讨这些。
• 查找协议，另一项技术，最近作为一种使超高效率证明系统发挥作用的方式正在获得使用。Binius 可以与查找协议结合用于许多应用。
• 超越平方根验证时间。平方根开销昂贵：232 位的 Binius 证明大约为 11 MB 长。你可以使用其他证明系统来制作“Binius 证明的证明”来解决此问题，从而同时获得 Binius 在证明主要声明方面的效率 和 小的证明大小。另一个选择是更复杂的 FRI-Binius 协议，该协议创建了一个多对数大小的证明（就像 常规 FRI）。
• Binius 如何影响 "SNARK 友好" 的定义。基本总结是，如果你使用 Binius，你将不再需要过多关心使计算“算术友好”:“常规”哈希不再比传统算术哈希更高效，模 232 或模 2256 的乘法相较于模 p 的乘法也不再是大头痛，等等。但这是一个复杂的话题；当一切都在二元中完成时，许多事情都会改变。

我预计在未来几个月，基于二元域的证明技术会有更多改进。

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