引子

在上一篇的最后，我提到了零知识证明，这篇我们来解释下什么是零知识证明。由于零知识证明说涉及的密码学概念和工具较多，我将在后续用一个专题来详细介绍。这里会围绕这一系列的主线来主要介绍Zcash中是怎么应用zk-SNARK的。

要回答什么是零知识证明这个问题，我们先来举个例子。
大家可能听说过阿里巴巴与四十大盗的故事，这个故事也是我们当时学习零知识证明这个密码学概念的时候，便于理解的一个故事。
话说阿里巴巴知道藏有大量金银财宝的山洞的开门口令。强盗们抓住了阿里巴巴，但是他不知道阿里巴巴是不是真的知道山洞门的口令，阿里巴巴需要向强盗们证明他知道口令，但是同时他不能向强盗们泄漏口令，因为一旦泄漏了口令，阿里巴巴对于强盗们来说就没有利用价值了，他就性命不保了。那么聪明的阿里巴巴就想到了这样一个办法：他让强盗们全都退离到一定的距离之外让强盗听不到，但是强盗们能看到山洞是否打开了。这时阿里巴巴小声的练了一遍口令，山洞门开了，在远处的强盗们看到门开了。这证明了阿里巴巴知道这个秘密，但是由于离得远，强盗们没有得到口令，阿里巴巴没有性命的担忧了。这就是零知识证明在现实世界的一个很简单的应用。

非形式化定义

其实零知识证明就只包含两层意思

1. 证明人P向验证人V证明他拥有某个秘密s；
2. 但是验证人V不能从这个证明过程中得到任何关于秘密s的信息。

实际上当我们了解BTC的时候，我们已经了解了数字签名或者说ECDSA的工作原理了。实际上数字签名也是一种零知识证明体系——签名人向其他人证明他拥有与公钥相关的私钥，但是整个签名信息却没有暴露任何关于他的私钥的信息。

零知识证明系统是一种密码学协议，协议可能就需要进行信息交互。但是有一种零知识证明是不需要进行信息交互的，只需要证明人发出一条信息即可，不需要有接受人的回复。从另一方面说，证明人只需要向全网广播一条证明信息，不需要有接收者回复。这种特殊的零知识证明称为非交互式零知识证明（non-interactive ZKP，简称NIZK）。非交互的性质是加密货币需要的，因为在加密货币系统中，不能假设用户一直在线来进行交互。用户是把消息全部公布在公开网络上的区块链中。

C-SAT问题

Zcash总用到的零知识证明系统被称为zk-SNARK，它是一种高效的NIZK系统。这个系统的实现方案是基于电路可满足问题（Circuit-SAT）这个NP完全同意问题。

简单介绍下电路可满足问题，以下简称C-SAT。
实际上，我们用到的所有计算设备的底层都是0-1的电路门，通过这些电路门的不同排列组合，来构造出更非常复杂的逻辑电路（软件或者硬件），计算我们想要的计算问题。这些电路无论如何复杂，都具有部分输入线和部分输出线。电路内部可以看成是一个二元算术世界的多项式f(x_1,x_2,…x_n)，输入是布尔向量（多个布尔值），输出为布尔值（正确与否）。如果一个电路有某一组布尔向量的输入运行之后的输出结果是True，那么我们称这个电路是可满足的电路。想象一下我们高中时学习的一元二次函数是否有解的问题。电路可满足性质就是说这个电路是否有解。
给定一个电路，判断这个电路是否可以被满足这一问题实际上是个数学上困难的问题。我们称这一问题为C-SAT问题。（可能有人会问，一元二次方程是否有解的问题是很简单的呀，但是目前电路问题还没有类似一元二次方程是否有解的判定算法。）但是给定一个布尔向量，来判断这个布尔向量是不是这个电路的解却是容易的（回想一下将解带入方程来验证是很容易的）。如果这个布尔向量确实是可以满足这个电路的，称这个布尔向量是一个证据（来证明这个电路的可满足性质）。电路可满足问题的零知识证明就是利用C-SAT问题的这个性质来构造一个证明来证明这个用户拥有某个证据。

最后回忆上一节给出的简单的协议。把cm ?= COMM_r(sn)这一过程抽象成一个电路，电路的输入端是r位置，输出端是这个等式收否成立。铸币的用户掌握铸币过程中的r是一个证据。用户用这个证据r可以做出一个证明pi来证明他1确实拥有这个r。并且更具C-SAT的零知识证明的性质，没有真正r的用户无法作出一个合法的证明。