原文：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 的子群 ：
我们选择 ，得到:
为了得到一个子群