10 篇塑造现代零知识证明的必读论文

来源：登链社区

零知识证明在近 40 年中取得了显著的发展，达到了前所未有的复杂性和效率水平。如今，每天都有新的论文和项目涌现，建立在丰富的思想和创新基础之上。

想知道这一切是如何开始的吗？ 在这篇文章中，我们将深入探讨零知识证明的历史，探索 10 篇帮助塑造这一领域的里程碑论文。

1 - 起源

Goldwasser, Micali, Rackoff - 交互式证明系统的知识复杂性 (1985) [^1]

我们的第一个里程碑带我们回到 1985 年那篇开创性的论文！这项工作引入了许多术语和基础概念，这些概念至今仍然是零知识证明的核心。

首先，论文定义了一个证明系统，其模型为一个涉及两个概率图灵机的双方协议：一个证明者和一个验证者。证明系统的目标是使证明者能够说服验证者某个给定输入 x 属于正式语言 L。在大多数早期工作中，证明者是计算上不受限制的，而验证者则限制在多项式时间计算。在交互结束时，验证者输出“接受”或“拒绝”。

2 - 第一个应用

Fiat, Shamir - 如何证明自己：识别和签名问题的实用解决方案 (1986) [^2]

这篇由 Fiat 和 Shamir 撰写的论文，发表于零知识证明基础工作的一年后，介绍了这些概念的第一个实际应用。他们提出了两个协议：一个识别方案，这是交互式的，另一个是签名方案，这是非交互式的。两者之间的关键区别在于，在识别方案中，第三方可以通过制作有效的记录来说服自己一个虚假的陈述。而在签名协议中，即使是一个不诚实的证明者也无法说服自己一个虚假的陈述，从而使签名不可伪造。

识别方案将二次剩余性证明系统应用为交互式协议，其中验证者发送随机挑战，证明者相应地回应。签名方案通过用对哈希函数的调用替换验证者的挑战来修改这一点。

作者的名字听起来熟悉吗？这是一个强大通用技术的首次实例，现在被广泛称为Fiat-Shamir 启发式。它使得通过用对随机预言机的查询（在实践中是加密哈希函数）替换验证者的挑战，将任何公共币交互式证明系统转换为非交互式的。

3 - 我们究竟能证明什么？

Goldreich, Micali, Wigderson - 如何在零知识中证明所有 NP 语句及密码协议设计的方法论 (1987) [^3]

这篇 1986 年的论文给出了一个显著的结果：每个 NP 中的语言都承认一个零知识证明系统。这很重要，因为这意味着我们可以在不透露额外信息的情况下证明任何可以在多项式时间内验证的陈述的真实性。作者通过提供一个图的 3-着色性的证明系统来展示这一点，该问题是确定图的节点是否可以用三种颜色着色，使得没有两个相邻的节点共享相同的颜色。此外，证明仅假设存在概率加密。

证明的直觉如下：在每一轮中，