【zkMIPS系列】FRI原理及其应用分析

  • ZKM
  • 更新于 2024-11-08 20:50
  • 阅读 220

FRI原理及其应用分析

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 $$ 如果等式成立,则通过验证。

点赞 1
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
ZKM
ZKM
github: https://github.com/zkMIPS