零知识证明

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

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

我们称验证者为 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 持有私钥的概率就越大。