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

本文主要是介绍STARKs, Part II: Thank Goodness It's FRI-day，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

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

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

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

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

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

给定一些值，通过 D+1 次查询，检测这些值是否在同一个度小于 D 的多项式上，其算法其实并不十分复杂。首先，从 D 个点中随机挑选一个子集，并用像拉格朗日插值法（在这里搜索 “Lagrange interpolation” 获得更多介绍）来还原这个唯一的度小于 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 次多项式相关。

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

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

因而，这使得验证者相信在对角线上的大部分点，确实与一个次数小于 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 次幂是一个使用费马小定理直面该问题的结果，它表示对于任意非零的 x < p，都有 x^(p-1)%p = 1.这表明 x^(p-2) 给出一个数，如果再乘以一个 x，得到 1，所以我们可以说 x^(p-2)（是一个整数）等于 1/x。对模块化除法操作符求值，一个有点更为复杂，但是更快的方式是扩展欧几里得算法，其 Python 实现在这里。

由于数字“环绕”，模块化数学有时又叫“时钟数学”

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

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

指数越高，效果越明显：比如，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），是因为：

它比 10 亿大，因为我们需要它至少是 10 亿，这样才能检测 10 亿个点。
它是质数
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 个元素。

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

虽然验证者复杂度仍然是亚线性的，但是证明者复杂度已经降到了 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.

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

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

可靠性

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

这里是 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的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！