技术入门 | 深入理解零知识证明算法之Zk-stark——FRI协议
作者头像
  • 紫色财经
  • 2019-12-04 08:54:02 5054

前言

终于到了“理解零知识证明算法值Zk-stark”系列的收尾。在前面的三篇文章里,我们依次介绍了zk-stark算法的整体结构(https://www.8btc.com/article/512859)、算法的第一部分:Arithmetization(https://www.8btc.com/article/516674)、算法的第二部分:Low Degree Testing(https://www.8btc.com/article/522057)。相信通过这几篇的阅读,大家能对zk-stark算法轮廓有了个整体的认知;在阅读的过程中,你可能会对文章中的某些语句或者图片的正确性发出疑问(确实有些内容需要更具体的介绍和说明,否则会产生误解),欢迎163邮箱留言交流(oceanjune512)。

回顾第三篇的文章,我们已经讲到,为了确保证明者返回的满足多项式等式相等的值确实是基于有效的多项式计算得到,我们需要对多项式进行LDT测试;同时为了使验证者的复杂度达到最优,我们把原始多项式进行变换,变换后,证明者要证明的多项式仅仅是原始多项式的一半,不断重复这一过程,一直到多项式的度可以直接判断为止。这其实就是FRI协议的核心思想,下面,让我们来详细介绍FRI协议的过程。

 

FRI协议

也许,我们应该先说一下FRI协议是什么?FRI,即Fast RS IOPP,全称Fast Reed-Solomen Interactive Oracle Proofs of Proximity,是一种更有效的proximiary 测试方法,测试一个点的集合大部分是在一个度小于某个值的多项式上,能达到线性级的证明复杂度和对数级的验证复杂度。在我们正式介绍FRI协议之前,我们先看一个简单的场景。 因此,当f0=P时,根据IFFT原理,存在P1、P2且deg(P1、P2) < 1/2*ρ*2^n,满足:

f0(x) = P(x) = P1(x^2) + x * P2(x^2) (1)

令Q(x, y) = P1(y) + x * P2(y),可以看出Q(x, y)关于x的度d < 2;关于y的度d < 1/2*ρ*2^n;此时,验证者随机选取一个值x0发送给证明者,然后令

f1(y) = Q(x0, y) = P1(y) + x0 * P2(y) (2)

对于f1(y),y=x^2,由于x取值范围是群1里的元素,因此x^(2^n) = 1 ==> (x^2)(2^(n-1)) = 1 ==> y(2^(n-1)) = 1。令y的作用域为群L1,则L1有以下属性:

因此,问题就转化为了证明f1(y)的度d < 1/2*ρ*2^n。同时也要保证函数f1和f0的一致性,流程可分为以下几个步骤: 可靠性分析:如果函数f1不是由函数f0转换而来,那么公式(1)的多项式P1(x^2)和P2(x^2)和公式(2)的多项式P1(y)和P2(y)互不相等。考虑到多项式的度d < 1/2*ρ*2^n,变量的取值范围为2^(n-1),那么在这个范围内随机选取一个值,多项式相等的概率为1/2*ρ*2^n / 2^(n-1) = ρ。ρ为coderates,如果ρ = 2^(-8),那么一次校验成功的概率仅仅为1/256。如果经过多次验证,那么作恶成功的概率就无线接近于0。

以上可知,对函数f1重复上述的过程,直到fr变成一个可以直接校验的度,就完成了整个测试验证过程。

下面,我们看一下FRI协议的具体内容,如图1所示:

FRI协议分为两个阶段:Commit阶段和Query阶段。从前面简单的场景可以看出,一次简单的循环,需要
  1. 验证者发送随机数x0
  2. 后证明者生成新函数f1,
  3. 进行一致性校验。
FRI协议把每一循环前2步归类到Commit阶段,把第3步归类到了Query阶段。即在Commit阶段,生成所有的函数f0~fr,r为循环的次数,然后在Query阶段,统一校验。

下面,先分别介绍Commit和Query协议里各参数和各个步骤的意义,然后总结一下相关的流程。

Commit:

Query 下面,以η = 1(即,q0(x) = x^2)为例,FRI协议的两个阶段的过程如图2所示:

由以上流程可以看出:

总结

以上就是FRI协议的具体过程,可以看出,验证复杂度满足对数关系r = Log2(ρ*2^n)。算法保证了,当且仅当原始多项式f0是小于ρ*2^n时,所有的round consistency 校验才会通过。真正的实现可能略有差别,具体的可以参考DEEP-FRI论文,相对于FRI,DEEP-FRI在保持证明和验证的最优复杂度的同时,提高了系统的可靠性。

结合本系列的前三篇的文章,总结ZK-STARK的算法如下:

  1. 算法分为两部分:算术化和LDT
  2. 算术化把问题转换位多项式相等以及多项式的LDT问题
  3. LDT阶段使用FRI协议,保证线性级的证明复杂度和对数级的验证复杂度
  4. 零知识属性保证验证者不能访问轨迹多项式里的点,轨迹多项式里保存着隐私值
  5. 同时为了保证零知识属性,需要对轨迹多项式附加数行随机值,由验证者和证明者协商确定
  6. 整个过程,不需要第三方的CRS
  7. 整个过程,不依赖任何数学难题

附录

  1. 官方FRI的简单介绍 https://medium.com/starkware/low-degree-testing-f7614f5172db
  2. FRI paper https://eccc.weizmann.ac.il/report/2017/134/
  3. DEEP-FRI paper chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https%3A%2F%2Farxiv.org%2Fpdf%2F1903.12243.pdf
  4. Reed-Solomen WIKI https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

    本文来源:紫色财经
责任编辑: : 紫色财经
声明:本文系紫色财经原创稿件,版权属紫色财经所有,未经授权不得转载,已经协议授权的媒体下载使用时须注明"稿件来源:紫色财经",违者将依法追究责任。
    分享
技术入门
    下一篇