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 小于 的多项式 ，使得 。
• 2）Verifier 发送随机值 。
• 3）Prover 对多项式 进行 commit。注意此时 的 degree 小于 。【 的 evaluation 值是不是基于 ，而是基于 。】
• 4）Prover 将原始的 多项式切分为 2 个 degree 小于 的多项式 ，使得 。
• 5）Verifier 发送随机值 。
• 6）Prover 对多项式 进行 commit。注意此时 的 degree 小于 。
• 7）……

重复以上过程，每一次切分，多项式 degree 都会减半。使得 步之后，可获得一个 constant 多项式，Prover 仅需将该常量值发送给 Verifier。

不过，要注意 domain：

• 1）以上协议中，要求 ，有 。
• 2） 的 evaluation 值是不是基于 ，而是基于 。然后基于这些 evaluation 值构建 Merkle tree commitment。
• 3）递归调用以上 FRI step， 需满足 属性。

这些要求很容易选择 domain 来满足（即，某 size 为 a power of 的 multiplicative subgroup 即可满足），而事实上，巧合的是，与高效 FFT 算法的要求一致（STARK 中对 execution trace 进行编码时，有用到 FFT 算法）。

2.6.2 FRI 协议的 Query 阶段

FRI 协议的 Query 阶段，是为了检查 Prover 没有作弊。Verifier 选择 中的随机点 ，query 。这 2 个值足以确定 的值，因可将其看成是 2 个线性方程式，以「 」为变量：

Verifier 可解这 2 个方程式，然后推断出 的值。同时，因 ，有 ，从而可知 也为 的线性组合。此时，Verifier 可 query ，并自行基于 的线性组合计算，判断二者是否相等。从而确定 Prover 在 commit 阶段发送的 的承诺值确实是正确的。

Verifier 可继续，进一步 query （注意， 且 的 commitment 是基于 的），从而推导出 。

Verifier 可重复以上过程，直到最终推导出 的值，其为 constant 多项式，其 constant 值由 Prover 在 commit 阶段发送（在 Verifier 发送 之前）。Verifier 需检查其收到的值 与 其根据之前 query 到的函数计算出来的值 是确实相等的。

总之，总的 query 次数为 。

为何 Prover 无法作弊呢？
假设 is zero on of the pairs of the form ，即 （称这种为「good」pairs）。而仍有 的为非零值（称为「bad」pairs）。
Verifier 在随机选择 query 时，有 的概率落入 bad pair，但是，仅有一个 取值能使得 ，其余的 取值都将导致 。若 Prover 在 上作弊，将被抓获。因此， 在下一层中也将大概率为 bad pair（当 时， 的值已不重要了）。如此持续，最后一层中的值为非零值的概率将很高。

不过，另一方面，若某函数具有 的零值，则 Prover 将无法 get close to a low degree polynomial other than the zero polynomial（该 fact 此处不证明）。特别的，这意味着在最后一层 Prover 必须发送 0 值。但是，Verifier 仅有约 的概率来抓获 Prover 作弊。这仅是一个非正式论证，详细证明可参看 2018 年论文 Fast Reed-Solomon Interactive Oracle Proofs of Proximity^[8]。

目前为止，以上测试 Verifier 抓获恶意 Prover 的概率仅为 10%，即错误概率为 ，但是，对多个独立 sample 的 值，重复以上 query 阶段，可指数级提升准确率。如，选择 850 个 query 值，错误概率可降为 ，可几乎忽略不计。

3. 总结

本文主要描述了低度测试问题。

若采用 Direct Test 低度测试方案，所需的 query 次数过多，无法满足 STARK 所需的 succinct 要求。

为实现 logarithmic query complexity，采用了名为 FRI 的交互协议，引入 Prover 添加信息，使得 Verifier 可信服该函数确实是低度的。

事实上，FRI 使得 Verifier 可以 次 query，来解决低度测试问题。