概述
全称Fast Reed-Solomon Interactive Oracle Proofs of Proximity，主要用于检查一个点集是否都在一个给定的多项式上
引言
首先从一个简单问题开始说起
假设Prover有一个点集，并声称这些点都在同一个度小于$d$的多项式上
Note：度就是自由度，度小于2则为一条直线（直线的自由度为1），度小于3为抛物线（抛物线的自由度为2），和阶的概念类似
接下来Prover想要为他的这个声称产生一个简洁的概率性证明
从朴素的方法来说，如果说Verifier想要检查Prover的断言，则其需要获得Prover的点集和这个度小于$d$的多项式，然后检查是否这些点都在多项式上
这个方法的缺点有两个，一个是必须检查所有的点，另一个是只要有一个点没检查，这个没检查的点就有可能不在多项式上，从而Prover存在作弊的可能
不过我们可以以一种概率的方式检查点集中的一部分点（比如检查点集中90%的点）是否在同一个多项式上
以这个图为例，图中的点表示Prover拥有的四个不同的点集
- 左上角：很明显，这个点集很接近一个多项式
- 右上角：大多数点在某个多项式上，但是并不接近该多项式
- 左下角：有些点接近一个多项式，另一些点接近另一个多项式，但是这两个多项式不相等
- 右下角：并不接近某个多项式
这么看来，如果我们可以以一种概率的方式检查多项式上的点，那么上面那个问题就很好解决了
但是引出了另一个问题，如果说Verifier只检查一部分的点，或者说Verifier可以要求检查他想要的特定的点，且Prover有义务出示这些点，但是作为条件，Prover会限制检查的点的数量，此时问题就转化为了，至少需要多少个点才能在某种程度上使得Verifier确定
显然，$d$个点不足以确定一个度为$d$的多项式（两个点确定一条直线，直线的度为1），因此为了确定一个度小于$d$的多项式，我们需要至少$d+1$个点，也即Verifier需要向Prover发起至少$d+1$次请求
那么我们可以这样，首先随机选择一个包含$d$个点的子集，利用拉格朗日插值法构造出一个度小于$d$的多项式，然后再随机选择一个或多个点，检查这些随机的点是否在这个多项式上
注意到这只是一个监禁测试，因为有可能对于一个很大的点集而言，其只有很少数的点，甚至只有几个点不在某个多项式上，此时随机选择这个点集的一个子集的话，很大概率不会包含这些错误的点
不过我们可以定义一个结果，如果说点集中有少于90%的点在多项式上，则上述测试会以极高概率失败
具体而言，如果说我们进行了$d+k$次查询，且选择的$k$个额外的殿中至少有$p$个点未通过检查，则失败的概率为$(1-p)^k$
但是多项式的度$d$往往很大，如果我们想以远小于$d$次查询来完成这个工作呢，但是直接做显然是做不到的，因为任意$k\leq d$个点都至少在一个度小于$d$的多项式上
接下来就要介绍FRI协议（Fast Reed-Solomon Interactive Oracle Proofs of Proximity），这个协议可以让我们以少于$d$次查询来渐进的检查一个度小于$d$的多项式
举个例子，首先假设有一个点集，大小为$N$（$N=10^9$），且这些点都在一个$d<10^6$的多项式$f(x)$上
接下来定义一个二元多项式$g(x,y)$，满足$g(x,x^{1000})=f(x)$，比如说这个多项式可以是$g(x,y)=xy^{11}+x^5y^3+xy+x^{12}+x+1$，然后接下来这么做
对于$f(x)$中度为$k$的项，将该项转化为$x^{k \ mod \ 1000}\cdot y^{\lfloor k/1000\rfloor}$
比如$k=185423$，度为$k$的项可能是$1744x^{185423}$，此时转化为$1744x^{423}y^{185}$，然后
然后接下来是证明过程，Prover首先对一个$10^9\times 10^9$的列表提交承诺（利用Merkle Tree或者其他的承诺方案），其中该列表的行坐标为$0\sim10^9-1$（也就是$x$），列坐标为对应的$x$的100次幂，如下图所示
之后Verifier随机选择若干行和若干列，对于Verifier选择的每一行和每一列，其要求Prover给出该行或该列上的1010个点，且确保这1010个点有一个点在整个列表的对角线上
接下来Prover响应Verifier的查询，同时发送对应的Merkle Tree的验证分支，Verifier检查这些分支是否满足Merkle Tree Root，并检查这些点是否对应于一个度为1000的多项式
如果Verifier通过验证，则其可以得到一个统计结论
- 大多数的行由度小于1000的多项式上的点构成
- 大多数的列由度小于1000的多项式上的点构成
- 对角线上的点大部分在这些多项式上，且对角线上的点对应于一个度小于$10^6$的多项式
举个例子，如果Verifier分别选择不同的30行和30列，则Verifier一共需要检查$60\cdot 1010=60600$个点，远小于$10^6$，不过考虑到计算时间，完成一次度小于1000的多项式的插值也存在一定的开销（尽管是亚平方阶的），因此整个算法的复杂度为亚线性的
但是Prover的工作量会很大，因为他要计算并承诺$10^{18}$个点，但是我们目前做到了验证比证明更快
模数学
加减乘都需要模一个数，但是为了确保封闭性，除法不是算数除法了
根据费马小定理，若$(a,p)=1$，则有$a^{p-1}\equiv 1 \ mod \ p$，也就是$a$和$a^{p-2}$互为模$p$下的逆元
不过模数学中的分配律和结合律还是满足的
此外费马小定理还告诉了我们一个结论，若某个数$k$，满足$k|(p-1)$，则函数$x\rightarrow x^k$存在一个小的像，这意味着这个函数只有$\frac{p-1}{k}+1$个结果
举个例子，比如$x\rightarrow x^2$在$p=17$时只有9个可能的结果，如下图所示
随着$k$的增大，则结果会越来越少，比如$k=8$时只有三个结果，$k=16$时就只剩俩了：$0\rightarrow0$和$1\rightarrow1$
更效率的检查
之前提到了Prover需要计算并承诺$10^{18}$个点，接下来看怎么减为根号级别
首先用模数学取代原本渐进多项式检查中采用的算术数学，同时利用上面提到的模幂下的小原像来进一步降低复杂度
比如说$p=1,000,005,001$，选择这个素数的原因是，它大于$10^9$，因此可以用来检查所有的$10^9$个点，此外$p-1$可以被1000整除，因为我们要用到$y=x^{1000}$，根据上面的公式，$x\rightarrow x^{1000}$有$1,000,006$个像
这么一来，我们就可以将原本的$10^9$行缩短到$10^6+6$行了
进一步，我们可以让Prover只对单个列进行承诺，因为经过上述操作，不难发现任意选择的一行都会包含1000个对角线上的点，此时可以插值得到一个度小于1000的多项式
之后和之前一样，Verifier选择一列，检查这列和该行的交点是否在该行插值得到的多项式上
然后Verifier还需要和之前一样，检查该列上的1000个点，插值得到一个度小于1000的多项式
这样一来，Prover的复杂度就降低至了$10^9$，因为引入模数学之后，Prover只需要对列进行承诺了，此时有$p=10^9+5001$列，Prover复杂度在$10^9$左右
更高效的方法
尽管降低为根号级别了，但是还可以更低，到对数阶，方法时将多项式嵌入到一个2D多项式中，该多项式中$x$的度的界为一个很小的常量
说得具体一点，这个常量可以是2，也即$f(x)=g(x,x^2)$，此时我们只需要检查三个点就可以了
如果说原始多项式的度小于$n$，此时行插值得到的多项式的度小于1，列插值得到的多项式的度小于$\frac{n}{2}$，从而我们将对度小于$n$的多项式的渐进检查转化到了度小于$\frac{n}{2}$的多项式的监禁检查
但是，Prover需要承诺的点和Prover的复杂度每次都会翻倍，因此做法是在上一节的优化下，针对列使用这个方法，直到列变为非常小以至于可以直接检查
此时总的复杂度为$n+\frac{n}{2}+\frac{n}{4}+...\approx2n$
实际上这个方法需要执行很多次，因为敌手可能会在某一轮进行伪造
不过经过这么处理，验证的复杂度也不会太大，即便是算上计算Merkle Tree承诺，验证复杂度也是关于度的对数阶的
至此基本上介绍完毕了，不过真实的FRI协议还需要一些小修改，比如使用的二元Galois域（模素数为2，但是是12次扩域），行的幂数为4而不是2
合理性
该方案可以做到计算合理性
后记
主要参考的是STARKs的官方说明，结合了一点自己的理解
后续的话可能会看一下FRI的paper，还有Deep-FRI
References
$[1]$ STARKs, Part II: Thank Goodness It's FRI-day