STARKs, Part II: Thank Goodness It's FRI-day

╰半夏微凉° 2022-06-03 08:19 161阅读 0赞

在本系列的上一篇文章中，我们谈到了，如何能够做出一些非常有意思且简洁的计算证明，比如通过利用多项式复合和除法技术，证明你算出了第一百万个斐波那契数。但是，它依托于一个非常重要的元素：给定一个集合，里面有很多的点，你必须能够证明集合里的大部分点都在同一个低次多项式上（译者注：本文所译的多项式度数或次数，皆对应 degree 一词）。这个叫做“低次测试”的问题，可能是协议中最为复杂的部分。

首先，再次回顾一下我们的问题。假设有一些点，你声称它们都在同一个多项式上，并且该多项式的度少于 D（也就是说，如果度小于 2，意味着这些点在同一直线。如果度小于 3，意味着它们在同一直线或抛物线，等等）。而你想创建一个简洁的概率证明，证明的确如此。

![左图：所有点都在度小于 3 的多项式上；右图：红色点与蓝色点不在同一个度小于 3 的多项式上][3 _ 3]

如果你想要验证，这些点*全部*都在同一个度小于 D 的多项式上，那么实际上你将不得不对每一个点进行检查，因为哪怕是仅仅漏掉一个点，也可能会出现差错：漏掉的这个点刚好不在这个多项式上，而其他点恰好都在上面。不过，你可以做的是，在所有的这些点中，*概率性地检测*至少有*部分*（比如 90%）点都在同一个多项式上。

![左上：可能足够接近于某一多项式；右上：不够接近某一多项式；左下：同时接近于两个多项式，但是又不足以接近任意一个；右下：显然不够接近任一多项式][1240]

如果你能够检查多项式上的*每一个点*，那么问题非常简单。但是，如果你只能够检查几个点呢？ – 也就是说，你可以要求检查任意几个点，作为协议的一部分，证明者也有义务给你这些点，但是查询次数总数是有所限制的？那么问题来了，你需要检查多少个点，才能在一定程度上进行确认？

显然，D 个点是**不够**的。因为 D 个点恰好可以唯一定义一个度小于 D 的多项式，所以你得到的*任意*的点集合，都只会与某个度小于 D 的多项式相关。从上图可以看出，D+1 或更多的点，*肯定*可以给我们带来更多信息。

给定一些值，通过 D+1 次查询，检测这些值是否在同一个度小于 D 的多项式上，其算法其实并不十分复杂。首先，从 D 个点中随机挑选一个子集，并用像拉格朗日插值法（在 [这里][Link 1] 搜索 “Lagrange interpolation” 获得更多介绍）来还原这个唯一的度小于 D 的多项式，并且该多项式能够通过这些所有的点。然后，随机再采样一个点，检测该点是否在同一个多项式上。

![第一步：选 D 个点；第二步：还原度小于 D 的多项式；第三步：再检查一个点][D _ D]

注意，这仅仅是一个临近测试（proximity test），因为无可避免地会出现这样一种情况，即虽然大部分点都在同一个低次多项式上，但却有另外一些点不在该多项式上，而第 D+1 个采样点恰好完全地错过了这些点。不过，我们可以对结果进行派生，如果在同一个度小于 D 的多项式上的点低于 90%，那么测试将很大可能失败。具体来说，如果你进行 D+k 次查询，有至少 `p%` 的点不在同一个多项式上，而其他点却在上面，那么通过测试的概率仅有 (1-p) ^k。

但是，如果像上一篇文章的例子那样， D 非常大，而你想要在少于 D 次查询的情况下，验证一个多项式的度，那该怎么办呢？当然，这不太可能直接“对症下药”， 因为上面已作出了简单的论证（即，*任意* k <= D 个点至少全部都在一个度小于 D 的多项式上）。但是，通过*提供辅助数据*，间接地进行验证还是非常有可能的，并且能够获得大幅地效率提升。这就是像 [FRI][]（“Fast RS IOPP”，RS=“[Reed-Solomon][]  
”， IOPP = “Interactive Oracle Proofs of Proximity”） 这样的新协议想要做的事情，它与早先叫做近似概率可检验性证明（probabilistically checkable proofs of proximity (PCPPs) ）的设计相类似。

## 初识亚线性 ##

为了证明这一切都是可行的，我们从一个相对简单的协议开始，虽然有非常粗糙的折衷操作，但是仍然可以达到亚线性验证复杂度的目的 – 也就是说，你可以通过少于 D 次查询，近似证明一个度小于 D 的多项式（在这里也就是，通过少于 O(D) 次计算来对证明进行验证）。

思路如下。假设有 N 个点（比方说 N 等于 10 亿），并且它们都在一个度小于 1,000,000 的多项式 `f(x)` 上。我们找到一个二元多项式（像 `1 + x + xy + x^5*y^3 + x^12 + x*y^11` 这样的表达式），表示为 `g(x, y)`，并且 `g(x, x^1000) = f(x)`。通过如下操作即可完成：对于 `f(x)` 中第 k 度项（比如，`1744 * x^185423`），我们将它分解为 `x^(k % 1000) * y^floor(k / 1000)`（在该例中，`1744 * x^423 * y^185`）。你可以看到，如果 `y = x^1000`，那么 `1744 * x^423 * y^185` 等于 `1744 * x^185423`。

在证明的第一阶段，证明者提交在*整个*正方形上 `[1..N] x {x^1000: 1 <= x <= N}` 上 `g(x, y)` 的值（也就是说，求一个 Merkle 树）– 也就是，列上的所有 10 亿个 x 坐标，以及所有 10 亿个对应的行上 y 坐标的一千次。正方形的对角线表示 `g(x, y)` 的值，其形式为 `g(x, x^1000)`，因此关联到 `f(x)` 的值。

然后，验证者可能随机选出几十行和几十列（如果我们想要一个非交互式的证明，可能使用 [the Merkle root of the square as a source of pseudorandomness][]），对于所选的每一行或列，比如说，验证者要求从行和列的 1010 个点中采样一个点，以确保在每种情况下，要求的点都在对角线上。证明者必须对这些点作出回应，通过 Merkle 分支，证明它们是给证明者提交原始数据的一部分。验证者检查 Merkle 分支的确相匹配，这表明证明者所提供的这些点确实与 1000 次多项式相关。

![image.png][]

这给了验证者一个统计证明：

1.  大部分行主要被度小于 1000 的多项式上的点所填充
2.  大部分列主要被度小于 1000 的多项式上的点所填充
3.  对角线大部分都在这些多项式上

因而，这使得验证者相信在对角线上的大部分点，确实与一个次数小于 1,000,000 的多项式相关。

如果我们选出 30 行和 30 行列，验证者需要检测总共 1010 个点 \* 60 行+列 = 60600 个点，虽然少于原始的 1,000,000 个点，但仍是差强人意。就计算时间而言，尽管由于多项式插值可以变为次二次（subquadratic），但对度小于 1000 的多项式进行插值，也有其自身的开销，从整体上看，算法验证仍是亚线性的。*证明者*的复杂度更高了：证明者需要计算并提交整个 N\*N 长方形，这总共是 10^18 的计算成本（实际上还要更多一点，因为多项式求值仍然是超线性（superlinear）的）。在所有的这些算法中，对计算进行证明，远比单单执行该计算要复杂的多，但是我们将会看到，其实这些开销并非需要*如此*地高。

## 模块化数学插曲 ##

在深入到更复杂的协议之前，我们需要稍微偏离下主题，讨论一下模块化数学（modular math）。通常，当面对代数表达式和多项式时，我们所面对的是使用的是 +,-,*,/（还有求幂，不过它实际只是重复的乘法而已）这样操作符的常规数字和运算，这些都是我们在学校里面就学会的知识：2 + 2 = 4, 72 / 5 = 14.4, 1001*  1001 = 1002001 等等。但是，数学家们已经意识到，这些定义加法，乘法，减法和除法的方式，并不是*唯一*定义这些操作符的自洽（self-consistent）方式。

定义这些操作符，另一种可替代也是最简单的例子是，下面定义的模块化数学。% 操作符代表“取余”，`15 % 7 = 1`, `53 % 10 = 3`, 等等（注意答案始终是非负的，比如 `-1 % 10 = 9`）。对于任意指定的素数 `p`，我们可以重新定义：

x + y   --->   (x + y) % p
    x * y   --->   (x * y) % p
    x ^ y   --->   (x ^ y) % p
    x - y   --->   (x - y) % p
    x / y   --->   (x * y ^ (p-2)) % p

上面的例子都是自洽的。比如，如果 p = 7, 那么：

*  5 + 3 = 1 (as 8 % 7 = 1)
 *  1 - 3 = 5 (as -2 % 7 = 5)
 *  2 \* 5 = 3
 *  3 / 5 = 2 (as (3 \* 55) % 7 = 9375 % 7 = 2)

对于像分配律这样更复杂的内容同样成立： (2 + 4)*3 和 2*  3 + 4 \* 3 都等于 4。在这种新的数学中，甚至像 (a^2-b^2)=(a-b)\*(a+b) 也仍然是成立的。除法是其中最困难的部分：我们无法使用常规除法，因为我们想要结果始终是整数，但是常规除法常常会得到非整数的结果（比如 3/5）。在上面的除法公式中，p-2 次幂是一个使用 [费马小定理][Link 2] 直面该问题的结果，它表示对于任意非零的 x < p，都有 x^(p-1)%p = 1.这表明 x^(p-2) 给出一个数，如果再乘以一个 x，得到 1，所以我们可以说 x^(p-2)（是一个整数）等于 1/x。对模块化除法操作符求值，一个有点更为复杂，但是更快的方式是 [扩展欧几里得算法][Link 3]，其 Python 实现在 [这里][Link 4]。

![由于数字“环绕”，模块化数学有时又叫“时钟数学”][1240 1]

通过模块化数学，我们已经创立了一个全新的数学系统，因为它与传统数学在各个方面都是自洽的，所以我们在模块化数学里面讨论各种同样的结构，包括我们以“常规数学”论之的多项式。密码学家喜欢用模块化数学（或者，更通俗一点，“有限域”），因为一个数字的大小有界，它可以作为任意一个模块化数学的计算结果 – 无论你做什么，值都不会“跳出” `{0, 1, 2 ... p-1}` 的范围。

费马小定理还有另一个有趣的结论。如果 p-1 是某个数 `k` 的倍数，那么函数 x -> x^k 有一个小的“像（image）” – 也就是，这个函数只能够给出 `(p-1)/k + 1` 个可能的结果。比如， x -> x^2 在 p=17 时，只有 9 个可能的结果。

![image.png][image.png 1]

指数越高，效果越明显：比如，x -> x^8 在 p = 17 时，只有 3 个可能的结果。当然， x -> x^16 在 p=17 是只有 2 个可能的结果。如果是 0，返回 0，其他任何都返回 1.

## 浅谈效率 ##

让我们来继续讨论一个稍微复杂点的协议，它的目标在于，将证明者的复杂度从 10^18 降至 10^15，继而降至 10^9。首先，我们并不是针对常规数字进行操作，而是使用*模块化数学*检查多项式的近似程度。正如在上篇文章所述，在  
STARKs 中，我们无论如何都要防止数字增长至 200,000 位。但是在这里，我们将要利用确定的模幂（modular exponentiation）的“小像（small image）”属性，并将其视作为一个副作用，来使得我们的协议更有效率。

具体来说，我们将选用 p = 1,000,005,001。之所以选择这个系数（modulus），是因为：

1.  它比 10 亿大，因为我们需要它至少是 10 亿，这样才能检测 10 亿个点。
2.  它是质数
3.  p-1 是 1000 的偶数倍。

幂 x^1000 的像大小为 1,000,006 – 也就是说，这个幂只有 1,000,006 个可能的结果。

这意味着“对角线”（x, x^1000） 现在变成了一个被包着（with a wraparound）的对角线；因为 x^1000 只可以取 1,000,006 个可能值，所以我们仅需要 1,000,006 行。故而，g(x, x^1000) 的所有取值现在只有 ~10^15 个元素。

![image.png][image.png 2]

这表明，我们可以更进一步地：让证明者仅提交在一个单列上 `g` 的值。关键技巧在于，原始数据本身已经包含了 1000 个点，而这些点在给定的任意行上，所以我们可以简单采样这些点，推导出它们所在的度小于 1000 的多项式，然后检查列上相关的点在同一个多项式上。再接着检查列本身是一个小于 1000 的多项式。

![image.png][image.png 3]

虽然验证者复杂度仍然是亚线性的，但是证明者复杂度已经降到了 10^9，并与查询次数成线性关系（尽管在实践中由于多项式求值的开销，仍是超线性的）。

## 二谈效率 ##

虽然证明者复杂度现在已经无法再低了，但是我们仍然可以进一步地降低验证者复杂度，即从二次降至对数。我们的方法是让算法递归。从上面谈到的协议开始，但是并非试图将一个多项式嵌入到一个 x 和 y 度相等的二维多项式中，我们将多项式嵌入到一个二维多项式中，该二维多项式的度 x 下界是一个小的常量值。简单来说，我们甚至可以说就是 2 。也就是说，我们表示 `f(x) = g(x, x^2)`，所以行检验仅需每个采样行的 3 个点（2 个来自对角线，还有 1 个来自列）。

如果原始多项式的度小于 n，那么行的度小于 2（也就是说，这些行是直线），列的度小于 n/2。因此，我们现在得到的是一个线性时间过程，它将证明一个度小于 n 的近似多项式问题转变为证明度小于 n/2 的问题。进一步地，需要提交的点数，和证明者的计算复杂度，每次会减少 1/2（Eli BenSasson 喜欢将 FRI 的这一点与[fast fourier transforms][] 相比较，与 FFT 不同的关键在于，每一步递归都只进入一个新的子问题，而不是将问题一分为二  
）。因此，我们可以简单地继续使用在上一轮协议所创建的列上的协议，直到列变得足够小，小到我们可以简单地直接检查。整体复杂度大概是 n + n/2 + n/4 + … ~= 2n.

![image.png][image.png 4]

实际上，协议将需要被重复多次，因为仍有极大的可能，攻击者会在协议的某*一*轮作弊。但是，只要证明不是太大，验证复杂度在量级上仍然是对数级，尽管它会上升到 log^2(n) ，如果你把 Merkle 证明的大小也算进去的话。

“真正”的 FRI 协议也有一些其他的修改。比如，它使用一个二分的 [Galois 域][Galois]（另一种奇怪的有限域。本质上，与我在  
[here][] 讨论的第 12 度扩展域是同样的东西，不过素数模是 2  
）。行所使用的指数通常是 4 而不是 2。这些修改提升了效率，并使系统更加友好，在上面更易构建 STARKs。但是，对于理解算法的工作原理，这些修改并非十分必要。如果你真的想要理解算法的话，利用这里所述的基于模块化数学的 FRI，虽然简单了一点，但是应付 STARKs 绝对是够了。

## 可靠性 ##

我必须要提醒 *计算可靠性（calculating soundness）* – 也就是，无论概率有多低，对于给定次数的检查，一个经过优化后的假证明，仍可能会通过测试。 – 这依旧是这个领域中的“危险”地带。可以简单测试一下，取 1,000,000 + k 个点，有一个简单的下界：如果一个给定的数据集有这样一个属性，对于任意多项式，数据集中至少有 p% 的点没有在多项式上，那么在该数据集通过测试的概率将至多是(1-p)^k。但是，即使下界很低 – 比如，不可能同时有超过 50% 的点接近*两个*低次多项式，并且你首先选择的点会是上面最多的点的概率相当低。对于一个成熟的 FRI 来说，仍会涉及各种特定类型攻击的复杂度。

[这里][Link 5] 是 Ben-Sasson 等人最近的一篇文章，里面在完整的 STARK fang’an背景下，介绍了 FRI 的可靠性属性。总的来说，“好消息”是，为了在 STARK 上通过 D(x) \* Z(x) = C(P(x)) 检查，一个无效方案的 D(x) 将需要是某种意义上的“最坏情况” - 他们需要最大化地远离*任意*有效的多项式。这表明，我们不需要检查*那么*近的距离。虽然有已证明的下界，但是这些界限表明一个真正的 STARK 在大小上需要 ~1-3 MB；一个属于推测尚未被证明的更严格界限，减少所需检测次数的 1/4。

本系列的第三部分，将讨论构建 STARKs 的最后一个主要的挑战：如何构建约束检查多项式（constraint checking polynomial），才能够证明任意的计算语句，而不仅仅是几个斐波那契数。

原文：[STARKs, Part II: Thank Goodness It’s FRI-day][STARKs_ Part II_ Thank Goodness It_s FRI-day]

[3 _ 3]: /images/20220603/f4872ebd79b64d62bea08d95fb08b0bd.png
[1240]: /images/20220603/171a27c72ca6476d89fb7428ec2a138d.png
[Link 1]: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649
[D _ D]: /images/20220603/463ccf3a64b0474daa4f38f88a8393b1.png
[FRI]: https://eccc.weizmann.ac.il/report/2017/134/
[Reed-Solomon]: https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#Constructions
[the Merkle root of the square as a source of pseudorandomness]: https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic
[image.png]: /images/20220603/a9b937567a1240de85adc44c7e33842b.png
[Link 2]: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
[Link 3]: https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
[Link 4]: https://github.com/ethereum/py_ecc/blob/b036cf5cb37e9b89622788ec714a7da9cdb2e635/py_ecc/secp256k1/secp256k1.py#L34
[1240 1]: /images/20220603/96b95cc7f2bf4e1692784576121fc8c8.png
[image.png 1]: /images/20220603/29a4cd3f4efb4836ba5d8a3db4566d54.png
[image.png 2]: /images/20220603/7f6369e34d8744a29987cd4ec7552352.png
[image.png 3]: /images/20220603/86d0afda8d004da8905cd7c5302d8a21.png
[fast fourier transforms]: https://en.wikipedia.org/wiki/Fast_Fourier_transform
[image.png 4]: /images/20220603/77cec151d4e04e8da5c5293c83314dc1.png
[Galois]: https://en.wikipedia.org/wiki/Finite_field#Explicit_construction_of_finite_fields
[here]: https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627
[Link 5]: https://eccc.weizmann.ac.il/report/2016/149/
[STARKs_ Part II_ Thank Goodness It_s FRI-day]: http://vitalik.ca/general/2017/11/22/starks_part_2.html