之前的文章提到了如何利用算术化将CI Statement转换到多项式的低度测试，接下来介绍一下什么是低度测试

低度测试指的是通过仅对函数进行少量的查询来确定一个给定的函数是否是某个度数有限的多项式，低度测试已经研究了很多年，是概率证明理论的核心，接下来详细的介绍一下低度测试，并介绍STARK中使用的低度测试的协议——FRI协议

Low Degree Testing

首先讨论一个问题：给定一个函数，要求在少量点处查询该函数是否小于等于某个度为常数$d$的多项式

从形式上描述这个问题就是，给定一个域$F$及其子集$L$给定度的界为$d$，我们希望确定一个函数$f:L\rightarrow F$等于一个域$F$上的度小于$d$的多项式$p(x)$

$$ p(x)=c_{d-1}x^{d-1}+...+c_1x+c_0 $$

且对于任意的$a\in L$，都有$f(a)=p(a)$（这里要求域$F$与子集$L$的大小相差很大，比如$|F|=2^{128}$，$|L|=10^7$）

对于这个问题，需要在整个子域$L$上检查函数$f$，因为$f$可能在$L$中除了某个位置以外均满足$f(a)=p(a)$，即便是以一个恒定的错误概率来放宽这个检查的限制，检查的数量仍然与子域$L$的大小呈线性关系

因此低度测试主要是针对该问题的近似松弛，不仅可以构造关于这个问题的概率性证明，还可以将检查的数量降低至关于$|L|$的对数度（如果$|L|=10^7$，则有$\log |L|\approx23 <<10^7$）

具体而言，区分下列两种情况

  • 函数$f$等于一个低度多项式：这意味着域$F$上存在一个度小于$d$的多项式$p(x)$，该多项式在子域$L$中的任何一个点都与$f$相等
  • 函数$f$与任意一个低度多项式都不等：比如说，我们需要修改函数$f$至少10%的值才能得到与$p(x)$相等的低度多项式

注意到还有一种可能，函数$f$可能略微接近低度多项式，但其度不为1（例如$f$中只有5%的值不等于$p(x)$），此类情况不属于上述两种情况，但是根据前两篇文章介绍的算术化，使得这种情况不会发生，因为算术化确保了诚实的Prover生成的CI Statement属于第一种情况，而恶意的Prover生成的CI Statement将以极大的概率属于第二种情况，为了区分这两种情况，需要采用概率多项式时间测试，在少量的点检查函数$f$

这里有一个需要注意的点：如果$f$确实是低度的，则测试应该以1的概率接受，如果$f$远非低度多项式，则测试应当与极其接近1的概率拒绝
这里引入一个参数$\delta$，若必须修改$\delta |L|$个点才能使得$f$是小于$d$度的多项式，则称$f$为$\delta$-远离任意$d$度多项式的，且测试以至少$\Omega(\delta)$的概率拒绝（大概意思就是说$\delta$越接近0则越难区分上述两种情况

接下来介绍如何完成测试

Direct Test

首先考虑一个简单的测试，用$d+1$次查询测试函数$f$是否（接近）一个小于$d$度的多项式，该测试依赖于一个多项式的性质：任何小于$d$度的多项式由域$F$上的任意$d$个不同的点决定，换言之，$F$上的任意$k$次多项式至多有$k$个不同的根，因此对于度为$d$的多项式而言，只需要查询$d+1$次就可以完成判断，最重要的是这个方法可以实现简洁性（因为$d$远小于$|L|$）

对于这个方法，首先讨论两种特殊的情况

  • $f$为常数函数（$d=1$）：比如$f(x)=c,c\in F$，此时只需要两次查询，检查一个固定的点$z_1$和一个随机的点$w$，$z_1,w\in F$并判断是否有$f(z_1)=f(w)$即可
  • $f$为线性函数（$d=2$）：假设$f(x)=ax+b,a,b\in F$，这种情况下需要三次查询，检查两个固定的点$z_1,z_2\in F$和一个随机的点$w$，分别计算$(z_1,f(z_1)),(z_2,f(z_2)),(w,f(w))$并判断这三个点是否共线，这么做的目的是通过前两个定点来确定函数$f$所表示的定直线，然后通过随机点$w$来检查是否所有的$f$的值都接近这条线

将上述两种特殊情况进行推广，在$d$个定点$z_1,z_2,...,z_d\in F$处确定$f$的值，然后选择一个随机的点$w\in F$，由于$d+1$个点$z_0,z_1,...,z_d$唯一确定了一个域$F$上阶小于$d$的多项式$h(x)$，该多项式在这些点上与$f$相等，此时检查是否有$h(w)=f(w)$即可，这个方法称为直接测试

根据定义，若$f$等于度小于$d$的多项式，则必然有$h(x)=p(x)$，从而直接测试通过的概率为1（满足完美完备性）

若$f$是$\delta$-远离任意$d$度多项式的函数，则利用直接测试拒绝的概率至少为$\delta$，也即$h(x)\neq p(x)$的概率至少为$\delta$

由于我们是在域上讨论函数$f:L\rightarrow F$，$d$和$|L|$都会很大，直接测试的方法需要的查询太多了（$d+1$次），我们希望把查询次数降低至对数阶（$O(\log d)$），但是如果在直接测试上进行对数次查询$f$就无法得到任何有效的结论

On the Prover Side

既然直接测试的方法无法减少Verifier查询的次数，那么Verifier可以寻求Prover的帮助，让Prover提供一些辅助信息来减少Verifier查询的次数，注意到Prover仍然是不可信的，因此如果Verifier利用Prover的辅助信息进行查询时，若Prover是恶意的，则Verifier也应当有较高的概率拒绝Prover，接下来介绍一下如何利用Prover减少查询的次数

假设我们有两个多项式$f,g$，我们希望测试这两个多项式的度数都小于$d$，如果我们利用直接测试，则需要$2d+2$次查询

为了减少查询次数，考虑下面这种情况Verifier选择一个域上随机的点$\alpha \in F$并发送给Prover，之后Prover需要响应$h(x)=f(x)+\alpha g(x)$，换言之，对于Verifier选择的$\alpha$，Prover需要计算域$L$上所有的$h$，并为这些$h$计算一个Merkle Tree，同时将树根发送给Verifier，此时Verifier可以以少于$d$次的查询来完成检查

不难看出，若$f$和$g$的度数至少为$d$，则$h$的度数也大概率是$d$，考虑系数非零的项$x^n(n\geq d)$，存在至少一个$\alpha$，使得$h(x)$中$x^n$的项的系数为零，这意味着$h$的度小于$d$的概率约为$\frac{1}{|F|}$，若域$F$足够大（比如$|F|\geq 2^{128}$），则错误的概率可以忽略不计

但实际上不是这样，因为我们不能从“字面上”检查$h$是否是一个小于$d$度的多项式，我们只能检查$h$是否接近这样的一个多项式，此外，由于Prover是不可信的，Verifier也无法确保Prover发送的多项式$h$具有$f+g\alpha$的线性组合形式，例如Prover发送一个低度多项式，但与Verifer要求的线性组合不同，倘若我们已经知道$h$接近于一个低度多项式，则测试这个低度多项式是否有正确的形式是很简单的，此时只需要Verifier向Prover请求$f,g,h$，然后随机选择一个点$z\in L$，验证是否有等式$h(z)=f(z)+\alpha g(z)$成立即可，且Verifier可以选择多个不同的$z$来提高准确率，且增加的查询的数量不会太多

小结一下，如果我们希望测试两个多项式$f,g$的度数都小于$d$，根据这个方法可以在Prover的帮助下以小于$2d+2$次查询完成验证

Splitting a polynomial into two smaller-degree polynomials

接下来再介绍另一个方法，将一个小于$d$度的多项式转换为两个小于$\frac{d}{2}$度的多项式，并使Verifier查询的次数减少一半

不失一般性，假设$d$为一偶数，$f(x)$为一度小于$d$的多项式，同时记$f(x)=g(x^2)+xh(x^2)$，其中$g,h$均为度小于$\frac{d}{2}$的多项式，此时可以将$g$视为组成$f$中下标为偶数的项，$h$则视为组成$f$中下标为奇数的项

举个例子，比如$d=6$，此时$f,g,h$分别如下

$$ \begin{aligned}f(x)&=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5\\ g(x)&=a_0+a_2x+a_4x^2\\ h(x) &=a_1+a_3x+a_5x^2\end{aligned} $$

代入$f(x)=g(x)+xh(x^2)$，不难得到

$$ f(x)=a_0+a_2x^2+a_4x^4+a_1x+a_3x^3+a_5x^5 $$

The FRI Protocol

根据上述这个将一个多项式拆分为两个较小的多项式的方法，构建一个新的协议，使其只需要$O(\log d)$次就可以测试一个函数$f$是否小于（接近度为$d$的函数）

该协议称为FRI协议（Fast Reed-Solomon Interactive Oracle Proof of Proximity，快速里德-所罗门交互式Oracle接近性证明）

接下来简单介绍一下这个协议，假设$d$为2的幂次，也即$d=2^n,n\in \N$

Commit phase

首先Prover将原始多项式$f_0(x)$拆分为两个度小于$\frac{d}{2}$的多项式，分别记为$g_0$和$h_0$，满足$f_0=g_0(x^2)+xh_0(x^2)$，之后Verifier选择一个随机的$\alpha_0$发送给Prover，并请求Prover对多项式$f_1(x)=g_0(x)+\alpha_0h_1(x)$进行承诺（$f_1$是度小于$\frac{d}{2}$的多项式）

接下来我们可以递归的将$f_1$拆分为$g_1$和$h_1$，同时选择$\alpha_1$并构建$f_2(x)=g_1(x)+\alpha_1h_1(x)$，在$\log d$次递归后，我们可以得到一些常数多项式，此时Prover可以直接将这些常数发送给Verifier

接下来关注一个问题：为了使上述协议正常执行，我们需要对于域$L$中的每个$z$，都认为$-z$也在$L$中，此外还需要要求$f_1(x)$的承诺不会在$L$内，而是在$L^2=\{x^2:x\in L\}$内，且由于这个协议是递归执行的，因此我们同样需要$L^2$也满足$\{z,-z\}$的性质，幸运的是这些性质可以通过自然的选择域$L$来满足（比如选择一个乘法子群，其大小为2的幂）

事实上这些要求与从高效FFT算法中的要求一致（FFT在STARK的其他地方有用到，比如对执行轨迹进行编码）

Query phase

然后我们需要有一个手段来检查Prvoer是否作弊

Verifier首先选择一个随机的$z\in L$，并向Prover请求$f_o(z)$和$f_o(-z)$

选择$\{z,-z\}$的原因是其可以决定$g_0(z^2),h_0(z^2)$，因为其可以将$f_0(z)$和$f_0(-z)$视为$g_0(z^2),h_0(z^2)$的线性组合

$$ \begin{aligned}f_0(z)&=g_0(z^2)+zh_0(z^2)\\ f_0(-z)&=g_0(z^2)-zh_0(z^2)\end{aligned} $$

Verifier可以通过解这个线性方程组来得到$g_0(z^2),h_0(z^2)$，得到这两个值后Verifier可以进一步的计算$f_1(z^2)$，之后Verifier请求$f_1(z^2)$并验证其计算正确，若计算正确则表明Prover在承诺阶段发送的$f_1(x)$确实正确

接下来Verifier继续请求$f_1(-z^2)$并计算$f_2(z^4)$（$-z^2\in L^2$，且$f_1(x)$的承诺是在$L^2$内的），Verifier递归进行这个步骤，直到所有的查询计算到$f_{\log d}(z)$的值，根据前面介绍的，此时$f_{\log d}(z)$是一个常数多项式，其常数值在选择$z$之前就由Prover在承诺阶段发送，Verifier只需要验证Prover发送的承诺值是否等于最终计算得到的常数多项式中的常数即可，这样一来我们就将查询次数减小到了$\log d$次

为什么Prover不能作弊：$f_0$在90%的$\{z,-z\}$对上是等于零的（称为好的数对），也即对于90%的$\{z,-z\}$，都有$f_0(z)=f_0(-z)=0$，而其余的10%的$\{z,-z\}$都有$f_0(z)=f_0(-z)\neq0$（称为坏的数对），对于随即选择的$z$而言，只有10%的概率其是一对坏的数对

此外，根据前面提到的内容，只有一个$\alpha$会使得$f_1(z^2)=0$，其余的$\alpha$都会导致$f_1(z^2)\neq0$，若Prover尝试在$f_1(z^2)$上作弊，则会以极高的概率被Verifier发现，因为经过若干次迭代后，最后一次的值不为零的概率会非常高，此时很容易被Verifier发现

由于我们从一个以90%概率为零的函数$f$开始，Prover不太可能接近一个度为零的多项式以外的低度多项式，这意味着Prover必须发送0作为最后一层的值，但是Verifier发现Prover作弊的概率为10%（也即错误概率为90%），Verifier可以通过若干次独立的选择$z$来降低这个概率（如随机选择850个不同的$z$可以得到错误概率为$2^{-128}$）