原文：https://rot256.dev/post/fri/
作者：Mathias Hall-Andersen
译者：Kurt Pan
引言
在本文中，我们将研究Fast Reed-Solomon IOP (FRI) (FRI) 邻近性测试，该测试可以使不受信任的证明者说服验证者，一个承诺的向量是接近于一个Reed-Solomon码字的，且通信量仅为编码维度的多项式对数。这可以很容易地用于仅从密码学哈希函数（更确切地说，随机预言）来构建实际高效的 zkSNARK，且无需可信设置。
假设读者了解群论和有限域的基础知识；没有这些，FRI 看起来就会像是一系列毫无动机的魔法方程。还会假设读者熟悉交互式预言证明 (IOP) 的基础知识和邻近性测试的总体目标/想法。我们不会花时间讨论 IOP 的基础知识，但尽管如此，本文所用的模型将始终会是 IOP ：即证明者可以向验证者发送（长的）预言/消息，验证者可以在任何时间对任意索引读取预言/消息。
FRI 原始论文只用了相对较少的时间来给出构造的动机，而用了大量的时间来进行可靠性分析，当然这也是可以理解的。此外，尽管 FRI 相对简单（正如我们将看到的），实际上对可靠性的形式化证明会极为复杂，尤其是超出唯一解码半径时。
本文的重点有所不同：我们将重点关注构造背后的直觉，“折叠过程”是如何想出的，给出一些例子，以及关注为什么直观上可以期望该构造是能够发挥作用的。换句话说，关注要如何想出 FRI 的构造？以及如何对其泛化推广？
FRI 概述
Fast Reed-Solomon IOP (FRI) 是一种对 Reed-Solomon 码的邻近性测试，即始终会接受的字符串“yes”语言就是 Reed-Solomon 码：
简单来说：即是一个维度为 的向量 ，次数小于 的多项式的求值。
FRI 的目标是去区分开对应于诚实行为的 和所有中远离所有 Reed-Solomon 码字的向量，即相对汉明距离大于某个
直观上这很有用, 因为如果 小于Reed-Solomon码的唯一解码半径, 则每当验证者接受时（），我们就可以唯一地去讨论编码在 中的"消息"了 。构造 SNARK 时，这会使得知识抽取器可以恢复出唯一的低次（ ）多项式 。
承诺问题（Promise Problems）：注意我们并不关心以下情况： ，即当 接近一个 Reed-Solomon 码字，但也不是码字本身时会发生什么。可能会有某种方式可以通过对 的测试，但也不是协议中的诚实行为。在复杂性理论中，这种对判定问题的泛化被称为承诺问题 ， 被称为*承诺（promise)*。
FRI 通过不断分别归约 到更小的语言 来达成这个目标。
我们稍后会花相当多的时间在这个归约上，因为这是 FRI 的核心，现在先令 为一个确定"压缩因子"的常数， ，以及 将为大小的求值域 :
FRI 的核心目标就是概率性地把 归约到 ，使得：
. (除去一个小概率)。
换句话说：如果你从一个码字开始，你最终得到的也会是一个码字；如果你从一个远离码字的东西开始，你最终也会得到一个远离码字的东西；除去一个很小/可忽略的概率。
重复此过程后 rounds 次后，我们会一直归约到某个常数维度的编码。这个时候只需发送 给验证者即可验证 ， 验证者检查 。整个协议的可靠性错误上界为如下可忽略事件： 任意一轮中， 但 。因此，一旦我们理解了FRI的一轮，我们就理解了整个协议。
注定失败集合：集合 ，或多或少直接显式出现在 对FRI的逐轮可靠性证明中，它与脚本的“注定失败集合”这一一般概念密切相关。形式化的可靠性分析在于给出证明者一开始在但可以离开这个注定失败集合的概率上界。
那么我们要如何得到这样的一个归约呢?
这就是本文的重点, 所以让我们开始深入探讨。
FRI的组成
要实例化 FRI，我们需要以下成分：
一个有限域 。 一个子群 。 一个群同态 , 从 到某个 ，具有非平凡的核。 压缩系数 ，以及由于效率原因我们会想要 比较小。那么我们要如何找到这些成分呢?
关于同态和多项式的观察
首先注意到，对于有限域, 任意映射 都可以使用拉格朗日插值写成多项式 。对于域上的群同态, 有人可能会天真地认为这会得到一个高达次的多项式 , 就像对一般函数一样, 但事实并非如此。相反, 多项式的次数 是与 的核的大小成正比的，即：
要看到这一点, 考虑一个非平凡的同态（即 ），令 为群的单位元，为和在 上一致的多项式， 并注意到有 个上的根 ，每个根对应于一个映射到的群元素。
具体来说, 对于商同态 ，这是群同态的多项式：
这很好，因为即使我们最终是对多项式感兴趣，这也让我们能够更抽象地思考域中的群同态。因为同态的核是一个子群，且每个子群 也是某个同态的核，即对于域 且 ，我们可以探索有限域的子群然后取商同态以得到多项式。
这比一开始就给出同态或找到"好"多项式要容易得多，所以：
在域中选择一些元素。 使其生成某个子群（ 或 下 ）。 考虑商群的同态。 生成该同态的多项式。
这种思考框架可以使我们更好地理解 FRI 的底层结构，了解为什么比如说平方映射是对某些域的自然选择，同时也使我们能够将 FRI 推广到其他设置。
为群论欢呼！
构造 L 和 q
如上所述, 最简单的构造 和 的方法是选择一个群 , 找到一个子群 并令其定义 为来自 的唯一的群同态 ，其中 为核。因为 , 我们想要 比较小。因此一个自然的选择就是选 并令 ; 对于的某些选择, 这显然会生成可能的最小非平凡 。
对于那些喜欢 SageMath 的人, 以下代码段做的就是这件事, 即对于一个给定的生成元 和群操作op，计算多项式 :
''' 给定：
- g : ker(q(x))的生成元
- op : 群操作
- X : 未定元
返回对\lt g>的多项式q(X)
'''
def phi(g, op, X):
# 计算 H = \lt g>
e = g
H = []
while 1:
H.append(e)
e = op(e, g)
if e == g: break
# 找到群单位元
one = H[-1]
assert all([op(one, e) == e for e in H])
# 插值同态多项式
return prod([(X - e) for e in H]) + one
有限域自然地提供了两种群结构供我们探索：
域的乘法群 ，这是一个循环群。 域的加法群 ，与一个向量空间同构。
这两种都可以工作，有时一种会比另一种更好, 具体取决于域。
那么让我们依次来看看......
循环子群
回顾一下，任意有限域 的单位群 都是循环的： 。
对于任意循环群 ，子群 （其中 表示应用群操作 次）具有阶 。假设 （其中 ）, 那么可以通过令 并定义 得到一个阶为 的群 。此外， 有一个非平凡的阶的子群：
可能有点抽象, 我们看几个例子:
例子： F17
考虑素域 。域 有 个单位(非零元素)。元素 是一个本原根，即
分解群的阶, 我们会得到 。因此我们有阶的循环子群：任何因子的乘积。假设我们想要一个阶 的群 与一个阶2 的子群 :
我们接着选择 ，得到：
为了得到一个子群，从 中选择一个2阶元素，即
注意在这种情况下, 单位元是 。因此多项式 为：
下面的SageMath代码可以用来生成这个例子：
# 选择单位根
F = GF(17)
w = F.multiplicative_generator()
print(w)
# 选择2阶子群的生成元
m = w.multiplicative_order()
assert m % 2 == 0
g = w^(m / 2)
print(g)
# 计算同态：
# 群操作是乘法
P.\lt X> = PolynomialRing(F)
q = phi(g, lambda a,b: a*b, X)
print(q)
如上所示, 在选择阶 的乘法子群时 时， 中的很多系数 (数学上) 消去了，并产生了 "平方"映射 ，正如 radix-2 Cooley-Tukey FFT 中所使用的那样。但是我们也可以选择其他 值。
让我们看另一个例子：
例子： F31
考虑素域 。域 有 个单位(非零元素)。元素 是一个本原元素，即
如果我们分解群的阶, 我们会得到 。 因此我们有阶为的循环子群：任何因子的乘积。假设我们想要一个阶为 的群 以及一个阶为3的子群 ：
我们选择 ，得到:
为了得到一个子群，从 中选择一个3阶元素，即
多项式 为:
惊不惊喜：这是一个“立方”映射，因为 。
以下 SageMath 代码用于生成这个例子：
# 选择单位根
F = GF(31)
w = F.multiplicative_generator()
print(w)
# 选择3阶子群的生成元
m = w.multiplicative_order()
assert m % 3 == 0
g = w^(m / 3)
print(g)
# 计算同态：
# 群操作是乘法
P.\lt X> = PolynomialRing(F)
q = phi(g, lambda a,b: a*b, X)
print(q)
因为FRI会需要一系列的小子群, 上述方法非常适合 有许多小素因子的域 。在实践中, 这意味着选择一个素数 使得 ，对某个数 以及适当大的 。
然而, 在比如说二进制域 的情况下，上述策略并不能很好地发挥作用, 因为 可能并不平滑, 在域变得非常大之前我们也没有 的实际选择来进行尝试——与在上述素域情况下选择不同。
扩域和向量空间
对于域 的一个自然的选择是加法子群。
例子 ：F16
考虑扩域：。注意 的每个元素在加法群中的阶都为2, 令为某个非零元素:
将 加到自己，得到:
因此我们可以通过选择任何元素 并令来得到一个2阶群 。为举例子，我们挑 ，得到
商映射 为:
以下 SageMath 代码用于生成这个例子：
# 域定义
F = GF(2)
R.\lt z> = PolynomialRing(F)
F2 = F.extension(z^4 + z + 1, 'z')
# 任意选择一个生成元
g = F2(z^3 + z + 1)
# 计算同态：
# 群操作是加法
P.\lt X> = PolynomialRing(F2)
q = phi(g, lambda a,b: a + b, X)
print(q)
# 检验
e1 = F2.random_element()
e2 = F2.random_element()
assert q(e1 + e2) == q(e1) + q(e2)
子空间和线性映射
除了是上的多项式之外，映射 还是一个线性空间 上的-线性映射。其核的维度为 1，因此秩为 3 ，它将对应于的向量 映射到向量 。该线性映射对应的矩阵可以通过作为多项式, 在标准基上求值 得到,：
因此 -线性映射 可以写成 -矩阵:
上面的矩阵是使用以下 SageMath 代码计算的：
# 在标准基上求值q
B = [F2(1), F2(z), F2(z^2), F2(z^3)]
E = [q(e) for e in B]
print(E)
# 构造GF(2)矩阵
M = Matrix([vector(e) for e in E])
print(M)
# 检验
e3 = F2.random_element()
assert vector(e3) * M == vector(q(e3))
很明显 是一个线性映射，但多项式什么时候是线性映射？
当我们对于线性子空间计算 时，例如上面的 ，总是会产生一个线性化（Linearized）多项式，其中唯一的非零系数是次数 的单项式， 是域的特征，即 。这对读者来说并不奇怪：这些正是对应于线性空间上的线性操作的单项式线性组合的多项式。
练习： 证明上述断言。
提示：使用 当且仅当 。
提示：使用对于任何 -线性映射 。
一般来说，我们不想对整个域进行求值，因为域的大小 可能非常大（指数级），
此外 FRI 的可靠性分析实际上需要 达到Johnson界（给出更好的具体参数），即该域需要比求值域大得多。所以一个自然的想法是选择 作为的线性/仿射子空间 。接下来我们看一个例子。
例子：F243的子空间
考虑扩域： ，有 个元素。
注意 中的每个元素在加法群中阶都为3。我们可以构造一个具有 个元素的 子空间 ，方法是选取两个 线性独立的元素 ，并令 ：由 和 张成的向量空间。一个自然的选择是选取标准基的两个元素：。这让我们得到了一个具有以下元素的子空间：
为获得 , 可以选择任意元素 。同样, 一个自然的选择是选择两个基元素之一, 例如 。在这种情况下我们得到:
注意 是只发送" 坐标"为零的线性映射, 即 。因为我们选择了第一个基向量 作为线性映射的核。
因此, 当满足以下任一条件时, 就可以满足 FRI 的先决条件:
是光滑的, 例如 . 是小特征的扩域。
完成所有这些预备工作后，接下来就让我们来构造 FRI 协议吧。
FRI 时间到！
在继续之前，让我们简要回顾一下 FRI 的成分。
FRI 通过以下参数确定：
一个有限域 一个子群 一个群同态 ， 很小。
而且不用担心, 文末会有很多例子。
开始FRI
令为证明者选择的多项式。FRI 首先让证明者对 在 上求值并发送求值给验证者。
在实践中是用FFT 在 上高效计算 。幸运的是，适用于 FRI 的域也支持高效的FFT 。还有值得注意的是, 计算码字 所需的准线性复杂度是FRI中最昂贵的部分, 即唯一是次数的超线性复杂度的部分。
考虑q(X)基分解
对现在定义为 的 , 考虑 的唯一" 基" 分解 :
这可以通过重复多项式除法来计算, 但并不需要显式计算此分解: 我们只需要其作为说明性的教学工具。
用未定元 替换 并重写分解 为一个二元多项式 :
在继续之前, 先进行一些快速观察:
将 插回 ，得到 。 因此对 ，求值 会被发送给验证者。
到目前为止还没有魔法, 双方都还没有做任何事情。
g(X,Y)求值表
事实上，关于部分求值 的次数还有一些观察：
对任意， 。因为它是次数多项式的线性组合的多项式：
回想一下 且很小（ 次数的常数） 。
对任意， 。因为当多项式 被替换为其在 的求值，它就只是一个单变量次数 的多项式:
因此, 如果我们考虑一个求值表 ，每行对应一个不同的, 每一列对应一个不同的 ，每个条目对应 在 处的求值:
表： 的求值表, 由 定义。注意相比于列 ，该表具有更多行 。
表中每一行的点都位于一个 次的多项式上，表格中每一列上的点都位于一个次多项式上 ：
这里有一个关键的观察：表的每一列都包含来自 的 个元素。这如下所示：
对于每一个 ，原像集合 具有相同的基数。这是因为 是一个上的群同态, 因此每个 都是一个核的陪集, 而每个核都有 个元素。再次，为群论欢呼! 每列 有 个点 包含在 中。因为对每一个 , 意味着 ，如前所述我们有 。
结果是, 次数为 的"列多项式" 实际上唯一由 个在 的求值 所定义。即通过Lagrange插值唯一的 次和上的求值一致的多项式 。下图中来自 的点标有黄色十字， :
有了这些观察结果, FRI 协议实际上非常简单:
选择随机行：随机选择 ，并让诚实的证明者发送该行。即定义 并发送新码字 。 检查随机列：为避免恶意证明者发送除正确计算的行 之外的东西，我们检查 和 在随机位置/列 上之间的一致性。
列一致性检查是可能的，因为来自 的点唯一定义了对于任意 的每个列多项式 。证明者已经发送了来自 的点给验证者。因此，验证者可以简单地在行 处求值该多项式以检查行中的位置计算是否正确：即检查 。具体来说，验证者：
均匀随机采样一列 。 读取在 列中 的元素：
插值列多项式 ：
在行求值列多项式：
停下来思考一下：如果 的点在选定的列和选定的行相交，验证者要做什么？比如在上图中，验证者如果查询 列，他要做些什么？
答： 验证者不应该做任何特别的事情:
验证者在每个 打开 。插值唯一的次与 在 上一致的单变量多项式 。然后打开 并检查 。
注：通常从中选取的域 要比求值域大得多，比如说是安全参数的指数。所以上述事件在实际中发生的可能性很小。
选择随机行：验证者选择随机行，诚实的证明者承诺该行。通过查询随机列来测试邻近性。
因为行 应该属于一个纠错码，所以如果只有少数位置求值错误，我们并不需要抓住证明者，如果是接近的，我们可以纠正一些错误的位置，即我们仍然可以唯一解码唯一的与大多数求值一致的低次 。我们实际上只需要抓住发送的东西与正确的求值相去甚远的证明者。
因此，随机测试几列的策略是合理的。如果许多位置（比如一个常数分数）不正确，则证明者会以很高的概率被抓住。因此，相反地，如果检查以高概率通过，那么 一定接近正确的求值。
递归
新多项式 的次数是 。
为了进一步降低 的次数，我们可以对重复上面的过程。令：
新求值域： 新多项式： 选择一个子群 , 令其定义 ， 类似上述 。
递归地对 应用使用新参数 的FRI 协议。
注意：要继续递归一个新的子群 需要定义一个新的商映射 。因此，要递归多次，我们需要原始的 拥有许多小子群：这样我们就可以在每一层递归上用一个新的子群进行求商。
注意：为了提高FRI的轮复杂度和可靠性，一致性检查仅在折叠结束时执行，即没有中间的一致性检查，仅在递归结束时进行，同时检查各层的一致性。这是因为折叠具有非常小的可靠性错误（对于指数大小的域可忽略），而无论域的大小如何，一致性检查都具有常数的可靠性错误。
FRI 的交互式范例/ FRI 游乐场
因为理解事物通过例子总是更容易，因此该页面实际上已经在浏览器中实现了 FRI协议，以可视化正在发生的情况。我在这上面花了很多时间，所以请享受它。让我们看一些例子：
（译者注：简单起见，以下截图仅选取最简单的选项，更多交互式内容请读者跳转至原始网页查看。）
域和商映射
一开始要选取一个域，一个求值域 ，以及一个子群：
求值域和域：
得到下列商映射：
在上的求值表 如下所示：
| x | 1 | 13 | 16 | 4 |
|---|---|---|---|---|
| q(x) | 1 | 16 | 1 | 16 |
选择多项式/承诺阶段
考虑下面的（随机生成的）多项式：
在上的求值表 如下所示：
| x | 1 | 13 | 16 | 4 |
|---|---|---|---|---|
| f(x) | 14 | 0 | 5 | 2 |
证明者发送 给验证者。的分解为：
用一个未定元替换，得到 ：
考虑 在 和 上的求值表，其中每行对应不同的 ，每列对应不同的 。
注意：对于较大的域，表的行已被截断以提高可读性。
这个时候，除了在承诺 时已发送给验证者的绿色条目，该表格仅存在于证明者的头脑中。
折叠
验证者现在选择一个随机挑战 。
其定义了表中的一行（标注为蓝色）：
此行对应于多项式
要求证明者承诺这一行。当然，他也可能不会这样做……
一致性检查
验证者逐列运行一致性检查，尝试检测此类错误：
验证者选择 列。
列中的点（用橙色标记）是：
这些点位于 1 次列多项式上：
验证者在 处求值此多项式（蓝色标记的行）以检查一致性：
为了增强可靠性，验证者会重复这个“安全参数”次。如果检测到错误，它就知道证明者已损坏并中止。经过此测试后，验证者确信承诺的行 是接近于 在 上的求值的。
递归
对于 FRI 的下一轮，我们将新的多项式（现在为 ）设置为：
其次数为原 的一半。我们将新求值域定义为：
并选取子群 以继续。
注意：码字 是证明者已经发送的蓝色行。
Kurt Pan 翻译后记： 在目前诸多FRI相关文献之中，我视此篇为质量最上乘。此篇没有用fancy的相关技术内容吸引眼球，也没有陷入可靠性分析从而深入代数编码理论的论文窠臼，而是重视FRI构造的motivation & intuition，通过例子以及SageMath代码说明了FRI协议中最核心的一轮归约函数的本质：一个具有非平凡小核的商群同态映射的多项式，以及通过求值表的观察说明了FRI协议的“选择随机行，检查随机列”的模块化邻近性测试的本质。同等内容可迁移至对FFT/NTT，以及Additive FFT/ECFFT/FRI-Binius/ Circle FRI 等前沿技术的理解。Learn math the hard way. The hard way is the easy way.
