Loading...
系列： Zcash from First Principles 。第 5 篇文章：零知识证明 受众： 新手。我们会借助此前每一篇文章中的内容（有限域、曲线、承诺、Merkle 树），但会在需要时逐一回顾每个概念。 你将收获： 对零知识证明是什么、它提供的三个保证、任意陈述如何被证明，以及是什么支撑了 Zcash 的 Sapling 和 Orchard，形成直观且正确的理解。
这是整个系列一路铺垫至此的文章。从 第 0 篇文章 开始，我们一直在说，一笔支付是在“帷幕之后”被验证的：其正确性得到了证明，却不泄露任何信息。零知识证明就是这道帷幕。它最终解开了我们一开始提出的悖论：公众如何验证一笔自己无权看见的交易？
回想一下 Zcash 核心中的矛盾：
这两点看起来彼此冲突。验证似乎必须依靠查看。隐私则禁止查看。如果无法调和二者，就不可能拥有一种任何人都信任的隐私货币。
零知识证明（ZKP）就是这种调和。它让证明者能够让验证者相信某个陈述为真，而除了“它确实为真”这一事实之外，不泄露任何其他信息。 不泄露金额。不泄露身份。不泄露 note。只告诉你：“这里的一切都遵守规则。” 在进入具体机制之前，我们先建立直觉。
证明你知道密码，但不说出密码。 网站可以通过看你解开某个只有密码才能解开的东西，来验证你知道密码，而无需直接看到密码本身。你证明的是知道，而不是披露。
色盲朋友和两个球。 你手里有一个红球和一个绿球，但它们在你的色盲朋友眼里看起来完全一样。你想让他相信它们颜色不同，却不告诉他哪个是哪个。他把两个球藏到背后，可以选择是否交换，然后拿出其中一个给你看。你说出他是否交换过。如果球确实不同，你每次都能答对。如果球其实完全一样，那你只能猜，答对概率只有一半。经过 20 轮后，你连续全对足以让他相信两球确实不同，但他依然不知道哪个球是红的。他确信了一个事实，却没有学到其他任何信息。 这就是零知识的微缩版。
洞穴。 一个环形洞穴深处有一扇魔法门，只有知道某个秘密口令才能打开。你声称自己知道这个口令。为了在不泄露口令的情况下证明这一点：验证者在洞外等待，而你随机走入左边或右边的通道。然后验证者喊出希望你从哪一边走出来。如果你真的知道口令，你总能做到（必要时可以打开那扇门切换到另一边）。如果你在虚张声势，那么你只能靠运气从正确的一侧出来，每轮成功率是 50/50。重复 20 次后，骗子蒙混过关的概率低于百万分之一。
这个洞穴故事悄悄展示了每个零知识证明都必须具备的三个保证。
| 保证 | 在洞穴故事中 | 在 Zcash 中 |
|---|---|---|
| 完备性 | 如果你知道口令，你总能从正确的一侧出来 | 一笔有效交易总能产生被接受的证明 |
| 可靠性 | 骗子会以极高概率被识破 | 欺诈交易（伪造资金、双花）无法产生被接受的证明 |
| 零知识性 | 验证者从未听到秘密口令 | 网络永远不会得知金额、地址或是哪一个 note |
如果其中任意一个失效，系统就会崩溃：没有完备性，诚实用户会被拒绝；没有可靠性，伪造者就能凭空印钱；没有零知识性，隐私就会蒸发。
洞穴只能证明一个很巧妙的小事实。Zcash 需要证明的是一个丰富得多的陈述：“我知道树中一个尚未花费的 note，我被授权花费它，它的 nullifier 被正确计算，而且我的输入总额等于输出总额。” 我们如何从球和洞穴走到这一步？
桥梁是一个把整个系列串联起来的思想：
任何能够通过计算来检查的陈述，都可以被改写成一个算术电路： 也就是有限域上的加法和乘法网络（第 1 篇文章）。
可以把这个电路看成一组算术约束的清单：只有当该陈述为真时，这些约束才会全部成立。 使一切校验通过的那些私有输入——你的 note、你的密钥、Merkle 路径——就叫作 witness。
这就是为什么我们在第 1 篇文章里讲有限域，在第 3 篇文章里讲 ZK 友好哈希：因为电路使用的是域上的算术，所以陈述中的每一步操作（包括哈希，以及第 4 篇文章里的 Merkle 向上攀升）都必须以这种方式表达出来。每种操作表达得越便宜，证明就越小、越快。
洞穴例子需要来回进行很多轮。这对区块链来说并不现实，因为证明必须一次性发布，并且之后所有人都要永久地检查它。两个升级解决了这个问题。
非交互（Fiat-Shamir 思路）。 不再需要一个在线验证者不断喊出随机挑战，而是由证明者通过对自己“当前为止的证明内容”进行哈希，自行生成这些“随机挑战”。因为一个好的哈希是不可预测的（第 3 篇文章），证明者无法按对自己有利的方式操纵挑战。原本需要反复对话的过程，被压缩成了一个单独、自包含的证明，任何人日后都可以检查，无需交互。
简洁。 最优秀的系统能让证明非常小，而且验证速度极快，不管被证明的陈述有多大。 这才是真正令人惊叹的部分。
一个 Groth16 证明（Sapling 使用的系统）大约只有 192 字节，并且可在毫秒级完成验证，无论它所证明的陈述是很小还是极其庞大。 区区几百字节，就可以为一个包含数千条约束的计算背书。
把这两点合在一起，就得到了你会经常看到的那个缩写：
zk-SNARK = zero-knowledge Succinct Non-interactive ARgument of Knowledge。零知识（不泄露信息）、简洁（小且快）、非交互（一次完成）、知识论证（证明者确实知道一个有效的 witness）。
没有免费的午餐。许多 SNARK 都需要一次性的 setup，为该电路生成公开参数。这个 setup 会伴随产生一些秘密随机性，而这些秘密必须被销毁。如果有人保留了它，他们就可以伪造证明，也就是说，能够伪造货币（但关键是，他们仍然不能破坏隐私）。
这份残留的秘密通常被称为 toxic waste。为了安全地处理它，Zcash 举办了复杂的多方仪式，由许多彼此独立的参与者各自贡献随机性；只要其中哪怕有一个人诚实地销毁了自己的那一部分，这份 toxic waste 就无法被恢复。
更新的系统则完全取消了这一要求，这也是 Zcash 的证明系统会随着时间演进的最大原因之一。
| 设计 | 证明系统 | Trusted setup？ | 构建于 |
|---|---|---|---|
| Sprout（最早期） | 早期 zk-SNARK | 是 | 原始仪式 |
| Sapling | Groth16 | 是（多方 “Powers of Tau” + Sapling 仪式） | BLS12-381（第 2 篇文章） |
| Orchard（当前） | Halo 2 | 无 trusted setup | Pallas / Vesta（第 2 篇文章） |
从 Sprout 到 Sapling 再到 Orchard，这一演进过程在很大程度上就是证明变得更小、更快，并逐步摆脱 trusted setup 的过程。Orchard 使用的 Halo 2 完全不需要任何仪式，并且从设计上支持递归（可验证其他证明的证明），这也是为什么 Orchard 使用了第 2 篇文章中的 Pallas/Vesta 曲线循环：每条曲线都被调优为可以验证写在另一条曲线上的证明。
这就闭合了第 0 篇文章中最大的那个环。“帷幕之后”的魔法，就是一个 zk-SNARK：它证明你的交易满足一个编码了全部规则的算术电路，同时除了单独那一位“有效”之外，什么也不泄露。
零知识证明是一个很深的领域，而我们是有意停留在直觉层面的。我们没有定义可靠性中的精确概率界限，没有展开算术电路的确切形式（R1CS、PLONKish 等），也没有讲多项式和承诺如何把一个电路变成短证明，更没有深入 Groth16 和 Halo 2 的真实内部结构。洞穴只是一个交互式证明；生产系统则是非交互的，而且复杂得多。但这一切都不改变核心：证明某个电路被一个秘密 witness 所满足，而且是完整地、可靠地、并且不泄露任何信息地完成证明。至于其中的机制，本身就足够再写成一个完整系列。
| 术语 | 通俗含义 |
|---|---|
| Zero-knowledge proof | 让别人相信某个陈述为真，同时不泄露任何其他信息 |
| Prover / Verifier | 提供证明的人 / 检查证明的人 |
| Completeness | 真陈述总会被接受（前提是证明者诚实） |
| Soundness | 假陈述会被拒绝（作弊者除非靠运气，否则赢不了） |
| Witness | 使陈述成立的那些秘密输入 |
| Arithmetic circuit | 将一个陈述改写为有限域上的加法与乘法 |
| Non-interactive (Fiat-Shamir) | 一次完成、无需实时来回交互的证明 |
| Succinct | 无论陈述规模多大，证明都很小且验证很快 |
| zk-SNARK | Zero-knowledge Succinct Non-interactive ARgument of Knowledge |
| Trusted setup / toxic waste | 一次性参数生成过程，其残留秘密必须被销毁 |
如果证明什么都不泄露，那验证它怎么还能有意义？ 因为数学结构被安排成：只有真实、有效的 witness 才能生成通过校验的证明。通过校验这件事本身，就是证据，不需要额外披露。
有人可以伪造证明吗？ 可靠性让这件事在实际上不可行。唯一的例外是：某个 SNARK 的 trusted-setup toxic waste 被保留了；这也正是为什么销毁它的那些仪式至关重要。
如果 trusted setup 被破坏，会泄露我的隐私数据吗？ 不会。它会让攻击者能够伪造新的货币，但不会暴露金额、地址或 notes。隐私和可靠性是两个彼此独立的保证。
为什么 Zcash 会随着时间更换证明系统？ 为了获得更小、更快的证明；而到了 Halo 2，则进一步完全消除了 trusted setup，并启用了递归能力。
在洞穴的例子里，为什么验证者必须在证明者已经走进去之后，才选择要求其从哪一侧出来，而不能提前宣布？（答案见下。）
如果验证者先宣布哪一侧，那个并不知道口令的骗子只需要一开始就走进那一侧，然后再若无其事地从那里走出来，根本不需要那扇门。只有在证明者先选定通道之后再发出挑战，才会迫使骗子依赖运气（每轮 50/50），而这正是多轮重复之所以有说服力的原因。这种“先承诺，再接受挑战”的顺序，正是 Fiat-Shamir 通过从证明者已经提交的证明内容中哈希出挑战值所保留下来的结构。
第 6 篇文章：端到端的 shielded protocol： 系列终章。我们将把所有部分——notes、承诺、note commitment tree、nullifiers、价值平衡，以及零知识证明——拼装成一笔完整的 Zcash shielded transaction，闭合从第 0 篇文章起打开的每一个环。
本文属于 Zcash from First Principles 系列，由 ZecHub 发布。采用 CC BY-SA 4.0 许可。