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

作者：维塔利克·布特林 2024年4月29日 原文链接

本文主要面向那些大致熟悉2019年时代密码学的读者，特别是SNARKs和STARKs。如果您不熟悉，建议先阅读这些文章。特别感谢Justin Drake、Jim Posen、Benjamin Diamond和Radi Cojbasic的反馈和审阅。

在过去两年中，STARKs已成为一项关键且不可替代的技术，用于为极其复杂的计算生成可快速验证的密码学证明（例如，证明以太坊区块的有效性）。其中一个关键原因是小域大小：与基于椭圆曲线的SNARKs需要使用256位整数才能确保安全性不同，STARKs允许使用更小的域大小，这带来了更高的效率：首先是Goldilocks域（64位整数），然后是Mersenne31和BabyBear（均为31位）。得益于这些效率提升，使用Goldilocks的Plonky2在证明各类计算时比其早期版本快数百倍。

一个自然而然的问题是：我们能否将这种趋势推向逻辑上的终点，构建一个直接在 0 和 1 上运行的、运行得更快的证明系统？这正是 Binius 正在尝试实现的目标。它使用了一些数学技巧，使其与三年前的 SNARKs 和 STARKs 有着很大的不同。本文将探讨为什么小域能让证明生成更高效，为什么二进制域具有独特的强大威力，以及 Binius 使用了哪些技巧来让二进制域上的证明如此有效地工作。

Binius。读完本文后，你应该能够理解这张图的每个部分。

目录

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

回顾：有限域

密码学证明系统的一个关键任务是处理大量数据，同时保持数字较小。如果你能将一个关于大型程序的陈述压缩成一个只包含几个数字的数学方程，但这些数字和原始程序一样大，那么你实际上并没有获得任何好处。

为了在保持数字较小的同时进行复杂的算术运算，密码学研究者通常使用模运算。我们选择一个质数"模数"p。%运算符表示"取余数"：15%7=1，53%10=3等（注意结果始终是非负的，例如−1%10=9）。

你可能已经在时间的加减运算中见过 模运算（例如，9:00后4小时是什么时间？）。但在这里，我们不仅仅是对某个数进行加减模运算，还要进行乘法、除法和指数运算。

我们重新定义： 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 步。我需要证明的条件是在 x={0,1...98} 的范围内，F(x+2)=F(x)+F(x+1)。我可以通过给你商多项式来说服你：

H(x)=F(x+2)−F(x+1)−F(x)Z(x)

其中 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) 初始化虚拟机并运行一个计算步骤的输出"。你也可以用更大的数字（比如 100000000）替换数字 100，以容纳更多的步骤。

所有的 SNARKs 和 STARKs 都基于这个使用多项式（或者有时是向量和矩阵）的简单方程来表示多个数值之间关联关系的想法。并非所有方法都像上面那样检查相邻计算步骤之间的等价性：例如 PLONK 就不是，R1CS 也不是。但是许多最高效的方法都这样做，因为多次执行相同的检查（或相同的几个检查）更容易最小化开销。

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

五年前，对零知识证明不同类型的合理总结如下。有两种类型的证明：（基于椭圆曲线的）SNARKs 和（基于哈希的）STARKs。从技术上讲，STARKs 是 SNARKs 的一种类型，但在实践中，通常使用"SNARK"仅指基于椭圆曲线的类型，而"STARK"指基于哈希的构造。SNARKs 体积小，因此可以很快地验证它们，并且容易放在链上。STARKs 体积大，但它们不需要可信设置，并且它们具有抗量子特性。

STARKs 通过将数据视为多项式，计算该多项式在大量点上的求值，并使用该扩展数据的默克尔根作为"多项式承诺"来工作

在这段历史发展中，基于椭圆曲线的 SNARKs 率先得到广泛应用：直到大约2018年，借助 FRI 的突破，STARKs 才达到了足够的效率可以投入使用，而那时 Zcash 已经运行了一年多。基于椭圆曲线的 SNARKs 存在一个关键限制：如果要使用基于椭圆曲线的 SNARKs，那么这些方程中的算术运算必须使用模椭圆曲线点数的整数来完成。这是一个很大的数字，通常接近2^256：例如，对于 bn128 曲线，它是 21888242871839275222246405745257275088548364400416034343698204186575808495617。但实际计算使用的是小数字：如果你思考一下用你最喜欢的编程语言编写的"真实"程序，它处理的大多数内容都是计数器、for 循环中的索引、程序中的位置、表示 True 或 False 的单个位，以及其他几乎总是只有几位长的数值。

即使你的"原始"数据由"小"数字组成，证明过程需要计算商、扩展、随机线性组合以及数据的其他转换，这会产生相同或更多的对象，这些对象平均大小与你的域的完整大小相当。这造成了一个关键的低效问题：要证明对n个小值的计算，你必须对n个更大的值进行更多的计算。最初，STARK 从 SNARK 继承了使用 256 位域的习惯，因此也遭受同样的低效问题。

Reed-Solomon 多项式求值扩展。即使原始值很小，额外的值都会膨胀到域的完整大小（在这种情况下为 $2^31-1$）。

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，那就绝对达不到要求了。攻击者完全有能力通过尝试伪造证明 20 亿次，直到获得成功。

为了阻止这种情况，我们从扩域中采样 r。例如，你可以定义 y，其中 y3=5，并取 1、y 和 y2 的组合。这将总坐标数量重新提高到大约 293。证明者计算的大部分多项式并不进入这个扩域；它们仅使用模 231−1 的整数，因此你仍然可以获得使用小域带来的所有效率。但是，随机点检查和 FRI 计算确实需要深入这个更大的域，以获得所需的安全性。

从小素数到二进制

计算机通过将较大的数字表示为由零和一组成的序列来进行运算，并在这些位之上构建电路来计算加法和乘法等运算。计算机对16位、32位和64位整数的计算进行了特别优化。像264−232+1和231−1这样的模数（modulus）之所以被选择，不仅是因为它们适合这些范围，还因为它们与这些范围完美对齐：你可以通过执行常规的32位乘法来完成模264−232+1的乘法运算，并在几个位置进行位移和复制输出；这篇文章很好地解释了一些技巧。

然而，更好的方案是直接在二进制中进行计算。如果加法可以"仅仅"是异或运算，而不需要担心从一个位位置的1 + 1溢出"进位"到下一个位位置呢？如果乘法也能以同样的方式实现更好的并行化呢？这些优势都将是在能够用一个位表示True/False值之外的额外收益。

Binius正是试图捕获这些直接进行二进制计算的优势。来自Binius团队在zkSummit的演示的表格显示了效率提升：

尽管"大小"大致相同，但32位二进制域运算比31位梅森域运算所需的计算资源少5倍。

从单变量多项式到超立方体

假设我们认同这种推理，并希望在比特（零和一）上完成所有操作。那么我们如何实际地提交一个表示十亿比特的多项式呢？
在这里，我们面临两个实际问题：

1. 要让多项式表示大量的值，这些值需要在多项式的求值中可访问：在我们上面的斐波那契示例中，是 F(0)、F(1) ... F(100)，而在更大的计算中，索引会达到数百万。我们使用的域需要包含达到这个规模的数字。
2. 要证明我们在默克尔树（Merkle tree）中提交的值的任何内容（所有 STARK 都是这样做的）需要里德-所罗门编码（Reed-Solomon encoding）：将 n 个值扩展为例如 8n 个值，使用冗余来防止恶意证明者通过在计算中间伪造一个值来作弊。这也需要一个足够大的域：要将一百万个值扩展到八百万个，你需要八百万个不同的点来求值多项式。
   Binius 的一个关键思想是分别解决这两个问题，并通过以两种不同的方式表示相同的数据来实现。首先是多项式本身。基于椭圆曲线的 SNARK、2019 年时代的 STARK、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并不太困难。

现在，我们来看纠删码。STARK的工作方式是：你取n个值，将它们通过里德-所罗门扩展到更多的值（通常是8n，一般在2n到32n之间），然后随机选择扩展后的一些默克尔分支并对它们进行某种检查。超立方体在每个维度上的长度为2。因此，直接扩展它是不实际的：从16个值中采样默克尔分支的"空间"不够。那么我们该怎么做呢？我们假装超立方体是一个正方形！

Simple Binius - 一个示例

请参见此处查看此协议的 Python 实现。

让我们通过一个示例来说明，为了方便起见，我们使用普通整数作为我们的域（在实际实现中，这将是二进制域元素）。首先，我们取要提交的超立方体，并将其编码为一个方形：

现在，我们对这个方形进行里德-所罗门（Reed-Solomon）扩展。也就是说，我们将每一行视为在x = {0，1，2，3}处求值的三次多项式，并在x = {4，5，6，7}处求值相同的多项式：

注意数字增长得很快！这就是为什么在实际实现中，我们总是使用有限域而不是普通整数：例如，如果我们使用模 11 的整数，第一行的扩展就只是[3，10，0，6]。

如果你想自己尝试扩展并验证这里的数字，可以使用我的简单里德-所罗门扩展代码。

接下来，我们将这个扩展视为列，并为这些列构建默克尔树（Merkle tree）。默克尔树的根就是我们的承诺值。

现在，假设证明者想要证明这个多项式在某个点 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′以及一些随机采样列的默克尔证明。这是O(N)的数据量。在我们的示例中，我们让证明者只提供最后一列；而在实际应用中，证明者需要提供几十列才能达到足够的安全性。

现在，我们利用里德-所罗门码的线性特性。我们使用的关键性质是：对里德-所罗门扩展取线性组合得到的结果与对线性组合进行里德-所罗门扩展得到的结果相同。当你有两个都是线性的运算时，这种"顺序无关性"经常出现。

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

在这个例子中，扩展t′和计算列的相同线性组合（[6,−9,−8,12]）都得到了相同的答案：−10746。这证明了默克尔根是"善意构建"的（或者至少"足够接近"），并且与t′匹配：至少绝大多数列是彼此兼容的，也与t′兼容。

但验证者还需要检查一件事：实际检查多项式在{r0..r3}处的计算值。到目前为止，验证者的所有步骤实际上都没有依赖于证明者声称的值。所以我们是这样进行检查的。我们取评估点的"列部分"的张量积（tensor product）：
⨂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协议的完整描述。这已经具有一些有趣的优势：例如，由于数据被分割成行和列，你只需要一半大小的域（field）。但这远未实现在二进制中进行计算的全部优势。为此，我们需要完整的Binius协议。但首先，让我们对二进制域有更深入的理解。

二元域

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

+ 0 1 0 0 1 1 1 0

* 0 1 0 0 0 1 0 1

我们可以通过进行扩展来构造更大的二元域：如果我们从F2（即模2的整数）开始，然后定义x，其中x2=x+1，我们可以得到以下加法和乘法表：

+ 0 1 x x+1 0 0 1 x x+1 1 1 0 x+1 x x x x+1 0 1 x+1 x+1 x 1 0

+ 0 1 x x+1 0 0 0 0 0 1 0 1 x x+1 x 0 x x+1 1 x+1 0 x+1 1 x

事实证明，我们可以通过重复这种构造来将二进制域扩展到任意大小。这与实数上的复数有所不同：在复数中你只能添加一个新元素 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 =1+x0+x2+x2x1+x3+x2x3+x0x2x3+x1x2x3+x0x1x2x3

这是一种相对不常见的表示法，但我喜欢将二进制域元素表示为整数，采用二进制表示法，其中更高位的位在右侧。也就是说，1=1，x0=01=2，1+x0=11=3，1+x0+x2=11001000=19，以此类推。在这种表示方法中，1100101010001111 就是 61779。

二进制域中的加法就是异或运算（顺便说一下，减法也是）；需要注意的是，这意味着对于任意 x，x+x=0。要计算两个元素 x∗y 的乘法，有一个相当简单的递归算法：将每个数字分成两半：

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

然后，展开乘法：

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

最后一项是唯一稍微棘手的部分，因为你必须应用约简规则，将 Rx∗Ry∗xk2 替换为 Rx∗Ry∗(xk−1∗xk+1)。还有一些更高效的乘法方法，类似于卡拉楚巴算法和快速傅里叶变换，但我将把这些留给感兴趣的读者去探索。

二元域中的除法是通过组合乘法和求逆来完成的：35=315。求逆的"简单但缓慢"的方法是广义费马小定理的应用：对于任意满足22k>x的k，1/x=x^(22k-2)。在这个例子中，15=514=14，因此35=314=9。还有一个更复杂但更高效的求逆算法，你可以在这里找到。你可以使用这段代码来自己尝试二元域的加法、乘法和除法运算。

左图：四位二元域元素的加法表（即仅由1、x_0、x_1、x_0 x_1组合构成的元素）。右图：四位二元域元素的乘法表。

这种二元域的优美之处在于它结合了"常规"整数和模运算的一些最佳特性。像常规整数一样，二元域元素是无界的：你可以无限延伸。但像模运算一样，如果你在某个大小限制内进行运算，所有的答案也会保持在相同的范围内。例如，如果你计算42的连续幂，你会得到：

1，42，199，215，245，249，180，91……

在255步之后，你会回到42^255=1。而且像常规整数和模运算两者一样，它们遵循通常的数学定律：ab=ba，a*(b+c)=ab+ac，甚至还有一些奇特的新定律，例如a^2+b^2=(a+b)^2（通常的2ab项消失了，因为在二元域中，1+1=0）。

最后，二进制域在处理比特时非常方便：如果你用 2k 比特大小的数字进行运算，那么所有输出也会恰好保持在 2k 比特以内。这避免了类似 以太坊 的 EIP-4844 中出现的尴尬情况，其中 blob 的单个"块"必须是模 52435875175126190479447740508185965837690552500527637822603658699938581184513 的数字，因此编码二进制数据时需要浪费一些空间，并在应用层进行额外的检查以确保每个元素存储的值小于 2248。这也意味着二进制域运算在计算机上超级快速——无论是在 CPU 上，还是在理论最优的 FPGA 和 ASIC 设计中。

这意味着我们可以像上面那样执行 Reed-Solomon 编码，完全避免了我们在示例中看到的整数"爆炸"问题，而且这种方式对于计算机擅长的计算类型来说极其自然。二进制域的"分割"特性——就像我们能够将 1100101010001111 分解为 11001010+10001111∗x3，然后可以根据需要继续分割一样，这对于实现更大的灵活性至关重要。

完整版 Binius

参见此处获取该协议的 Python 实现。

现在我们来看"完整版 Binius"，它对"简单版 Binius"进行了调整，使其（i）能够在二进制域上工作，以及（ii）让我们能够对单个比特进行承诺。这个协议很难理解，因为它不断地在不同的比特矩阵视角之间来回切换；对我来说，理解它所花费的时间比我通常理解一个密码学协议所需的时间要长得多。不过好消息是，只要你理解了二进制域，Binius 就不会再涉及任何"更难的数学"。这与椭圆曲线配对不同，后者有着越来越深的代数几何兔子洞可以深入；在这里，二进制域就是你所需要的全部。

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

到目前为止，你应该已经熟悉了大部分组件。将超立方体"展平"成网格的概念、将行组合和列组合计算为评估点的张量积的概念，以及检查"先里德-所罗门扩展再计算行组合"与"先计算行组合再里德-所罗门扩展"之间等价性的概念，这些都在简单版 Binius 中出现过。

"完整版 Binius"有什么新内容？基本上有三点：

• 超立方体和方阵中的各个值必须是比特（0 或 1）
• 扩展过程通过将比特分组成列并暂时将它们视为更大的域元素，从而将比特扩展成更多比特
• 在行组合步骤之后，有一个按元素"分解成比特"的步骤，将扩展转换回比特

我们将依次介绍这两个部分。首先是新的扩展程序。里德-所罗门码有一个基本限制：如果你要将n个值扩展到kn个值，你需要在一个包含kn个不同值作为坐标的域中进行运算。在F2（即二进制位）中，你无法做到这一点。因此，我们将相邻的F2元素"打包"在一起形成更大的值。在这个例子中，我们每次将两个比特打包成{0,1,2,3}中的元素，因为我们的扩展只有四个评估点，所以这就足够了。在"实际"的证明中，我们可能会一次打包16个比特。然后我们在这些打包的值上执行里德-所罗门码，最后再将它们解包成比特。

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

这就带来了一个问题：我们知道如何将成对的比特组合成更大的值，然后对其进行里德-所罗门扩展，但如何对更大值的配对做同样的事情呢？

Binius的技巧是按位进行：我们查看每个值的单个比特（例如，对于我们标记为"11"的值，即[1,1,0,1]），然后按行进行扩展。也就是说，我们对每个元素的1行执行扩展程序，然后是x0行，然后是"x1"行，然后是x0x1行，以此类推（在我们的示例中到此为止，但在实际实现中，我们会扩展到128行，最后一行是x6...*x0）。

总结：

• 我们取超立方体中的比特，并将它们转换成网格

• 然后，我们将每一行上相邻的比特组视为更大的域元素，并对它们进行算术运算以实现Reed-Solomon行扩展

• 然后，我们取每一列比特的行组合，得到一个（对于大于4x4的方阵来说，要小得多的）比特列作为每一行的输出

• 然后，我们将输出视为一个矩阵，再次将其比特视为行

为什么这样可行？在"普通"数学中，如果你开始按位切分数字，（通常）按任意顺序进行线性运算得到相同结果的性质就不再成立。例如，如果我从数字345开始，先乘以8再乘以3，得到8280，如果按相反顺序进行这两个运算，也得到8280。但是如果我在两个步骤之间插入一个"按位分割"操作，就会出现问题：如果你先乘8再乘3，你得到： 345→×82760→[2,7,6,0]→×3[6,21,18,0]

但如果你先乘3再乘8，你得到： 345→×31035→[1,0,3,5]→×8[8,0,24,40]

但在用塔式构造（tower construction）建立的二进制域中，这种操作确实可行。其原因与它们的可分离性有关：如果你用一个小值乘以一个大值，每个段内发生的事情都会保持在该段内。如果我们将1100101010001111乘以11，这等同于先将1100101010001111分解为11 + 10∗x2 + 10∗x2x1 + 10∗x3 + 11∗x2x3 + 11∗x1x2x3，然后分别将每个分量乘以11。

综合分析

通常，零知识证明系统通过对多项式做出陈述来工作，这些多项式同时表示了关于底层求值的陈述：就像我们在斐波那契示例中看到的那样，F(X+2)−F(X+1)−F(X)=Z(X)∗H(X)同时检查了斐波那契计算的所有步骤。我们通过在随机点上证明求值来检查多项式的陈述：给定对F的承诺，你可能随机选择例如1892470，要求在该点对F、Z和H的求值证明（以及H在相邻点的证明），检查这些证明，然后检查F(1892472)−F(1892471)−F(1892470)=Z(1892470)∗H(1892470)是否成立。在随机点上的这个检查代表了对整个多项式的检查：如果多项式方程不匹配，它在特定随机坐标上匹配的概率是极小的。

在实践中，主要的效率问题来自于在实际程序中，我们处理的大多数数字都很小：for循环中的索引、True/False值、计数器等类似的东西。但是当我们使用里德-所罗门编码"扩展"数据以提供使基于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 编码扩展每一行，对组位进行编码，以为随机默克尔分支查询提供所需的冗余度来确保安全性。接着，我们计算行的随机线性组合，其系数的设计使得新组合的行实际上包含了我们关心的计算值。这个新创建的行（被重新解释为128行比特）以及几个随机选择的带有默克尔分支的列会被传递给验证者。这是 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 节），但这本身就是一个"需要深入研究的复杂课题"。

• 如何安全地进行特定值检查。斐波那契示例需要检查关键的边界条件：F(0)＝F(1)＝1，以及 F(100) 的值。但使用"原始"的 Binius，在预知的评估点进行检查是不安全的。有一些相对简单的方法可以将已知评估检查转换为未知评估检查，使用所谓的求和检查协议；但我们在这里没有深入讨论这些。

• 查找协议，另一项技术最近作为构建超高效证明系统的方式获得了越来越多的应用。Binius 可以与查找协议结合用于多种应用。

• 超越平方根验证时间。平方根验证的开销很大：一个 232 位的 Binius 证明约需要 11 MB 存储空间。你可以通过使用其他证明系统来生成"Binius 证明的证明"来解决这个问题，从而同时获得 Binius 在证明主要陈述方面的效率和较小的证明规模。另一个选择是更为复杂的 FRI-Binius 协议，它可以创建对数复杂度大小的证明（类似于常规 FRI）。

• Binius 如何影响"SNARK 友好"的定义。简而言之，如果使用 Binius，你就不再需要过分关注使计算"算术友好"："常规"哈希不再比传统算术哈希更高效，模 2^32 或模 2^256 的乘法与模 p 的乘法相比也不再是一个难题，诸如此类。但这是一个复杂的话题；当所有运算都在二进制域中进行时，很多特性都会发生变化。

我预计在接下来的几个月里，基于二进制域的证明技术将会有更多突破性进展。

INFO

以太坊和Internet Computer（ICP）是两个截然不同但同样雄心勃勃的区块链平台。以太坊的目标是成为一个完全去中心化和无需信任的基础设施，任何人都可以在其上开发和运行应用程序。Internet Computer则采取了一种不同的方法：它是一个更加垂直一体化的平台，在区块链上直接提供计算服务。但这两个平台都有其优势和局限性。在这篇文章中，我们将探究一个介于两者之间的可能性：一个结合了以太坊的去中心化和ICP高效执行模型的混合系统。我将这个假设的系统称为"Binius"。

为什么要探索这样的混合体？

以太坊和ICP各有其独特的优势：

以太坊的主要优势：

• 完全去中心化和无需信任：没有任何中心化的参与者能够审查或干预交易
• 交易排序的去中心化和无需许可性
• 强大的经济最终确定性保证

ICP的主要优势：

• 高效的链上计算，成本仅为传统云服务的几倍
• 更好的用户体验：用户可以直接通过浏览器与应用程序交互，无需使用钱包
• 对计算资源的更细粒度控制