【ZK 简明教程】（1）零知识证明的背景和数学基础

零知识证明作为一种密码学工具/思想，在加密，区块链，隐私保护，可信计算，联邦学习等诸多重要领域都有很重要的应用，但是其思想和具体的协议又相对比较具有技巧性，这给普通开发者和爱好者的理解带来了很高挑战。目前中文世界中能看到的零知识证明介绍有些过于简单，甚至例子本身有问题，不满足零知识性；有些则过于专业，对读者的背景知识提出了很高的挑战。所以本系列力图从基础的数学工具出发，通过严谨的推理帮助读者理解零知识证明的机制，并且能够自己推导，证明，直至构造零知识证明。本系列力求使用尽可能简单的数学工具，大多数推理基于高中的数学知识，部分涉及到大学数学代数和离散数学的部分，但这些部分也会被指出，并给予解释。如果读者依旧具有阅读困难，可以只接受结论，回过头来再看之前的证明的细节。本系列参考了 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 码表就可以用数字来表示英文字母和符号，组成”有意义“的句子。总之，从数学的角度来看，这些命题之间并没有不可逾越的鸿沟（当然，仅仅是我们关注的这些命题）。

证明则是针对某一个命题。在公理的基础上，经行逻辑推导的过程。最著名的公理-证明系统之一就是欧几里得在《几何原本》中构造的几何学。我们在中学时代应该都接触过欧几里得的平面几何的五条公理：

1. 从一点向另一点可以引一条直线；

2. 任意线段能无限延伸成一条直线；

3. 给定任意线段，可以以其一个端点作为圆心，该线段作为半径作一个圆；

4. 所有直角都相等；

5. 若两条直线都与第三条直线相交，并且在同一边的内角之和小于两个直角，则这两条直线在这一边必定相交。

在这几条公理的基础上，通过逻辑推理，可以证明/证否各种各样的几何定理。比如

• 平行于同一平面的两条直线平行.

零知识证明则是一种特殊的证明，其特殊体现在这种证明具有”零知识性“，也就是证明本身只会说明命题的真伪与否，而不会揭示其他任何信息。比如可以证明：

• 用户 A 的信用评分大于 10，但是不用揭示用户的信用评分或者其他个人数据；

• 证明人 P 知道一个三阶多项式，1 和 2 是这个多项式的两个根，但是证明人 P 不需要揭示这个多项式是什么，也不需要提供关于多项式的其他信息。

因此，一个零知识证明系统中至少需要包含两个角色：证明者和验证者，证明者需要提供一份证明，使得验证者确认某个特定命题的真伪，并且，证明过程不应该泄露任何其他知识。

【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/欧几里得几何