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

原文标题：《Binius: highly efficient proofs over binary fields》

撰文：Vitalik

编译：Kate，火星财经

来源：火星财经

这篇文章主要针对大致熟悉 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=3，等等。（请注意，答案总是非负数的，所以例如 -1=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，以容纳更多的步骤。