my’blog

技术入门 | 深入理解零知识表明算法之Zk

序言 终于到了“理解零知识表明算法值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制定之前,吾们先望一个浅易的场景。 在有限域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所示:

FRI制定分为两个阶段:Commit阶段和Query阶段。以前面浅易的场景能够望出,一次浅易的循环,必要 验证者发送随机数x0 后表明者生成新函数f1, 进走相反性校验。 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 定义fr 第2步的输出 插值出P(x) d是众项式P(x)的度 保存d+1个众项式P(x)的系数 a0~ad Commit 阶段终止 4 i < r 定义f(i+1) 遵命第2步的计算手段 保存f(i+1)的值,在群L(i+1) 进入下一步循环 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所示:

由以上流程能够望出: 针对每一轮的相反性的校验,确保了原起众项式f0实在已足d < ρ*2^n 上述制定重复l次,能够大大降矮作凶者成功的概率 总结 以上就是FRI制定的详细过程,能够望出,验证复杂度已足对数有关r = Log2(ρ*2^n)。算法保证了,当且仅当原起众项式f0是幼于ρ*2^n时,一切的round consistency 校验才会议决。真实的实现能够略有不同,详细的能够参考DEEP-FRI论文,相对于FRI,DEEP-FRI在保持表明和验证的最优复杂度的同时,挑高了体系的郑重性。

结相符本系列的前三篇的文章,总结ZK-STARK的算法如下: 算法分为两片面:算术化和LDT 算术化把题目转换位众项式很是以及众项式的LDT题目 LDT阶段行使FRI制定,保证线性级的表明复杂度和对数级的验证复杂度 零知识属性保证验证者不克访问轨迹众项式里的点,轨迹众项式里保存着隐私值 同时为了保证零知识属性,必要对轨迹众项式附添数走随机值,由验证者和表明者商议确定 整个过程,不必要第三方的CRS 整个过程,不倚赖任何数学难题 附录 官方FRI的浅易介绍 https://medium.com/starkware/low-degree-testing-f7614f5172db FRI paper https://eccc.weizmann.ac.il/report/2017/134/ DEEP-FRI paper chrome-extension://cdonnmffkdaoajfknoeeecmchibpmkmg/assets/pdf/web/viewer.html?file=https://arxiv.org/pdf/1903.12243.pdf Reed-Solomen WIKI https://en.wikipedia.org/wiki/Reed–Solomon_error_correction

 


posted @ 20-09-10 10:26  作者:admin  阅读量: