一文解读零知识证明

本文包括以下内容：1. 什么是零知识证明？2. 为什么需要零知识证明？3. 零知识证明的应用场景。4. 零知识证明的工作原理。5. 零知识证明的分类和应用案例。6. 零知识证明的缺陷。

PART.01

什么是零知识证明

零知识证明(Zero-Knowledge Proof)，是由 S.Goldwasser、S.Micali 及 C.Rackoff 在20世纪 80 年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

举一个简单的例子，泡芙说自己是个大厨，中餐，韩餐、意大利菜都会做。我妈表示不信，因为我在家没做过一顿饭。那么这个时候我要怎么证明我会做菜呢？

我可以让老妈在厨房看着我做完一顿饭，这样就证明我确实会做。但是我不想让老妈看到我做饭的时候把厨房弄的一团乱，不然又要被唠叨，那该怎么办呢？我一个人进厨房，爸妈都在外面等着，等我做完饭收拾好了，把菜端出来。这依然可以证明我会做饭。至于我用了什么食材，放了什么调料，过程中把厨房弄得乱不乱，这都不需要，老妈只要知道我能做一顿饭，就证明我没说谎。

简单说：零知识证明在试图以最小的信息交换量在双方之间建立信任。在不透露更多信息的前提下，一方（证明者， the prover）可以向另一方（验证者，the verifier）证明一件事是对的。

PART.02

为什么需要零知识证明

保护隐私数据

流氓厂商们都想尽可能多地收集用户数据，其中一些和他们业务无关的收据也给用户要权限（真的是非常讨厌它们）。他们又把我们收集到的用户个人身份信息（PII）放在中心化的数据库中，这些数据库非常容易被攻击，一旦受到攻击，个人身份信息泄露，进而导致各种诈骗问题。

身份认证

在使用网站时，用户可以向网站证明他拥有私钥，或者知道某个只有自己才知道的答案，网站不用知道密钥，但可以通过零知识证明确认用户身份，通过去中心化存储，服务器可以向用户证明数据被妥善保存下来且不被泄露。

计算压缩与区块链扩容

在传统的区块架构中，同样的计算被重复多次，比如签名校验，交易的合法性校验，智能合约执行等一些其他的地方，因为有了计算的证明，同一个计算就不需要多次重复了，计算过程可以被零知识技术证明压缩。

零知识证明真正解决了数据的信任，实现了隐私数据的保护，也让区块链真正实现了信任机器这一构想。

PART.03

零知识证明的应用场景

零知识证明的主要应用场景有：匿名支付、身份证明、可验证计算、匿名投票。

匿名支付

加密货币交易在公链上都是公开可见的。用户通过匿名进行交易，但是也链接到真实世界的身份（例如，通过在 Twitter 或 GitHub 个人资料中包含 ETH 地址），要么就可以通过链上和链外数据分析获得用户真实世界的身份。

有专为完全匿名交易而设计的特定“隐私币”。例如Zcash 和 Monero ，他们会屏蔽交易细节，包括发送方/接收方地址、资产类型、数量和交易时间表。通过将零知识技术融入协议，以隐私为中心的区块链网络允许节点在无需访问交易数据的情况下验证交易。

零知识证明也被应用于公共区块链上的匿名交易。例如 Tornado Cash，一种去中心化的非托管服务，允许用户在以太坊上进行私人交易。Tornado Cash 使用零知识证明来混淆交易细节并保证财务隐私。

身份证明

在不暴露具体身份信息的前提下，，出具具体的身份特征证明。例如使用在线服务需要证明用户的身份和访问这些平台的权利。这通常需要提供个人信息，例如姓名、电子邮件地址、出生日期等。

零知识证明可以简化平台和用户的身份验证。使用公共输入（例如，证明用户是平台成员的数据）和私人输入（例如，用户的详细信息）生成了 ZK 证明，用户可以在需要访问时简单地出示它以验证其身份服务。例如证明用户是否成年，不用出具身份证信息，或者具体的出生年份，只出具是否满十八岁的结论。

可验证计算

当用户的设备无法支持需要的计算，或者在本地进行计算成本太高的时候，就会考虑第三方服务。这些第三方服务可以快速且廉价地向用户返回输出的结果（例如 Chainlink 的 oracle 服务）。这种场景下零知识证明允许第三方算力提供商输出计算完整性证明，确保用户收到的输出结果是正确的。

匿名投票

在不暴露具体身份的前提下，证明用户的身份并获得投票权限，完成投票。

PART.04

零知识证明的工作原理

零知识证明最早由 MIT 的 Shafi Goldwasser 和 Silvio Micali 在 1985 年一篇名为《互动式证明系统的知识复杂性》的论文中提出。作者在论文中提到，证明者（prover）有可能在不透露具体数据的情况下让验证者（verifier）相信数据的真实性。零知识证明可以是交互式的，即证明者面对每个验证者都要证明一次数据的真实性；也可以是非交互式的，即证明者创建一份证明，任何使用这份证明的人都可以进行验证。零知识证明目前有多种实现方式，如 zk-SNARKS、zk-STARKS、PLONK 以及 Bulletproofs。每种方式在证明大小、证明者时间以及验证时间上都有自己的优缺点。

零知识证明有三个基本特征，即：

完整性：如果 statement 为 true，则诚实的验证者可以相信诚实的证明者确实拥有正确的信息。

可靠性：如果 statement 为 false，则任何不诚实的证明者都无法说服诚实的验证者相信他拥有正确的信息。

零知识性：如果 statement 为 true，则验证者除了从证明者那里得知 statement 为 true 以外，什么都不知道。

总而言之，要创建零知识证明，验证者需要让证明者执行一系列操作，而证明者只有在得知底层信息的情况下才能正确执行。如果证明者乱蒙一个结果，那么验证者极有可能在验证中发现并证明他的错误。

PART.05

零知识证明的分类

零知识证明可以根据交互方式分为『交互式零知识证明』和『非交互式零知识证明』。

交互式零知识证明

证明者和验证者需要进行多次互动，验证者会不断提出问题来挑战证明者，证明者则要不断回应这些挑战，直到验证者被说服。

交互式零知识证明——色盲游戏

Alice 是色盲，Bob 不是色盲，在 Bob 手上有两个大小，形状完全一样的球，但这两个球的颜色不一样，一个球是蓝色的，另一个球是红色的，由于 Alice 是色盲，所以 Alice 无法分辨这两个球是否是一样的，Bob 需要向 Alice 证明这两个球是不一样的。在这里，Alice 被称为验证者，他需要验证 Bob 的陈述正确与否，Bob 被称为证明者，他需要证明自己的陈述（存在两个颜色不一样的球），Bob 需要在 Alice 不能获得两个球的颜色的情况下，向 Alice 证明这两个球的颜色是不一样的这个事实，这与零知识证明的定义是相符合的。

Alice 当 Bob 的面拿起两个球，左手拿蓝球，右手拿红球，然后将双手放到背后，这样 Bob 就看不到 Alice 手上的球了，Alice 在背后随机交换左右手上的球，交换完成后 Alice 将手伸出，并询问 Bob 两个球是否交换过位置，如果 Bob 能看到球上的颜色，那么每次Alice换过球的位置后，Bob 都能正确回答出 Alice 的问题。

第一次，Alice 偷偷交换了手中球的位置，然后 Alice 问 Bob 是否交换了球的位置，如果 Bob 回答 Yes，那么 Alice 有 50% 的概率相信 Bob 是可以区分这两个球的颜色，因为 Bob 有 1/2 的概率蒙对，所以 Alice 可以再进行一次测试。如果 Bob 回答 No，那么 Alice 可以肯定 Bob 不能区分两个球的颜色。

第二次，Alice 没有交换手中球的位置，然后 Alice 问 Bob 是否交换了球的位置。如果 Bob 回答 No，那么 Alice 有 75% 的概率相信 Bob 是可以区分两个球的颜色。

第一次迭代后，Alice 可以说 Bob 陈述的断言为真的概率为 50％。如果 Bob 第二次回答正确，那么 Alice 可以说 Bob 陈述为真的概率达 75％。在第三次迭代后，它将是 87.5％。如果连续n次Bob都通过了检查，则 Alice 有 1-(1/2)^n 的概率可以认为  Bob 说的是真的，这两个球的确是有红蓝两种颜色。

交互式零知识证明是一种基于概率的验证方式，验证者（verifier）基于一定的随机性向证明者（prover)提出问题，如果证明者都能给出正确回答，则说明证明者大概率拥有他所声称的“知识”。零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗的证明者有可能通过虚假的陈述骗过验证者。换句话说，零知识证明是概率证明而不是确定性证明，但是也存在技术能将误差降低到可以忽略的值。

这种交互式方法有一些局限：

每次验证都需要进行整个冗长的过程。

证明方与验证方都需要同时在场，不管是在线还是面对面。

只能够取信于一个验证者，如果要取信于多个验证者，则对每个验证者都需要进行一遍证明过程。

非交互式零知识证明

交互式零知识证明需要两方随时可用并反复交互。即使验证者确信证明者是诚实的，该证明也无法用于独立验证（计算新证明需要证明者和验证者之间的一组新消息）。

为了解决交互式零知识证明面临的问题，非交互式零知识证明应运而生。Manuel Blum、Paul Feldman 和 Silvio Micali 提出了第一个交互式零知识证明——其中证明者和验证者有一个共享密钥。这使证明者可以在不提供信息本身的情况下证明他们对某些信息的了解。

非交互式零知识证明---数独游戏

数独是源自 18 世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据 9×9 盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含 1-9，不重复。

Alice 为了向 Bob 证明她已经解决了一个数独难题，为此 Alice 创建了一个防篡改的机器。Alice 将生成好的数独答案放入机器中，机器可以向 Bob 发送证明。Alice 的机器遵循以下公开可验证的协议：首先，Alice 在机器中放入尚未被解决的原始数独题目，数独中的谜题卡片三张正面朝上。接下来，Alice 上机器将他的答案正面朝下放置在相应的单元格上，同样也是每个单元格放三张。最后 Bob 向机器获取证明，机器返回给 Bob27 个袋子：

机器将数独中每一行 9 张卡片取出，并分别混淆后放入一个袋子中，一共有9行，用掉 9 个袋子；机器将数独中每一列 9 张卡片取出，并分别混淆后放入一个袋子中，一共有 9 列，用掉 9 个袋子；机器将数独中每个粗线宫（3*3）内卡片取出，并分别混淆后放入一个袋子中，一共有 9 个，用掉 9 个袋子；

Bob 分别对这 27 个袋子进行检查，如果每个袋子中的卡片都包含数字 1 到 9，而且没有任何数字丢失或重复，那么 Bob 可以确认 Alice 的确解开了数独，并且 Bob 并没有从机器返回的证明中获取任何关于数独解的知识，因为机器返回给 Bob 袋子中的数据是被随机打乱的。

非交互式零知识证明克服了交互式零知识证明的一些缺点，不需要冗长的在线交互，可以取信于很多人（甚至所有人），证明始终有效，但是可能需要额外的机器和程序来确定实验的顺序。例如，在数独这个例子中，由程序决定要验证的列或行。验证序列必须保密，否则验证者可能会在不知道真正“知识”的情况下通过验证。

交互式零知识证明 VS 非交互式零知识证明

交互式证明的每次验证都需要进行新一轮通信，非交互式证明只需要参与者（证明者和验证者）之间进行一轮通信。证明者将秘密信息传递给特殊算法以计算零知识证明。该证明被发送给验证者，验证者使用另一种算法检查证明者是否知道秘密信息。

非交互式证明减少了证明者和验证者之间的通信，使 ZK 证明更加高效。此外，一旦生成了证明，其他任何人（可以访问共享密钥和验证算法）都可以进行验证。

PART.06

零知识证明的技术方案和应用

零知识技术可以让开发者既能利用以太坊等底层区块链的安全性，又能为 dApp 提高交易吞吐量和速度，并同时将用户个人信息放在链下，以保护用户隐私。交易将打包上传至链上，以降低终端用户的使用成本。最终，项目可以利用这些功能打造出高级的 dApp，不仅在性能上可以与 Web2 系统媲美，而且还能保持 Web3 去中心化的优势。

（图片来源：Chainlink）

在 Layer2 中 zk-rollup 会将多笔交易打包在一起，并发布到 Layer1 区块链上，同时还会发布一个验证计算有效性的零知识证明。发布到链上的证明也被称作“有效性证明”。有效性证明技术分为 SNARKs 和 STARKs 两类。

zk-SNARs

SNARK 的全称是“zero-knowledge succinct non-interactive argument on knowledge”（简洁的非交互式零知识证明）。这是一种加密证明，文件很小而且很容易验证。它利用椭圆曲线生成一个加密证明，该椭圆曲线假设无法从一个公开的基点找到随机椭圆曲线元素的离散对数。椭圆曲线的计算成本低于 STARK 的哈希函数，因此 SNARK 协议的 gas 成本更低。

案例：Zcash, Loopring, zkSync1.0,zkSync 2.0,Zigzag, Mina

zk-STARK

STARK 全称是“zero-knowledge scalable transparent argument of knowledge”（零知识的可扩展、透明知识证明）。这种加密证明几乎不需要证明者和验证者之间产生任何交互。STARKs 相比 SNARKs 的最大优势在于证明时间更短，而且更容易扩展。另外，由于 STARKs 采用哈希函数，因此也可以抗量子攻击。

值得一提的是，STARKs 的发明者是 Eli Ben-Sasson，此人是 StarkWare 的联合创始人，这个团队也开发了 StarkEx 和 StarkNet。

案例：StarkEx, StarkNet, Immutable X, Starkware

PART.07

零知识证明的缺点

高昂的硬件成本

根据证明系统的不同，零知识证明生成过程有所不同。但最终都会面临难题：大数字向量（字段或组）的乘法，特别是可变基数和固定基数的多标量乘法（MSM），或者快速傅立叶变换（FFT）和逆 FFT。

MSM 和 FFT 的运算速度都很慢。在同时存在 FFT 和 MSM 的系统中，大约 70% 的证明生成时间花在 MSM 上，30%的时间花在FFT 上。需要硬件加速才能在复杂的计算中实现。通常认为对 ZK 硬件加速最重要的技术是 FPGA 而不是 GPU（由于成本和能源效率）或 ASIC（由于它们的不灵活性和长迭代周期）。顶级 FPGA比顶级 GPU 便宜约 3 倍。而且FPGA 的能效比 GPU 高出10 倍以上，主要原因是 GPU 需要连接到主机设备，这会消耗大量电能。

验证成本

验证证明需要大量复杂的计算，这也增加了运算成本。例如，ZK-rolluos 需要支付约500，000gas 来验证以太坊上的单个 AK-SNARK 证明，ZK-STARKs 需要的费用就更高了。

信任假设

零知识证明的前提是，双方都是诚实的，都很希望知道真实答案，不会进行数据造假。在 ZK-SNARK 中，生成一次公共参数可以让参与零知识协议的各方重复使用，这就默认参与者是提供的数据是正确的。

但事实上，用户没有办法评估参与者的诚实度，即使参与者输入了假的数据，用户也必须相信。在 ZK-STARK 中没有信任假设，现在，研究人员正在为 ZK-SNARKs 进行非可信设置，来提高证明机制的安全性。

量子计算威胁

ZK-SNARK 使用了椭圆曲线数字签名算法（ECDSA）进行加密，目前看来 ECDSA 算法是安全的，但是未来量子计算机的发展很可能破解这种算法。

通常认为 ZK-STARK 不会受到量子计算的威胁，因为它使用抗碰撞哈希进行加密，与 ECDSA 的公私密钥对不同，抗碰撞哈希更难被量子计算破解。