1. 引言
前序博客有：
ZKP 大爆炸[1] STARKs and STARK VM: Proofs of Computational Integrity[2] STARK 入门知识[3] STARK 中的 FRI 代码解析[4] Rescue-Prime hash STARK 代码解析[5] Fast Reed-Solomon Interactive Oracle Proofs of Proximity 学习笔记[6]
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. 低度测试
低度测试针对的场景为：给定某函数，仅查询该函数的「少量」位置，来判定该函数是否为 小于某常量 degree 的某多项式。
即，已知某域 的子集 和 degree bound ，判定 是否等于某 degree 小于 的多项式，即，是否存在多项式：
over ，其中对于 ，有 。可想象 field size 很大，如为 ， 的 size 约为 1 千万（10,000,000）。
为解决该问题，需要 query at 整个 域，因 可能仅在 中的某个单点不满足 。即使我们允许一定概率的错误，所需 query 的次数仍然与 的 size 呈线性关系。
低度测试，通过构建 probabilistic proof，将 query number 降为 logarithmic in （如 ），可解决上述问题。确切来说，分为如下 2 种情况：
1）第一种情况——若函数 等于某低度多项式：即存在多项式 over ，其 degree 小于 ，并 agrees with everywhere on 。 2）第二种情况——若函数 为 far from ALL low degree polynomials：如，需调整 中至少 的值，才能获得一个与 degree 小于 多项式一致的函数 。
还有一种可能性是：
3）第三种情况——若函数 中度接近某低度多项式，但不等于任何低度多项式。如，某函数具有 的值不等于低度多项式，因此不符合以上两种情况。但是，之前的 STARK arithmetization 步骤中，确保了本情况不会发生。即，诚实的 Prover 在处理 true statement 算术化过程中，会落入第一种情况；而作弊的 Prover 在试图证明 false claim 时，将大概率落入第二种情况。
为了区分以上两种情况，将使用 a probabilistic polynomial-time test 来 query at a small number of locations。
若 确实是低度的，则该测试通过的概率为 。 若 为 far from low degree，则该测试将大概率不通过。 若 为 -far from any function degree less than （即，必须修改至少 个位置来获得某个 degree 小于 的多项式），则测试被拒绝的概率不低于 （或其它“nice” function of ）。直观来说，若 越接近零，则区分这两种情况的难度越大。
接下来将一种简单的低度测试方案，并解释其为何无法满足要求，然后介绍一种效率指数级提升的复杂低度测试方案——STARK 中使用的 FRI。
2.1 Direct Test 低度测试方案
Direct Test 低度测试方案是：
通过采用 次 query，来判断某函数是否为（或接近为）某 degree 小于 的多项式。
Direct Test 低度测试方案 基于的多项式 basic fact 为：
任意 degree 小于 的多项式，可由 中任意 个不同位置的值唯一确定。
该 fact 源自：degree 为 的多项式，最多具有 个 roots in 。
Direct Test 低度测试方案中，query 次数为 ，远小于 的 domain size 。
首先讨论 2 个简单的特例情况：
1）若函数 为 constant function，即 ：则低度测试问题转为区分 为某 constant function（ for some in ） 还是 为 far from any constant function。
针对这种特例情况，仅需要 2-query test 即可：query at 某固定点 以及某随机点 ，然后检查 是否成立即可。直观的， 可决定 的常量值， 测试是否所有的 都接近该常量值。
2）若函数 为线性函数，即 ：则低度测试问题转为区分 为某线性函数（ for some in ） 还是 为 far from any linear function。
针对这种特例情况，仅需要 3-query test 即可：query at 某 2 个固定点 以及某随机点 ，然后检查 是否共线性。直观的， 可决定 线性函数， 测试所有 值是否都在该线上。
将以上特例情况推广至具有 degree bound 的通用情况：query at 个固定点 以及某随机点 。根据 在 的 个值，可唯一确定 degree 小于 的多项式 over that agrees with at these points。然后检查随机点的 是否成立即可，因此称为 Direct Test。
根据定义可知，若 等于 某 degree 小于 的多项式 ，则 等于 ，Direct Test 被通过的概率为 。该属性称为「完美完备性」，即意味着 Direct Test 具有 only 1-sided error。
接下来讨论，若 为 -far from any function of degree less than 的情况，如假设 。此时，Direct Test 被拒绝的概率不低于 。通过随机选择 ，使得 的概率为 ，则 必须不小于 。
反向证明，若 小于 ，则可推论 为 -close to ，与 为 -far from any function of degree less than 的前提情况矛盾。
2.2 Direct Test 低度测试方案不足以满足需求
因 STARK 中的 testing 函数 中编码了 computation traces，其 degree （和 domain ）非常大，若直接运行 query 次的 Direct Test，将是非常昂贵的。为此，为指数级（相对于 computation trace size）的节约 STARK 中 Verifier 的验证时间，需要将 次 reduce 为仅需 次 query。
但是，若 query at 小于 个位置，将无法得出任何结论。
方案之一是，考虑函数 的 2 种不同分布：
分布一：uniformly 选择一个 degree 正好为 的多项式，并对其 evaluate on 。 分布二：对于任意 个点 ，其值 为均匀独立分布的。
即意味着从信息轮角度来将，即使借助某 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
已知，若要测试某函数 close to 某 degree 小于 的多项式，需要 次 query，但是我们无法承担那么多的 query 次数。
将该低度测试问题转换为：某 Prover 可提供关于函数 的有用辅助信息。
通过引入 Prover，可将低度测试的 query 次数实现指数级改进，所需 query 次数降为 。
具体协议为：
（untrusted）Prover：直到待测试的整个函数 。 Verifier：查询函数 的少量位置，并希望借助 Prover 的帮助，但不需要信任 Prover 是诚实的。即意味着 Prover 可能会作弊且不遵循该协议，但 Prover 一旦作弊，Verifier 有权拒绝，无论函数 是否为低度的。关键点在于，除非 确实是低度的，否则 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 个多项式 ，想要证明 和 的 degree 都小于 ，若运行 Direct Test，则需要分别对 进行 query，一共需要 次 query。接下来将说明如何将 query 次数降为 再加某 smaller-order term。
1）Verifier 选择随机值 发送给 Prover； 2）Prover 将 在 domain 进行 evaluate，并将 evaluation 值进行 commit 后发送给 Verifier（事实上，Prover 将 的所有 值作为叶子节点构建 Merkle tree，将相应 Merkle tree root 发送给了 Verifier）；【注意此处的 domain 仍为函数 的 domain 】 3）Verifier 现在可通过 Direct Test 测试 的 degree 是否小于 ，需要的查询次数为 。
直观的，若 或 的 degree 不小于 ，则大概率 的 degree 也不小于 。
如，假设 的 项系数不为零，且 ，则最多仅有一个 取值（由 Verifier 选择发送），使得 的 项系数为零，即意味着 degree 小于 的概率约为 。若 field 足够大，如 ，该错误概率可忽略。
不过，我们在第 3）步中，并不检查 为某 degree 小于 的多项式，而转为仅检查 close to 某 degree 小于 的多项式。这就意味着以上分析并不准确。是否有可能 为 far from a low degree polynomial and the linear combination will be close to one with a non-negligible probability over ？答案是不可能，详细可阅读 2017 年论文 Ligero: Lightweight Sublinear Arguments Without a Trusted Setup[7] 以及 2018 年论文 Fast Reed-Solomon Interactive Oracle Proofs of Proximity[8]。
此外，Verifier 如何知道 Prover 发来的多项式 的形式为 ？恶意 Prover 可发送确实是低度的多项式，但是不同于 Verifier 请求的多项式线性组合 。若已知 close to 某低度多项式，然后测试该低度多项式具有正确的形式：
Verifier：随机选择 中的点 ，然后 query at ，然后检查 成立即可。这个测试应该重复多次，以提高测试的准确性，但误差随着样本数量的增加而呈指数级缩小。因此，这一步骤仅将查询数量（到目前为止是 d+1），增加了一个 smaller-order term。
2.5 将单个多项式切分为 2 个 smaller-degree 多项式
根据 2.4 可知，借助 Prover 的帮助，可将测试 2 个多项式 degree 均小于 的 query 次数，由 降为 。接下来，描述，如何将 degree 小于 的多项式 切分为 2 个 degree 小于 的多项式。
令 为 degree 小于 的多项式，且 为偶数。则有 ，其中 的 degree 均小于 。事实上，可令 由 的偶数项系数组成， 由 的奇数项系数组成。
如，令 ，有：
有：
为 algorithm for polynomial evaluation（若直接计算，为 algorithm）。
2.6 FRI 协议
以上已形成了 2 种思想：
1）以一半的 query 次数，实现对 2 个多项式的低度测试； 2）将单个多项式切分为 2 个度数更低的多项式。
FRI 协议（全称为 Fast Reed-Solomon Interactive Oracle Proofs of Proximity，详细可参看 2018 年论文 Fast Reed-Solomon Interactive Oracle Proofs of Proximity[8]）为将这 2 种思想结合，仅需要 次 query，可测试某函数 具有（准确来说是 close to）degree 小于 。
为简单起见，令 为 a power of 。FRI 协议包含 2 个阶段：
1）Commit 阶段 2）Query 阶段
2.6.1 FRI 协议的 Commit 阶段
FRI 协议的 Commit 阶段为：
1）Prover 将原始的 多项式切分为 2 个 degree 小于 的多项式