神奇的零知识——深入浅出zkSNARKs（一）

zkSNARKs的成功性令人印象深刻，因为你可以在不执行，甚至不知道执行的具体内容是什么的情况下确定某个计算的结果是否正确 -- 而你唯一知道的信息就是它正确的完成了。不幸的是，zkSNARKs的大多数解释在某些时候都只是表面的，而且他们往往会留下一些“神奇的”东西，这表明只有最聪明的人才能理解他们的工作方式和原因。现实情况是，zkSNARKs可以简化为四种简单的技术，这篇博文旨在解释它们。任何能够理解RSA密码系统如何工作的人，也应该对当前使用的zkSNARKs有很好的理解。让我们拭目以待！

作为一个非常简短的总结，当前使用的zkSNARKs有4个主要成分（不用担心，我们将在后面的章节中解释所有术语）：

A）编码为多项式问题

将需要检查的程序被编译成多项式的二次方程：t（x）h（x）= w（x）v（x），其中当且仅当程序被正确计算时，等式成立。证明者想要说服验证者这个等式成立。

B）简单随机抽样

验证者会选择一个私密评估点 s 来将多项式乘法和验证多项式函数相等的问题简化成简单乘法和验证等式 t(s)h(s) = w(s)v(s) 的问题。

这极大地减少了证明大小和验证时间。

C）同态编码/加密

使用具有一些同态属性的编码/加密函数E（但不是完全同态的，这是不可行的）。这允许证明者在不知道s的情况下计算E（t（s）），E（h（s）），E（w（s）），E（v（s）），她只知道E（s）和一些其他有用的加密值。

D）零知识

证明者通过乘以一个数字来置换值E（t（s）），E（h（s）），E（w（s）），E（v（s）），以便验证者再不知道实际的编码值仍然可以检查它们的正确性结构。

有一个粗糙的想法是这样的，因为校验 t(s)h(s) = w(s)v(s) 和校验 t(s)h(s) k = w(s)v(s) k（对于一个不等于 0 的私密的随机数 k 来说）几乎是完全一样的，而不同的地方在于如果你只接收到了 (t(s)h(s) k) 和 (w(s)v(s) k) 那么从中获取到 t(s)h(s) 或者 w(s)v(s) 的值就几乎是不可能了。

这只是表面的部分，这样你就可以理解zkSNARKs的本质，现在我们深入了解细节。

RSA和零知识证明

让我们首先快速回想一下RSA如何工作，省略一些琐碎的细节。请记住，我们经常使用一个数字对一些数字取模，而并不是所有的整数。这里的等式“a +b≡c（mod n）”，等价于“（a + b）％n = c％n”。注意，“（mod n）”部分不适用于右侧“c”，但实际上适用于“≡”和所有其他“≡”上面。这使得它很难阅读，但我保证会谨慎使用它。现在回到RSA：

证明者提出以下数字：

p，q：两个随机的私密素数n := p qd：1 < d < n – 1 的随机数e：d e ≡ 1 (mod (p-1)(q-1))

公钥是 (e, n)，私钥是 d。素数 p 和 q 可以丢弃，但是不能暴露。

消息m通过下面公式加密

E（m）：= m ^e ％n

并且c = E（m）通过解密

D（c）：= c ^d ％n。

因为c ^d ≡（m ^e ％N） ^d ≡m ^ed （mod n），m的指数就是对（P-1）（Q-1）这组数取模，我们得到m ^ed ≡m（mod n）。此外，RSA的安全性依赖于这样的假设：n不能轻易被因式分解，因此d不能从e计算（如果我们知道p和q，这将是容易的）。

RSA 的一个牛逼的特性是同态乘法。通常来讲，如果你可以交换两个操作的顺序而不影响计算结果，那么我们就说这两个操作是同态的。在同态加密中，这就是你可以对加密数据进行计算的一个属性。完全同态加密是存在的，但是现在还没有应用到实际中，它能够对任何基于加密数据的程序完成计算。在这里对于 RSA 来说，我们只讨论组乘法。更正式地：E（x）E（y）≡x ^e y ^e ≡（xy） ^e ≡E（xy）（mod n），文字描述就是：两个加密消息的的乘积等于两个信息乘机的加密。

这种同态性已经允许某种零知识的乘法证明：证明者知道一些秘密数字x和y并计算它们的乘积，但只发送加密版本a = E（x），b = E（y）和c = E（xy）到验证者。验证者现在检查（ab）％n≡c％n 是否成立，此时验证者只知道加密版的乘积以及乘积是否被正确的计算，但是她不知道两个乘数和真正的乘积。如果你用加法来替代乘法，那就是一个主要操作为添加余额的区块链方向了。

交互验证

我们已经对零知识这个概念有了一定的了解了，让我们现在关注zkSNARKs的另一个主要特征，即简洁性。正如您稍后将看到的，简洁性是zkSNARKs中更为显着的部分，因为由于某种编码允许有限形式的同态编码，零知识部分将“免费”给出。

SNARKs 是 succinct non-interactive arguments of knowledge 的缩写。一般都通用设置之所以叫做交互式协议，是因为这里有一个证明者和一个验证者，证明者想要通过交换信息的方式让验证者相信一个表达式（比如 f(x) = y）。一般来说，没有证明者可以让验证者相信一个错误的表达式（可靠性），而且对于证明者来说一定存在一个确定的策略让验证者相信任何真实的表达式（完整性）。SNARKs 各个部分的的意义如下：

简洁：与实际计算的长度相比，消息的大小很小

非交互式：没有或者只有很少很少的交互。对于 zkSNARKs 来说就是在证明者向验证者发送一条信息之后的过程。此外，SNARKs 还常常拥有叫做『公共验证者』的属性，它的意思是在没有再次交互的情况下任何人都可以验证，这对于区块链来说是至关重要的。

参数：验证者仅受到计算限制的证明者的保护。具有足够计算能力的证明器可以创建关于错误语句的证明/参数（注意，如果具有足够的计算能力，则可以破坏任何公钥加密）。这也称为“计算可靠性”，而不是“完美可靠性”。

知识：对于证明者来说在不知道一个叫做证据（witness）（比如一个哈希函数的原象或者一个确定 Merkle-tree 节点的路径）的情况下，构造出一组参数和证明是不可能的。

如果你添加了零知识的前缀，那么在交互中你就需要一个性质，即验证者除了知道表达式的正确与否之外其他一无所知。尤其是验证者不能知道 见证字符串 稍后我们会详细解释这是什么。

举个例子，让我们考虑下面的交易验证计算：当且仅当 σ ₁ 和σ ₂ 是账户默克树s（pre 和 post 状态）的根哈希，s 和 r 是发送者和接收者账户， P _S 和P _R 是默克树 的证明（当 v 从 s 的余额中转移到 r 的余额的过程中，能够证明在  中 s 的余额至少是 v 并且他们的哈希结果是  而不是 ），这些条件都成立时，f（σ _1， σ _2， s ,r,v,p _s ,p _r ,v) 成立。

如果所有输入都已知，则验证f的计算相对容易。正因为如此，我们可以将F转换成一个zkSNARK，其中只有σ 1和σ 2是公开的和（s ,r,v,p _s ,p _r ,v）是witmess-string。零知识属性现在会使得验证者能够检查证明方是否知道一些见证，它可以将根哈希从σ 1转换至σ 2，而这样的转换又不影响正常的交易，但是验证者却不知道到底是谁发送了多少钱给谁。

关于零知识的部分相对正式的定义（仍然缺乏一些细节）就是：存在一个模拟器，它可以生成一些设置字段，但是却不知道私密的 证人，它还可以和验证者交互 -- 但是外部的观察者却不能分辨出哪个与验证者进行的交互，哪个是与证明者进行的交互。

（未完待续）

来源：格密链