零知识证明作为一种密码学工具/思想，在加密，区块链，隐私保护，可信计算，联邦学习等诸多重要领域都有很重要的应用，但是其思想和具体的协议又相对比较具有技巧性，这给普通开发者和爱好者的理解带来了很高挑战。目前中文世界中能看到的零知识证明介绍有些过于简单，甚至例子本身有问题，不满足零知识性；有些则过于专业，对读者的背景知识提出了很高的挑战。所以本系列力图从基础的数学工具出发，通过严谨的推理帮助读者理解零知识证明的机制，并且能够自己推导，证明，直至构造零知识证明。本系列力求使用尽可能简单的数学工具，大多数推理基于高中的数学知识，部分涉及到大学数学代数和离散数学的部分，但这些部分也会被指出，并给予解释。如果读者依旧具有阅读困难，可以只接受结论，回过头来再看之前的证明的细节。本系列参考了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=DfJ8W49R0rI）。这也是许多刚接触到零知识证明的读者会产生不适的原因。所以与其去尝试在了解细节之前尝试建立一个宏观的直觉，反倒不如跟随数学和逻辑的指引，逐步深入。因为可能零知识证明本身就并不是一个简单的知识。
并且，很多读者在学习零知识证明，乃至各种密码学工具的过程中，最大的障碍可能不是如何实现，而是这些算法的数学基础。因此本系列从数学基础开始，一步步解决这些困难。
零知识证明的思想可以追溯到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年提出的”百万富翁“问题，但这个问题之后往往被用作不经意传输的样例。
零知识证明=零知识+证明
零知识证明本身是一个证明，可以尝试证明任何命题，比如：
- 用户A的信用评分大于10；
- 公司C在2021年的营业额大于100万；
- 用户R有登录订票系统的权限。
当然，命题也可以更数学化，比如：
- 证明人P知道一个三阶多项式，1和2是这个多项式的两个根。
不要担心数学化的命题如何证明实际中有意义的命题，因为我们可以比较容易的设计一套映射规则，把实际命题映射到数学命题上，比如ASCII码表就可以用数字来表示英文字母和符号，组成”有意义“的句子。总之，从数学的角度来看，这些命题之间并没有不可逾越的鸿沟（当然，仅仅是我们关注的这些命题）。
证明则是针对某一个命题。在公理的基础上，经行逻辑推导的过程。最著名的公理-证明系统之一就是欧几里得在《几何原本》中构造的几何学。我们在中学时代应该都接触过欧几里得的平面几何的五条公理：
- 从一点向另一点可以引一条直线；
- 任意线段能无限延伸成一条直线；
- 给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆；
- 所有直角都相等；
- 若两条直线都与第三条直线相交，并且在同一边的内角之和小于两个直角，则这两条直线在这一边必定相交。
在这几条公理的基础上，通过逻辑推理，可以证明/证否各种各样的几何定理。比如
- 平行于同一平面的两条直线平行.
零知识证明则是一种特殊的证明，其特殊体现在这种证明具有”零知识性“，也就是证明本身只会说明命题的真伪与否，而不会揭示其他任何信息。比如可以证明：
- 用户A的信用评分大于10，但是不用揭示用户的信用评分或者其他个人数据；
- 证明人P知道一个三阶多项式，1和2是这个多项式的两个根，但是证明人P不需要揭示这个多项式是什么，也不需要提供关于多项式的其他信息。
零知识证明的系统结构
因此，一个零知识证明系统中至少需要包含两个角色：证明者和验证者，证明者需要提供一份证明，使得验证者确认某个特定命题的真伪，并且，证明过程不应该泄露任何其他知识。
在此基础上，我们可以看出零知识证明具有的三个属性：
- 完备性：如果命题是真的，那么证明者可以使验证者确信命题为真；
- 正确性：如果命题是假的，那么证明者无法使验证者确信命题为真；
- 零知识性：整个证明过程除了揭示了命题本身的真假，不能够揭示其他任何知识。
可以看出，其中性质1和2都是证明本身具有的属性，而性质3则是零知识证明的关键，也就是说，之后的所有的工作，都是在证明的基础上，通过数学方式，来避免揭示其他任何知识，保证零知识性。
【1】Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems[J]. SIAM Journal on computing, 1989, 18(1): 186-208.
【2】Petkus M. Why and How Zk-SNARK Works[J]. ArXiv, 2019.
【3】https://zh.m.wikipedia.org/zh-cn/欧几里得几何
