详谈区块链零知识证明
交互的消息能仍体现了传统证明的精髓，而它们本身不泄漏「断言为真」之外的任何知识。本文作者列举了零知识证明的定义和那些广泛流传的错误的例子，并给出观点。
一觉醒来，忽然发现零知识证明这一小众专业和阿里巴巴的故事俨然成了大众话题。昨日发呆，在微信上写了人生的第一个科普，后来发现了一些 typos，决定在这里重写一个稍微丰满的版本。感谢一些好友的提醒和提供的例子。
构成一个传统数学定理证明的精髓有两点：
- 能够高效地、机械式（无需任何创造性）地对证明进行验证；
- 对于一个错误的断言无法找到一个能够通过验证的证明。
这两点本质上都只与验证有关：它只强调普通的时间有限的验证者能进行验证而不会被恶意的证明所欺骗。通常我们并不关心一个证明是怎么找到的，有些时候寻找一个定理的证明需要漫长的时间和极高的创造力，这也解释了为什么我们会有菲尔兹奖，沃尔夫奖 …
传统的证明是非交互的，我们可以把它写在纸上供验证者在无需证明者在场的情况下进行验证。1985 年 Goldwasser，Micali 和 Rackoff 通过给传统的数学证明引入随机性和交互，即以问答方式进行证明，由此产生的交互证明系统 , 这给后来整个计算机科学和密码学的发展带来了（远远超出概念提出者所预料的）深远的影响。
现在回过头去看，如果把目光放宽一点，你会发现交互证明已经在人类历史上出现很久了，比如法庭上控方律师对被告的诘问，可以看成是被告对自己无罪所作的的一个交互证明。
这里交互和随机性的作用体现的淋漓尽致：试想如果被告能在开庭前一天获得控方律师所有的提问，那么他很可能能够编造一个完美的故事骗过对方；如果控方律师所有的提问都是未知的，那么他能骗过对方的概率应该不大，毕竟在短时间内一个谎言接着一个谎言地编下去还能使对方信服，这对智商要求太高。
但这丝毫不影响交互证明这一概念的（在当时的）前卫性和革命性。我想强调的是，在科学上，一个好的定义本身的意义并不亚于一个好的结果的意义。 交互性证明的革命性本质上体现在下面两个方面（均是传统数学证明无法实现的）:
第一个方面是它能实现零知识性，允许你安全地向他人进行证明。交互的消息能构成一个证明（仍然体现了传统证明的精髓）而它们本身不泄漏「断言为真」之外的任何知识。
这里的「知识」可以理解为「计算能力」，证明是「零知识的」意味着整个证明过程没有增加验证者的计算能力（即验证者之前无法解决的问题在证明完成之后仍然无法解决）。这个性质保证了交互完成后验证者只知道被证明的断言为真，但他并不知道怎么转而向其他人证明这一断言，它的代价是会产生一些微小的错误。
这里一个比较精确一点的例子就是向红绿色盲来证明两个球着色不同（一个红一个 绿，见这里）：视觉正常的证明者持有的传统证明 / 证据是眼里看到的不同颜色，他先将两个球分别放在色盲的两只手中，记住左右手中的颜色；色盲将手放背后，脑子里随机决定是否在背后交易所手中的球，然后将双手握球展示给证明者并问他自己是否刚才在背后交易所了手中的球，证明者通过对比之前色盲两手中球的颜色来回答他的问题。
这一交互证明体现了上述传统证明系统的两点精髓，对于第二点 , 这里带来了 1/2 的错误概率，即对于错误的断言（即两个球颜色相同），证明者仍能以 1/2 的概率骗过验证者，不过这可以重复多次来降低这一概率。零知识在这里显而易见：色盲在交互结束后除了相信他手中球是颜色不同的之外并没有得到任何额外的知识。还有一些其他的例子，如证明两种白酒味道不同，可口可乐和百事可乐的味道不同（见 这里） , 但这两个例子一般用来说明交互的威力，而非零知识性。
GMR 通过引入模拟范式精确定义了零知识性。这一模拟范式对密码学影响深远，它为密码学从艺术到科学的转变奠定了基础。
第二个方面是它能够产生不可思议的可极端高效验证的证明，允许证明者来证明在传统证明系统下几乎无法（即使给定证明）验证的断言，比如断言 B:「断言 A 不存在 长度小于 10000 个字符（为方便，假设为 2 进制字符）的传统数学证明」。
（当然不是所有的这种类型的数学断言都需要这么长的证明，对于某些断言 A 我们容易证明它是错误的（因此不存在任何长度的证明），但注意到所有有着多项式长度证明的数学定理构成一个 NP 完全集合，上述类型的断言在某种意义上组成一个 Co-NP 的集合，在合理的假设下总会有一些这类型断言会有很长很长的传统证明。）
读者可能会对第二个方向上研究的应用价值产生怀疑。毕竟在能够大多数能想象得到的场景下我们需要证明方（在拥有传统的数学证明前提下）也能够中被高效地实现，而不是一台全能的能瞬间回答任何难题的假想机器。
然而，好奇心驱动的基础研究就是这样，无论你对它持有什么态度，你无法证明它将来没有用。上面第二个方向上的研究经历了几年的曲折和意外。Fortnow 在交互证明提出不久后给出了一个 证据 暗示交互证明可能无法证明上面提到的断言 B 类型的断言（后来的研究大大突破了他的负面结果）。
第一次对理解交互证明威力的突破性进展是 Nisan 在 1989 年的在他著名的邮件（参见 Babai 的 演讲 , 这里你可以看到 Nisan 所引发的空前惨烈的学术竞争，提到了 蔡进一 老师的结果）中宣布的，然后导致了 Shamir 的 IP=PSPACE （这个证明可以在 两页半 纸上写下），Arora 等人的–我认为是理论计算机领域继 Cook-Levin 定理之后最为深刻的–PCP 定理（对历史感兴趣的同学请参考这里）。
这方面的研究最后能够落地应用在于 Babai 和 Levin （是的，同 Cook-Levin 中的 Levin，Micali 称他为 「a force of nature」）等人实现的 「universal 交互证明系统」：对于有着极端冗长传统证明的断言我们可以通过 universal 交互证明系统让全能的 证明者协助验证者高效地 验证，当我们对那些有着比较短传统证明的断言应用同样的交互证明系统时，则我们可以让普通的能高效实现的 证明者来协助验证者以惊人的效率 来验证。
这些研究也为最近十年来兴起的一些浪潮背后的理论工具，如云 / 外包计算，区块链中的简洁非交互证明系统等。这或许是对人类好奇心的回报吧。
（注：零知识证明的定义和那些广泛流传的错误的例子）
写这个文章的一个初衷是在目前能找到的有关零知识证明的中文科普绝大部分都在使用大量误导性极强的错误的例子，其中一个典型的举例如下（来自零知识证明_百度百科，被到处使用）：
证明举例：
- A 要向 B 证明自己拥有某个房间的钥匙，假设该房间只能用钥匙打开锁，而其他任何方法都打不开。这时有 2 个方法：
- A 把钥匙出示给 B，B 用这把钥匙打开该房间的锁，从而证明 A 拥有该房间的正确的钥匙。
- B 确定该房间内有某一物体，A 用自己拥有的钥匙打开该房间的门，然后把物体拿出来出示给 B，从而证明自己确实拥有该房间的钥匙。
后面的②方法属于零知识证明。好处在于在整个证明的过程中，B 始终不能看到钥匙的样子，从而避免了钥匙的泄露。
- A 拥有 B 的公钥，A 没有见过 B，而 B 见过 A 的照片，偶然一天 2 人见面了，B 认出了 A，但 A 不能确定面前的人是否是 B，这时 B 要向 A 证明自己是 B，也有 2 个方法。
- B 把自己的私钥给 A，A 用这个私钥对某个数据加密货币，然后用 B 的公钥解密，如果正确，则证明对方确实是 B。
- A 给出一个随机值，B 用自己的私钥对其加密货币，然后把加密货币后的数据交给 A，A 用 B 的公钥解密，如果能够得到原来的随机值，则证明对方是 B。
后面的方法属于零知识证明。
这两个例子都是谬误。
严谨一点地讲，零知识性是保护证明者的安全性，它保证了对于任意的（甚至是恶意的）验证者，他在与证明者（持有断言的传统数学证明）整个交互过程中所看到的消息都能够被一个高效的机器在不知道（同一个断言的）传统数学证明情况下完整地模拟出来。
上面证明 A 拥有房间钥匙的方法显然不是零知识的，抛开定义不讲，它跟「零知识」的字面意义也不符：考虑一个「恶意的」验证者 B （零知识本身可以抵抗恶意的验证者），他不知道房间里有些什么，但他可以要求 A「请把房间里外套拿出来」，如果 A 拿出来了，B 立即知道了原来房间里还有件外套，这是 B 在证明之前所不知道的。
第二个例子中我没看懂「用公钥解密」。估计该作者想举的例子如下。B 向 A 证明自己拥有一个公钥加密货币方案（其中公钥是双方都知道的）的私钥：A 选择一个随机数，用该公钥对其加密货币得到一个密文 c，将 c 发送给 B；B 用自己的私钥解密后返回明文给 A，如果该明文与 A 之前选择的随机数一致，则 A 确认 B 确实知道该公钥对应的私钥。
这也是个错误的例子，对于初学者有着极强的误导性。考虑如下场景：D 给 B 转账一笔钱，将数目用 B 的公钥加密货币后发给 B 明文 c‘。A 无意截获了这个密文 c’，它可以与 B 进行一次交互证明：将 c’ 发送给 B, 然后 B 返回 c’ 对应的明文（即该笔钱的数目）。在这个场景中，A 得到了交互证明之前他不知道的知识，即 D 转账给 B 的数目。
（注：我上面对百度百科的第二个例子可能曲解了原意。前面也提到了我无法理解原文中「A 用 B 的公钥解密」，如果这句话理解成「A 将密文发送给 B，请求 B 用自己的私钥解密，然后返回相应密文」，则整个过程连证明都算不上：B 显然能在不知道相应私钥的情况下执行整个过程，因为它知道相应的明文（和计算密文时使用的随机数），换句话，这一过程与被证明的断言「我知道公钥对应的私钥」无关。）
文章标题：《零知识证明：一个略微严肃的科普》
来源：知乎专栏
作者：DENG
来源链接：zhuanlan.zhihu.com