深入了解zk-SNARKs_链圈子

这篇文章主要是更深入介绍zk-SNARKs，不可避免的会有”一些“数学出现，不过会尽量着重在数学式背后的意义，而不是深入探讨数学公式。

一开始的假设
1. Alice有一个多项式P(x) 
2. Bob选一个点s给Alice 
3. Alice回传P(s)给Bob

希望能达到
1. Alice不知道点s，Bob不知道多项式P(x)。(Blindness) 
2.但Alice可传回P(s)给Bob，并且Bob可以验证P(s)。(verifiable) 
也就是双方都不知道对方的资讯，却可以共同得到一个可被验证的结果

上面就是基本的假设。然后，定义一些基本的数学式
上述所提的多项式定义为：
P(x) = C_0+C_1x+C_2x² + … + C_nx^n

首先，先介绍Homomorphic Hiding( 同态隐藏 ) ，借由同态隐藏可以达到隐藏资讯的目的。我们从数学定义来看他有什么特质。首先E(x)的定义为E(x) = g^x ，然后E(x+y) = E(x)*E(y)

HH支持线性相加，所以下列式子成立
E(ax+by) = g^{ax+by} = g^{ax}*g^{by} =E(x)^a + E(y)^ b（＊）
* HH的假设：知道E(x)，是无法回推x的值

若我们对P(x)作同态隐藏，可以得出
E(P(x)) = E( C_0+C_1x+C_2x² + … + C_d^d) = E(1)^{C_0} * E(s )^{C_1}*E(s²)^{C_2}…E(s^d)^{C_d}

也就是Bob只需要给E(1), E(s), E(s²),…E(s^d)，而不用给s（E(s)无法反推出s），Alice就可以得出E (P(s))的值。借此可以达成第一点的blindness，接下来就是要如何达成verifiable，因为Alice有可能给一个假的值，非P(x)上的点，所以要确保Alice会乖乖地照规矩来。接下来就要介绍如何保证Alice会送出正确的结果，并且Bob可以验证。

Computation → Arithmetic Circuit → R1CS → QAP → zk-SNARK

接着我们回到SNARKs基本的计算

SNARKs无法处理所有的问题，只能处理符合某种特定”形式/格式”的问题，SNARKs才能解决，而那特定的”形式/格式”就称为QAP（quadratic arithmetic program）。

首先，要先把问题用Arithmetic Circuit跟R1CS做简化。简单来说就是把复杂的数学式子简化成基本的+-*/，例如：我们要求(c1⋅c2)⋅(c1+c3)=7，把式子拆解成许多单一运算的结合。如下：

// Arithmetic Circuit 
S1 = C1 * C2 
S2 = C1 + C3 
S3 = S1 * S2

接着我们定义一组向量(a, b, c)，使得s . a * s . b — s . c = 0。其中s代表[1, C1, C2, C3, S1, S2, S3]，所以可以得到阵列

// R1SC 
// S1 = C1 * C2 
a=[0,1,0,0,0,0,0] 
b=[0,0,1,0,0,0,0] 
c=[0,0 ,0,0,1,0,0]// S2 = C1 + C3 
a=[1,0,0,0,0,0,0] 
b=[0,1,0,1,0,0,0] 
c=[0,0,0, 0,0,1,0]// S3 = S1 * S2 
a=[0,0,0,0,1,0,0] 
b=[0,0,0,0,0,1,0] 
c=[0,0,0, 0,0,0,1]

接着就是重点！

再来要将上面的向量组转成多项式，而这个转换的过程就叫做QAP。QAP利用Lagrange interpolation，将a, b, c三组向量转换成多项式A'(x), B'(x), C'(x) ，所以原本的式子变成P(x) = s.A' (x)*s.B'(x)-s.C'(x) 。接着，我们定义P(t)=0当t = 1, 2, 3…，而P(t)=0相当于P(t)可以被(xt)整除，因此，存在着H(x)，可以满足

P(x) = A(x)*B(x) — C(x) = H(x)*Z(x) , 
Z(x) = (x-1)(x-2)… 
(这里为了简化式子，s.A'(x) = A(x), s.B'(x)=B(x), s.C'(x)=C(x))

到这里先暂停一下，让大脑喘息一下。这一小段的重点在于QAP的多项式，所以在Arithmetic Circuit跟R1CS没有多著墨。这个多项式这SNARKs是核心的一个概念，之后的验证也是基于这个多项式，所以如果看没有很懂，就记住P(x) = A(x)*B(x) — C(x) = H( x)*Z(x)这个重要的方程式就好ＸＤ。

ＫＣＡ（Knowledge of Coefficient Test and Assumption）

回到原本的问题，”Alice回传P(s)给Bob验证“，原本Bob在不知道P(x)的状况下，无法验证P(s)，但是藉由QAP把问题转化后，Alice回传P(s)跟H(s)，Bob藉由验证P(s) ?= H(s)Z(s)来验证P(s)（避免让数学式看起来太复杂，这里我们先忽略同态隐藏， P(s)应该是E(P(s))）。接下来的问题是，Alice有机会假造H'(s)使得P'(s) == H'(s)Z(s)，这就是这节的重点，要怎么逼迫Alice遵守规范。

概念上就是Bob提供不止一个点，而是提供一对有关联性的点(a, b)， b = α*a，这样的一组点就叫做α-pair。若Alice回传另一组α-pair，(a', b') 而b' = α*a'，则可以藉由这样的关系来获得P(s)。

因为α值是无法得知的（无法从b/a得知），所以要传回一组新的α-pair (a', b')最直觉的想法是将(a, b)再乘上