零知识证明

零知识证明是一种验证方式，让验证者在不获取任何有效信息的前提下能够对被验证者进行验证。

这种验证方式是基于概率的，验证者基于一定的随机性向被验证者提出问题，如果都能给出正确回答，则说明被验证者大概率拥有他所声称的“知识”。

我们称验证者为 verifier，被验证者为 prover，即 prover 向 verifier 证明自己拥有某项知识，但不让 verifier 知道任何有效信息。

下面是一个经典的例子:

阿里巴巴被强盗抓住，为了保命，他需要向强盗证明自己拥有打开石门的口令，同时又不能把密码告诉强盗。他想出一个解决办法，先让强盗离开自己一箭之地，距离足够远让强盗无法听到口令，足够近让阿里巴巴无法在强盗的弓箭下逃生。如果强盗举起左手，阿里巴巴就使用口令将石门打开，如果举起右手，就将石门关闭。阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。如果每次都能正确打开和关闭大门，则证实阿里巴巴确实知道石门的密码。

强盗通过石门的开关来验证阿里巴巴是否知道密码，但强盗自己不知道密码，这个过程就是零知识证明。

零知识证明系统也叫做最小泄露证明系统，是一种交互式证明系统，需要 prover 和 verifier 通过交互来完成证明过程，最终由 verifier 得出结论。

一个零知识证明系统需满足三个性质

• 正确性 prover 无法欺骗 verifier，如同阿里巴巴无法欺骗强盗，门开了就是开了、关了就是关了
• 完备性 verifier 无法欺骗 prover，在上面的例子中，强盗也无法欺骗阿里巴巴
• 零知识性 verifier 无法获取 prover 的信息

下面，举一个密码学方面的例子，P 拥有自己的公私钥，V 有一个公钥，V 想要验证 P 是不是这个公钥的私钥持有人，怎么验证呢？如下：

首先，V 生成一个随机数发给 P，P 用自己的私钥加密进行签名，然后将签名发给 V，V 通过自己持有的公钥对签名进行验证，验证通过则说明 P 拥有对应的私钥。

V 可以多发几次随机数或者将随机数的长度增长，这样，P 持有私钥的概率就越大。