zk-SNARK Pinocchio零知识证明

参考链接：https://aandds.com/blog/zkp-snark.html#56077802

参考链接：https://blog.csdn.net/studyzy/article/details/115266915

定义：证明者（prover）在不泄漏任何额外信息的前提下要让验证者（verifier）确信某些陈述（Statement）是正确的。

0x00 引入

 如果我们有两个阶为$d$的不相等多项式，它们相交的点数不会超过$d$。事实上， 我们不可能找到两条不同的曲线，它们会在某段区域内重合（它们只会相交于一些点）。

 prover如何证明自己知道某个多项式（Verifier也知道这个多项式）？

 Verifier选择$x$，代入多项式计算，并将$x$发给prover，prover也计算，并将结果发给Verifier。Verifier比较计算结果，如果相等那就说明 prover 有很大的可能也知道这个多项式。

 Schwartz-Zippel定理：对于有限域$\mathbb{F}$，有一个$n$元$d$次多项式$f\left(x_1, x_2, \cdots, x_n\right)$。对于$\mathbb{F}$的子集$S$，我们从中随机挑选$n$个$x$值给每个变量赋值，那么这个多项式等于零的概率小于等于：$\frac{d}{|S|}$。

问题1：如果一个 prover 声称他知道一个 3 阶多项式$p(x)$，其中两个根分别为$x=1;x=2$ 。那么 verifier 怎么证明 prover 没有说谎呢？

 如果 prover 想要在不揭示多项式的前提下，证明他的多项式确实有这两个根，那么他就需要去证明他的多项式$p(x)$是$t(x)=(x-1)(x-2)$和另一个多项式$h(x)$的乘积。

 协议步骤如下：

1.verifier 挑选一个随机值$r$，计算$t=t(r)$，将$r$发送给 prover；

2.prover 计算$h(x)=p(x) / t(x)$ ，并对$p(r)$和$h(r)$进行求值，将计算结果$p,h$提供给 verifier；

3.verifier 验证$p=t \cdot h$，如果这个等式成立相等，就意味着$t(x)$是$p(x)$的因式。

 上述协议的问题：prover 可能并不知道他所声称的$p(x)$，他可以先算一下$t=t(r)$，然后随便选择一个数$h$ ，由此计算出$p=t \cdot h$。因为等式是成立的，所以也能通过 verifier 的校验。

 为什么有这个问题？ prover 知道了$r$和$t(r)$。但如果 verifier 给出的这个值像放在黑盒里一样不可见的话就完美了，也就是一个人即使不破坏协议，也依然能在这些模糊的值上面完成计算。

 解决方法：同态加密（允许在密文上进行算术运算，进行算术运算时不用先解密出原文）

问题2：prover 声称他知道一个$d$阶多项式$p(x)=c_d x^d+\cdots+c_1 x^1+c_0 x^0$ ，这个多项式包含因子$t(x)$（这个多项式前面介绍过，称为目标多项式）。那么 verifier 怎么证明 prover 没有说谎呢？

 Verifier操作：

1. 取一个随机数$s$，也称为秘密值；
2. 分别计算$i$取值为$0,1,…,d$时$s^i$的加密结果，即$E\left(s^i\right)=g^{s^i}$；
3. 代入$s$计算未加密的目标多项式$t(s)$；
4. 将第 2 步计算出来的加密值$g^{s^0}, g^{s^1}, g^{s^2}, \cdots, g^{s^d}$提供给 prover。

 Prover 操作：

1. 计算多项式$h(x)=p(x) / t(x)$；
2. 使用加密值$g^{s^0}, g^{s^1}, g^{s^2}, \cdots, g^{s^d}$和 prover 所已知的$p(x)$的系数$c_0, c_1, \cdots, c_d$计算出$p(x)$的加密值，采用式子$E(p(s))=g^{p(s)}=\left(g^{s^d}\right)^{c_d} \cdots\left(g^{s^1}\right)^{c_1} \cdot\left(g^{s^0}\right)^{c_0}$即可，其结果记为$g^p$；
3. 使用和上一步相同的方法计算出$h(s)$的加密值$E(h(s))$，记为$g^h$；
4. 把上两步的结果$g^p$和$g^h$提供给 verifier。

 这个时候，上述问题1的方案的缺陷就可以得到解决。但是还是有一个问题，prover只需要给出$g^p=z_p, g^h=z_h$，满足$z_p=\left(z_h\right)^{t(s)}$即可，即我们不能确定prover给出的$g^p$和$g^h$是拿$g^{s^0}, g^{s^1}, g^{s^2}, \cdots, g^{s^d}$计算的。

 我们以一个例子说明上述问题：

 存在由一个变量和一个系数组成的一阶多项式$y=cx$，对应的$x=s$的加密值为$E(s)=g^s$。这里我们要做的就是确保 prover 是拿 $g^s$（而不是其他值）与系数$c$做同态相乘的。所以结果的形式一定是：$\left(g^s\right)^c$。

 通过限制多项式 Knowledge-of-Exponent Assumption（简称 KEA）方法可以实现上面的目标。例如，如果我们想限制对某个值只能进行指数取模运算，那么可以这样做：A选取$a$，生成$a^{\prime}=a^\alpha(\bmod n)$，将$(a, a^{\prime})$发给B，B返回$(b, b^{\prime})$。如果$(b)^\alpha=b^{\prime}(\bmod n)$成立，那么说明B对$a$和$a^{\prime}$采用了相同的指数进行运算。

https://aandds.com/blog/zkp-snark.html#56077802

To be continued…