零知识证明 zero-knowledge proofs,简写为 ZKPs,最初由 S.Goldwasser、S.Micali 及 C.Rackoff 在 1985 年的论文《互动证明系统的知识复杂性》提出,指的是证明者能够在不向验证者提供任何有用信息的情况下,使验证者相信某个论断是正确的。允许证明者 prover、验证者 verifier 证明某项提议的真实,却不必泄露除了「提议是真实的」之外的任何信息。

其实质是一种涉及两方或更多方的协议,即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息,但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明,零知识证明在密码学中非常有用,尤其在 NP 问题、身份验证、数字签名、水印检测、密钥交换等,可以有效解决许多问题。加密数字货币与区块链为零知识证明的应用提供了新的方向。

综上,零知识证明是一种特殊的交互式证明,其中证明者知道问题的答案,他需要向验证者证明「他知道答案」这一事实,但是要求验证者不能获得答案的任何信息。

童话里的零知识证明

举个最简单的阿拉伯童话《一千零一夜》里的零知识证明:阿里巴巴与四十大盗的故事其中一个片段。

阿里巴巴会芝麻开门的咒语,强盗向他拷问打开山洞石门的咒语,他不想让人听到咒语,便对强盗说:「你们离我一箭之地,用弓箭指着我,你们举起右手,我念咒语打开石门,举起左手,我念咒语关上石门,如果我做不到或逃跑,你们就用弓箭射死我。」

这个方案对阿里巴巴没损失,也能帮助他们搞清楚阿里巴巴到底是否知道咒语,于是强盗们同意。强盗举起了右手,只见阿里巴巴的嘴动了几下,石门打开了;强盗举起了左手,阿里巴巴的嘴动了几下,石门又关上了。强盗有点不信,没准这是巧合,多试几次过后,他们相信了阿里巴巴。

这即是最简单易懂的零知识证明。

零知识证明的性质

根据零知识证明的定义和有关例子,可以得出零知识证明具有以下三个性质:

  1. 完备性 completeness:如果证明方和验证方都是诚实的,并遵循证明过程的每一步,进行正确的计算,那么这个证明一定是成功的,验证方一定能够接受证明方。
  2. 合理性 soundness:没有人能够假冒证明方,使这个证明成功。
  3. 零知识性 zero-knowledge:证明过程执行完之后,验证方只获得了「证明方拥有这个知识」的信息,而没有获得关于这个知识本身的任何信息。

零知识证明及其相关的协议的优点

  1. 随着零知识证明的使用,安全性不会降级,因为该证明具有零知识性质。
  2. 高效性。该过程计算量小,双方交换的信息量少。
  3. 安全性依赖于未解决的数学难题,如离散对数、大整数因子分解、平方根等。
  4. 许多零知识证明相关的技术避免了直接使用有政府限制的加密算法,为相关产品的出口带去优势。

证明举例

A 要向 B 证明自己拥有某个房间的钥匙,假设该房间只能用钥匙打开锁,而其他任何方法都打不开。有两个方法:

  1. A 把钥匙出示给 B,B 用这把钥匙打开该房间的锁,从而证明 A 拥有该房间的正确的钥匙。

  2. B 确定该房间内有某一物体,A 用自己拥有的钥匙打开该房间的门,然后把物体拿出来出示给 B,从而证明自己确实拥有该房间的钥匙。

后面的方法 2 属于零知识证明。好处在于在整个证明的过程中,B 始终不能看到钥匙的样子,从而避免了钥匙的泄露。

A 拥有 B 的公钥,A 没有见过 B,而 B 见过 A 的照片,某天二人偶然碰面,B 认出了 A,但 A 不能确定面前的人是否是 B,这时 B 要向 A 证明自己是 B,也有两个方法:

  1. B 把自己的私钥给 A,A 用这个私钥对某个数据加密,然后用 B 的公钥解密,如果正确,则证明对方确实是 B。

  2. A 给出一个随机值,B 用自己的私钥对其加密,然后把加密后的数据交给 A,A 用 B 的公钥解密,如果能够得到原来的随机值,则证明对方是 B。

后面的方法属于零知识证明。

有一个缺口环形的长廊,出口和入口距离非常近(在目距之内),但走廊中间某处有一道只能用钥匙打开的门,A 要向 B 证明自己拥有该门的钥匙。采用零知识证明,则 B 看着 A 从入口进入走廊,然后又从出口走出走廊,这时 B 没有得到任何关于这个钥匙的信息,但是完全可以证明 A 拥有钥匙。

利用零知识证明的 Zcash

加密数字货币 Zcash 挖矿进入稳定奖励期,其市场价格基本稳定在 0.1 BTC 左右。但是,随着隐私重要性逐渐被大众认知,对其需求逐步增加,相信在未来会成为另一大主流的数字货币。其理念是在实现点对点电子现金系统的同时,实现 100% 隐秘性保护。与 Bitcoin 相比,Zcash 集成了一种机制在转账自动隐藏发送方、接收方的地址,甚至转账金额。仅限定持有浏览权限秘钥的人员查看。与隐私匿名技术混币 Dash、环签名 Monero 相比,Zcash 可达成任意等级强隐私保护。

Zcash 是分布式状态和你所拥有的资产证明的结合体,其终极匿名特性也归功于零知识证明,通过名为 zk-SNARK 的技术验证交易的真实性,利用一个公共区块链来展示交易,但会隐藏掉交易的金额,而查看密钥的所有者,即币的拥有者,可允许他人查看这个密钥相关联的信息。

Zcash 的零知识证明

Zcash 使用了 SCIPR 实验室的零知识证明库 libsnark,在此基础上做了修改。

SCIPR 实验室的 libsnark https://github.com/scipr-lab/libsnark

Zcash 修改后的 libsnark https://github.com/zcash/libsnark

零知识证明白皮书 https://eprint.iacr.org/2013/507.pdf