编者按：零知识证明技术在区块链领域应用是非常广泛的，例如存储扩容、隐私保护等，对于未来数字化世界具有非凡的应用价值。正因如此，关于零知识证明的科普介绍从不绝尔，不同的案例版本在网络上盛行，导致很多初学者无从分辨，绕了许多弯路。区块链应用
为此，我们特别刊登来自中国科学院信息工程研究所邓燚研究员的《零知识证明：一个略微严肃的科普》，对“零知识性”的本质和“交互证明”的革命性及历史演变进行了全面的诠释，建议收藏。
构成一个传统数学定理证明的精髓有两点：
(1) 能够高效地、机械式（无需任何创造性）地对证明进行验证；
(2) 对于一个错误的断言无法找到一个能够通过验证的证明。
这两点本质上都只与验证有关：它只强调普通的时间有限的验证者能进行验证而不会被恶意的证明所欺骗。通常我们并不关心一个证明是怎么找到的，有些时候寻找一个定理的证明需要漫长的时间和极高的创造力，这也解释了为什么我们会有菲尔兹奖，沃尔夫奖
传统的证明是非交互的，我们可以把它写在纸上供验证者在无需证明者在场的情况下进行验证。1985年goldwasser，micali和rackoff通过给传统的数学证明引入随机性和交互，即以问答方式进行证明，由此产生的交互证明系统，这给后来整个计算机科学和密码学的发展带来了（远远超出概念提出者所预料的）深远的影响。
一、交互证明的革命性
现在回过头去看，如果把目光放宽一点，你会发现交互证明已经在人类历史上出现很久了，比如法庭上控方律师对被告的诘问，可以看成是被告对自己无罪所作的的一个交互证明。这里交互和随机性的作用体现的淋漓尽致：
试想如果被告能在开庭前一天获得控方律师所有的提问，那么他很可能能够编造一个完美的故事骗过对方；如果控方律师所有的提问都是未知的，那么他能骗过对方的概率应该不大，毕竟在短时间内一个谎言接着一个谎言地编下去还能使对方信服，这对智商要求太高。
但这丝毫不影响交互证明这一概念的（在当时的）前卫性和革命性。我想强调的是，在科学上，一个好的定义本身的意义并不亚于一个好的结果的意义。交互性证明的革命性本质上体现在下面两个方面（均是传统数学证明无法实现的）:
第一个方面是它能实现零知识性，允许你安全地向他人进行证明。交互的消息能构成一个证明（仍然体现了传统证明的精髓）而它们本身不泄漏“断言为真”之外的任何知识。这里的“知识”可以理解为“计算能力”，证明是“零知识的”意味着整个证明过程没有增加验证者的计算能力（即验证者之前无法解决的问题在证明完成之后仍然无法解决）。这个性质保证了交互完成后验证者只知道被证明的断言为真，但他并不知道怎么转而向其他人证明这一断言，它的代价是会产生一些微小的错误。
这里一个比较精确一点的例子就是向红绿色盲来证明两个球着色不同：
视觉正常的证明者持有的传统证明证据是眼里看到的不同颜色，他先将两个球分别放在色盲的两只手中，记住左右手中的颜色；色盲将手放背后，脑子里随机决定是否在背后交换手中的球，然后将双手握球展示给证明者并问他自己是否刚才在背后交换了手中的球，证明者通过对比之前色盲两手中球的颜色来回答他的问题。
这一交互证明体现了上述传统证明系统的两点精髓，对于第二点，这里带来了12的错误概率，即对于错误的断言（即两个球颜色相同），证明者仍能以12的概率骗过验证者，不过这可以重复多次来降低这一概率。零知识在这里显而易见：色盲在交互结束后除了相信他手中球是颜色不同的之外并没有得到任何额外的知识。
还有一些其他的例子，如证明两种白酒味道不同，可口可乐和百事可乐的味道不同（见下文①），但这两个例子一般用来说明交互的威力，而非零知识性。
零知识证明一个显然的密码学应用就是身份认证。如你可以随机挑选两个素数 , 计算它们的乘积，将乘积作为你的身份公布 。需要进行身份认证时，你向验证方证明“我知道我的身份对应的两个素因子”。
在“分解整数是困难的”假设下，这构成了一个身份认证系统：验证方在证明完成后没有得到任何有关两个素因子的知识。gmr通过引入模拟范式精确定义了零知识性。这一模拟范式对密码学影响深远，它为密码学从艺术到科学的转变奠定了基础。
第二个方面是它能够产生不可思议的可极端高效验证的证明，允许证明者来证明在传统证明系统下几乎无法（即使给定证明）验证的断言，如下方案例：
断言b：“断言a不存在长度小于1000个字符（为方便，假设为2进制字符）的传统数学证明”。注意到断言b本身的传统证明有可能是所有可能的长度为 1000比特的字符串，它的长度约为1000×21000 比特，即验证者验证断言b很可能需要检查几乎所有长度为1000比特的字符串， 并且逐一否定其构成断言a的证明才能确定断言b的正确性，这显然不会“高效”，即使给定断言b的传统数学证明，你也无法在有限的一生中验证完毕。
当然不是所有的这种类型的数学断言都需要这么长的证明，对于某些断言a我们容易证明它是错误的（因此不存在任何长度的证明），但注意到所有有着多项式长度证明的数学定理构成一个np完全集合，上述类型的断言在某种意义上组成一个co-np的集合，在合理的假设下总会有一些这类型断言会有很长很长的传统证明。
然而，交互证明能够让验证者在远远远远小于1000×21000时间（机器运行步数）-比如1分钟-内高效验证断言b的正确性。一个经典的例子就是：
如何在短时间内向他人证明断言c：“这两个n顶点的图g0和g1是不同构的”。这个断言的传统数学证明会很长（你可以认为就是由几乎所有n个点到n个点上的置换映射组成，验证者逐一验证每一个置换映射都不构成这俩图的同构后确认这两图不同构。这虽然不正确, 但不影响我们的讨论。图同构目前有准多项式时间算法②），你无法在有限的时间内验证完毕。0
如果假定存在一个无所不能的超级计算机m它能在瞬间判断两个图是否同构，则你可以通过交互在m（它扮演证明者的角色）的协助下验证断言c的正确性：
你随机选择一个比特 b和一个同构映射φ并计算一个新的图h=φ（gb），将h发送给m并询问m是与g0和g1中的哪个图同构，如果m的回答刚好等于b，你就可以接受断言c。如果m足够强大，这一证明过程将在很短的时间内结束。
这个证明系统也会带来12的错误，注意到如果上述断言错误，即给定的两个图是同构的（进而上述三个图 g0，g1和h 相互同构），那么即使全能的机器也不能以超过12的概率使得验证者接受。我们可以依照上面的例子处理来降低这一风险。
二、交互证明的突破演变
读者可能会对第二个方向上研究的应用价值产生怀疑。毕竟在能够大多数能想象得到的场景下我们需要证明方（在拥有传统的数学证明前提下）也能够被高效地实现，而不是一台全能的能瞬间回答任何难题的假想机器。
然而，好奇心驱动的基础研究就是这样，无论你对它持有什么态度，你无法证明它将来没有用。
上面第二个方向上的研究经历了几年的曲折和意外。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 交互证明系统让全能的证明者协助验证者高效地验证，当我们对那些有着比较短传统证明的断言应用同样的交互证明系统时，则我们可以让普通的能高效实现的证明者来协助验证者以惊人的效率来验证。
这些研究也是最近十年来兴起的一些浪潮背后的理论工具，如云外包计算，区块链中的简洁非交互证明系统等。这些或许是对人类好奇心的回报吧。
欢迎参考如下附加文档，获取更多干货内容：
①链接地址：
wwwcsprincetoneducoursesarchivefall07cos433lec15pdf
②链接地址：
:peoplecsuchicagoedu~laciupdatehtml
③链接地址：
wwwsciencedirectcomsdfepdfdownloadeid1-s20-0020019088901998first-page-pdf
④链接地址：
wwwcsprincetoneducoursesarchivespr09cos522babaiemailpdf
⑤链接地址：
:wwwlirmmfr~ashenmathtextip1992ip-pspace-simplifiedpdf
⑥链接地址：
coursescswashingtoneducoursescse53305aupcp-historypdf
⑦链接地址：
:citeseerxistpsueduviewdocdownload;jsessionid=d09eeb939ed2251b3d7c1648a1b2c4e6?doi=1011425832&rep=rep1&type=pdf