了解神秘的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的文章）如下

合成多项式

接着就把这四个限制条件的多项式合成为一个，这个最终的多项式就叫做合成多项式（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）的多项式，

所以最终的合成多项式，如下

其中的α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)，以此类推验证证明者传来的多项式。

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

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

非互动性

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