1. 引言

前序博客有：

• ZKP大爆炸
• STARKs and STARK VM: Proofs of Computational Integrity
• STARK入门知识
• STARK中的FRI代码解析
• Rescue-Prime hash STARK 代码解析
• Fast Reed-Solomon Interactive Oracle Proofs of Proximity学习笔记

Low Degree Testing低度测试为STARK证明succinctness的秘方。

在STARK中，通过Arithmetization将Computational Integrity问题reduce为low degree testing问题。

所谓low degree testing低度测试，是指，若要判定某函数是否为具有某指定上限degree的多项式，仅需要make a small number of queries to the function。
低度测试问题已研究了二十多年，是probabilistic proof理论的核心工具。本文重点在于详细解释低度测试，并介绍FRI协议——STARK中所用的低度测试解决方案。

2. 低度测试

低度测试针对的场景为：
给定某函数，仅查询该函数的 “少量” 位置，来判定该函数是否为 小于某常量$d$ degree的某多项式。

即，已知某域$F$的子集$L$和degree bound $d$，判定$f:L\to F$是否等于某degree小于$d$的多项式，即，是否存在多项式：
$$p(x)=c_0+c_{1}x+\cdots +c_{d-1}{x}^{d-1}$$
over $F$，其中对于$\forall a\in L$，有$p(a)=f(a)$。
可想象field size很大，如为$2^{128}$，$L$的size约为1千万（10,000,000）。

为解决该问题，需要query $f$ at 整个 $L$域，因$f$可能仅在$L$中的某个单点不满足$p(a)=f(a)$。即使我们允许一定概率的错误，所需query的次数仍然与$L$的size呈线性关系。

低度测试，通过构建probabilistic proof，将query number降为logarithmic in $|L|$（如$L\approx 10,000,000，则{\log }_2(L)\approx 23$），可解决上述问题。确切来说，分为如下2种情况：

• 1）第一种情况——若函数$f$等于某低度多项式：即存在多项式$p(x)$ over $F$，其degree小于$d$，并agrees with $f$ everywhere on $L$。
• 2）第二种情况——若函数$f$为far from ALL low degree polynomials：如，需调整$f$中至少$10\%$的值，才能获得一个与degree小于$d$多项式一致的函数$f^{\prime }$。

还有一种可能性是：

• 3）第三种情况——若函数$f$中度接近某低度多项式，但不等于任何低度多项式。如，某函数具有$5\%$的值不等于低度多项式，因此不符合以上两种情况。但是，之前的STARK arithmetization步骤中，确保了本情况不会发生。即，诚实的Prover在处理true statement算术化过程中，会落入第一种情况；而作弊的Prover在试图证明false claim时，将大概率落入第二种情况。

为了区分以上两种情况，将使用a probabilistic polynomial-time test来query $f$ at a small number of locations。

【

• 若$f$确实是低度的，则该测试通过的概率为$1$。
• 若$f$为far from low degree，则该测试将大概率不通过。
• 若$f$为$\delta$-far from any function degree less than $d$（即，必须修改至少 $\delta |L|$ 个位置来获得某个degree小于$d$的多项式），则测试被拒绝的概率不低于$\Omega (\delta )$（或其它“nice” function of $\delta$）。直观来说，若$\delta$越接近零，则区分这两种情况的难度越大。
  】

接下来将一种简单的低度测试方案，并解释其为何无法满足要求，然后介绍一种效率指数级提升的复杂低度测试方案——STARK中使用的FRI。

2.1 Direct Test 低度测试方案

Direct Test 低度测试方案是：
通过采用$d+1$次query，来判断某函数是否为（或接近为）某degree小于$d$的多项式。

Direct Test 低度测试方案 基于的多项式basic fact为：

• 任意degree小于$d$的多项式，可由$F$中任意$d$个不同位置的值唯一确定。

该fact源自：degree为$k$的多项式，最多具有$k$个roots in $F$。

Direct Test 低度测试方案中，query次数为$d+1$，远小于$f$的domain size $|L|$。

首先讨论2个简单的特例情况：

• 1）若函数$f$为constant function，即$d=1$：则低度测试问题转为区分 $f$为某constant function（$f(x)=c$ for some $c$ in $F$） 还是 $f$为far from any constant function。
  针对这种特例情况，仅需要2-query test即可：query $f$ at 某固定点$z_1$以及某随机点$w$，然后检查$f(z_1)=f(w)$是否成立即可。直观的，$f(z_1)$可决定$f$的常量值，$f(w)$测试是否所有的$f$都接近该常量值。

• 2）若函数$f$为线性函数，即$d=2$：则低度测试问题转为区分 $f$为某线性函数（$f(x)=ax+b$ for some $a,b$ in $F$） 还是 $f$为far from any linear function。
  针对这种特例情况，仅需要3-query test即可：query $f$ at 某2个固定点$z_1,z_2$以及某随机点$w$，然后检查$(z_1,f(z_1)),(z_2,f(z_2)),(w,f(w))$是否共线性。直观的，$f(z_1)和f(z_2)$可决定$f$线性函数，$f(w)$测试所有$f$值是否都在该线上。

将以上特例情况推广至具有degree bound $d$的通用情况：
query $f$ at $d$个固定点$z_1,z_2,\cdots ,z_d$以及某随机点$w$。根据$f$在$z_1,z_2,\cdots ,z_d$的$d$个值，可唯一确定degree小于$d$的多项式$h(x)$ over $F$ that agrees with $f$ at these points。然后检查随机点的$h(w)=f(w)$是否成立即可，因此称为Direct Test。

根据定义可知，若$f(x)$等于 某degree小于$d$的多项式$p(x)$，则$h(x)$等于$p(x)$，Direct Test被通过的概率为$1$。该属性称为“完美完备性”，即意味着Direct Test具有only 1-sided error。

接下来讨论，若$f$为$\delta$-far from any function of degree less than $d$的情况，如假设$\delta =10\%$。此时，Direct Test被拒绝的概率不低于$\delta$。通过随机选择$w$，使得$h(w)\ne f(w)$的概率为$\mu$，则$\mu$必须不小于$\delta$。

【反向证明，若$\mu$小于$\delta$，则可推论$f$为$\delta$-close to $h$，与$f$为$\delta$-far from any function of degree less than $d$的前提情况矛盾。】

2.2 Direct Test低度测试方案不足以满足需求

因STARK中的testing函数$f:L\to F$中编码了computation traces，其degree $d$（和domain $L$）非常大，若直接运行query $d+1$次的Direct Test，将是非常昂贵的。
为此，为指数级（相对于computation trace size）的节约STARK中Verifier的验证时间，需要将$d+1$次 reduce为仅需$O(\log d)$次query。

但是，若query $f$ at 小于$d+1$个位置，将无法得出任何结论。

【
方案之一是，考虑函数$f:L\to F$的2种不同分布：

• 分布一：uniformly选择一个degree正好为$d$的多项式，并对其evaluate on $L$。
• 分布二：对于任意$d$个点$z_1,z_2,\cdots ,z_d$，其值$f(z_1),f(z_2),\cdots ,f(z_d)$为均匀独立分布的。

即意味着从信息轮角度来将，即使借助某test也无法区分以上2种分布（since polynomials from the first distribution should be accepted by the test while those of degree exactly d are very far from all polynomials of degree less than d, and thus should be rejected）。
】

2.3 引入Prover

已知，若要测试某函数$f:L\to F$ close to某degree小于$d$的多项式，需要$d+1$次query，但是我们无法承担那么多的query次数。

将该低度测试问题转换为：
某Prover可提供关于函数$f$的有用辅助信息。

通过引入Prover，可将低度测试的query次数实现指数级改进，所需query次数降为$O(\log d)$。

具体协议为：

• （untrusted）Prover：直到待测试的整个函数$f$。
• Verifier：查询函数$f$的少量位置，并希望借助Prover的帮助，但不需要信任Prover是诚实的。即意味着Prover可能会作弊且不遵循该协议，但Prover一旦作弊，Verifier有权拒绝，无论函数$f$是否为低度的。关键点在于，除非$f$确实是低度的，否则Verifier不会被说服。

可将上面的Direct Test看成是Prover啥也没干的特例情况，Verifier没有任何人辅助，自行测试该函数是否为低度多项式。为此，需充分有效利用Prover的功能，使得效率比Direct Test要高。

在整个协议中，Prover将want to enable the Verifier to query auxiliary functions on locations of the Verifier’s choice。可通过“commitment”来达成。即，Prover可将其选择的函数commit为a Merkle tree，然后Verifier可要求Prover公开该committed函数的任意位置集。这种承诺机制的主要属性在于：一旦Prover对某函数commit之后，其必须公开正确的值，且无法作弊（即，其无法在看到Verifier发来的请求位置之后再决定函数的值）。

2.4 2个函数的情况下将query次数减半

接下来将举例说明在Prover的帮助下如何将query次数减半。

假设有2个多项式$f,g$，想要证明$f和g$的degree都小于$d$，若运行Direct Test，则需要分别对$f,g$进行query，一共需要$2\ast (d+1)$次query。接下来将说明如何将query次数降为$(d+1)$再加某smaller-order term。

• 1）Verifier选择随机值$\alpha$发送给Prover；
• 2）Prover将$h(x)=f(x)+\alpha g(x)$在domain $L$进行evaluate，并将evaluation值进行commit后发送给Verifier（实时上，Prover将$\forall x\in L$的所有$h(x)$值作为叶子节点构建Merkle tree，将相应Merkle tree root发送给了Verifier）；【注意此处的domain $L$仍为函数$f$的domain $L$】
• 3）Verifier现在可通过Direct Test测试$h$的degree是否小于$d$，需要的查询次数为$d+1$。

直观的，若$f$或$g$的degree不小于$d$，则大概率$h$的degree也不小于$d$。
如，假设$f$的$x^n$项系数不为零，且$n\ge d$，则最多仅有一个$\alpha$取值（由Verifier选择发送），使得$h$的$x^n$项系数为零，即意味着$h$ degree小于$d$的概率约为$1/|F|$。若field足够大，如$|F|>2^{128}$，该错误概率可忽略。

不过，我们在第3）步中，并不检查$h$为某degree小于$d$的多项式，而转为仅检查$h$ close to 某degree小于$d$的多项式。这就意味着以上分析并不准确。是否有可能$f$为far from a low degree polynomial and the linear combination $h$ will be close to one with a non-negligible probability over $\alpha$？答案是不可能，详细可阅读 2017年论文Ligero: Lightweight Sublinear Arguments Without a Trusted Setup 以及 2018年论文Fast Reed-Solomon Interactive Oracle Proofs of Proximity。

参考资料

[1] StarkWare 2019年论文 Low Degree Testing