FRI原理及其应用分析
FRI
- FRI原理 1.1 原理概述 1.2 实现过程 1.3 性能权衡
- FRI应用于多项式承诺
Fast Reed-Solomon Interactive Oracle Proof of Proximity (FRI)是一种用来检查被承诺的多项式的阶是否小于特定值d的交互式协议,其大致思路如下:给定两个多项式 $ p $ 和 $ q $ 具有阶 $ d $ ,那么对于任意的一个随机挑战 $ a $, $ p+aq $ 是 $ d $ 阶(则其编码值也靠近 $ d $ 阶多项式)。
具体而言,FRI协议主要分为三个阶段,由Commit, Folding和Query三块组成
FRI的主要优点在于:
FRI的主要缺点在于:
接下来说明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,计算以下信息:
Folding: 这里使用二分法将问题规模减半,即将阶为d的多项式转换为两个阶为d/2的多项式,并采用随机线性组合(Random Linear Combination)来生成一个新的阶为d/2的多项式,直到最终生成的多项式为一个常数或达到规定的阶,其计算过程如下: 对于第i轮的FRI folding(直到压缩为一个常数为止,即 $ i $ 最大为logd):
Query: 这里需要验证方发起若干个随机挑战,以检查证明方在折叠过程中的正确性(可以认为是重新执行一次折叠过程),证明方需要提交对应随机挑战的所有评估值,及评估值对应的Merkle path,其中所有评估值用于检查折叠过程,Merkle path用于检查该评估值确实在Merkle root中,其具体交互逻辑如下(需要执行多次,这里目前仅考虑一轮的验证,因为每轮的验证方式都是一样的):
for i=1 to log(d)
计算 $ 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 $
随后将下列的式子整理展开即可。
FRI在证明大小(proof size),证明时间(prover time)和验证时间(Verification time)中存在折中,主要由集合 $ \Omega $ 的大小 $ n=qd $ 决定:
为了减小证明大小(即Merkle path的长度),在Plonky2中通常提交Merkle cap,而非Merkle root,即Merkle root的各个子树的节点值。
与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 $$ 如果等式成立,则通过验证。
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!