简明理解零知识证明历史、原理与发展现状

DeGate   |   17. Jul, 2021   |   126 次阅读

密码学可以说是区块链技术的基石，而其中的零知识证明更是因为深度契合区块链的技术特点，而得到了广泛的应用和关注。

本文旨在用最简单的语言和形式，向大家介绍零知识证明相关的历史、概念、原理、技术实现以及发展现状。

那么让我们开始吧。

历史和起源

密码学是一门可以追溯到 2000 多年前的古老学问，其发展历史主要可以划分为以下几个阶段：

古典密码学
这一时期的密码学主要被应用于军事领域，如何有效的传递密文，又能防止被敌人截获后破解，是其主要考量。16 世纪由法国人发明的「维吉尼亚密码」是古典密码理论发展上的一个重要里程碑，它使用一个词组作为密钥，词组中每一个字母都将确定一个替换表，「维吉尼亚密码」循环的使用每一个替换表完成明文字母到密文字母的变化。

明文：ilovebitcoin
密钥：satoshi

对于第一个字母 i，取第 i 行第 s 列，得到 A；第二个字母 l，取第 l 行第 a 列，得到 L…依次循环，最后得到密文：ALHJWIQLCHWF。可见，在不知道密钥的前提下，不借助计算机已经非常难以破解这样的密码。

近代密码学
这一阶段真正的开始源于香农在 20 世纪 40 年代末发表的一系列论文，特别是 1949 年的「Communication Theory of Secrecy Systems （保密系统通信理论）」，把已有数千年历史的密码学推向了基于信息论的科学轨道，密码学终于从艺术转向科学。

这一时期的重要突破是 DES 的出现，直至今日也只能用穷举法对其进行破解。DES 加密算法风行世界，并在金融等商业领域得到了广泛的应用。

现代密码学
1977 年，麻省理工学院的 Ron Rivest、Adi Shamir、Leonard Adleman 提出的非对称加密算法 RSA，有效的解决了密钥传送的问题，标志着密码学进入了百家争鸣的现代阶段。

1989 年，由麻省理工学院研究人员 Goldwasser、Micali 及 Rackoff 提出了「零知识证明」的概念，当时的他们一定不曾想到，若干年后出现的区块链技术彻底激活了零知识证明的应用，而零知识证明则为区块链技术提供了一种绝佳的解决方案。零知识证明的方法特点和区块链技术的系统特点达成了完美的契合。

零知识证明及 zkSNARK

零知识证明是指，在不揭晓我所知道或拥有的某样东西的前提下，向别人证明我有很大概率确实知道或拥有这样东西。

zkSNARK 则是在区块链中应用最广泛的一种零知识证明，其全称是「zero-knowledge Succinct Non-Interactive Arguments of Knowledge （简洁非交互式零知识证明）」。

光听定义，大家一定一头雾水，本节将借用一个例子，尽可能接地气的向大家介绍这两个概念。

Alice、Bob 和 Charlie 都是数独爱好者，所谓数独是这样一种游戏，玩家需要根据 9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3x3）的数字均含 1 到 9，且不重复。

有一天 Alice 设计了一道巨难的数独题目来考 Bob 和 Charlie，Bob 苦思冥想了几天也做不出，便向 Alice 抱怨这肯定是道无解的题目。Alice 不想将实际的解告诉 Bob，但是又需要证明她确实知道解，于是她设计了一种巧妙的「零知识证明」的方式。

证明（The Proof )
Alice 拿出 81 （9x9）张空白的卡片，并在每张纸上写上 1-9 中的一个数字，接着她将代表谜面的卡片数字面朝上、代表谜底的卡片数字面朝下都放在桌上，并组成了 9x9 的矩阵。

随机挑战（The Random Challenge）
接下来怎么让 Bob 确认这就是正确的解呢？很简单，由 Bob 随机选择行、列或是粗线宫中的一种进行验证，假如选择行，则将这 81 张卡片按 9 行分别放到 9 个麻布袋中，摇匀并确保卡片次序打乱。

验证（The Verify）

简洁（Succinct）
虽然数独游戏有 3 种情况需要验证（行、列、粗线宫），但每次验证时 Bob 实际只需要验证其中的一种，这有效减少了验证工作量，提供给验证者的实际是一个比原命题小的多的证明，这就是所谓的简洁。

重复（Repeat）
之后重复这个随机验证步骤，我们假设 Alice 运气很好，每次都能提前猜中 Bob 会选择哪种验证方式，并以此来模拟一个解，那么她通过 1 次验证的概率为 1/3，通过 2 次验证的概率为 1/9，通过 10 次验证概率就只有 1/59049 了。在不厌其烦的进行了 20 次验证之后，Bob 无奈的承认，Alice 是真的知道这个答案的解，因为 Alice 凭运气通过验证的概率只有 35 亿分之一！（这也是为何我们说零知识证明是在概率上成立的证明）

模拟（The Simulation）
这个时候，Charlie 也来向 Alice 抱怨这个题目的无解，Alice 和 Bob 又重复了刚才的证明，没想到却没有得到 Charlie 的认可。Charlie 提出了这个证明中的漏洞，如果 Bob 和 Alice 是一伙的，每次 Bob 都会提前告诉 Alice 他要选择的验证方式，那么 Alice 就可以很容易的在没有解的情况下模拟出一个证明来通过这些测试。

非交互式证明（Non-Interactive Proofs）
不可能让每个持有这种怀疑的人都重复一遍 Bob 进行的随机验证，于是三个小伙伴设计了一台神奇的机器，Alice 只需要提交一次卡片，这台机器就可以按照初始设置好的验证序列，自动化的对这些卡片进行重复验证。验证从交互式的，变成了非交互式的。这里我们要注意，并不是说非交互式证明就没有重复随机实验这个过程。实际上，只不过是随机点不由验证者给出，而是由一个可信的第三方在初始化阶段就给出，这样一来，证明者就可以直接给出证明，验证者只需要验证证明即可，验证者和证明者之间不再需要交互。

可信设置仪式（Trusted Setup Ceremony）
其中最有趣也最重要的环节就是验证序列的初始设置。在机器启动前，会有一排设置旋钮，通过这些旋钮可以选定每一轮的验证方式。在设置这些旋钮时，每个人依次进入放置机器的房间，选择一个旋钮并设置好，之后就用一个铁盒子彻底焊死这个旋钮，让其他人无法看见也无法改变这个旋钮的选择。为了让初始设置尽可能的可信，小伙伴们邀请了镇长、小学校长和警察局长这三位小镇上最德高望重的长者来参加设置仪式，大家都相信他们绝对不可能参与作假，因此他们称之为「可信任的初始设置仪式」。

一台数独游戏的简洁非交互式零知识证明机，诞生了！

zkSNARK 的技术实现

通过上一节我们已经弄明白了零知识证明和 zkSNARK 的基本概念和原理，这一节我们再来一窥 zkSNARK 的技术实现。可以说整个实现过程相当的繁琐晦涩，且需要一定的背景知识，因此本小节只力图讲清楚其核心思想，而不拘泥于过分复杂的数学推导。

我们从一个方程式开始，X^3 + X + 5 = 35，显然解是 3。那么现在，证明者如何向验证者证明自己知道方程的解是 3，而又不告诉验证者这个解呢？

首先，我们将方程转化为计算机语言，这很容易实现：

y = x*3
return x + y + 5

接着，我们将上面的代码拍平。所谓将代码拍平，是指让代码一次只做一件事，形如 x = y op z。

拍平后，代码变成以下语句：

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym2 + 5

然后，我们引入 R1CS 一阶约束系统（rank-1 constraint system），R1CS 是一个由三向量组（a, b, c）组成的序列，同时有一个解向量 s，s 满足 s·a * s·b - s·c = 0。

在本例中，s 的结构为（~one, x, ~out, sym_1, y, sym_2），可见其由一个特殊的 ~one、方程的解 x、方程的输出 ~out 和一系列中间变量（拍平后的语句等号左边的变量）构成，其顺序不重要，只要保证有序即可。

我们把语句变换成如下形式，来方便我们求解 abc：

x * x - sym_1 = 0
sym_1 * x - y = 0
y + x - sym_2 = 0
sym_2 + 5 - ~out = 0

我们很容易得出第一个式子对应的三个向量：

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

推导过程其实很简单，我们知道要满足 s·a * s·b - s·c = 0，那么对应第一个式子 x * x - sym_1 = 0，只需要 s·a = x、s·b = x、s·c = sym_1 即可，而 s =（~one, x, ~out, sym_1, y, sym_2），那么 a 只要在 x 的位置等于 1，其余位置等于 0，即得出（0，1，0，0，0，0）。

大家可能对上面一系列眼花缭乱的变换感到莫名其妙，我们究竟在做什么？这里要揭晓谜底了，我们对每个式子验证 s·a * s·b - s·c = 0，其本质是在验证每一步都得到了正确的计算，也即如果我们可以验证每一步都是正确的，那么最终结果也一定是正确的。

以上的每一步，看似都在舍近求远，因为 s 里本身就包含了方程的解 x，验证者只需把 x 代入就能进行验证。但从另一个角度看，通过这一系列的转换，我们构建了一种将证明和验证分离的方式。在证明过程中，证明者需要知道解并生成一系列中间结果，而验证者则只需要验证其一系列结果构成的解向量是否满足一系列约束，而不需要关心这个解到底是多少。

现在只剩一个问题留待解决，就是能否通过一种方式，让验证者看不到裸着的解 x，同时依然可以进行验证过程。答案是肯定的，借由椭圆曲线、双线性对运算和指数知识假设这一系列数学手段我们就可以做到这一点，因为其推导过程过于复杂，本文不做赘述。整个 zkSNARK 的技术实现流程参见下图，需要了解更多细节的同学可以阅读参考资料中给出的 Vitalik 的文章。

零知识证明发展现状

零知识证明协议
零知识证明目前有如下几种协议，每个协议代表一条实现零知识证明的道路，不同道路最后会产生不一样的效果。

其中，安全性最高的是 STARKs 算法，其不依赖数学难题假设，具有抗量子性，并实现了透明通用字符串；Proof size 最小的 snarks 协议是 groth16 算法；Plonk 是 SNARK 协议中的一个算法，Proof size 和安全性处于适中状态。

SNARKs 协议算法
作为区块链技术中应用最广泛的 SNARKs，已经发展出了诸多各具特点的协议算法：

Groth16：
Groth16 是目前最快、数据量最小的 zk-SNARK，被用于 Zcash 等。Groth16 的 CRS （the Common Reference String）不是通用的，其设置需要绑定到一个特定的电路。由于其速度和证明的小数据量，因此常常被新的 zk-SNARK 拿来比较性能。
Groth16 论文链接

Sonic：
Sonic 是一种早期的通用 zk-SNARK 协议，支持通用、可升级的参考字符串，论文发表于 2019 年 1 月。Sonic 的证明大小固定，但是验证成本高，理论上可以将多个证明分批验证以获得更好的性能。下面列举的许多新的 zk-SNARK 都是基于 Sonic。
Sonic 论文链接

Fractal：
Fractal 是一种允许递归的 zk-SNARK。通过对电路的预处理实现了透明设置。证明最大 250KB，这比其他构建生成的证明都要大的多。
Fractal 论文链接

Halo：
Halo 支持递归证据组织，无需可信设置，与其他新的 zk-SNARK 构建不同，Halo 的验证时间是线性的。
Halo 论文链接

SuperSonic：
Sonic 的改进版，是第一个在验证时间和证明数据量方面实用化的透明 zk-SNARK。
SuperSonic 论文链接

Marlin：
Sonic 的改进版，证明时间缩短 10 倍，验证时间缩短 4 倍。
Marlin 论文链接

Plonk：
Sonic 的改进版，证明时间缩短 5 倍。
Plonk 论文链接

当前零知识证明缺乏专用硬件，导致硬件成本偏高，租用云服务器满负荷下成本约为 0.002 元 / 笔，有空载情况下约为 0.02 元 / 笔。Vitalik 曾提出一个设想，当以太坊共识机制改为 PoS，不需要那么多挖矿硬件后，这些算力可以经改造后转向支持零知识证明，这可能有效降低零知识证明的运行成本。

如今，零知识证明已经在区块链领域大放异彩，包括第一个实现 zkSNARK 的匿名加密货币 Zcash （ZEC）、Layer2 的主要解决方案 zk Rollup 等等。

DeGate 团队也将在产品实现中大量应用零知识证明，藉由其强大特性，我们将 Orderbook 的撮合交易转到 MatchNode （Layer3）中进行，使用户可以实时的挂单、撤单和成交，且其中挂单撤单免费；之后再将订单批量结果生成证明，传回 Layer2 上进行验证，这让 DeGate 在继承以太坊安全性的同时，既可以隐藏下单关键信息又可以有效降低 Layer2 上的 Gas 费消耗。而我们的最终目标是，无论在操作体验上，还是手续费消耗上，都使 DeGate 达到媲美中心化交易所的水平。

Aviv Zohar - The Incredible Machine
Vitalik Buterin - Quadratic Arithmetic Programs: from Zero to Hero