Vitalik：Binius——对二进制字段的高效证明

这篇文章主要针对大致熟悉2019年时代密码学的读者，特别是SNARK和STARK。如果你不是，我建议你先阅读这些文章。特别感谢Justin Drake, Jim Posen, Benjamin Diamond和Radi Cojbasic的反馈和评论。

在过去的两年中，STARK已经成为一种关键且不可替代的技术，可以有效地对非常复杂的语句进行易于验证的加密证明（例如，证明以太坊区块是有效的）。其中一个关键原因是字段大小小：基于椭圆曲线的 SNARK 要求您在 256 位整数上工作才能足够安全，而 STARK 允许您使用更小的字段大小，效率更高：首先是 Goldilocks 字段（64 位整数），然后是 Mersenne31 和 BabyBear（均为 31 位）。由于这些效率的提高，使用Goldilocks的Plonky2在证明多种计算方面比其前辈快数百倍。

一个自然而然的问题是：我们能否将这一趋势引向合乎逻辑的结论，通过直接在零和一上操作来构建运行速度更快的证明系统？这正是 Binius 试图做的事情，使用了许多数学技巧，使其与三年前的 SNARK 和 STARK 截然不同。这篇文章介绍了为什么小字段使证明生成更有效率，为什么二进制字段具有独特的强大功能，以及 Binius 用来使二进制字段上的证明如此有效的技巧。

Binius。在这篇文章的最后，你应该能够理解此图的每个部分。

回顾：有限域（finite fields）

加密证明系统的关键任务之一是对大量数据进行操作，同时保持数字较小。如果你可以将一个关于大型程序的语句压缩成一个包含几个数字的数学方程，但是这些数字与原始程序一样大，那么你将一无所获。

为了在保持数字较小的情况下进行复杂的算术，密码学家通常使用模运算(modular arithmetic)。我们选择一个质数“模数”p。%运算符的意思是“取余数”：15%7=1，53%10=3，等等。（请注意，答案总是非负数的，所以例如-1%10=9）

你可能已经在时间的加减上下文中见过模运算(例如，9点过4小时是几点？但在这里，我们不只是对某个数进行加、减模，我们还可以进行乘、除和取指数。

我们重新定义：

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

5+3=1（因为8%7=1）

1-3=5（因为-2%7=5）

2*5=3

3/5=2

这种结构的更通用术语是有限域。有限域是一种数学结构，它遵循通常的算术法则，但其中可能的值数量有限，因此每个值都可以用固定的大小表示。

模运算(或质数域)是有限域最常见的类型，但也有另一种类型：扩展域。你可能已经见过一个扩展字段：复数。我们“想象”一个新元素，并给它贴上标签i，并用它进行数学运算：（3i+2）*（2i+4）=6i*i+12i+4i+8=16i+2。我们可以同样地取质数域的扩展。当我们开始处理较小的字段时，质数字段的扩展对于保护安全性变得越来越重要，而二进制字段(Binius使用)完全依赖于扩展以具有实际效用。

回顾：算术化

SNARK 和 STARK证明计算机程序的方法是通过算术：你把一个关于你想证明的程序的陈述，转换成一个包含多项式的数学方程。方程的有效解对应于程序的有效执行。

举个简单的例子，假设我计算了第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}。我可以通过给你商数来说服你：

其中 Z(x) = (x-0) * (x-1) * …(x-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，以容纳更多的步骤。

所有 SNARK 和 STARK 都基于这种想法，即使用多项式(有时是向量和矩阵)上的简单方程来表示单个值之间的大量关系。并非所有的算法都像上面那样检查相邻计算步骤之间的等价性：例如，PLONK没有，R1CS也没有。但是许多最有效的检查都是这样做的，因为多次执行相同的检查(或相同的少数检查) 可以更轻松地将开销降至最低。

Plonky2：从 256 位 SNARK 和 STARK 到 64 位......只有STARK

五年前，对不同类型的零知识证明的合理总结如下。有两种类型的证明：(基于椭圆曲线的)SNARK和(基于哈希的)STARK。从技术上讲，STARK是SNARK的一种，但在实践中，通常使用“SNARK”来指代基于椭圆曲线的变体，而使用“STARK”来指代基于哈希的结构。SNARK很小，因此你可以非常快速地验证它们并轻松地将它们安装在链上。STARK很大，但它们不需要可信的设置，而且它们是抗量子的。

STARK 的工作原理是将数据视为多项式，计算该多项式的计算，并使用扩展数据的默克尔根作为“多项式承诺”

这里的一个关键历史是，基于椭圆曲线的SNARK首先得到了广泛的使用：直到 2018 年左右，STARK 才变得足够高效，这要归功于 FRI，而那时 Zcash 已经运行了一年多。基于椭圆曲线的SNARK有一个关键的限制：如果你想使用基于椭圆曲线的SNARK，那么这些方程中的算术必须使用椭圆曲线上的点数模数来完成。这是一个很大的数字，通常接近2的256次方：例如，bn128曲线为21888242871839275222246405745257275088548364400416034343698204186575808495617。但实际的计算使用的是小数字：如果你用你最喜欢的语言来考虑一个“真正的”程序，它使用的大部分东西是计数器，for循环中的索引，程序中的位置，代表True或False的单个位，以及其他几乎总是只有几位数长的东西。

即使你的“原始”数据由“小”数字组成，证明过程也需要计算商数、扩展、随机线性组合和其他数据转换，这将导致相等或更大数量的对象，这些对象的平均大小与你的字段的全部大小一样大。这造成了一个关键的低效率：为了证明对n个小值的计算，你必须对n个大得多的值进行更多的计算。起初，STARK继承了SNARK使用256位字段的习惯，因此也遭受了同样的低效率。

一些多项式求值的Reed-Solomon扩展。尽管原始值很小，但额外的值都将扩展到字段的完整大小(在本例中是2的31次方-1)

2022年，Plonky2发布。Plonky2的主要创新是对一个较小的质数进行算术取模：2的64次方 – 2的32次方 + 1 = 18446744067414584321。现在，每次加法或乘法总是可以在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)。如果攻击者可以提前猜出坐标，那么攻击者就可以欺骗证明系统——这就是为什么证明系统必须是随机的。但这也意味着坐标必须从一个足够大的集合中采样，以使攻击者无法随机猜测。如果模数接近2的256次方，这显然是事实。但是，对于模数量是2的64次方-2的32次方+1，我们还没到那一步，如果我们降到2的31次方-1，情况肯定不是这样。试图伪造证明20亿次，直到一个人幸运，这绝对在攻击者的能力范围内。

为了阻止这种情况，我们从扩展字段中采样r，例如，你可以定义y，其中y的3次方=5，并采用1、y、y的2次方的组合。这将使坐标的总数增加到大约2的93次方。证明者计算的多项式的大部分不进入这个扩展域；只是用整数取模2的31次方-1，因此，你仍然可以从使用小域中获得所有的效率。但是随机点检查和FRI计算确实深入到这个更大的领域，以获得所需的安全性。

从小质数到二进制数

计算机通过将较大的数字表示为0和1的序列来进行算术运算，并在这些bit之上构建“电路”来计算加法和乘法等运算。计算机特别针对16位、32位和64位整数进行了优化。例如，2的64次方-2的32次方+1和2的31次方-1，选择它们不仅是因为它们符合这些界限，还因为它们与这些界限很吻合：可以通过执行常规的 32 位乘法来执行乘法取模 2的64次方-2的32次方+1，并在几个地方按位移位和复制输出；这个文章很好地解释了一些技巧。

然而，更好的方法是直接用二进制进行计算。如果加法可以“只是”异或，而无需担心“携带”从一个位添加1 + 1到下一个位的溢出？如果乘法可以以同样的方式更加并行化呢？这些优点都是基于能够用一个bit表示真/假值。

获取直接进行二进制计算的这些优点正是Binius试图做的。Binius团队在zkSummit的演讲中展示了效率提升：

尽管“大小”大致相同，但32位二进制字段操作比31位Mersenne字段操作所需的计算资源少5倍。

从一元多项式到超立方体

假设我们相信这个推理，并且想要用bit(0和1)来做所有的事情。我们如何用一个多项式来表示十亿bit呢？

在这里，我们面临两个实际问题：

1.对于一个表示大量值的多项式，这些值需要在多项式的求值时可以访问：在上面的斐波那契例子中，F(0)，F(1) … F(100)，在一个更大的计算中，指数会达到数百万。我们使用的字段需要包含到这个大小的数字。

2.证明我们在Merkle树中提交的任何值(就像所有STARK一样)都需要Reed-Solomon对其进行编码：例如，将值从n扩展到8n，使用冗余来防止恶意证明者通过在计算过程中伪造一个值来作弊。这也需要有一个足够大的字段：要将一百万个值扩展到800万个，你需要800万个不同的点来计算多项式。

Binius的一个关键思想是分别解决这两个问题，并通过以两种不同的方式表示相同的数据来实现。首先，多项式本身。基于椭圆曲线的SNARK、2019时代的STARK、Plonky2等系统通常处理一个变量上的多项式：F(x)。另一方面，Binius从Spartan协议中获得灵感，并使用多元多项式：F(x1,x2,… xk)。实际上，我们在计算的“超立方体”上表示整个计算轨迹，其中每个xi不是0就是1。例如，如果我们想要表示一个斐波那契数列，并且我们仍然使用一个足够大的字段来表示它们，我们可以将它们的前16个数列想象成这样：

也就是说，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)多项式。所以我们可以把这组值看作是多项式的代表；我们不需要计算系数。

这个例子当然只是为了说明：在实践中，进入超立方体的全部意义是让我们处理单个bit。计算斐波那契数的“Binius原生”方法是使用一个高维的立方体，使用每组例如16位存储一个数字。这需要一些聪明才智来在bit的基础上实现整数相加，但对于Binius来说，这并不太难。

现在，我们来看看纠删码。STARK的工作方式是：你取n值，Reed-Solomon将它们扩展到更多的值(通常8n，通常在2n和32n之间)，然后从扩展中随机选择一些Merkle分支，并对它们执行某种检查。超立方体在每个维度上的长度为2。因此，直接扩展它是不实际的：没有足够的“空间”从16个值中采样Merkle分支。那么我们该怎么做呢？我们假设超立方体是一个正方形！

简单的Binius -一个例子

请参阅此处查看该协议的python实现。

让我们看一个示例，为了方便起见，使用正则整数作为我们的字段(在实际实现中，将使用二进制字段元素)。首先，我们将想要提交的超立方体，编码为正方形：

现在，我们用Reed-Solomon扩展正方形。也就是说，我们将每一行视为在x ={0,1,2,3}处求值的3次多项式，并在x ={4,5,6,7}处求值相同的多项式：

注意，数字会迅速膨胀！这就是为什么在实际实现中，我们总是使用有限域，而不是正则整数：如果我们使用整数模11，例如，第一行的扩展将只是[3,10,0,6]。

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

接下来，我们将此扩展视为列，并创建列的Merkle树。默克尔树的根是我们的承诺。

现在，让我们假设证明者想要在某个时候证明这个多项式的计算r={r0,r1,r2,r3}。在Binius中有一个细微的差别，使它比其他多项式承诺方案更弱：证明者在提交到 Merkle 根之前不应该知道或能够猜测s  (换句话说，r应该是一个依赖于默克尔根的伪随机值)。这使得该方案对“数据库查找”无用(例如，“好吧，你给了我默克尔根，现在证明给我看P(0,0,1,0) ！”)。但是我们实际使用的零知识证明协议通常不需要“数据库查找”；他们只需要在一个随机的求值点检查多项式。因此，这个限制符合我们的目的。

假设我们选择r={1,2,3,4} (此时多项式的计算结果为-137；你可以使用此代码进行确认)。现在，我们进入了证明的过程。我们分为r两部分：第一部分{1,2}表示行内列的线性组合，第二部分{3,4}表示行的线性组合。我们计算一个“张量积”，对于列部分：

对于行部分：

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

[(1-r2)*(1-r3), (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。也就是说，我们取：

你可以把这里发生的看作是部分求值。如果我们把全张量乘积乘以所有值的全向量，你将得到计算P(1,2,3,4) = -137。在这里，我们将仅使用一半评估坐标的偏张量乘积相乘，并将N值网格简化为一行根号N的值。如果你把此行提供给其他人，他们可以用另一半的求值坐标的张量积来完成剩下的计算。

证明者向验证者提供以下新行：t以及一些随机抽样列的Merkle证明。在我们的说明性示例中，我们将让证明程序只提供最后一列；在现实生活中，证明者需要提供几十列来实现足够的安全性。

现在，我们利用Reed-Solomon代码的线性。我们使用的关键属性是：取一个Reed-Solomon扩展的线性组合得到与线性组合的Reed-Solomon扩展相同的结果。这种“顺序独立性”通常发生在两个操作都是线性的情况下。

验证者正是这样做的。他们计算了t，并且计算与证明者之前计算的相同的列的线性组合(但只计算证明者提供的列)，并验证这两个过程是否给出相同的答案。

关于【Vitalik：Binius——对二进制字段的高效证明】的延伸阅读

• a16z：机器学习和零知识证明的制衡

  本文详述了零知识证明在机器学习中的应用方式以及两个领域互为促进的多种推演。

• Starknet的空投到底成不成功？

  本文比较了Starknet和Optimism两次代币空投的差异，发现Optimism更节省Gas，但Starknet的数据收集困难。数据显示，只有39.8%的人领取了空投，且空投效果不佳，只有1.1%的用户最终保留了代币。代币价格下跌50%，但TVL保持稳定。总体来看，这次空投并不成功。STARK空投效果不佳，只有1.1%的用户保留了代币，但从保留和CAC角度来看，相对成功。STARK采取了多样性分配代币的思路，但收集和分析数据仍然困难，需要更合适的工具。

在本例中，是扩展t，计算相同的线性组合([6,-9,-8,12]，两者给出了相同的答案：-10746。这证明默克尔的根是“善意”构建的(或者至少“足够接近”)，而且它是匹配t的：至少绝大多数列是相互兼容的。

但是验证者还需要检查另一件事：检查多项式{r0…r3}的求值。到目前为止，验证者的所有步骤实际上都没有依赖于证明者声称的值。我们是这样检查的。我们取我们标记为计算点的“列部分”的张量积：

在我们的例子中，其中 r={1,2,3,4} 所以选择列的那一半是{1,2})，这等于：

现在我们取这个线性组合t：

这和直接求多项式的结果是一样的。

以上内容非常接近于对“简单”Binius协议的完整描述。这已经有了一些有趣的优点：例如，由于数据被分成行和列，因此你只需要一个大小减半的字段。但是，这并不能实现用二进制进行计算的全部好处。为此，我们需要完整的Binius协议。但首先，让我们更深入地了解二进制字段。

二进制字段

最小的可能域是算术模2，它非常小，我们可以写出它的加法和乘法表：

我们可以通过扩展得到更大的二进制字段：如果我们从F2(整数模2)然后定义x在哪里 x的平方=x+1，我们得到以下的加法和乘法表：

事实证明，我们可以通过重复这个构造将二进制字段扩展到任意大的大小。与实数上的复数不同，在实数上，你可以加一个新元素，但不能再添加任何元素I （四元数确实存在，但它们在数学上很奇怪，例如：ab不等于ba)，使用有限的字段，你可以永远添加新的扩展。具体来说，我们对元素的定义如下：

等等......。这通常被称为塔式结构，因为每一个连续的扩展都可以被看作是给塔增加了一个新的层。这并不是构造任意大小二进制字段的唯一方法，但它有一些独特的优点，Binius利用了这些优点。

我们可以把这些数字表示成bit的列表。例如，1100101010001111。第一位表示 1 的倍数，第二位表示 x0 的倍数，然后后续位表示以下 x1 数的倍数： x1, x1*x0, x2, x2*x0, 依此类推。这种编码很好，因为你可以分解它：

这是一种相对不常见的表示法，但我喜欢将二进制字段元素表示为整数，采用更有效bit在右侧的位表示。也就是说，1=1，x0=01=2，1+x0=11=3，1+x0+x2=11001000 =19, 等等。在这个表达式中，是61779。

二进制字段中的加法只是异或(顺便说一句，减法也是如此)；注意，这意味着x+x=0 对于任何x。将两个元素x*y相乘，有一个非常简单的递归算法：把每个数字分成两半：

然后，将乘法拆分：

最后一部分是唯一有点棘手的，因为你必须应用简化规则。有更有效的方法来做乘法，类似于Karatsuba算法和快速傅里叶变换，但我将把它作为一个练习留给有兴趣的读者去弄清楚。

二进制字段中的除法是通过结合乘法和反转来完成的。“简单但缓慢”的反转方法是广义费马小定理的应用。还有一个更复杂但更有效的反演算法，你可以在这里找到。你可以使用这里的代码来玩二进制字段的加法，乘法和除法。

左图：四位二进制字段元素（即仅由 1、x0、x1、x0x1）的加法表。右图：四位二进制字段元素的乘法表。

这种类型的二进制字段的美妙之处在于，它结合了“正则”整数和模运算的一些最好的部分。与正则整数一样，二进制字段元素是无界的：你可以随意扩展。但就像模运算一样，如果你在一定的大小限制内对值进行运算，你所有的结果也会保持在相同的范围内。例如，如果取42连续幂，则得到：

255步之后，你就回到42的255次方=1，就像正整数和模运算一样，它们遵循通常的数学定律：a*b=b*a、a*(b+c)=a*b+a*c，甚至还有一些奇怪的新法律。

最后，二进制字段可以方便地处理bit：如果你用适合2的k次方的数字做数学运算，那么你所有的输出也将适合2的k次方bit。这避免了尴尬。在以太坊的EIP-4844中，一个blob的各个“块”必须是数字模52435875175126190479447740508185965837690552500527637822603658699938581184513，因此编码二进制数据需要扔掉一些空间，并在应用层进行额外的检查，以确保每个元素存储的值小于2的248次方。这也意味着二进制字段运算在计算机上是超级快的——无论是CPU，还是理论上最优的FPGA和ASIC设计。

这一切都意味着我们可以像上面所做的Reed-Solomon编码那样做，以一种完全避免整数“爆炸”的方式，就像我们在我们的例子中看到的那样，并且以一种非常“原生”的方式，计算机擅长的那种计算。二进制字段的“拆分”属性——我们是如何做到的 1100101010001111=11001010+10001111*x3，然后根据我们的需要进行拆分，这对于实现很大的灵活性也是至关重要的。

完整的Binius

请参阅此处查看该协议的python实现。

现在，我们可以进入“完整的Binius”，它将“简单的Binius”调整为(i)在二进制字段上工作，(ii)让我们提交单个bit。这个协议很难理解，因为它在查看比特矩阵的不同方式之间来回切换；当然，我花了更长的时间来理解它，这比我通常理解加密协议所花的时间要长。但是一旦你理解了二进制字段，好消息是Binius所依赖的“更难的数学”就不存在了。这不是椭圆曲线配对，在椭圆曲线配对中有越来越深的代数几何兔子洞要钻；在这里，你只需要二进制字段。

让我们再看一下完整的图表：

到目前为止，你应该熟悉了大多数组件。将超立方体“扁平化”成网格的思想，将行组合和列组合计算为评价点的张量积的思想，以及检验“Reed-Solomon扩展再计算行组合”和“计算行组合再Reed-Solomon扩展”之间的等价性的思想，都是在简单的Binius中实现的。

“完整的Binius”有什么新内容？基本上有三件事：

•超立方体和正方形中的单个值必须是bit(0或1)。

•扩展过程通过将bit分组为列并暂时假定它们是较大的字段元素，将bit扩展为更多的bit

•在行组合步骤之后，有一个元素方面的“分解为bit”步骤，该步骤将扩展转换回bit

我们将依次讨论这两种情况。首先，新的延期程序。Reed-Solomon代码有一个基本的限制，如果你要扩展n到k*n，则需要在具有k*n不同值的字段中工作，这些值可以用作坐标。使用 F2 （又名bit），你无法做到这一点。因此，我们所做的是，将相邻F2 的元素“打包”在一起形成更大的值。在这里的示例中，我们一次将两个bit打包到 {0，1，2，3}元素中，因为我们的扩展只有四个计算点，所以这对我们来说已经足够了。在“真实”证明中，我们可能一次返回 16 位。然后，我们对这些打包值执行 Reed-Solomon 代码，并再次将它们解压缩为bit。

现在，行组合。为了使“在随机点求值”检查加密安全，我们需要从一个相当大的空间(比超立方体本身大得多)中对该点进行采样。因此，虽然超立方体内的点是位，但超立方体外的计算值将大得多。在上面的例子中，“行组合”最终是[11,4,6,1]。

这就出现了一个问题：我们知道如何将bit组合成一个更大的值，然后在此基础上进行Reed-Solomon扩展，但是如何对更大的值对做同样的事情呢？

Binius的技巧是按bit处理：我们查看每个值的单个bit (例如：对于我们标为"11"的东西，即[1,1,0,1] )，然后按行扩展。对象上执行扩展过程。也就是说，我们对每个元素的 1 行执行扩展过程，然后在 x0 行上，然后在“ x1 ”行上，然后在 x0x1 行上，依此类推（好吧，在我们的玩具示例中，我们停在那里，但在实际实现中，我们将达到 128 行（最后一个是 x6*…*x0 ））

回顾：

•我们把超立方体中的bit，转换成一个网格

•然后，我们将每行上的相邻bit组视为更大的字段元素，并对它们进行算术运算以Reed-Solomon扩展行

•然后，我们取每列bit的行组合，并获得每一行的bit列作为输出(对于大于4x4的正方形，要小得多)

•然后，我们把输出看成一个矩阵，再把它的bit当作行

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

但是，如果你做 3 倍，然后做 8 倍，你会得到：

但在用塔结构构建的二进制场中，这种方法确实有效。原因在于它们的可分离性：如果你用一个大的值乘以一个小的值，在每个线段上发生的事情，会留在每个线段上。如果我们1100101010001111乘以11，这和第一次分解1100101010001111是一样的，为

然后将每个分量分别乘以 11 相同。

把它们放在一起

一般来说，零知识证明系统的工作原理是对多项式进行陈述，同时表示对底层评估的陈述：就像我们在斐波那契的例子中看到的那样，F(X+2)-F(X+1)-F(X) = Z(X)*H(X) 同时检查斐波那契计算的所有步骤。我们通过在随机点证明求值来检查关于多项式的陈述。这种随机点的检查代表整个多项式的检查：如果多项式方程不匹配，则它在特定随机坐标处匹配的可能性很小。

在实践中，效率低下的一个主要原因是在实际程序中，我们处理的大多数数字都很小：for循环中的索引、True/False值、计数器和类似的东西。但是，当我们使用Reed-Solomon编码“扩展”数据以使基于Merkle证明的检查安全所需的冗余时，大多数“额外”值最终会占用字段的整个大小，即使原始值很小。

为了解决这个问题，我们想让这个场越小越好。Plonky2将我们从256位数字降至64位数字，然后Plonky3进一步降至31位。但即使这样也不是最优的。使用二进制字段，我们可以处理单个bit。这使得编码“密集”：如果你的实际底层数据有n位，那么你的编码将有n位，扩展将有8 * n位，没有额外的开销。

现在，让我们第三次看这个图表：

在Binius中，我们致力于一个多线性多项式：一个超立方体P(x0,x1,…xk)，其中单个评估 P(0,0,0,0)，P(0,0,0,1)直到P(1,1,1,1), 保存我们关心的数据。为了证明某一点上的计算，我们将相同的数据“重新解释”为一个平方。然后，我们扩展每一行，使用Reed-Solomon编码，为随机默克尔分支查询提供安全所需的数据冗余。然后我们计算行的随机线性组合，设计系数，使新的组合行实际上包含我们关心的计算值。这个新创建的行(被重新解释为128行bit)和一些随机选择的带有Merkle分支的列都被传递给验证者。

然后，验证器执行“扩展的行组合”(或者更确切地说，是扩展的几列)和“行组合的扩展”，并验证两者是否匹配。然后计算一个列组合，并检查它是否返回证明者所声明的值。这就是我们的证明系统(或者更确切地说，多项式承诺方案，它是证明系统的关键组成部分)。

我们还没有讲到什么？

•有效的算法来扩展行，这是实际提高验证器计算效率所必需的。我们在二进制字段上使用快速傅里叶变换，在这里描述(尽管确切的实现将有所不同，因为这篇文章使用了一个不基于递归扩展的效率较低的结构)。

•算术化。一元多项式很方便，因为您可以做一些事情，例如F(X+2)-F(X+1)-F(X) = Z(X)*H(X) 将计算中相邻的步骤联系起来。在超立方体中，“下一步”的解释远不如“X+1”。你可以做X+k，k的幂，但是这种跳跃行为会牺牲Binius的许多关键优势。Binius论文介绍了解决方案。参见第4.3节)，但这本身就是一个“深兔子洞”。

•如何安全地进行特定值检查。斐波那契例子需要检查关键边界条件：F(0)=F(1)=1和F(100) 的值。 但是对于“原始的”Binius，在已知的计算点进行检查是不安全的。有一些相当简单的方法可以将已知计算检查转换为未知计算检查，使用所谓的和检查协议；但是我们这里没有讲到这些。

•查找协议，这是另一项最近被广泛使用的技术，它被用来制作超高效的证明系统。Binius可以与许多应用程序的查找协议结合使用。

•超越平方根验证时间。平方根是昂贵的：bit的Binius证明2的32次方大约11MB长。你可以使用其他证明系统来弥补这个问题，以制作“Binius 证明的证明”，从而获得Binius证明的效率和较小的证明大小。另一种选择是更复杂的FRI- binius协议，它创建了一个多对数大小的证明(就像普通的FRI)。

•Binius是如何影响“SNARK友好”的。基本的总结是，如果你使用Binius，你不再需要关心如何使计算“算术友好”：“常规”哈希不再比传统的算术哈希更有效率，乘法模2的32次方 或模 2的256次方 与乘法模相比不再是一件令人头疼的事情，等等。但这是一个复杂的话题。当一切都以二进制形式完成时，很多事情都会发生变化。

我希望在未来的几个月里，基于二进制字段的证明技术会有更多的改进。

免责声明：本文仅代表作者个人观点，不代表链观CHAINLOOK立场，不承担法律责任。文章及观点也不构成投资意见。请用户理性看待市场风险，以及遵守所在国家和地区的相关法律法规。
图文来源：火星财经，如有侵权请联系删除。转载或引用请注明文章出处！

标签：BiniusSNARKSTARKVitalik二进制数字零知识证明