1. FRI协议概述

1.1 FRI概念

FRI协议是一种通过交互证明多项式低阶性（degree constraint）的证明系统。证明者（Prover）向验证者（Verifier）承诺一个多项式的形式，验证者通过采样该多项式的若干点，并进行多次随机线性组合和多项式折叠，来确保承诺的多项式确实是低阶的。这种交互式证明系统在零知识证明中尤其重要，因为它允许在不暴露多项式本身的情况下，验证其性质。

1.2 FRI基本原理

FRI基于Reed-Solomon编码和多项式评估，通过采样和折叠逐步减少多项式的阶数，直至其低阶性质显而易见。该过程中的折叠操作（Polynomial Folding）可以有效减少证明者和验证者之间的通信量，使得它在大规模的证明系统中尤其高效，其通信复杂度和通信轮数（交互式证明系统）与多项式的阶呈对数关系，即 $O(logd)$ ，其中 $d$ 是多项式的最高阶。

FRI是由Commit, Folding和Query三块算法构成的，其算法定义如下：

• 1. Commit: 给定一个 $ d $ 阶多项式 $ p(X) $ ，一个预定义大小为 $ n (n=qd, q>2) $ 的集合domain $ \Omega={w_1, w_2, \dots, w_n} $ 和一个抗碰撞的哈希函数 $ H $ ，计算以下信息：

  1. 计算每个 $ p(w_i) $ ，并将每个 $ p(w_i) $ 作为Merkle tree的叶子节点；
  2. 通过抗碰撞的哈希函数H来构造Merkle tree;
  3. 验证方将Merkle root作为commitment，证明方保存整棵Merkle tree。

• 2. Folding: 这里使用二分法将问题规模减半，即将阶为 $ d $ 的多项式转换为两个阶为 $ d/2 $ 的多项式，并采用随机线性组合(Random Linear Combination)来生成一个新的阶为d/2的多项式，直到最终生成的多项式为一个常数或达到规定的阶，其计算过程如下: 对于第i轮的FRI folding（直到压缩为一个常数为止，即 $ i $ 最大为 $ \log d $ )：

  1. 计算新的domain $ \Omega_i: w_j | \rightarrow w^2_j $ ，以确保多项式在后续的domain中仍然保有该特性；
  2. 验证方发送一个随机挑战 $ x $ ；
  3. 证明方计算压缩后的多项式 $ p_{fold}(X)=p_e(X)+x p_o(X) $ ，其中 $ p_e(X) $ 是 $ p(X) $ 中所有的偶数(even)项，而 $ p_o(X) $ 是 $ p(X) $ 中所有的奇数(odd)项；
  4. 对 $ p_{fold}(X) $ 在 $ \Omega_i $ 进行计算，计算得到的结果作为树的叶子节点，并构建Merkle tree，Merkle root $ root_i $ 作为第i轮的承诺值。 当规约到特定阶的多项式，或达到一个常数时，则结束folding。

• 3. Query: 这里需要验证方发起若干个随机挑战，以检查证明方在折叠过程中的正确性（可以认为是重新执行一次折叠过程），证明方需要提交对应随机挑战的所有评估值，及评估值对应的Merkle path，其中所有评估值用于检查折叠过程，Merkle path用于检查该评估值确实在Merkle root中，其具体交互逻辑如下（需要执行多次，这里目前仅考虑一轮的验证，因为每轮的验证方式都是一样的）：

  1. 在 $ \Omega $ 集合中先选取一个值 $ t $ ；
  2. 证明方反馈对应的 $ p(t) $ 及相应的Merkle path； for i=1 to $ \log d $
  3. 计算 $ t=t^2 $ 作为下一轮打开的点；
  4. 证明方反馈对应的 $ p_{fold}(t) $ 及相应的Merkle path；
  5. 判断 $ p_{fold}(t)=p_e(t)+t p_o(t)$。

特别注意的是，计算 $ p_e(X) $ 和 $ p_o(X) $ 只需要问询 $ p(X) $ 在 $ X=t $ 和 $ X=-t $ 位置的值即可，因为有以下等式成立（Prover在responds时需要同步提交对应的Merkle path）： $$ p(X)=p_e(X)+X p_o(X). $$ 对于 $ p(X) $ 而言，提取所有偶数项 $ p_e(X)=[p(X)+p(-X)]/2 $ ，提取所有奇数项 $ p_o(X)=[p(X)-p(-X)]/2 $。

1.3 FRI示例

我们通过一个具体的三阶多项式来演示FRI的Commit阶段流程。假设我们有一个三阶的多项式： $$ f(x) = 2x^3 + 3x^2 + x + 5. $$ 根据FRI的定义，则需要 $ \log 4=2 $ 轮的交互，来完成多项式的规约。

1.3.1 Prover 分解多项式

首先，Prover 将这个三阶多项式 $ f(x) $ 分解成两个二阶多项式的形式： $$ f(x) = g_0(x^2) + xh_0(x^2). $$ 其中， $ g_0(x^2) $ 和 $ h_0(x^2) $ 是关于 $ x^2 $ 的多项式。因此，我们可以将 $ f(x) $ 重写为： $$ f(x) = (2x^2 + 5) + x(3x + 1). $$ 因此：

• $ g_0(x^2) = 2x^2 + 5 $
• $ h_0(x^2) = 3x + 1 $

1.3.2 Verifier 发送随机值

接下来，Verifier 发送一个随机值 $ \alpha_0 $ 。

1.3.3 Prover 提交并继续分解

Prover 根据收到的随机值 $ \alpha_0 $ ，计算 $ f_1(x) = g_0(x) + \alpha_0 h_0(x) $ 。假设 $ \alpha_0 = 1 $ ，那么： $$ f_1(x) = (2x^2 + 5) + 1 \cdot (3x + 1) = 2x^2 + 5 + 3x + 1 = 2x^2 + 3x + 6. $$ 接下来，Prover 将这个二阶多项式 $ f_1(x) $ 再次分解成两个更低阶的多项式： $$ f_1(x) = g_1(x^2) + xh_1(x^2). $$ 因此：

• $ g_1(x^2) = 2x^2 + 6 $
• $ h_1(x^2) = 3 $

1.3.4 Verifier 发送随机值 $ \alpha_1 $

在 Prover 完成了对 $ f_1(x) $ 的分解后，Verifier 继续发送一个新的随机值 $ \alpha_1 $ 供下一步使用。

1.3.5 Prover 提交并继续分解

Prover 根据收到的随机值 $ \alpha_1 $ ，计算 $ f_2(x) = g_1(x) + \alpha_1 h_1(x) $ 。假设 $ \alpha_1 = 1 $ ，则有： $$ f_2(x) = (2x^2 + 6) + 1 \cdot 3 = 2x^2 + 6 + 3 = 2x^2 + 9. $$ 接下来，Prover 再次将这个二阶多项式 $ f_2(x) $ 分解为两个一阶多项式： $$ f_2(x) = g_2(x^2) + xh_2(x^2). $$ 因为 $ f_2(x) = 2x^2 + 9 $ ，所以：

• $ g_2(x^2) = 2x^2 + 9 $
• $ h_2(x^2) = 0 $ （因为没有 $ x $ 的项）

1.3.6 Verifier 发送随机值 $ \alpha_2 $

接着，Verifier 发送随机值 $ \alpha_2 $ ，Prover 计算 $ f_3(x) = g_2(x) + \alpha_2 h_2(x) $ 。因为 $ h_2(x) = 0 $ ，所以此时： $$ f_3(x) = 2x^2 + 9. $$

1.3.7 常数(多项式)提交

此时已经得到一个常数多项式 $ f_3(x) = 9 $ ，这表明多项式的阶数已经降低到了零，证明过程结束。

2. DEEP-FRI原理

2.1 DEEP-FRI优势

尽管FRI本身已经具有较高的效率，但在处理复杂约束条件或更大规模的证明时，仍然存在进一步优化的空间。DEEP-FRI通过引入深度代数结构，优化了多项式折叠和随机线性组合的策略，能够在不显著增加通信成本的情况下，进一步提高证明效率。

与此同时，DEEP-FRI支持在域之外的点进行问询，极大地提升了原始FRI协议的soundness，同时问询的次数可以相应减少，以减小证明大小 (Proof Size)。

2.2 商(Quotient)操作

这个操作通常在一些证明或算法中用于调整函数的形态，消除某个特定点 $ z $ 处的值，或者在多项式构造中用于简化和归约，其具体流程如下：

• 给定一个集合 $ L \subseteq \mathbb{F}_q $ ，即这个集合是有限域 $ \mathbb{F}_q $ 的一个子集。
• 给定一个函数 $ f \colon L \to \mathbb{F}_q $ ，它将集合 $ L $ 中的每个元素映射到有限域 $ \mathbb{F}_q $ 中的一个元素。
• 给定一个点 $ z \in \mathbb{F}_q $ 和一个值 $ b \in \mathbb{F}_q $ 。

2.2.1 定义

首先，定义多项式 $ Z(Y) = Y - z $ 。这是一个简单的线性多项式，它的根为 $ z $ 。

接着定义一个新的函数 $ g \colon L \to \mathbb{F}_q $ ，其公式为： $$ g(y) = \frac{f(y) - b}{Z(y)} = \frac{f(y) - b}{y - z}. $$ 1. 输入参数 ：

• $ f(y) $ ：原函数在 $ y $ 处的值。
• $ b $ ：给定的常数。
• $ z $ ：给定的点。 2. 输出：一个新函数 $ g(y) $ ，它是原函数 $ f(y) $ 减去常数 $ b $ 之后，再除以 $ y - z $ 。

2.3 DEEP-FRI具体流程

DEEP-FRI是由Commit, Folding和Query三块算法构成的，在这里我们考虑交互式证明系统，如果需要转换为非交互式系统，对于验证方发送的每个挑战值而言，使用Fiat-Shamir转换的方式替换每个挑战值，DEEP-FRI的交互式证明算法定义如下：

2.3.1 Commit

假设给定一个 $ d $ 阶多项式 $ p(X) $ ，以及一个预先定义大小为 $ n = qd $ （其中 $ q > 2 $ ）的集合域 $ \Omega = { w_1, w_2, \dots, w_n } $ 和一个抗碰撞的哈希函数 $ H $ 。在这个阶段，需要进行以下步骤：

1. 计算每个 $ p(w_i) $ ：将每个 $ p(w_i) $ 作为 Merkle 树的叶子节点。
2. 通过哈希函数 $ H $ ：使用哈希函数 $ H $ 构造 Merkle 树。
3. 验证 Merkle 根 ：验证方将 Merkle 根节点作为承诺（commitment），证明方保存整个 Merkle 树。

2.3.2 Folding

Folding阶段是通过递归的方式，继续将多项式 $ f^{(i)}(x) $ 的查询域折叠，并且生成一个新的多项式，使得下一个迭代过程中的多项式的阶数递减，其具体过程如下：

对于第i轮的folding ( $ i < \log d $ )

1. 多项式查询：

1. 双方共同计算下一轮的域 $ L^{(i+1)} $ ；
2. 对于每一轮 $ i $ ，验证者选择随机点 $ z^{(i)} $ ，其中 $ z^{(i)} $ 以很大概率不在域 $ L^{(i)} $ 的范围；
3. 证明者将低阶多项式 $ f^{(i)}(x) $ 按照给定规则回复一个多项式，使其得到一个新的多项式 $ B^{(i)}{z^{(i)}}(X) $ ，满足下列等式： $$ B^{(i)}{z^{(i)}}(x) = H_x \left [f^{(i)} \right]. $$

2. 随机挑战和多项式降阶

1. 验证方首先发送一个随机挑战 $ x^{(i)} $ ；
2. 证明方根据规则进行折叠，并在域 $ L^(i+1) $ 上计算折叠后多项式的评估值，所有的评估值作为叶子节点，构建Merkle tree，并生成对应的Merkle Root。

折叠方式如下：

我们有一个函数 $ f^{(i+1)} \colon L^{(i+1)} \to \mathbb{F}q $，这个函数的定义是基于商操作（QUOTIENT）。在给定 $ y $ 作为输入时，函数 $ f^{(i+1)} $ 被定义为： $$ f^{(i+1)}(y) = \frac{H{x(i)}[f^{(i)}] - B^{(i)}_{z^{(i)}}(x)}{y - z^{(i)}}. $$ 其具体说明如下：

1. $H_{x(i)}[f^{(i)}]$：这是对函数 $ f^{(i)} $ 经过某种变换得到的新函数值，这里的 $ H_x $ 折叠方式应当和FRI的折叠方式一样。
2. $z^{(i)}$ ：这是给定的点 $ z $ ，与之前的商公式 $ Z(Y) = Y - z $ 对应，这里是在分母中使用 $ y - z^{(i)} $ 来进行商操作。
3. $B^{(i)}_{z^{(i)}}(x)$ ：这是另一个与 $ z^{(i)} $ 和 $ x $ 相关的函数或值，可能是某种补偿项或目标值。

以上的步骤执行结束，如果折叠后的多项式是一个常数C，或者多项式达到了一个预定义的阶。

2.3.3 Query

Query阶段主要用于验证多项式的最终计算结果是否正确，其具体过程如下：

1. 重复查询 $ \ell $ 次：

1.1. 验证者从域 $ D $ 中选择一个随机点 $ s^{(0)} $ ，并根据每个 $ i $ 定义对应的点 $ s^{(i+1)} $ ，其 中：$s^{(i+1)} = q^{(i)}(s^{(i)})$ 偶数项公式为： $$ f{even}(X)=\frac{f(X)+f(-X)}{2}. $$ 奇数项公式为： $$ f{odd}(X)=\frac{f(X)-f(-X)}{2}. $$

1.2. 证明者向验证者提供 $ f^{(i+1)}(s^{(i+1)}) $ 和 $ H_x(i)[f(i)]$ 的值（对 $ f^{(i+1)}(X) $ 多项式在 $ X=s^{(i+1)}和X=-s^{(i+1)} $ 中进行问询)，及对应的Merkle path。

1.3. 验证者验证对应值是否在对应的Merkle Tree中，同时验证以下等式： $$ Hx \left [f^{(i)} \right] = f^{(i+1)}(s^{(i+1)}) \cdot (s^{(i+1)} - z^{(i)}) + B^{(i)}{z^{(i)}}(x^{(i)}). $$ 2. 最终结果验证 ：检查最终的多项式计算结果是否与事先承诺的值 $ C $ 一致，若不一致则拒绝，否则接受。