FRI

1. FRI原理 1.1 原理概述 1.2 实现过程 1.3 性能权衡
2. FRI应用于多项式承诺

1. FRI原理

1.1 原理概述

Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI）是一种用来检查被承诺的多项式的阶是否小于特定值d的交互式协议，其大致思路如下：给定两个多项式 $ p $ 和 $ q $ 具有阶 $ d $ ，那么对于任意的一个随机挑战 $ a $， $ p+aq $ 是 $ d $ 阶（则其编码值也靠近 $ d $ 阶多项式）。

具体而言，FRI协议主要分为三个阶段，由Commit, Folding和Query三块组成

• Commit: 选取一个大小为 $ n $ 的集合，对一个 $ d $ 阶多项式 $ p $ ，采用集合中的每个元素进行运算，并作为叶子节点保存，随后建立一个Merkle tree，其中Merkle root作为最终的承诺值；
• Folding: 不断将多项式p的规模降低为 $ d/2 $ ，即将问题的规模减半，直到最后多项式的阶达到0（即一个常数）或预定义的阶；
• Query: 验证方发送随机挑战，以验证证明方folding的正确性，证明方除了提供对应点外，还要提供对应点的Merkle path，以证明该点确实在对应的Merkle tree中。

FRI的主要优点在于：

• 证明速度快，因为仅使用了抗碰撞的哈希函数；
• 后量子安全且不依赖于可信初始化，因为仅依赖于编码和抗碰撞的哈希函数。

FRI的主要缺点在于：

• 验证速度属于polylog级别，相较于Marlin，Plonk等更慢；
• proof size大，包含了所有challenge对应的evaluation和Merkle path (logn)

1.2 实现过程

接下来说明FRI协议的Commit，Folding和Query三阶段。需要注意的是，本节所给出的FRI协议是一个交互式版本的协议，即验证方会根据需要发送随机挑战给证明方。若需要转换为非交互式版本，则需要使用Fiat-Shamir转换将随机挑战值替换为对随机预言机的访问。

• 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

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

  1. 计算新的domain $ \Omega_i: w_j |→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)项； 这里只需要进行两次问询即可提取出对应的偶数项 $ p_e(X) $ 和奇数项 $ p_o(X) $ ： 偶数项公式为： $ p_e(X) = [p(X) + p( - X)]/2 $ 奇数项公式为： $ p_o(X) = [p(X) - p( - X)]/2 $
  4. 对 $ p_{fold}(X) $ 在 $ \Omega_i $ 进行计算，计算得到的结果作为树的叶子节点，并构建Merkle tree，Merkle $ root_i $ 作为第i轮的承诺值。 当规约到特定阶的多项式，或达到一个常数时，则结束folding。

• 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 $ 和 $ -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在证明大小(proof size)，证明时间(prover time)和验证时间(Verification time)中存在折中，主要由集合 $ \Omega $ 的大小 $ n=qd $ 决定：

1. 如果增大 $ q $ ，则随着证明方需要证明的点的个数的增多，证明方的证明时间需要同步增加，与此同时，所提交的Merkle path也增多，故总体的proof size也增加，但是用户的验证时间减少；
2. 如果减小 $ q $ ，则随着证明方需要证明的点的个数的减少，证明方的证明时间需要同步减小，与此同时，所提交的Merkle path也减少，故总体的proof size也减少，但是用户的验证时间增加。

为了减小证明大小（即Merkle path的长度），在Plonky2中通常提交Merkle cap，而非Merkle root，即Merkle root的各个子树的节点值。

2 FRI应用于多项式承诺

与KZG多项式承诺一样，FRI也可用于多项式承诺。 对于一个给定的多项式 $ p(X) $ 和一个点 $ t $ ，存在 $ p(t)=y $ ，则有 $$ h(X)=(p(X)-y)/(X-t) $$ 在多项式承诺中，采用对 $ h(X) $ 和 $ p(X) $ 同步承诺，并在特定点打开的方式，依次检查 $ h(X) $ 和 $ p(X) $ 最多具有阶 $ d-1 $ 和 $ d $ ，同步通过随机挑战的方式，在最后检查 $$ h(X) (X-t)= p(X)-y $$ 如果等式成立，则通过验证。