1. 前言

为了确保证明者返回的满足多项式等式相等的值确实是基于有效的多项式计算得到，我们需要对多项式进行 LDT 测试；同时为了使验证者的复杂度达到最优，我们把原始多项式进行变换，变换后，证明者要证明的多项式仅仅是原始多项式的一半，不断重复这一过程，一直到多项式的度可以直接判断为止。这其实就是 FRI 协议的核心思想，下面，让我们来详细介绍 FRI 协议的过程。

2. FRI 协议

也许, 我们应该先说一下FRI 协议是什么? FRI, 即 Fast RS IOPP, 全称 Fast Reed−Solomen Interactive Oracle Proofs of Proximity，是一种更有效的 proximiary 测试方法, 测试一个点的集合大部分是在一个度小于某个值的多项式上，能达到线性级的证明复杂度和对数级的验证复杂度。在我们正式介绍 FRI 协议之前，我们先看一个简单的场景。

在有限域 F 上，存在一个乘法群 L₀ ，群的阶为 2ⁿ ；

• 这时，证明者声称码字 f₀ : L₀ -> F 是满足 RS[F,L₀,ρ] 编码参数的一个码字，即 f₀ 的大部分点在一个阶为 d<ρ∗2ⁿ 的多项式上 P(x) 上，这里 ρ=2^(−R) ；

因此, 当 f₀=P 时, 存在阶满足 deg(P₁、P₂)<1/2∗ρ∗2ⁿ 关系的多项式 P₁、P₂ 满足以下等式：

f₀(x)=P(x)=P₁(x²)+x∗P₂(x²)  -- (1)

令 Q(x,y)=P₁(y)+x∗P₂(y) ，可以看出二元多项式 Q(x,y) 关于变量 x 的阶 d<2 ；关于变量 y 的阶 d<1/2∗ρ∗2ⁿ 且当 y=x² ，有 Q(x,y)=f₀(x) ；此时，验证者 V 随机选取一个值 x₀ 发送给证明者 P ，证明者 P 计算 Q(x₀,y) 且令:

f₁(y)=Q(x₀,y)=P1(y)+x₀∗P₂(y)  -- (2)

对于多项式 f₁(y) ，由于 y=x² ，且 x 取值范围是群 L₀ ，因此有等式 x⁽²ⁿ⁾=1 ，进一步转换为 (x²)ⁿ=1 ，因此，如果定义自变量 y 的取值范围为群 L₁ ，则 L₁ 应具备以下属性：

• 群的阶为 2⁽ⁿ⁻¹⁾ ;

• 群 L₁ 的每个元素对应群 L₀ 的两个元素；即对于群 L₁ 的任意元素 y ，群 L₀ 都有两个元素 x 和 (−x)mod p ，满足 x²mod p=y && (−x)²mod p=y ；

至此，问题就转化为了证明者 P 证明多项式 f₁(y) 的阶 满足 d<1/2∗ρ∗2ⁿ 问题；同时也要保证函数 f₁ 和 f₀ 的一致性，具体步骤如下：

a. 验证者 V 分别从群 L₁ 和群 L₀ 选取三个点 y,s₀,s₁ 满足 s0!=s1 && s₀²=s₁²=y

b. 证明者 P 返回 f₀(s₀),f₀(s₁),f₁(y) 三个值

c. 验证者 V 根据 f₀(s₀),f₀(s₁) 插值出一个阶 d<2 的多项式 g(x)

d. 验证者 V 验证 g(s₀)=f₁(y) ，不相等，则失败

e. //2022-01-11 修改错误描述 g(x⁰)=f₁(y)

可靠性分析：如果函数 f₁ 不是由函数 f₀ 按照上述过程转换而来，那么公式 (1) 的多项式和 P₁(x²) 和 P₂(x²) 和公式 (2) 的多项式和 P₁(y) 和 P₂(y) 之间大概率互不相等。考虑到多项式的阶满足 d<1/2∗ρ∗2ⁿ ，变量的取值范围为 2⁽ⁿ⁻¹⁾ ,根据 Schwartz-Zippel 定理, 在这个范围内随机选取一个值,多项式相等的概率为 (1/2∗ρ∗2ⁿ) / 2⁽ⁿ⁻¹⁾=ρ 。ρ 为编码 coderates，如果 ρ=2⁻⁸ ，那么一次校验成功的概率仅仅为 2⁻⁸ 。如果经过 k 次验证，那么作恶成功的概率就等于 2^−8k ，随着 k 的增大，概率无限接近 0。

对函数 f₁ 重复上述的过程，直到多项式 f_r 变成一个可以有效判断阶的形式，就完成了整个 LDT 过程。

下面，我们看一下 FRI 协议的具体内容，如图 1 所示：

FRI 协议分为两个阶段：Commit 阶段和 Query 阶段。从前面简单的场景示例可以看出，一次交互过程需要：

a. 验证者 V 发送随机数 x₀ 给证明者 P ；

b. 证明者 P 生成新多项式 f_i ，

c. 验证者 V 生成 query 的点集 s_0,i,s_1,i,y_i 发送给证明者 P

d. 证明者 P 算对应的多项式值 f_i(y_i),f_i−1(s_0,i),f_i−1(s_1,i)

e. 验证者 V 进行有效性校验。

a. verifier input

 • R / η / L_i / RS_i / x_i / f_i / P(x) 见 Commit

 • l query 次数，重复多次以达到需要的安全级别

b. 重构 f_r

 • 访问 oracle 获取 a₀,...,a_d，重构多项式 P^r(x)

 • 计算 P^r(x) 在群 L_r 上的所有取值，并赋值给 f_r

c. repeat l times

 • i = {0~r-1}

ⅰ. S_i 满足 s_i+1=q₀(s_i) 的 s_i 的集合

ⅱ. 比如，从群 L₀ 开始，随机选取一个元素 s₀ ，计算 s₁=q₀(s₀) ，则 s₁ 为群 L₁ 的元素；但在群 L₀ 上满足上述关系的还有 −s₀ （这里假设 q₀(x)=x² ）,因此有 S₀={s₀,−s₀} ；同样的，继续对 s₁ 重复进行上述运算，直到 r 次，会得到一系列的集合 S₀,S₁,...,S_r−1

 • i = {0~r-1}

ⅰ. 分别在步骤 1 得到的集合 S₀,S₁,...,S_r−1上，QUERY 多项式 f_i 的取值

ⅱ. 校验返回的值与对应的多项式承诺一致（如果 COMMIT 阶段的承诺是基于 merkle 的 hash 计算，这里就需要用到多次 hash 计算，计算出 root）

ⅲ. 依次插值出 P₀(x),P₁(x),...,P_r−1(x)

 • round consistency check i = {0~r-1}

ⅰ. 依次校验 f_i+1(s_i+1)=P_i(x_i)

ⅱ. 如果都校验成功，则验证通过

下面，以η = 1（即 q₀(x)=x²）为例，展示 FRI 协议的两个阶段的过程，如下图所示：d<ρ∗2ⁿ

• 上述协议重复 l 次，可以大大降低作恶者成功的概率

3. 总结

以上就是 FRI 协议的具体过程，可以看出，验证复杂度满足对数关系 r=Log₂(ρ∗2ⁿ)。算法保证了，当且仅当原始多项式 f₀ 满足 d<ρ∗2ⁿ ，所有的 round consistency 校验才会通过。真正的实现可能略有差别，具体的可以参考 DEEP-FRI 论文，相对于 FRI，DEEP-FRI 在保持证明和验证的最优复杂度的同时，提高了系统的可靠性。

附录

1. 官方 FRI 的简单介绍

https://medium.com/starkware/low-degree-testing-f7614f5172db

2. FRI paper

https://eccc.weizmann.ac.il/report/2017/134/

3. DEEP-FRI paper

chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html%3Ffile%3Dhttps%253A%252F%252Farxiv.org%252Fpdf%252F1903.12243.pdf

4. Reed-Solomen WIKI 

https://en.wikipedia.org/wiki/Reed%25E2%2580%2593Solomon_error_correction