了解零知识证明历史

来源：登链社区

零知识、简洁、非交互式知识证明（zk-SNARKs）是一种强大的加密原语，允许一方，即证明者，说服另一方，即验证者，某个陈述是真实的，而不透露除了该陈述的有效性之外的任何其他信息。由于它们在可验证的私人计算、提供计算机程序执行正确性的证明以及帮助扩展区块链方面的应用，它们引起了广泛关注。我们认为 SNARKs 将对塑造我们的世界产生重大影响，正如我们在我们的文章^[6]中所描述的那样。SNARKs 作为不同类型的证明系统的总称，使用不同的多项式承诺方案（PCS）、算术化方案、交互式 Oracle 证明（IOP）或概率可检查证明（PCP）。然而，这些基本思想和概念可以追溯到 20 世纪 80 年代中期。在比特币和以太坊的引入后，开发工作显著加快，这证明了它们是一个令人兴奋且强大的用例，因为你可以通过使用零知识证明（通常称为此特定用例的有效性证明）来扩展它们。SNARKs 是区块链可扩展性的重要工具。正如 Ben-Sasson 所描述的，过去几年见证了加密证明的寒武纪爆发^[7] 。每个证明系统都有优点和缺点，并且在设计时考虑了某些权衡。硬件的进步、更好的算法、新的论证和小工具导致了性能的提升和新系统的诞生。其中许多系统正在生产中使用，并且我们不断推动界限。我们是否会有一个适用于所有应用的通用证明系统，还是适用于不同需求的几个系统？我们认为一个证明系统将统治所有应用的可能性不大，因为：

应用的多样性。

我们有不同的约束类型（关于内存、验证时间、证明时间）。

对鲁棒性的需求（如果一个证明系统被破解，我们仍然有其他系统）。

即使证明系统发生了很大变化，它们都具有一个重要特性：证明可以快速验证。通过具有验证证明并且可以轻松适应处理新的证明系统的层， 也解决了与更改基础层（如以太坊）相关的困难。

为了概述 SNARKs 的不同特征：

密码假设：抗碰撞哈希函数、椭圆曲线上的离散对数问题、指数知识。

透明 vs 可信设置。

证明者时间：线性 vs 超线性。

验证者时间：常数时间、对数、次线性、线性。

证明大小。

递归的便利性。

算术化方案。

一元 vs 多元多项式。

本文将探讨 SNARKs 的起源、一些基本构建模块以及不同证明系统的兴起（和衰落）。本文并不打算对证明系统进行详尽的分析。相反，我们专注于对我们当前产生影响的那些。当然，这些发展只有在这一领域的先驱们的伟大工作和思想的基础上才得以实现。

基础知识

正如我们所提到的，零知识证明并不是新鲜事物。定义、基础、重要定理甚至重要协议都是从 20 世纪 80 年代中期确立的。一些用于构建现代 SNARKs 的关键思想和协议是在 1990 年代提出的（sumcheck 协议），甚至在比特币出现之前（2007 年的 GKR）。当时采用的主要问题，主要是缺乏强大的用例（1990 年代互联网发展不如今日）以及所需的计算能力有关。

零知识证明：起源（1985/1989）

零知识证明领域在学术文献中首次出现是在 [Goldwasser, Micali and Rackoff](https://people.csail.mit.edu/silvio/Selected Scientific Papers/Proof Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf?ref=blog.lambdaclass.com "Goldwasser, Micali and Rackoff") 的论文中。有关起源的讨论，你可以参见以下视频^[8] 。该论文引入了完备性、正确性和零知识的概念，并提供了二次剩余（quadratic residuosity）和二次非剩余（quadratic non-residuosity）的构造。

Sumcheck 协议（1992）

sumcheck 协议^[9]是由 Lund, Fortnow, Karloff, and Nisan^[10] 于 1992 年提出的。它是简洁交互证明的最重要的构建模块之一。它帮助我们将多元多项式的求值之和的声明减少到在随机选择的点上的单个求值。

Goldwasser-Kalai-Rothblum（GKR）（2007）

GKR 协议^[11]是一种交互式协议，其证明者的运行时间与电路的门数成线性关系，而验证者的运行时间与电路的大小成次线性关系。在该协议中，证明者和验证者就深度为 d 的有限域上的扇形二通算术（an arithmetic circuit of fan-in-two）电路达成一致，其中层 d 对应于输入层，层 0 对应于输出层。协议从对电路输出的声明开始，将其减少为对前一层值的声明。通过递归，我们可以将其转换为对电路输入的声明，这可以轻松地进行检查。这些减少是通过 sumcheck 协议实现的。

KZG 多项式承诺方案 （2010）

KZG 多项式承诺方案 （KZG polynomial commitment scheme 简称 PCS ）Kate, Zaverucha, and Goldberg^[12]于 2010 年引入了使用双线性配对群的多项式承诺方案。该承诺由单个群元素组成，提交者可以有效地打开对多项式的任何正确评估的承诺。此外，由于批处理技术，可以对多个评估进行打开。KZG 承诺是 Pinocchio、Grotp6 和 Plonk 等几种高效 SNARKs 提供了基本构建模块。它也是 EIP-4844^[13] 的核心。有关批处理技术的直观理解，你可以参见我们关于 Mina-Ethereum 桥^[14]的文章。

使用椭圆曲线的实用 SNARKs