August 31, 2022 5:07 PM (GMT+8)· 阅读 883
https://juejin.cn/post/7137964305424580622
我正在参与掘金创作者训练营第6期，点击了解活动详情
零知识证明作为一种密码学工具/思想，在加密，区块链，隐私保护，可信计算，联邦学习等诸多重要领域都有很重要的应用，但是其思想和具体的协议又相对比较具有技巧性，这给普通开发者和爱好者的理解带来了很高挑战。目前中文世界中能看到的零知识证明介绍有些过于简单，甚至例子本身有问题，不满足零知识性；有些则过于专业，对读者的背景知识提出了很高的挑战。
所以本系列力图从基础的数学工具出发，通过严谨的推理帮助读者理解零知识证明的机制，并且能够自己推导，证明，直至构造零知识证明。本系列力求使用尽可能简单的数学工具，大多数推理基于高中的数学知识，部分涉及到大学数学代数和离散数学的部分，但这些部分也会被指出，并给予解释。如果读者依旧具有阅读困难，可以只接受结论，回过头来再看之前的证明的细节。
本系列参考了Shafi Goldwasser，Silvio Micali和Charles Rackoff的《The Knowledge Complexity of Interactive Proof Systems》，Maksym Petkus的《Why and How zk-SNARK Works: Definitive Explanation》等一些专家学者的著作，建议读者在阅读本系列之后能够去阅读这些经典论文的原文，想必会有更深的收获。
零知识证明诞生的标志是Shafi Goldwasser, Silvio Micali, 和Charles Rackoff在1985年发表在SIAM Journal on computing的《The Knowledge Complexity of Interactive Proof Systems》一文。这篇论文创造性的使用计算复杂度理论分析了一个证明需要提供多少知识，并且指出了通常定理的证明比定理本身包含了更多的知识。比如，证明方程x^2-3x+2=0存在解，那么只需要展示其中一个解即可，比如x=1，但是，我们可以看出，这比证明方程存在解本身提供了更多的知识——揭示了其中的一个解。因此，如果一个证明，除了被讨论的命题的正确性本身之外，不传达出任何其他知识，那么这个证明可以被认为是”零知识性“的。 由于这些跨时代的工作，这篇论文的三位作者都获得了计算理论最高荣誉 ”哥德尔奖“，论文的前两位作者更因其在密码学领域的杰出贡献共同获得了2012年的 图灵奖。
但是零知识证明被学术界和公众接受并不是一件一帆风顺的事情，即使《The Knowledge Complexity of Interactive Proof Systems》这篇具有跨时代意义，并且开创了一个新领域乃至产业的论文，在最初的的投稿的时候也被拒绝了六七次。理解零知识证明，尤其是直观的建立一个简单的理解是困难的，即使是发明者本身，在举例子的时候仍然非常谨慎，有兴趣的读者可以参看Goldwasser的图灵奖采访中的一个片段（youtube.com/watch?v=DfJ…). 这也是许多刚接触到零知识证明的读者会产生不适的原因。 所以与其去尝试在了解细节之前尝试建立一个宏观的直觉，反倒不如跟随数学和逻辑的指引，逐步深入。因为可能零知识证明本身就并不是一个简单的知识。
并且，很多读者在学习零知识证明，乃至各种密码学工具的过程中，最大的障碍可能不是如何实现，而是这些算法的数学基础。因此本系列从数学基础开始，一步步解决这些困难。
零知识证明的思想可以追溯到1977年由Ron Rivest （2002年图灵奖），Adi Shamir（2002年图灵奖），和Leonard Adleman（2002年图灵奖）提出了的RSA非对称加密算法，乃至1976年由Ralph C. Merkle （2010年IEEE理察·卫斯里·汉明奖章，Merkle tree发明者），Bailey Whitfield Diffie（2015年图灵奖）和Martin Edward Hellman（2015年图灵奖）提出的Diffie–Hellman密钥交换协议。这些重要的密码学算法的数学基础都有很多通用的，因此学习这部分知识也会为进一步理解密码学打下比较好的基础。不仅是这些数学基础，零知识证明本身在数学结构上也很具有启发性，匈牙利数学家数学家László Lovász和以色列计算机科学家Avi Wigderson也因相关工作，刚刚在2021年获得了数学领域举足轻重的阿贝尔奖。另外，与之相关的研究还有姚期智（2000年图灵奖）在1982年提出的”百万富翁“问题，但这个问题之后往往被用作不经意传输的样例。
零知识证明本身是一个证明，可以尝试证明任何命题，比如：
当然，命题也可以更数学化，比如：
不要担心数学化的命题如何证明实际中有意义的命题，因为我们可以比较容易的设计一套映射规则，把实际命题映射到数学命题上，比如ASCII码表就可以用数字来表示英文字母和符号，组成”有意义“的句子。总之，从数学的角度来看，这些命题之间并没有不可逾越的鸿沟（当然，仅仅是我们关注的这些命题）。
证明则是针对某一个命题。在公理的基础上，经行逻辑推导的过程。 最著名的公理-证明系统之一就是欧几里得在《几何原本》中构造的几何学。我们在中学时代应该都接触过欧几里得的平面几何的五条公理：