深入了解 zk-SNARKs

[Whisker17]

深入了解 zk-SNARKs

Contents：

[Whisker17]

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

[Whisker17]

我们假设 Alice 有一个多项式 P(x) ，Bob 选择一个点 s 给 Alice ，最后 Alice 回传一个 P(s) 给 Bob，在这个过程中，我们希望：

1. Alice 不知道点 s，Bob 不知道多项式 P(x)

2. Alice 可以传回 P(s) 给 Bob，并且 Bob 可以验证 P(s)

即，双方都不知道对方的知识，但是可以共同得到一个可以被验证的结果

[Whisker17]

假设多项式为

对该多项式进行同态隐藏，即：

也就是说， Bob 只需要给出 ，而不需要给出 s ，Alice 就可以得出 E(P(s)) 的值

[Whisker17]

对于一个计算：

我们简化为：

然后我们定义一组向量 (a,b,c) ，使得：

其中 s 代表 [1,C1,C2,C3,S1,S2,S3]

于是可得：

[Whisker17]

现在我们需要将上面的向量组转化为多项式，这个过程就是 QAP。

利用 Lagrange interpolation ，将 a,b,c 三组向量转为多项式

于是原本的式子就变为：

我们定义当 t=1,2,3...， P(t)=0，即：

[Whisker17]

问题是， Alice 有机会通过造假 H'(s) 使得 P'(s)==H'(s)Z(s)，所以我需要限定 Alice 遵守规则。于是引入了α-pair

回到原本的多项式

每个多项式都有一组 α-pair：

最后我们再引入同态隐藏：

同理可得其他两组

[Whisker17]

但是在加入同态隐藏之后，出现了一个问题，我们无法计算同为加密后的结果的乘积，只能计算和值，于是我们引入了配对：

于是重新定义：

[Whisker17]