理解零知识证明算法Zk-stark（四）——FRI协议

安比技术社区 2020-01-10 13:40

The following article is from 币探索 Author 江小白

币探索

本文作者江小白，来自安比技术社区的小伙伴，本系列文章将对 Zk-stark 算法展开介绍。


回顾



理解零知识证明算法Zk-stark（一）：Zk-stark 与 Zk-snark

理解零知识证明算法Zk-stark（二）：Arithmetization

深入理解零知识证明算法Zk-stark（三）：Low Degree Testing


前言

终于到了“理解零知识证明算法值Zk-stark”系列的收尾。在前面的三篇文章里，我们依次介绍了zk-stark算法的整体结构（理解零知识证明算法Zk-stark（一）：Zk-stark 与 Zk-snark）、算法的第一部分：Arithmetization（理解零知识证明算法Zk-stark（二）：Arithmetization）、算法的第二部分：Low Degree Testing（深入理解零知识证明算法Zk-stark（三）：Low Degree Testing）。
相信通过这几篇的阅读，大家能对zk-stark算法轮廓有了个整体的认知；在阅读的过程中，你可能会对文章中的某些语句或者图片的正确性发出疑问（确实有些内容需要更具体的介绍和说明，否则会产生误解），欢迎163邮箱留言交流（oceanjune512）。
回顾第三篇的文章，我们已经讲到，为了确保证明者返回的满足多项式等式相等的值确实是基于有效的多项式计算得到，我们需要对多项式进行LDT测试；同时为了使验证者的复杂度达到最优，我们把原始多项式进行变换，变换后，证明者要证明的多项式仅仅是原始多项式的一半，不断重复这一过程，一直到多项式的度可以直接判断为止。这其实就是FRI协议的核心思想，下面，让我们来详细介绍FRI协议的过程。 

FRI协议

也许，我们应该先说一下FRI协议是什么？FRI，即Fast RS IOPP，全称Fast Reed-Solomen Interactive Oracle Proofs of Proximity，是一种更有效的proximiary 测试方法，测试一个点的集合大部分是在一个度小于某个值的多项式上，能达到线性级的证明复杂度和对数级的验证复杂度。
在我们正式介绍FRI协议之前，我们先看一个简单的场景。
  • 在有限域F上，存在一个乘法群L0，群的阶为2^n；
  • 这时，证明者声称码字 f0:L0-->F 是满足 RS[F,L0,ρ] 编码参数的一个码字，即f0的大部分点在一个度 d<ρ*2^n 的多项式上P(x)上，这里 ρ=2^(-R)；
因此，当 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有以下属性：
  • 群的阶为 2^(n-1);
  • 群L1的每个元素对应群L0的两个元素，即群L1的任意y，群L0都有两个x和(-x)mod F，满足 x^2 mod F = y && (-x)^2mod F = y；
因此，问题就转化为了证明f1(y)的度 d < 1/2*ρ*2^n。同时也要保证函数f1和f0的一致性，流程可分为以下几个步骤：
  • 验证者分别从群L1和群L0选取三个点y, s0, s1满足 s0!=s1 && s0^2 = s1^2 = y
  • 证明者返回f0(s0),f0(s1),f1(y)三个值
  • 验证者根据f0(s0),f0(s1)插值出一个关于x的d<2的多项式g(x)
  • 验证者验证g(s0) = f1(y)，不相等，则失败
可靠性分析：如果函数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所示：
Image
FRI协议分为两个阶段：Commit阶段和Query阶段。从前面简单的场景可以看出，一次简单的循环，需要
  1. 验证者发送随机数x0
  2. 后证明者生成新函数f1，
  3. 进行一致性校验。
FRI协议把每一循环前2步归类到Commit阶段，把第3步归类到了Query阶段。即在Commit阶段，生成所有的函数f0~fr，r为循环的次数，然后在Query阶段，统一校验。
下面，先分别介绍Commit和Query协议里各参数和各个步骤的意义，然后总结一下相关的流程。


Commit

  • Common input
    • R RS编码比率
    • i 循环次数索引，取值{0~r}
    • r 循环次数 取值 k0-R/η
    • η空间映射参数 x-->x^(2^η)
    • L0群的阶 2^k0
    • RS[F,Li,ρ] 编码参数[ 有限域，作用域，编码比率 ]
    • q0(x) = x^(2^η)（实际实现的定义，和图中不一致），L(i+1) = q0(Li)，表示群Li到群L(i+1)的2^η --> 1映射
  • Prover input
    • fi 第i次循环的函数输入
    • Li 第i次循环的群，阶位2^(n-i)
    • RSi fi对应的编码参数
  • LOOP i <= r
    1. xi 验证者发送的随机数
    2. Sy 群L(i+1)的每一个元素对应于群Li的元素的集合，f(i+1)(y) 计算f(i+1)在群L(i+1)上的所有取值
    3.  i==r
      1. 定义fr 第2步的输出
      2. 插值出P(x)
      3. d是多项式P(x)的度
      4. 保存d+1个多项式P(x)的系数 a0~ad
      5. Commit 阶段终止
    4. i < r
      1. 定义f(i+1) 按照第2步的计算方式
      2. 保存f(i+1)的值，在群L(i+1)
      3. 进入下一步循环


Query

  • verifier input
    • R /η /Li /RSi /xi /fi /P(x) 见Commit
    • l query次数
  • 重构fr
    • 获取a0~ad，重构P`(x)
    • 计算P`(x)在群Lr上的所有取值，并赋值给fr，注fr满足RSr
  • repeat l times
    • i = {0~r-1}：Si 满足s(i+1) = q0(x)的x的集合
    • i = {0~r-1}：在Si上，插值出Pi(x)
    • round consistency check i = {0~r-1}：f(i+1)(s(i+1)) = Pi(xi)
    • 都成功，则验证通过

下面，以η = 1（即，q0(x) = x^2）为例，FRI协议的两个阶段的过程如图2所示：
Image
由以上流程可以看出：
  • 针对每一轮的一致性的校验，确保了原始多项式f0的确满足d < ρ*2^n
  • 上述协议重复l次，可以大大降低作恶者成功的概率


总结

以上就是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 https://arxiv.org/pdf/1903.12243.pdf
  4. Reed-Solomen:  https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

封面图片来自 John Moeses Bauan on Unsplash

往期回顾

探索零知识证明系列（一）：初识「零知识」与「证明」

探索零知识证明系列（二）：从「模拟」理解零知识证明

探索零知识证明系列（三）：读心术：从零知识证明中提取「知识」

探索零知识证明系列（四）：亚瑟王的「随机」挑战：从交互到非交互式零知识证明

零知识证明学习资源汇总

理解零知识证明算法Bulletproofs（一）：Range Proof

理解零知识证明算法Bulletproofs（二）：Improved Range Proof

理解零知识证明算法Bulletproofs（三）：Range Proof 实现分析

理解零知识证明算法Bulletproofs（四）：Arithmetic Circuits

链上富人寻「隐私」记（一：Mixer 篇）

浅谈零知识证明之一：背景与起源

浅谈零知识证明之二：简短无交互证明（SNARK）

从零开始学习 zk-SNARK（一）——多项式的性质与证明

从零开始学习 zk-SNARK（二）——多项式的非交互式零知识证明

zkPoD:区块链，零知识证明与形式化验证，实现无中介、零信任的公平交易

PoD-Tiny——实现零信任交易的最简协议

如果量子计算时代到来，我们的比特币安全吗？

Image

长按二维码添加微信进群讨论零知识证明


info@secbit.io


安比（SECBIT）实验室


Scan to Follow