FRI原理解析

FRI (Fast Reed-Solomon IOPP)是零知识证明协议ZK-STARK的核心。ZK-STARK协议主要可以分为两部分内容：

1. 算术化：将程序的执行过程转化为一个算术问题，这个算术问题被称为RPT (Reed-Solomon Proximity Testing)
2. FRI协议：即针对RPT问题设计的零知识证明协议

本文主要目的是概述FRI的原理。算术化的部分将在另一篇文中介绍。

Reed-Solomon编码

所谓的Reed Solomon编码，下文称RS码，就是利用多项式冗余进行出错校验的编码。这里的多项式都是系数在中的多项式。

设编码大小为。给定一个集合。待编码的内容为个中的元素，编码过程如下进行：设多项式，编码结果为，即多项式在集合指定的这个点上的取值，简洁起见，将这个编码记为。

我们知道，给定个不同点上的取值，可以唯一确定一个次的多项式。因此，当时，从编码可以唯一确定被编码的数据，这个过程被称为多项式的插值。

对于两个不同的次多项式，在这个点中，最多有个点上的取值相等，所以两个不同的编码，至少有个位置不同。因此，这样的编码可以容纳个随机的错误。显然，如果，这个编码毫无容错性，这个编码就成了从向量空间到它自身的一一映射。

一个RS码记为，其中，表示多项式的次数不超过。实际上，表示了如下集合：

RPT问题

简单来说，RPT (RS Proximity Testing)问题是给定一个长度为的编码，判断它是否属于，即判断一个编码是否是一个合法的RS编码。

最简单直接的方法是对给定的编码进行解码，即多项式插值，恢复出多项式的各项系数。如果的次数不大于，则输出，否则输出。实际上，作为一个纠错码，RS码最初设计来就是这么用的。

RPT是否存在更高效的解法？例如，能否不读取完整的编码，即完整的，只读取其中一小部分(级别)，就能够以大概率作出准确的判断？

乍一看，上述目标似乎是不可能的。毕竟，对一个合法的编码，只需要改动其中任何一位，就立刻得到一个非法的编码。如果一个验证算法只读取的一小部分，它就有大概率错过那被改变的一位，得到的输入和没有任何区别。

RPT问题还有另外一个限制条件：它的输入要么是一个合法的编码，要么和所有合法的编码都有至少个位置不同。这就是它的名称中Proximity这个词的意思。

但是，即使加上了上述限制条件，效率依然不能提高多少。无论有多大，验证算法至少需要验证个点。实际上，如果只能读取编码上不到个位置，再强大的算法也不可能判断出这个编码是否合法，这些信息实在太少，甚至还不足以唯一确定一个次以内的多项式，更不要说识别出一个更高次数的多项式了。

我们退而求其次：除了编码本身，还可以允许验证算法和一个Prover进行交互。这就引入了交互式证明模型。

IOP

IOP (Interactive Oracle Proofs)是一个交互式证明模型。在一个交互式证明模型中，两个算法Prover和Verifier进行交互，Prover的目标是向Verifier证明一个实例属于语言。例如，对于RPT问题而言，实例就是一个RS码，而语言就是。

IOP是在两个更早的交互式证明模型IP和PCP的基础上发展而来的。

• IP (Interactive Proofs)：最早提出的交互式证明模型。在这个模型中，Prover和Verifier进行多轮交互，交互结束后，Verifier输出0或者1
• PCP (Probabilistic Checkable Proofs)：在这个模型中，Prover和Verifier只进行一次交互，这一次交互中，Prover向Verifier发送一个字符串，叫做PCP。和IP的主要区别是，Verifier不需要读取完整的PCP字符串，而是可以对其进行随机访问。Verifier计算结束后，输出0或者1

IOP其实就是IP和PCP的结合：它像IP一样允许多轮交互，而每一轮交互都是一个PCP模型，即Verifier可以随机访问Prover发来的字符串，而不需要读取整个字符串。多轮交互结束后，Verifier输出0或者1。

IOP的一个变种叫做IOPP，这个多出来的P就是Proximity。在上一节介绍RPT时讲过，Proximity的意思是要么是合法的，要么和中的任何一个元素都相差至少距离。

至此，我们把FRI的全称Fast Reed-Solomon IOPP涉及的每个概念都介绍完毕。

FRI是为RPT问题构造的一个IOPP，由Prover和Verifier双方交互执行。协议开始时，Verifier已经获知了完整的编码，但还没有读取这个编码，它可以在协议执行过程中随时查询编码的任意部分。Prover知道多项式，其次数不大于。协议执行过程中，Prover和Verifier进行多次交互，每次交互中，Prover会向Verifier发送一个字符串，Verifier可以随机读取这个字符串的任意比特，而并不需要读取整个字符串。交互结束后，Verifier确信是次数不大于的，输出1；或者Verifier判断Prover是一个恶意攻击者，输出0。

密码学承诺

在介绍FRI的设计思想之前，首先澄清一个问题：什么叫做Verifier已经获知了，但还没有读取它，只是可以随时读取它的任意部分？你可能想象为，存储在Verifier的内存里。不过，这样的前提假设带来几个问题：

1. 我们希望FRI具有零知识性，也就是说，Prover希望在协议结束的时候，除了Verifier查询的那少量几个位置，以及这个多项式的次数确实低于这一事实外，对这个多项式一无所知。显然，如果整个编码都在Verifier的内存中，零知识性一开始就不存在了；
2. 如果Prover和Verifier的内存中都存着完整的，那么在此之前，它们必然需要为此通信，通信量至少为编码长度，而FRI协议的初衷就是为了减少Verifier的计算量，光是通信代价就达到了级别，这显然是说不过去的。

实际上，应当这样理解这个模型：假设存在一个可信的第三方，设这个可信第三方为。在协议的最开始，Prover将整个编码发送给。在协议进行过程中，Verifier可以随时向查询这个编码的任意部分。作为可信第三方，一定据实作答。

如果真的要依赖一个可信第三方才能执行，FRI协议就没有什么意义了。实际上，我们要用一个密码学方案来模拟这个第三方，这个方案就叫做承诺(commitment)。最简单的承诺可以用哈希函数来实现。FRI中，我们需要支持承诺内容的部分查询，这就需要用到一个叫做Merkle-Tree的结构。这里不做详细的介绍。接下来，如果说到Prover“承诺”了某些数据，就想象为Prover把数据发送给可信第三方，同时要记得，使用密码学承诺，Prover和Verifier只需要进行常数量级的通信即可。

FRI思想概述

我们重新描述一下FRI需要解决的问题：Prover宣称多项式在集合上的取值属于Reed-Solomon码。注意我们用代替了，是一个乘法群，设其大小为。这里用上标号是为了表示这是递归的第一步，目前可以先忽略。是一个二元域，即大小为2的幂的有限域。

协议开始前，Prover已经对整个编码，即进行过承诺，Verifier可以随时要求Prover提供在中的某个点上的取值，Prover不能撒谎。

初始方案：Verifier逐点查询的值，它至少要查询个点才能有把握做出判断，即用多项式插值。这个方法的通信复杂度为。称这个原始方法为暴力查询方法。

下一步，对进行如下拆分：中的偶数次项放到一起，看作是关于的多项式，记为，奇数次项放在一起，提取公因子后也可以看做是关于的多项式。

其中和这两个多项式的次数都在以内，定义域为，其中是对中的每个元素做平方得到的。因为，的元素个数刚好是的个数减半，即。

例如：

• 偶数次项为，于是；
• 奇数次项为，于是。

接下来，定义二元多项式。其中，，即这个多项式的定义域为。根据定义，，即时，。

如下图所示，绿色部分为的定义域，图中红色的线为线。因为为离散的有限域而非实数域，这条线的实际形状并非如此，只是为了辅助理解，画成实数上的抛物线形状。

因为当时，，所以在图中红色抛物线上，的值和的值相等。

另外，固定时，相对于变量是一个线性函数，所以在上图中任意值处画一条横线，在这条横线上是线性函数。

同样的，固定时，关于是一个低于次的一元多项式。所以在图中任意值处画一条竖线，这条竖线就代表一个低于次的多项式。

接下来，Verifier在中均匀随机选取，令。也就是说，将的第一个变量固定到处，得到一个一元多项式，记为。如下图中紫色的竖线所示。根据上一段，的次数低于。

至此，完成了第一步递归，从得到了。

有了以上这些定义，Prover和Verifier执行以下协议：

第一步：Verifier随机选取一个发送给Prover，然后Prover计算，并承诺。

第二步：Verifier随机选取，求出的两个根和。然后，Verifier向Prover查询在和处的值，记为和，以及在处的值，记为。如下图所示：

Verifier验证这三点是共线的。上文提到，在每条横线上是线性的。

这一步验证过程进行多次，以保证对于大多数的，都是线性的。

第三步：Verifier验证

要得出上述方案的正确性，需要证明，如果以下两点同时成立，即可推出：

1. 对大部分值，上述第二步验证都可以通过；
2. 第三步能够验证通过，即

证明过程这里就不赘述了，有兴趣的参考论文[1]。

注意第一点只要求“大部分”，因为验证过程是对值进行抽样调查。抽样调查有以下两个特性：

• 如果抽到的全部样本都合格，可以大概率相信总体中绝大部分样本是合格的；
• 但不能证明全部样本是合格的。

假如一万个样本中只有一个不合格，抽查其中一百个，只有百分之一的概率能把那个不合格的样本抽到。所以，即使一百个样本全部合格，也不能确信全部样本是合格的，但是大概率可以相信百分之九十九的样本都是合格的。

所以，对编码的Proximity要求在这里起了关键作用，即要么属于，要么和这个集合中所有多项式的距离都大于。从这一点可以推出，上述第二步验证中，不合格的值要么一个也没有(即合法的情况)，要么就有相当大的比例(即不合法的情况)，使得第二步可以使用抽样调查进行。

为了验证第二点，即次数已经打了对折的，Verifier可以选择暴力查询，它的验证复杂度已经减少了一半。Verifier也可以选择对递归使用上面的方法，直到递归了次之后，的大小是一个给定的常数，此时对进行暴力查询也只需要常数时间。

综上所述，整个递归协议中，Verifier需要发送给Prover，然后Prover承诺这个多项式。Verifier通过暴力查询验证的次数在以内。对于每一对，，Verifier执行上面提到的第二步验证，即随机挑选若干值，求解为的根，验证以下三点共线：

上述验证中，暴力查询验证所需的通信和计算复杂度为常数，每一对多项式随机挑选的值数量也是常数，每次验证三点共线所需的通信和计算量也是常数。因此，整个递归算法的通信复杂度是级别的。

小结

FRI是ZK-STARK的核心协议。它是针对Reed-Solomon编码上的RPT问题设计的零知识证明协议，实质上是给定多项式在个点上的取值，验证多项式的次数低于。FRI在每一次递归中，将RPT问题的次数降低一半，并通过次数的递归，将原问题转化为常数次数，最终得到一个Verifier复杂度为的证明协议。

FRI距离通用的零知识证明协议ZK-STARK还有一段距离，即“算术化”，也就是将任意的程序执行过程转化为RPT问题。算术化的方法将在另一篇文中介绍。

参考资料

[1] FRI论文：Eli Ben-Sasson, etc. Fast Reed-Solomon Interactive Oracle Proofs of Proximity. 2017