了解神秘的ZK-STARKs_链圈子

STARK被视为新一代的SNARK,除了速度较快之外,最重要的是有以下好处1.不需要可信任的设置(trusted setup)2.抗量子攻击

但STARK 也没这么完美,STARK 的证明量(proof size)约40–50KB,太占空间,相较于SNARK 只有288 bytes,明显大上几个级距。此外,这篇论文发布约两年的时间,就密码学的领域来说,还需要时间的验证。

STARK的S除了简洁(Succinct)也代表了扩展性(Scalable),而T代表了透明性(Transparency),扩展性很好理解,透明性指的是利用了公开透明的算法,可以不需要有可信任的设置来存放秘密参数。SNARK跟STARK都是基于多项式验证的零知识技术。差别在于,如何隐藏资讯、如何简洁地验证跟如何达到非互动性。

快转一下SNARK是如何运作的。
Alice有多项式P(x)、Bob有秘密s,Alice不知道s、Bob不知道P(x)的状况下,Bob可以验证P(s)。藉由同态隐藏(Homomorphic Hindings)隐藏Bob的s → H(s),藉由QAP/Pinocchio达到了简洁地验证,然后把H(s)放到CRS(Common Reference String),解决了非互动性。

问题转换

零知识的第一步,需要先把「问题」转成可以运算的多项式去做运算。这一小节,只会说明怎么把问题转成多项式,至于如何转换的细节,不会多琢磨。

问题→ 限制条件→ 多项式

在SNRAK 跟STARK 都是藉由高维度的多项式来作验证。也就是若多项式为: x³ + 3x² + 3 = 0,多项式解容易被破解猜出,若多项式为x^2000000 + x^1999999 + … 则难度会高非常多。

第一步,先把想验证的问题,转换成多项式。
这边以Collat​​z Conjecture为例子,什么是Collat​​z Conjecture呢?(每次都用Fibonacci做为例子有点无聊XD)
1.若数字为偶数,则除以2 
2.若数字为奇数,则乘以3再加1 (3n+1)

任何正整数,经由上述两个规则,最终结果会为1 。(目前尚未被证明这个猜想一定成立,但也还未找出不成立的数字)

52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.

把每个运算过程的结果纪录起来,这个叫做执行轨迹(Execution Trace),如上述52 -> 26 -> … -> 1。接着我们把执行轨迹转换成多项式(由执行轨迹转成多项式不是这里的重点,这里不会赘述,细节可以参考StarkWare的文章)如下
了解神秘的ZK-STARKs_链圈子

合成多项式

接着就把这四个限制条件的多项式合成为一个,这个最终的多项式就叫做合成多项式(composition polynomial),而这个合成多项式就是后面要拿来验证的多项式。

就像一开始提的,SNARK跟STARK都是使用高维度多项式,接着,来介绍STARK是藉由哪些方式,达到零知识的交换、透明性(Transparency)跟可扩展性(Scalability)。

修改多项式维度

这一步是为了后面验证做准备的。在验证过程使用了一个技巧,将多项式以2的次方一直递减为常数项(D, D/2, D/4 … 1),大幅减低了验证的复杂度。因此,需要先将多项式修改为2^n维度

假设上述的每个限制多项式(不是合成多项式喔)为Cj(x),维度为Dj,D >= Dj 且D 等于2^n,为了达到D 维度,乘上一个维度(D -Dj)的多项式,
了解神秘的ZK-STARKs_链圈子

所以最终的合成多项式,如下
了解神秘的ZK-STARKs_链圈子

其中的αj、βj是由验证者(verifier)所提供,所以最终的多项式是由证明方(prover)跟验证方所共同组成。

*这小节的重点是将多项式修改成D维度,觉得多项式太烦可忽略

FRI

FRI 的全名是”Fast RS IOPP”(RS = “Reed-Solomon”, IOPP = “Interactive Oracle Proofs of Proximity”)。藉由FRI可以达到简洁地验证多项式。在介绍FRI 之前,先来讨论要怎么证明你知道多项式f(x) 为何?

RS 纠删码:

纠删码的概念是把原本的资料作延伸,使得部分资料即可以做验证与可容错。其方式是将资料组成多项式,藉由验证多项式来验证资料是否正确。举例来说,有d个点可以组成d-1 维的多项式y = f(x),藉由验证f(z1) ?= y,来确定z1是否是正确资料。

回到上面的问题,怎么证明知道多项式?最直接的方式就是直接带入点求解。藉由纠删码的方式,假设有d+1个点,根据Lagrange插值法,可以得到一个d 维的多项式h(x),如果如果两个多项式在(某个范围内)任意d 点上都相同( f(z) = h(z), z = z1, z2…zd),即可证明我知道f(x)。但是我们面对的是高维度的多项式,d 是1、2百万,这样的测试太没效率,且不可行。FRI 解决了这个问题,验证次数由百万次变成数十次。

降低复杂度

假设最终的合成多项式为f(x),藉由将原本的1元多项式改成2元多项式,以减少多项式的维度。假设f(x) = 1744 * x^{185423},加入第二变数y,使y = x^{1000},所以多项式可改写为g(x, y) = 1744*x^{423}*y ^{185}。藉由这样的方式,从本来10万的维度变成1千,藉由这种技巧大幅降低多项式的维度。在FRI 目前的实做,是将维度对半降低y = x²(f(x) = g(x, x²))。

此外,还有另一个技巧,将一个多项式拆成两个较小的多项式,把偶数次方跟奇数次方拆开,如下:

f(x)= g(x²) + xh(x²)

假如:

f(x) = a0 + a1x + a2x² + a3x³ + a4x⁴ + a5x⁵ 
g(x²) = a0 + a2x² + a4x⁴, (g(x) = a0 + a2x + a4x²)
h(x²) = a1x + a3x² + a5x⁴, (h(x) = a1 + a3x + a5x² )

藉由这两个方法,可以将高维度的多项式拆解,重复地将维度对半再对半,以此类推到常数项。而FRI 协议在流程上包含两阶段— 「提交」跟「查询」。

提交阶段:
提交阶段就如同上述过程,将多项式拆解后,由验证者提供一乱数,组成新的多项式,再继续对多项式拆解,一直重复。

f(x) = f0(x) = g0(x²) + x*h0(x²) 
==> f1(x) = g0(x) + α0*h0(x), ← α0(验证者提供)
== > f2(x) = g1(x) + α1*h1(x), ← α1(验证者提供)
==> . . .

查询阶段:
这个阶段要验证证明者所提交的多项式f0(x), f1(x), f2(x), …是否正确,这边运用一个技巧,带入任意数z及-z(这代表在选域的时候,需满足L²= {x²:x ∊ L},这边不多提)。所以可以得

f0(z) = g0(z²) + z*h0(z²) 
f0(-z) = g0(z²) -z*h0(z²)

藉由两者相加、相减,及可得g0(z²)、h0(z²),则可以计算出f1(z²),再推导出f1(x),以此类推验证证明者传来的多项式。

了解神秘的ZK-STARKs_链圈子
Interactive Oracle Proofs (IOPs)

藉由FRI(RS纠删码、IOPs),将验证次数由数百万降至20–30次(log2(d)),达到了简洁地验证。不过,我们解决了复杂度,但还有互动性!

* 与SNARK比较:SNARK在验证方面利用了QAP跟Pinocchio协定。

非互动性

藉由Micali 建构(Micali construction)这个概念来解释如何达到非互动的验证。Micali 建构包括两部分,PCPs(Probabilistically checkable proof)跟杂凑函数。PCPs 这是一个随机抽样检查的证明系统。简单来说,证明者产出一个大资料量的证明(long proof),经由随机抽样来验证这个大资料量的证明。过程大约是这样,证明者产出证明

原创文章,作者:惊蛰财经,如若转载,请注明出处:http://www.xmlm.net/bi/31947.html