2021.07 随机漫步 · 零知识证明

Overview

对一个给定的秘密信息 x，一方可以在不泄漏任何 x 相关信息（零知识）的情况下，向另一方证明 “自己知道 x” 这个事实。

随机漫步 · 零知识证明

被 “重新发现” 的零知识证明

“零知识证明” (Zero-Knowledge Proofs, ZKPs) 这样一个技术向的概念，近期怎么“突然”热起来了？

（好吧，确实还没有像 “元宇宙” 那样破圈成功）

先看看 Jill Carlson 的这条推：

Jill’s Prediction

Jill 的预测：在接下来的 5 年中，我们将看到人们像讨论区块链应用那样讨论零知识的应用。此前的突破所带来的潜力将会被主流认可。

另外有两条有趣的推：

1. 在 “零知识证明” 里，“零知识” 是关于隐私/保密 (privacy/confidentiality) 的，而 “证明” 却是关于完整性 (integrity) 的。此技术目前仍是被严重低估的状态。(from @zooko)
2. 技术成熟时，你对区块链的需求将会极小化，而对零知识的需求将会极大化。区块链将仅提供数据的可用性和共识的保障，所有的执行都将会是对证据的验证。 (from @zmanian)

看起来 ZKPs 虽然概念上 1985 年前就被提出来了，但是确实是通过与区块链结合，在一系列应用中，它的价值被 “重新发现” 了。

2021 年度阿贝尔奖

今年 3 月份，零知识证明的相关研究者，以色列计算机科学家 Avi Wigderson 与匈牙利数学家拉兹洛・洛瓦兹（László Lovász）一同获得了 2021 年度的阿贝尔奖（据说设立此奖的一个原因也是因为诺贝尔奖没有数学奖项，奖金的数额也大致同诺贝尔奖相近）。

值得一提的是 Wigderson 非常厉害，这里跑个题，简单说一下他的两大成就：

其一是关于随机性在计算中的作用。在很多情况下，比如寻找迷宫的出口，掷骰子往往能让算法更快地找到解答。Wigderson 与合作者在 90 年代证明，如果使用了随机性的算法看起来很高效，那么必定存在另一种同样高效的非随机算法（能达到同样的目的）。这从理论上确保了随机算法确实可以找到高效地找到正确的解答 。

“A lot of programs practically run much faster if you allow them to do this random choice.” - Peter Sarnak (a number theorist at the IAS)

其二就是零知识证明与数学的关系。1991 年，Wigderson 与合作者证明，本质上所有数学论述都可以改写成一个允许被 “零知识证明” 化的版本 (essentially all mathematical statements can be translated in a way that allows a zero-knowledge proof) ——关于这一点，Wigderson 认为，“这可能他最令人惊讶、也最矛盾的结果”。

好吧，问题来了，说了半天，究竟什么是 “零知识证明”？

究竟什么是 “零知识证明”？

这里是 Wikipedia 上对零知识证明的定义：

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that they know a value x, without conveying any information apart from the fact that they know the value x.

简单讲，对一个给定的秘密信息 x，一方可以在 不泄漏任何相关信息（零知识） 的情况下，向另一方证明 “自己知道 x” 这个事实。

那么，什么情况下，我们需要用到这种方式的证明呢？

永动机和公私钥系统

举个例子，我发明了永动机。

虽然我迫不及待地想向外界发布这个信息，然而，我既不想让别人看到这个永动机长什么样，也不想让别人看到理论的细节和推导的过程，更不想让别人看到使用的材料和实验的步骤。

这个时候，我就需要 “零知识证明” 了。

反应敏捷的你，可能会问，在比特币系统中常见的 “A 使用私钥对特定的公开信息签名， B 使用对应的公钥验证该签名是否有效”，是否是对 “该签名者拥有私钥” 这一声明的零知识证明呢？

从上面的概念上讲，这是不算的。

因为，虽然 A 在未透露私钥的情况下证明了自己持有私钥，但为了使得其他人可以验证，他必须提供与该私钥对应的公钥给验证者，这违反了上面说的 “without conveying * any * information” 这个条件 (公钥和私钥具有相关性)。正因如此， Wikipedia 上接着说，真正的难点在于 “不能透露该信息，及额外的相关信息” (the challenge is to prove such possession without revealing the information itself or any additional information)

李永乐老师在 Youtube 上的讲解视频 里，举了四个例子。它们分别是

1. 分球 - (在不讨论颜色的情况下) 证明自己并非色盲
2. 山洞 - (不展示验证口令过程的情况下) 证明自己已知口令
3. 数独 - (不展示具体解法的情况下) 证明一个特定解已知
4. 染色 - (不展示具体解法的情况下) 证明特定结构有三色解

李永乐老师 - 神奇的零知识证明！

李老师的视频紧凑连贯，平易近人，小学生都可以 1.25 倍速无压力看完（小学生亲测有效）。

这四个例子前后只用了十来分钟，就基本上把零知识证明展示得明明白白了，推荐你现在就去看。

当然，看完了别忘了回来。

姚氏百万富翁问题

李永乐老师在视频末尾提出了一个问题，这个问题就是著名的 “姚氏百万富翁问题” (Yao’s Millionaire’s Problem)。

这里是 解决方案 和 对应的代码 ，具体的就不细说了。

真实世界案例

看完了视频里的几个例子，一起来看看下面这个真实世界的房屋租赁案例吧。

小美在硅谷工作，最近刚跳槽到一家她中意了很久的大公司，打算在附近找套房子安顿下来。

公司同事给她介绍了一个中介——小黄。

本来小美对房子挺满意的，可是一想到要一下子把自己的手机号码，银行卡流水，收入情况，社保号码这些隐私信息，一下子给一个头一次见面，才刚认识不久的房产中介，小美不由皱了皱眉头。

再说了，万一房产中介保管不善，这些信息被第三方的拿走了，甚至被贩卖给做黑产的怎么办。想到这些，小美打了个寒颤。

要是能不透露自己的这些私人信息，又能向合同签订方证明自己的信用记录就好了。

我们来一起看看，怎么用零知识证明解决这个问题。

完整的证明过程

在开始前我们假设，这套房子的租金是 $1k/月，房东要求房客需要出示至少 $4k/月的收入证明。

在一个房间里有十个盒子，盒子上分别写着 $1k / $2k / … / $10k，作为标记。每个盒子上都有一把锁，彼此互相无法开启。每个盒子顶部有一条缝 (可以塞纸条进去)，但塞进去的纸条只有用钥匙开启才能看到内容。

这个时候，中介小黄先进去，把第四个写着 $4k (也就是房东要求的最低收入证明) 的盒子钥匙拿走，并把其他所有盒子的钥匙都销毁，也就是说，之后小黄只能看 4 号盒子的内容了。

完成后，小黄离开房间。

此时小美进入房间。小美需要准备一些上面有 “+” 和 “-” 的卡片，并按照盒子上的金额，把她收入能覆盖的盒子全部放入 “+” 卡片，而超出她收入的盒子放 “-” 卡片。在这个例子里，你可以看到小美的收入为 $7k/月。完成后小美离开房间。

最后一步，小黄回到房间，用他的 4 号钥匙开启 4 号盒子。

这个时候，如果他看到 “+”，就是说，小美满足了条件，看到 “-”，就是小美不满足条件。

你可能已经注意到了，整个验证过程中，小黄得到了自己想要的答案，小美也没有暴露任何信息，而这就是零知识证明的神奇之处。

在真实世界里，情况比这会略微复杂一些，比如我们会使用自动化数据获取而不是依赖手动标记，会使用哈希而不是明文的标识，但核心逻辑是类似的。

总得来说，对于目前我们正在使用的绝大多数互联网应用，大部分情况下，我们都选择了牺牲一些隐私换来便利。然而，通过应用零知识证明，应用程序得以避免存储用户的隐私数据 (如身份证正反面的照片) 来规避“保管敏感信息导致泄漏”的风险，而总是可以选择在需要的时候去验证。

换句话说，通过使用零知识证明，我们从一开始就避免了敏感数据的传送，也就自然不再需要像以前那样被迫接受关于隐私的折衷与妥协。

区块链应用

在区块链行业，零知识证明得到了极大的发展。下图集中展示了 ZKPs 在区块链场景下的应用。

ZKPs applications in blockchain

值得注意的是，去年以来，通过 ZKPs 来为区块链扩容 成为新的应用场景。以下这两个的方案值得关注：

其中，Mina Protocol 本质上回答了下面这个问题：

How can we be convinced of the current state of the blockchain, without seeing the entire history of that state?

在 Mina 的方案中，通过使用递归的 zk-SNARKs，最终得到了一个 恒定尺寸只有 22KB 的区块链，被称为史上最轻量的区块链。

不仅个人的隐私可以得到保护（联系方式，收入，社保等敏感信息），组织 (跨部门资源管理，背景调查)，社会 (个人征信)，甚至国家也一样可以从零知识证明中受益。

在 2016 年，普林斯顿等离子物理研究室和普林斯顿大学的研究人员演示了一个可以用于核裁军协商的技术。通过这个技术，观察员可以在无法记录，分享和泄漏机密的内部机制的前提下，确认一个给定的物体是否是核武器。

2019年7月，美国国防部高级研究计划局(Defense Advanced Research Projects Agency)宣布了一项名为“保护用于加密核查和评估的信息”(Securing Information for Encrypted Verification and Evaluation)的新举措，旨在将零知识证明应用于美国军方。在实践中，这可能意味着有能力证明数据的来源或出处，而不说明具体是如何获得的。这可能涉及证明数字系统存在安全漏洞，而无需披露漏洞的细节或利用漏洞的方法。SIEVE 最具体的例子涉及到，将网络攻击归因于一个特定的人群、实体或国家。在这种情况下，目标将是能够证明归属，而不需要透露机密情报或任何一方的具体黑客能力。如果零知识证明可以以这种方式使用，这项技术将大大简化处理网络安全的“归因问题”。

在隐私，安全等考虑之外，还有其他你可能想不到的应用。

把零知识证明用在一个开放式游戏里？

是的，ETH 上的 Dark Forest 正是这么做的。

区块链上的数据是公开，透明，可追踪，可审计的，但零知识证明的应用，使得玩家在一个公开透明的环境下，可以在 不向外部透露自己的坐标等关键信息 的情况下与合约交互，参与游戏（像不像大刘笔下的黑暗森林？）。这大大拓展了游戏的深度和广度。

此前他的开发者 Brian Gu 做了一篇访谈，我把这个访谈的要点记在了这篇 blog 里。

---

• 顾露 (Gu Lu) 于免成居
• 时间: 2021-06-29
• 编号: Bt-011-2107

---

• 【留言点这里】

---