「区块链基础概念100」由火星财经「学习区块链」频道出品，在区块链基础概念之上延展深度阅读，并紧密连接产业，关注产业发展热点和趋势。

1. 基础概念

零知识证明/ Zero-Knowledge Proof

证明者和验证者之间进行交互，证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

2. 深度解读

可能是最耐心的硬核详解：零知识证明的可靠性与知识的存在性

原文标题：《读心术：从零知识证明中提取「知识」》
作者：郭宇，安比实验室创始人

「零知识」vs. 「可靠性」

我们在许多介绍零知识证明的文章中都能看到这样三个性质：

• Completeness —— 完备性
• Soundness —— 可靠性
• Zero-Knowledge —— 零知识

但是少有文章深入解释这个特性背后的深意和洞见。在『系列（二）理解「模拟」』一文中，我们介绍了「模拟器」这个概念。许多介绍文章避而不谈「模拟」，但「模拟」可以说是安全协议中核心的核心，因为它是定义「安全性」的重要武器。通常，我们定义安全会采用这样一种方式，首先列出一些安全事件，然后说明：如果一个系统安全，那么列出来的安全事件都不会发生。

Rather than giving a list of the events that are not allowed to occur, it (the definition of zero-knowledge proof) gives a maximalist simulation condition.
— Boaz Barak

借用密码学家 Boaz Barak 的话，翻译一下，「零知识证明」并不是通过给出一个不允许发生的事件列表来定义，而是直接给出了一个最极致的「模拟条件」。所谓「模拟条件」是指，通过「模拟」方法来实现一个「理想世界」，使之与「现实世界」不可区分；而由于在理想世界中不存在知识，所以可以推导出结论：现实世界满足「零知识」。我们继续分析下一个交互系统（安全协议）的三个性质：「完备性」、「可靠性」与「零知识」。

可靠性（Soundness）：Alice 在没有知识的情况下不能通过 Bob 的验证。
*完备性（Completeness）：Alice 在有知识的情况下可以通过 Bob 的验证。
*零知识（Zero-knowledge）*：Alice 在交互的过程中不会泄露关于知识的任何信息。

我们可以看出来「可靠性」和「完备性」有一种「对称性」。可靠性保证了恶意的 Alice 一定失败，而完备性保证了诚实的 Alice 一定成功。

「完备性」比较容易证明，只要 Alice 诚实，Bob 也诚实，那么皆大欢喜。这好比，写好一段代码，喂了一个测试用例，跑完通过收工。

我们来想想「可靠性」应该如何定义？这个可靠性的逆否命题是：（在现实世界中）如果 Alice 能通过 Bob 的验证，那么 Alice 一定有知识。或者说：Alice 知道那……个「秘密」！

下面的问题是如何证明 Alice 知道一个「秘密」？

这好像也很难，对不对？假如我们需要证明一台机器知道一个「秘密」，最简单的办法就是我们在机器的硬盘里，或者内存中找到这个「秘密」，但是这样暴露了秘密。如果这台机器是黑盒子呢？或者是 Alice 呢？我们没有读心术，猜不到她心里的那个秘密。

如何定义「To Know」？

「零知识」保证了 验证者 Bob 没有（计算）能力来把和「知识」有关的信息「抽取」出来。不能抽取的「知识」不代表不存在。「可靠性」保证了知识的「存在性」。只有「知识」在存在的前提下，保证「零知识」才有意义。

本文将探讨「可靠性」和「To Know」。

为了进一步分析「知识」，接下来首先介绍一个非常简洁，用途广泛的零知识证明系统 —— Schnorr 协议。这个协议代表了一大类的安全协议，所谓的 Σ-协议，而且 Schnorr 协议扩展也是『零知识数据交换协议 zkPoD』[1] 的核心技术之一。

简洁的 Schnorr 协议

Alice 拥有一个秘密数字，a，我们可以把这个数字想象成「私钥」，然后把它「映射」到椭圆曲线群上的一个点 a*G，简写为 aG。这个点我们把它当做「公钥」。

sk = a
*PK = aG*

请注意「映射」这个词，我们这里先简要介绍「同态」这个概念。椭圆曲线群有限域之间存在着一种同态映射关系。有限域，我们用 Zq 这个符号表示，其中素数 q是指有限域的大小，它是指从0, 1, 2, …, q-1这样一个整数集合。而在一条椭圆曲线上，我们通过一个基点，G，可以产生一个「循环群」，标记为 0G, G, 2G, …, (q-1)G，正好是数量为 q个 曲线点的集合。任意两个曲线点正好可以进行一种「特殊的二元运算」，G + G = 2G ，2G + 3G = 5G，看起来这个二元运算好像和「加法」类似，满足交换律和结合律。于是我们就用 + 这个符号来表示。之所以把这个群称为循环群，因为把群的最后一个元素 (q-1)G，再加上一个 G 就回卷到群的第一个元素 0G。

给任意一个有限域上的整数 r，我们就可以在循环群中找到一个对应的点 rG，或者用一个标量乘法来表示r*G。但是反过来计算是很「困难」的，这是一个「密码学难题」—— 被称为离散对数难题[2]。

也就是说，如果任意给一个椭圆曲线循环群上的点 R，那么到底是有限域中的哪一个整数对应 R，这个计算是很难的，如果有限域足够大，比如说 256bit 这么大，我们姑且可以认为这个反向计算是不可能做到的。

Schnorr 协议充分利用了有限域和循环群之间单向映射，实现了最简单的零知识证明安全协议：Alice 向 Bob 证明她拥有 PK对应的私钥sk。

第一步：为了保证零知识，Alice 需要先产生一个随机数，r，这个随机数的用途是用来保护私钥无法被 Bob 抽取出来。这个随机数也需要映射到椭圆曲线群上，rG。

第二步：Bob 要提供一个随机数进行挑战，我们把它称为 c。

第三步：Alice 根据挑战数计算 z = r + a * c，同时把 z发给 Bob，Bob 通过下面的式子进行检验：z*G ?= R + c_PK = rG + c*(aG)

大家可以看到 Bob 在第三步「同态地」检验z的计算过程。如果这个式子成立，那么就能证明 Alice 确实有私钥a。可是，这是为什么呢？

z的计算和验证过程很有趣，有几个关键技巧：

1. 首先 Bob 必须给出一个「随机」挑战数，然后 Bob 在椭圆曲线上同态地检查 z 。如果我们把挑战数 c看成是一个未知数，那么r+a*c=z可以看成是一个一元一次方程，其中r与a是方程系数。请注意在c未知的前提下，如果r + a*x = r' + a'*x要成立，那么根据 Schwatz-Zippel 定理 [3]，极大概率上r=r'，a=a'都成立。也就是说， Alice 在c未知的前提下，想找到另一对不同的r',a'来计算z骗过 Bob 是几乎不可能的。这个随机挑战数c实现了r和a的限制。虽然 Bob 随机选了一个数，但是由于 Alice 事先不知道，所以 Alice 不得不使用私钥a来计算z。这里的关键：c 必须是个随机数。

2. Bob 验证是在椭圆曲线群上完成。Bob 不知道 r，但是他知道r映射到曲线上的点 R；Bob 也不知道 a，但是他知道 a映射到曲线群上的点PK，即 a*G。通过同态映射与 Schwatz-Zippel 定理，Bob 可以校验 z的计算过程是否正确，从而知道 Alice 确实是通过r和a计算得出的z，但是又不暴露 r与a 的值。

3. 还有，在协议第一步中产生的随机数r保证了 a 的保密性。因为任何一个秘密当和一个符合「一致性分布」的随机数相加之后的和仍然符合「一致性分布」。

证明零知识

我们这里看一下 Schnorr 协议如何证明一个弱一些的「零知识」性质——「SHVZK」：

注：这里我们证明的仅仅是 Special Honest Verifier Zero-Knowledge （SHVZK）。SHVZK 要求协议中的 Bob 的行为不能不按常理出牌，比如他必须按协议约定，在第二步时，去传送带上取一个新鲜的随机数，并且立即使用。而通常意义上的「零知识」是不会对 Bob 做任何要求，所以我们说这里是一个弱一些的性质。虽然目前 Schnorr 协议不能证明完全的「零知识」，但经过添加一些协议步骤，就可以达到完全零知识的目的，细节这里不展开，有兴趣的读者请参考文献 [4]。以后我们在讨论 Fiat-Shamir 变换时，还会再次讨论这个问题。

首先「模拟器」模拟一个「理想世界」，在理想世界中模拟出一个 Zlice 和 Bob 对话，Zlice 没有 Schnorr 协议中的知识，sk，而 Bob 是有公钥 PK 的。请大家看下图，Bob 需要在 Schnorr 协议中的第二步出示一个随机数 c，这里有个额外的要求， 就是 Bob 只能「诚实地」从一个外部「随机数传送带」上拿一个随机数，每一个随机数都必须是事先抛 k 次「硬币」产生的一个 2^k 范围内的一次性分布随机数。Bob 不能采用任何别的方式产生随机数，这就是为何我们要求 Bob 是诚实的。

下面演示 Zlice 如何骗过 Bob：

序幕：请注意 Zlice 没有关于sk的知识，这时 Bob 的随机数传送带上已经预先放置了一些随机数。

第一步：Zlice 产生一个一致性分布的随机数c，并且利用一个新的「超能力」，将刚刚产生的随机数c替换掉 Bob 的随机数传送带上第一个随机数。这时候，Bob 无法察觉。

第二步：Zlice 再次产生一个随机数z，然后计算 R'=z*G - c*PK，并将 R' 发送给 Bob。

第三步：这时候 Bob 会从随机数传送带上取得c，并且将c发送给 Zlice。请注意这个c正好就是第一步中 Zlice 产生的c。

第四步：Zlice 将第三步产生的随机数 z 发送给 Bob，Bob 按照 Schnorr 协议的验证公式进行验证，大家可以检查下，这个公式完美成立。

大家可以再对比下「现实世界」的 Schnorr 协议，在两个世界中，Bob 都能通过验证。但区别是：

• 在「理想世界中」，Zlice 没有 sk；而在「现实世界中」，Alice 有 sk
• 在「理想世界中」，z 是一个随机数，没有涉及 sk；而在「现实世界中」，z 的计算过程里面包含 sk
• 在「理想世界中」，Zlice 使用了超能力，替换了 Bob 的随机数；而在「现实世界中」，Alice 看不到 Bob 的随机数传送带，也无法更改传送带上的数字

这里请大家思考下：

Schnorr 协议中，Bob 在第二步发挑战数能不能和第一步对调顺序？也就是说 Bob 能不能先发挑战数，然后 Alice 再发送 R = r*G。

（两分钟后……）

答案是不能。如果 Alice 能提前知道随机数，那么 （现实世界中的） Alice 就可以按照模拟器 Zlice 做法来欺骗 Bob。

再遇模拟器

其实，「可靠性」和「零知识」这两个性质在另一个维度上也是存在着一种对称性。可靠性保证了恶意的 Alice 一定失败，零知识保证了恶意的 Bob 一定不会成功。有趣地是，这种对称性将体现在模拟出来的「理想世界」中。

我们分析下可靠性这个定义：Alice 没有知识导致Bob 验证失败。它的逆否命题为：Bob 验证成功导致Alice 一定有知识。

我们再次求助模拟器，让他在可以发挥超能力的「理想世界」中，去检验 Alice 的知识。

再次，请大家设想在平行宇宙中，有两个世界，一个是叫做「理想世界」，另一个叫做「现实世界」。理想世界有趣的地方在于它是被「模拟器」模拟出来的，同时模拟器可以在理想世界中放入带有超能力的 NPC。这次把 Alice 的两个分身同时放入「理想世界」与「现实世界」。

假设「你」扮演 Bob 的角色，你想知道和你对话的 Alice 是否真的是「可靠的」。于是把你放入「理想世界」，借助一个具有超能力的 NPC，你可以把对面的 Alice 的知识「抽取」出来。

W...hat？我们不是刚刚证明过：协议是零知识的吗？零知识就意味着 Bob 抽取不出任何的「知识」碎片。这里敲黑板，「零知识」是对于「现实世界」而言的。我们现在正在讨论的是神奇的「理想世界」。

重复一遍，在「理想世界」中，你可以借助一个有超能力的 NPC 来抽取 Alice 的知识，从而可以保证「现实世界」中的 Alice 无法作弊。可以想象一下，一个作弊的 Alice，她肯定没有知识，没有知识也就不可能在「理想世界」中让 NPC 抽取到任何东西。

然而在「现实世界」中，你无法借助 NPC，当然也就看不到 Alice 的知识，也就不会和「零知识」性质冲突。因为两个世界发生的事件是「不可区分」的，我们可以得到这样的结论：在「现实世界」中，Alice 一定是存在知识的。整理一下思路：如何证明在一个交互会话中 Alice 不能作弊呢？我们需要为这个交互会话定义一个「模拟算法」，该算法可以模拟出一个「理想世界」，其中有一个特殊的角色叫做「抽取器」(Extractor)，也就是我们前面说的 NPC，它能够通过「超能力」来「抽取」Alice 的知识，但是让对方「无所察觉」。

注意，超能力是必不可少的！这一点在『系列（二）理解「模拟」』有解释，如果模拟器在没有超能力的情况下具备作弊能力，那相当于证明了协议「不可靠」（Unsoudness）。同样地，如果「抽取器」在没有超能力的情况下具备抽取信息能力，那相当于证明了协议不零知（Not-zero-knowledge）。最后一点，超能力是什么？

这个要取决于具体的交互系统的证明，我们接下来就先拿我们刚刚讲过的 Schnorr 协议切入。

Proof of Knowledge ：「知识证明」

我们来证明一下 Schnorr 协议的「可靠性」，看看这个超能力 NPC 如何在「理想世界」中把 Alice 私钥抽取出来。而这个「超能力」，仍然是「时间倒流」。

第一步：Alice 选择一个随机数 r，并且计算 R=r*G，并将 R 发给「抽取器」

第二步：抽取器也选择一个随机的挑战数 c，并且发给 Alice

第三步：Alice 计算并且回应 z，然后抽取器检查 z 是否正确

第四步：抽取器发现 z 没有问题之后，发动超能力，将时间倒回第二步之前

第五步：抽取器再次发送一个不同的随机挑战数 c' 给 Alice，这时候 Alice 回到第二步，会有一种似曾相识的感觉，但是无法感知到时间倒回这个事实

第六步：Alice 再次计算了 z'，然后发给抽取器检查

第七步：这时候抽取器有了 z和z'，就可以直接推算出 Alice 所拥有的私钥 a，达成「知识抽取」

到这里，「可靠性」就基本证明完了。大家是不是对可靠性和零知性的「对称性」有点感觉了？

总结一下：「抽取器」在「理想世界」中，通过时间倒流的超能力，把 Alice 的「知识」完整地「抽取」出来，这就保证了一个没有知识的 Alice 是无法让抽取器达成目标，从而证明了「可靠性」。

注： 并不是所有的可靠性都必须要求存在抽取器算法。采用抽取器来证明可靠性的证明系统被称为「Proof of Knowledge」。

解读 ECDSA 签名攻击

在区块链系统中到处可见的 ECDSA 签名方案也是一个朴素的零知识证明系统。椭圆曲线数字签名方案 ECDSA 与 Schnorr 协议非常接近，基于 Schnorr 协议的签名方案发表在 1991 年的『密码学杂志』[5] 上。1991 年，正值美国国家标准局（NIST）选择数字签名算法，优雅的 Schnorr 签名方案居然被申请了专利，因此 NIST 提出了另一套签名方案 DSA （Digital Signature Algorithm），随后这个方案支持了椭圆曲线，于是被称为 ECDSA。

中本聪在构思比特币时，选择了 ECDSA 作为签名算法，但是曲线并没有选择 NIST 标准推荐的椭圆曲线 —— secp256-r1，而是 secp256-k1。因为江湖传言，NIST 可能在椭圆曲线参数选择上做了手脚，导致某些机构可以用不为人知的办法求解离散对数难题，从而有能力在「现实世界」中具备超能力。有不少人在怀疑，也许当年中本聪在设计比特币时，也有这种考虑，故意选择了 secp256-k1 这样一条貌似安全性稍弱的曲线。

我们拆解下 ECDSA 签名，用交互的方式定义一个类似 ECDSA 的认证方案，交互见下图。

第一步：Alice 仍然是选择一个随机数 k，并将 k映射到椭圆曲线上，得到点K，然后发送给 Bob

第二步：Bob 需要产生两个随机数，c和e，然后交给 Alice

第三步：Alice 计算 s，并且发送给 Bob，他来验证 s 的计算过程是否正确

注： 对熟悉 ECDSA 签名方案的读者，这里略作解释，Bob 产生的 c 对应被签消息的Hash值 Hash(m) ，而 e则是由一个转换函数F(K)来产生。其中F(.)是取椭圆曲线上的点的 x 坐标经过(mod q) 得到 [6]。

江湖上流传着一个说法：ECDSA 签名方案有个严重的安全隐患，如果在两次签名中使用了同一个随机数，那么签名者的私钥将会暴露出来。其实 Schnorr 签名方案也有同样的问题。

当年 Sony PlayStation 3 的工程师在调用 ECDSA 库函数时，本来应该输入随机数的参数位置上，却传入了一个常数。熟悉密码学的黑客们发现了这个严重的后门。2011 年 1 月，神奇小子 Geohot 公开发布了 Sony PS3 的主私钥，这意味着任何用户都可以轻松拿到游戏机的 root 权限。Sony 随后大为光火…… （后续故事大家可以上网搜）

如果 Alice 在两次交互过程中使用了同一个 K，那么 Bob 可以通过发送两个不同的 c和c'来得到s和s'，然后通过下面的公式算出私钥 a：

k = (c - c')/(s - s')
a = (k * s - c)/e

那么我们应该怎么来看这个「安全后门」呢？大家想想看，这个安全后门和我们前面证明过的 Schnorr 协议的可靠性证明几乎一模一样！这个算法正是 ECDSA 认证协议的「可靠性」证明中的「抽取器」算法。只不过在可靠性证明中，为了让 Alice 使用同一个随机数 k 来认证两次，「抽取器」需要利用「时间倒流」的超能力。

但是在 Sony PS3 系统中，随机数被不明所以的工程师写成了一个固定不变的值，这样相当于直接赋予了黑客「超能力」，而这是在「现实世界」中。或者说，黑客在不需要「时间倒流」的情况下就能实现「抽取器」。

提醒下，不仅仅是随机数不能重复的问题。而是随机数必须是具有密码学安全强度的随机数。

设想下，如果随机数 r是通过一个利用「线性同余」原理的伪随机数生成器产生，虽然 r 的值一直在变化，但是仍然不能阻止「知识抽取」。假设线性同余算法为r2= d*r1 + e (mod m)，还回到 Schnorr 协议的第三步：

1: z1 = r1 + c1*a
2: z2 = r2 + c2*a*

如果攻击者让 Alice 连续做两次签名，那么将 r2代入r1之后，就出现了两个线性方程求解两个未知数(r1, a)的情况，z1, z2, c1, c2, d, e* 对于 攻击者是已知的，这个方程组只用初中数学知识就可以求解。

请注意，这并不是 Schnorr 协议（或 ECDSA 协议）的「设计缺陷」，恰恰相反，这是 Schnorr 协议设计比较精巧的地方，它从原理上保证了协议的可靠性。类似技巧在密码学协议中频繁出现，达到一目了然的「简洁」。但是也不得不说，如果不清楚协议的内在机制，尤其是区分不清楚「理想世界」与「现实世界」，使用者很容易引入各种花式的「安全漏洞」。

作为一个能写出安全可靠软件的负责任的码农，我们需要了解哪些？彻底理解安全协议的设计机制当然是最好的，但是绝大多数情况下这是不现实的。一般来说，我们把各种密码学工具当做「黑盒」来用，但这可能是不够的，我们最好能了解下：

• 「安全定义」是什么？
• 「安全假设」到底是什么？
• 「理想世界」中的「超能力」到底是什么？

脑洞：我们生活在模拟世界中吗

第一次读懂「模拟器」时，我第一时间想到的是电影『黑客帝国』。我们生活所在「现实世界」也许是某一个模拟器模拟出来的「理想世界」，我们所看到、听到的以及感知到的一切都是被「模拟」出来的。在「现实世界」里，我们活在一个母体中。然而我们并不能意识到这一点。

早在春秋战国时期，庄子也在思考类似的问题：

昔者庄周梦为胡蝶，栩栩然胡蝶也。自喻适志与！不知周也。俄然觉，则蘧蘧然周也。不知周之梦为胡蝶与？胡蝶之梦为周与？周与胡蝶则必有分矣。此之谓物化。
——《庄子·齐物论》

通俗地解释下：庄子有一天睡着了，梦见自己变成了一只蝴蝶，翩翩起舞，醒来之后发现自己还是庄子，在梦中，蝴蝶并不知道自己是庄子。于是庄子沉思到底是他梦中变成了蝴蝶，还是蝴蝶梦中变成了庄子呢？如果梦境足够真实，……

「缸中之脑」是美国哲学家 Gilbert Harman 提出的这样一个想法：一个人的大脑可以被放入一个容器里面，然后插上电线，通过模拟各种电信号输入，使得大脑以为自己活在真实世界中。

这个想法源自哲学家笛卡尔的《第一哲学沉思集》[7]，在书中他论证我们应该怀疑一切，需要逐一检验所有人类的知识，数学，几何，以及感知到的世界。然而他发现除了「我思故我在」之外，所有的知识都可能不靠谱，因为我们的大脑很可能被一个具有「超能力」的 Evil Demon 所欺骗。

2003 年牛津大学的哲学教授 Nick Bostrom 郑重其事地写了一篇论文『我们生活在计算机模拟世界中吗？』[8]。认为以下三个事实中，至少有一个成立：

• 人类文明彻底灭绝。
• 人类文明已经到达可以完全模拟现实世界的科技水平，但是处于某种原因，没有一个人愿意去创造出一个新的模拟世界，充当上帝的角色。
• 我们现在的人类文明就生活在一个模拟世界中。

硅谷企业家 Elon Musk 在一次公开采访中，谈到「我们生活在基础现实世界」的概率只有「十亿分之一」。也就是说，他认为我们生活在一个电脑游戏（模拟世界）中，在模拟世界之外，有一个程序员，他开发并操纵了这个世界，我们每个人都是一个游戏角色（ NPC）。

在玩腻越狱 iPhone 和自动驾驶之后，神奇小子 Geohot 在今年三月份的「西南偏南」大会上做了一个题为「Jailbreaking the Simulation」的演讲 [9]。他认为，我们被生活在一个模拟世界中，所谓的上帝就是外部世界里活蹦乱跳的码农们，他们编程创造了我们的「现实世界」，当然，他们可能启动了不止一个世界副本。然而，他们可能也生活在一个外层「模拟世界」中。

如果我们确实生活在模拟世界中，或许我们可以在地球的某个地方找到一个后门——「Simulation Trapdoor」，从而获得「模拟器」的超能力，抽取出不可思议的「秘密知识」。

如果我们的世界的确是被程序模拟出来的，这个程序也许会有 Bug，如果有 Bug 存在，说不定我们可以利用这个 Bug 进行越狱，跳出「理想世界」，到达外面一层的世界中，与可爱的码农上帝聊一聊。这是在开玩笑吗？下面摘自自知乎的一个段子 [10]：

如果世界是虚拟的，有哪些实例可以证明？

1. 为什么宏观上丰富多彩，但是微观的基本粒子却都是一模一样的？这正和图片富多彩，但是像素是一模一样的一回事
2. 为什么光速有上限？因为机器的运行速度有限
3. 为什么会有普朗克常量？因为机器的数据精度有限
4. 为什么微观粒子都是几率云？这是为了避免系统陷入循环而增加的随机扰动
5. 为什么有泡利不相容原理？看来系统采用的数据组织是多维数组
6. 为什么量子计算机运行速度那么快，一瞬间可以尝试所有可能？因为这个本质上是调用了宿主机的接口
7. 为什么会有量子纠缠？这实际上是引用同一个对象的两个指针
8. 为什么会有观察者效应？这显然是 lazy updating
9. 为什么时间有开端？系统有启动时间

未完待续

设计一个密码学协议就好像在走钢丝，如果你想同时做到「零知识」和「可靠性」就意味着既要让协议内容充分随机，又要保证「知识」能够参与协议的交互。如果协议没有正确设计，亦或没有正确工程实现，都将导致系统安全性坍塌。比如可能破坏了零知性，导致「知识」在不经意间泄露；或者也许破坏了可靠性，导致任何人都能伪造证明。而且这种安全性，远比传统的代码底层机制漏洞来得更加严重，并且更难被发现。严格数学论证，这似乎是必不可少的。

我们的世界真的是某个「三体文明」模拟出来的吗？不能排除这个可能性，或许，我们需要认真地重新审视自己的各种执念。不过那又怎么样呢？至少自己的「思想」是真实的。

If you would be a real seeker after truth, it is necessary that at least once in your life you doubt, as far as possible, all things.

如果你是一个真正的真理探求者，在你人生中至少要有一次，尽可能地质疑所有的事情。

—— 笛卡尔

导读：只有「知识」在存在的前提下，保证「零知识」才有意义，本文将探讨「可靠性」和「To Know」。

一文读懂零知识证明背后的简单逻辑

文 | 李画

零知识证明的工程实现是一件极具挑战性的工作，但这并不意味着理解零知识证明这件事也同样困难，它背后的逻辑是简单的。

为什么需要去了解它？隐私问题自不用提，另一个重要原因则在于，随着对区块链探索的深入，我们发现通过密码学的方法来实现信任是对共识算法信任的有效补充，这两种信任可以更低摩擦地结合在一起，因此也更易被实现和应用。这个趋势也可以从近期区块链技术的发展方向中察觉到。

而只有当我们知道这些密码学方法背后的逻辑，才不会迷失其中，才能理解它为何要这样去设计，它适用于什么样的应用场景。

那么现在，就让我们开始零知识证明之旅吧。它包含三段旅程：

• 隐藏秘密之旅；

• 证明秘密之旅；

• 构建通用零知识证明之旅。

在《星际迷航》的宇宙，P = NP。

1. 隐藏秘密：单向功能

在《星际迷航》的宇宙中，P = NP，这对于计算界也许是件好事，它意味着所有可以在多项式时间内验证的问题，也可以在多项式时间内求解。但对于密码学界而言，这可能是一场灾难。

密码学需要存在一种「单向功能」，也就是说能够从 A 计算出 B，但从 B 计算出 A 存在着计算上的不可行性——计算从 A 到 B 是单向的，我们才有可能把 A 藏起来。而如果 P = NP，在多项式时间内可验证的问题同时也是可求解的，那么通过 B 就能计算出 A，秘密也就无法隐藏。

这就是密码学背后的简单逻辑：单向功能。而单向功能背后的支撑是 P! = NP。

这与零知识证明的关系是什么呢？我们可以把零知识证明分解为两个功能，第一个功能是隐藏秘密，第二个功能是证明自己有秘密。而隐藏秘密，如上文所述，就是找到一个具有单向功能的计算式。

零知识证明：零知识证明是指让验证者相信某个断言为真，且整个过程不泄露「断言为真」之外的任何知识。为了更容易理解，本文把它简化为隐藏秘密和证明拥有秘密。

椭圆曲线算法（ECC）是密码学中被普遍应用的一个具有单向功能的函数，它看起来是这样的：k × P = Q，在已知 P 的情况下，我们可以通过 k 计算出 Q，但难以通过 Q 反向计算出 k。需要注意的是，密码学中加法或乘法运算的含义不局限于我们熟悉的实数域上加法或乘法运算的含义。

让我们看看它是如何做到单向性的。在该函数中，P 是椭圆曲线上的一个点，我们把一个小球放在该点并沿切线方向击打出去，小球在椭圆曲线中撞来撞去撞了 k 次（大致可以这么理解），最后会落在一个点 Q 上。如果我们知道初始位置 P 和撞击次数 k，是能算出小球的落点 Q 的；但如果我们只看见小球落在 Q 上，是无法算出从 P 点到 Q 点撞了多少次，也就是 k 的。

下图是 k = 2 的一个示例，小球从 P 点出发，撞击了两次落在 Q 点上，因此 Q 等于2 × P。椭圆曲线算法常被用于生成公钥和私钥，公钥就是小球最后的落点 Q，私钥就是撞击次数 k。k × P = Q 的单向功能使得它可以隐藏私钥这个秘密。

椭圆曲线

2. 证明秘密：同态

对于零知识证明来说，隐藏秘密只是第一步，我们还需要证明自己确实掌握了秘密。就像在第一段旅程中只需要理解单向功能，在这第二段旅程中，我们只需要理解「同态」，有了同态我们就有了证明秘密的能力。那么什么是同态？

我们可以把单向功能看成一种映射关系，比如 k × P = Q 就是 k 到 Q 的映射：在一个空间中，我们有无数个 k 点，它们被映射到另一个空间，变成无数个 Q 点。这就像现实世界和影子世界，通过光线的映射，现实空间的物体变成了影子空间的影子。

这时候假设有一块机械手表，机芯就是那个隐藏起来的秘密。我们把含机芯的手表拆成 8 个零部件并映射到影子空间中，这时影子空间就会有 8 个影子；但注意在现实空间我们展示给大家看的是一块完整的手表，机芯是未暴露的，这块手表在影子空间也会有个影子，我们叫它第 9 号影子。

现在我们把 8 个零部件的影子组合起来，如果它们能够组成一块完整的手表影子，就可以用该影子与第 9 号影子做对比，如果两者是相同的，就能证明现实空间的这块手表中是有机芯的，因为它的影子与含机芯的零部件组成的影子相同。这其实就完成了一个简单的零知识证明过程。

完整零部件的影子组合成的手表影子与完整手表的影子相同，我们称这种映射为同态。用数学公式来表达就是 f(手表) = f(零件1 + …… + 零件8) = f(零件1) + …… + f(零件8)。其中，f(手表)是手表的影子，f(零件1) + …… + f(零件8) 是零部件的影子组合成的手表影子。

简化一下这种关系就是：f(a+b) = f(a) + f(b)，即「先计算后加密的结果」f(a+b) 与「先加密后计算的结果」f(a) + f(b) 是相同的。同态使得我们可以直接对密文进行计算，然后对隐藏了秘密的明文先计算后加密，再通过比较两者是否相同验证明文中是否真的藏有秘密。

同态定义：抽象代数中，同态是两个代数结构（例如群、环、或者向量空间）之间的保持结构不变的映射。

如果你只想了解零知识证明的基本逻辑，旅程到这里就可以结束了，知识点只有两个：1. 用单向功能隐藏秘密；2. 用同态映射证明秘密。是不是还算轻松？

接下来让我们看看这个过程在真实的密码学中是怎样的，以椭圆曲线数字签名算法（ECDSA）为例，它是一个具有「零知属性」的算法。你可以选择不看，它不会影响你对同态的理解。

椭圆曲线数字签名算法对签名的验证：在该算法中，关键的过程是验证 f(Z + dA × R) = f(Z) + f(dA × R) = f(Z) + Qa × R，其中，Z 是需要用私钥签名的消息，dA 是私钥，R 与随机数相关，Qa 是公钥。因为同态属性，这个等式是成立的，我们就可以用等式右边的 Qa(公钥)来验证 Z 是否是用等式左边的 dA(私钥) 签名的。 在这里，dA 是机芯，Z+dA×R 是藏有机芯的手表，f(Z + dA × R) 是这块手表的影子，而 f(Z) + f(dA × R) 是手表零部件的影子组合成的手表影子。

椭圆曲线算法的同态属性使得其他算法，比如椭圆曲线数字签名算法，可以利用它来隐藏并证明秘密，但该算法的能力有限，因为它只具备加法同态，也就是 f(a+b) = f(a) + f(b)，但不具备乘法同态，即 f(a×b) = f(a) × f(b)。

这相当于把现实空间的物体投射到影子空间后，影子空间可以用加法来组合影子，但对于一些需要用乘法才能组合的影子，它就无能为力了。

怎么办？可以引入「配对函数」。比如椭圆曲线配对函数就是对椭圆曲线算法做一系列的调整，生成一个新的映射空间，这个新空间既满足加法同态，也满足类乘法同态（注意，只是类乘法同态），这样一来，除了用加法，我们还可以用类乘法去证明秘密。

现在，第二段旅程抵达了终点。我们需要了解的是，同态是证明秘密的关键所在，但并不是所有的映射关系都有「良好」的同态，而不同的应用场景对同态的要求也不一样，在实际的设计中，需要根据具体需求实现不同的同态。

如果原空间与映射空间既满足加法同态，也满足乘法同态，我们称其为全同态。全同态意味着可以对密文进行任意的运算（可以对影子进行任意方式的组合），这对实现数据隐私有着重要的意义，但实现全同态是一件非常困难的事情。

3. 通用零知识证明：NPC 问题

你一定注意到了，我们说椭圆曲线数字签名算法具有「零知属性」，却并没有说它是零知识证明协议，因为它的主业是做数字签名，隐藏私钥只不过是它必须要实现的一个功能。而且它也只能隐藏私钥，如果想让它帮你隐藏一个你自己的秘密，它是做不到的。

而零知识证明协议，比如我们熟悉的 zk-SNARKs，它的主业就是隐藏并能证明需要它隐藏的各类秘密。这是如何做到的？

让我们回到本文最开始的那个单向函数 k × P = Q，它能隐藏一个秘密 k，如果我们把它变复杂一些，比如变成 t × h = (v0 + a1 × v1 + …… + am × vm)(w0 + b1 × w1 + …… + bm × wm)这样一个多项式，是不是就有了很多可以隐藏秘密的「空间」，比如把秘密放在 a1，a2，……，am 中。

事实上，上文中这个复杂的多项式就是 zk-SNARKs 中用于实现零知识证明的多项式，该多项式能够证明各类秘密，因为它能证明布尔电路。

为什么能证明布尔电路，就能证明各类秘密？因为布尔电路可满足性是一个 NPC（NP-Complete）问题，而 NPC 问题有一个「特性」，即所有的 NP 问题（包含NPC）都可以在多项式时间内归约（转换）成某一个具体的 NPC 问题。

比如布尔电路、图论三染色、甚至我们熟悉的扫雷游戏，都是 NPC 问题。我们可以把扫雷游戏规约成布尔电路的可满足性，也就是能够用证明布尔电路的多项式实现对扫雷游戏的零知识证明；可以把图论三染色规约成布尔电路的可满足性，也就是能够用证明布尔电路的多项式实现对三染色的零知识证明……

因此理论上，我们能够以任何一个 NPC 问题为基础构建一个通用的零知识证明协议。但这仅仅是理论上的，因为使用它们做证明的难易度是截然不同的。目前主流的方法是选择布尔电路或算术电路，因为它们实现起来相对容易、电路规模小，zk-SNARKs 和 Bulletproofs 都是选择的这种方法。

扫雷游戏

4. 零知识证明协议

在三段旅程之后，零知识证明对我们而言也许不再是神秘莫测的事物，它背后有着简单逻辑：1. 单向功能是隐藏秘密的方法；2. 同态映射是证明秘密的基础；3. 证明 NPC 问题的多项式（但这并非唯一的方法）可以实现通用零知识证明。

不同的零知识证明协议在这三点上的具体实现是不一样的，最主要的不同可能体现在第 3 点中，哪怕证明的是同一个 NPC 问题，也可以有截然不同的方法。因为不同的设计，零知识证明协议最常被提及的差异主要包括：

1. 不同的计算空间和计算时间。更小的空间和更短的时间是我们不断改进零知识证明协议的主要动力，也是比较不同零知识证明协议的主要指标。

比如下图是 ZCash 首席执行官 Zooko Wilcox 在谈到零知识证明协议时用到的表格，主要比较的就是不同协议的证明时间、验证时间和证明大小。

来源：https://slideslive.com/38911617/privacy-for-everyone  

2. 是否需要初始化可信设置。不需要可信设置当然更好，会减少信任问题和安全问题，不过新的证明方法就可能带来新的计算问题，比如 Bulletproofs 不需要可信设置，但它在高复杂度情况下的验证成本会很高。

3. 所依赖的安全假设。安全假设与安全密切相关，比如 Bulletproofs 依赖的是一个标准安全假设：离散对数问题，加上一个随机预言模型；而 zk-SNARKs 依赖的是一个不可否证的安全假设问题：指数知识假设。

上述的这些指标和属性很难被同时满足，因此在设计零知识证明协议，或者选择零知识证明协议/方法作为某个协议的功能组件的时候，需要考虑特定场景的需求问题。比如对证明时间有较高要求，就可能需要选择占用更多空间、或者具有较小通用性的方法；对可信设置有要求，就可能需要选择有更高证明成本的方法。

因此，一方面，零知识证明是不断发展的，各种不同的协议正在被设计出来，某些新协议在某些方面会更具优势；另一方面，不同的协议有不同的适用场景，要根据需求来做设计或选择，并没有一个适用于所有场景的更好的协议。

如果你愿意，旅程到此就可以结束了；如果你想继续，接下来的这一段有点「野」。

5. 另辟蹊径

 这是关于 zk-STARKs 的。它也是零知识证明协议，但它是基于信息编码的零知识证明，这是完全不同的一条道路，并且有可能打乱你已经清晰的思路。

zk-STARKs 并没有使用密码学中的单向函数，简单理解的话，它是这样做的：假设 P 有 9 个要证明的数，a1，a2，……，a9，那么把它们编码成 b1，b2，……，b9，每个bi中都含有a1，a2，……，a9 的部分信息。在做验证的时候，验证者 V 对 b1，b2，……，b9 做抽样检查，从少量 bi 中就能分析出编码有没有错误，这样就可以大概率探测到 a1，a2，……，a9 是否属实。

当 V 对 P 作随机抽样时，P 能够主动用随机数混淆抽样的 bi，同时又能使 V 完成验证，从而实现零知识性。

所以 zk-STARKs 的「单向」并不是基于计算不可行的单向，它是因为没有暴露 b1，b2，……，b9 全部，导致无法通过 b1，b2，……，b9 反向计算出 a1，a2，……，a9。在「同态」部分，它也不是抽象代数（或密码学）中的同态概念，而是基于线性编码纠错理论进行抽样验证。

zk-STARKs 也不是基于上文介绍的 NPC 难题做验证，它是基于概率检查做验证的。关于这类验证方法，可以从一种古老的验证系统 PCP（Probabilistically Checkable Proofs）中找到线索，不过在 zk-STARKs 中使用的方法叫 IOP（Interactive Oracle Proofs），与 PCP 的不同之处在于它用的是 Oracle。

之所以介绍 zk-STARKs，一方面是因为它也颇为流行，另一方面是想说明零知识证明可能是一个难以探索到边界的事物，比如 zk-STARKs 就是迥异的，因此本文只是理解零知识证明的一个角度，且因为自身认知有限，这种角度也许并不适用于所有的零知识证明方法。

希望这篇文章能让你更了解零知识证明一些，也希望能让你觉得密码学、数学是有趣的，因为它的复杂，也因为复杂背后的简单逻辑。

导读：当前zk-SNARK实现中的一个缺陷，是需要提前设置参数。如果这些参数被泄漏，那么整个网络将面临毁灭性的打击，零知识证明可能是一个难以探索到边界的事物。

一个略显严肃的科普：从交互到非交互式零知识证明
 

Challenges are at times an indication of Lord's trust in you.

挑战，有时是上天信任你的一种表现。 

——  D. Todd Christofferson

本文继续长篇大论零知识证明背后的机制原理，希望帮助大家理解这一类「现代密码学工具」的大致轮廓。本文约8000字，少量数学公式。

交互与挑战

我们之前介绍的零知识证明系统都是「交互式」的，需要验证者 Bob 在交互中提供一个或若干个「随机数」来挑战，比如「地图三染色问题」（参看『系列二』）中，验证者 Bob 需要「不断地」随机挑选一条边来挑战 Alice 的答案，直到 Bob 满意为止，而 Alice 的作弊概率会「指数级」地衰减。而让 Bob 相信证明的「基础」取决于 Bob 所挑选的随机数是不是足够随机。如果 Alice 能够提前预测到 Bob 的随机数，灾难就会发生，现实世界就会退化成「理想世界」，而 Alice 就可以立即升级成「模拟器」，通过超能力来愚弄 Bob。而『系列三』中，我们分析了 Schnorr 协议，协议中虽然验证者 Bob 只需要挑选一个随机数 c 来挑战 Alice ，让她计算一个值 z，但 Bob 绝对不能让 Alice 有能力来预测到 c 的任何知识，否则，Alice 也会变身成模拟器。随机数的重要性不言而喻：

通过随机数挑战是交互式零知识证明的「信任根基」。

但，「交互过程」会限制应用场景。如果能将交互式零知识证明变成「非交互」？这会非常非常激动人心。所谓的非交互可以看成是只有「一轮」的证明过程，即Alice 直接发一个证明给 Bob 进行验证。

非交互式零知识证明，英文是 Non-Interactive Zero Knowledge，简称 NIZK。它意味整个证明被编码为一个「字符串」，它可以写到一张纸上，通过邮件、聊天工具等各种方式随意发送给任何验证者，字符串甚至可以放在 Github 上随时供大家下载验证。

在区块链世界，「NIZK」可以作为共识协议的一部分。因为一个交易需要多个矿工进行校验。设想下，如果交易的发送者和每个矿工都要交互一下，让矿工进行挑战，那么共识过程将奇慢无比。而非交互式零知识证明则可以直接广播给所有的矿工节点，让他们自行验证。

可能有朋友会问：只让一个矿工挑战不就够了吗？把矿工和交易发送者的交互脚本编码成证明，然后广播给其他矿工，然后其他矿工就直接相信这个挑战过程是可信的，不也可以吗？但是，很显然，这里需要相信第一个交互矿工作为可信第三方，第三方？似乎不是一个好主意……

而非交互式零知识证明，以下我们直接说「NIZK」，似乎就很理想了，没有第三方赚差价。

「非交互」带来的困惑

非交互式零知识证明，NIZK，如果存在，那么它要比交互式证明强大得多。

• 交互式证明，只能取信于一个验证者；而 NIZK 可以取信于多个验证者，以至所有人。
• 交互式证明，只能在交互的那个时刻有效；而 NIZK 将始终有效。

NIZK 不仅可以跨越空间，还能跨越时间

听上去很美，不是吗？But, ……重复下上节的一个结论：

通过随机数挑战是交互式零知识证明的「信任根基」。

可是如果 NIZK 失去了挑战过程，有什么后果？我们已经回忆过「零知识」性质的证明（参考『系列二』），证明过程需要构造一个模拟器（算法），它也和验证者（Bob）在理想世界中进行交互，而验证者 Bob 没有能力区分出来对方是否是真的 Alice 还是一个模拟器。如果现在考虑下 NIZK 中的 非交互式，假如「我」向「你」出示一张纸，上面写着一个「真」证明 X ，又假如「你」在看过这张纸之后确实相信我了；又因为协议是「零知识」，那么如果把「我」换成一个模拟器，模拟器也能「伪造」一个假证明 Y，能够也让「你」相信。好了，问题来了：

• 你如何区分 X 和 Y ，孰真孰假？当然你无法区分，因为协议是零知识的，你必须不能区分
• 我可以同样可以把 Y 出示给你看，那岂不是「我」就可以欺骗你了吗？

是不是不和谐了？请大家在此处思考两分钟。(两分钟后……)因为 NIZK 没有了交互，也就没了挑战过程，所有的证明过程都有 Alice 来计算书写，理论上 Alice 确实是想写什么就写什么，没人拦得住，比如 Alice 就写「理想世界」的 假证明 Y。想必深刻理解模拟器的朋友，在这里会发现一个关键点：模拟器必须只能在「理想世界」中构造Y，也就是说，Y 这么邪恶的东西只能存在于「理想世界」，不能到「现实世界」祸害人间。继续思考……还有一个更深层次的问题，请大家回忆下「地图三染色问题」，之所以模拟器不能在「现实世界」中为非作歹，核心原因是，他在理想世界中有「时间倒流」的超能力，而在「现实世界」中不存在这种黑魔法。现实世界的「不存在性」是关键。而且，NIZK 中没有交互，于是导致了一个严重的后果，模拟器没有办法使用「时间倒流」这个超能力，当然似乎也就不能区分证明者在两个世界中的行为。换句话说，如果我们面对任何一个 NIZK 系统，似乎「模拟器」就很难高高在上了，它好像只能飘落人间，成为一个普普通通的凡人。如果，我说如果，按此推论，假设模拟器不再具备超能力，那就意味着 Alice 和模拟器没有区别，Alice 也可以成为一个模拟器，再继续推论，Alice 就可以在「现实世界」中任意欺骗 Bob，那么这个证明系统就不再有价值，因为它失去了「可靠性」。结论：任何的 NIZK 都不可靠。这一定是哪里出了问题……上面我们在分析的过程中，提到了交互挑战的缺失。确实，如果 Bob 不参与 Alice 产生证明的过程，证明所包含的每一个 bit 都由 Alice 提供，似乎「证明」本身不存在任何让 Bob 信任的「根基」。这个从「直觉」上似乎说不通。那是不是说，没有 Bob 的参与就「彻底」没办法建立「信任根基」了呢？信任的根基还可以从哪里来呢？答案是「第三方」！Wait ……，协议交互不是只有两方吗？Alice 和 Bob，哪来第三方？需要用特殊的方式引入第三方，而且方法不止一种，我们先研究第一种。（泪目：不是说的好好的，咱们不引入第三方吗？）

回顾 Schnorr 协议

我们再看一下老朋友——Schnorr 协议，它是一个三步协议：第一步，Alice 发送一个承诺，然后第二步 Bob 发送随机数挑战，第三步，Alice 回应挑战。

我们来看，如何把一个三步的 Schnorr 协议变成一步。看一下 Schnorr 协议的第二步，Bob 需要给出一个随机的挑战数 c，这里我们可以让 Alice 用下面这个式子来计算这个挑战数，从而达到去除协议第二步的目的。

其中 R 是 Alice 发给 Bob 的椭圆曲线点，PK 是公钥。大家可以好好看看这个利用 Hash 算法计算 c 的式子。这个式子达到了两个目的：

• Alice 在产生承诺 R 之前，没有办法预测 c，即使 c 最终变相是 Alice 挑选的
• c 通过 Hash 函数计算，会均匀分布在一个整数域内，而且可以作为一个随机数（注：请大家暂且这么理解，我们在后文再深入讨论）

请注意：Alice 绝不能在产生 R 之前预测到 c，不然， Alice 就等于变相具有了「时间倒流」的超能力，从而能任意愚弄 Bob。而一个密码学安全 Hash 函数是「单向」的，比如 SHA256，SHA3，blake2 等等。这样一来，虽然 c 是 Alice 计算的，但是 Alice 并没有能力实现通过挑选 c 来作弊。因为只要 Alice 一产生 R， c 就相当于固定下来了。我们假设 Alice 这个凡人在「现实世界」中是没有反向计算 Hash 的能力的。

看上图，我们利用 Hash 函数，把三步 Schnorr 协议合并为了一步。Alice 可以直接发送：(R, c, z)。又因为 Bob 拥有 PK，于是 Bob 可以自行计算出 c，于是 Alice 可以只发送 (R, z) 即可。我们把上面这个方案稍微变下形，就得到了「数字签名」方案。所谓的数字签名，就是「我」向「你」出示一个字符串，比如「白日依山尽，黄河入海流」，然后为了证明这句诗是我出示的，我需要签署某样东西。这个东西能证明我的身份和这句诗进行了关联。

从 NIZK 角度看数字签名

不严格地说，数字签名方案相当于在证明（1）我拥有私钥，并且（2）私钥和消息进行了关联计算。

我首先要证明我的身份，那么这个简单，这正是 Schnorr 协议的功能，能够向对方证明「我拥有私钥」这个陈述。并且这个证明过程是零知识的：不泄露关于「私钥」的任何知识。那么如何和这句唐诗关联呢？我们修改下计算 c 的过程：

这里为了保证攻击者不能随意伪造签名，正是利用了离散对数难题（DLP）与 Hash 函数满足抗第二原象（Secondary Preimage Resistance ）这个假设。注：这里严格点讲，为了保证数字签名的不可伪造性，需要证明 Schnorr 协议满足「Simulation Soundness」这个更强的性质。这点请参考文献[2]

上图就是大家所熟知的数字签名方案 —— Schnorr 签名方案[1]。在这里还有一个优化，Alice 发给 Bob 的内容不是 (R, z) 而是 (c, z)，这是因为 R 可以通过 c, z 计算出来。

注：为什么说这是一个「优化」呢？目前针对椭圆曲线的攻击方法有 Shanks 算法、Lambda 算法 还有 Pollard's rho 算法， 请大家记住他们的算法复杂度大约都是 [6]，n 是有限域大小的位数。假设我们采用了非常接近 2^256 的有限域，也就是说 z 是 256bit，那么椭圆曲线群的大小也差不多要接近 256bit，这样一来，把 2^256 开平方根后就是 2^128，所以说 256bit 椭圆曲线群的安全性只有 128bit。那么，挑战数 c 也只需要 128bit 就足够了。这样 Alice 发送 c 要比发送 R 要更节省空间，而后者至少需要 256bit。c 和 z 两个数值加起来总共 384bit。相比现在流行的 ECDSA 签名方案来说，可以节省1/4 的宝贵空间。现在比特币开发团队已经准备将 ECDSA 签名方案改为一种类 Schnorr 协议的签名方案——muSig[2]，可以实现更灵活地支持多签和聚合。

而采用 Hash 函数的方法来把一个交互式的证明系统变成非交互式的方法被称为 Fiat-Shamir 变换[3]，它由密码学老前辈 Amos Fiat 和 Adi Shamir 两人在 1986 年提出。

重建信任 —— 随机预言精灵

前文提到，失去了挑战，似乎失去了证明的「信任根基」。而在 Schnorr 签名方案中，Hash 函数担负起了「挑战者」的角色，这个角色有一个非常学术的名字：「随机预言机」（Random Oracle）[6]。

可是这里为何用 Hash？实际上当 Alice 要产生公共随机数时，需要一个叫做「随机预言机」的玩意儿，这是什么？开脑洞时间到！我们设想在「现实世界」中，天上有一位「精灵」，他手持一个双栏表格，左边一栏为字符串，右边一栏为数字。任何人，包括你我，包括 Alice 和 Bob，都可以发字符串给「精灵」。

精灵在拿到字符串之后，会查表的左边栏，看看表格里有没有这个字符串，下面分两种情况：

• 情况一：如果左边栏找不到字符串，那么精灵会产生一个「真随机数」，然后把字符串与随机数写入到表格中，然后把随机数返回地面上的凡人。
• 情况二：如果左边栏有这个字符串记录，那么精灵会将右边栏里面的数字直接返回给地面。

大家会发现这个精灵的行为其实很像一个随机数发生器，但是又很不一样，不一样的地方在于当我们发送相同的字符串时，他会返回相同的数。这个精灵就是传说中的「随机预言机」。而在合并 Schnorr 协议过程中，其实我们需要的是一个这样的随机预言精灵，而不是一个 Hash 函数。两者有什么不同的地方？区别就是：

• 随机预言机每次对于新字符串返回的是一个具有一致性分布的「真」随机数
• Hash 函数计算的结果并不是一个真正具有一致性分布的随机数

那么为什么前面用的是 Hash 函数呢？这是因为在现实世界中，真正的随机预言机不存在！为什么呢？事实上，一个 Hash 函数不可能产生真的随机数，因为 Hash 函数是一个「确定性」算法，除了参数以外，再没有其它随机量被引入。而一个具有密码学安全强度的 Hash 函数「似乎」可以充当一个「伪」随机预言机。那么合并后的安全协议需要额外增加一个很强的安全假设，这就是：

假设：一个密码学安全的 Hash 函数可以近似地模拟传说中的「随机预言机」

因为这个假设无法被证明，所以我们只能信任这个假设，或者说当做一个公理来用。插一句， Hash 函数的广义抗碰撞性质决定了它的输出可以模拟随机数，同时在很多情况下（并非所有），对 Hash 函数实施攻击难度很高，于是许多的密码学家都在大胆使用。不使用这个假设的安全模型叫做「标准模型」，而使用这个假设的安全模型当然不能叫「非标准模型」，它有个好听的专有名词，叫做「随机预言模型」。世界上有两种不同类型的人，喜欢甜豆花的，不喜欢甜豆花的。同样，世界上的密码学家分为两种，喜欢随机预言模型的，和不喜欢随机预言模型的[6]。

构造根基 —— 被绑架的精灵

Schnorr 协议经过 Fiat-Shamir 变换之后，就具有 NIZK 性质。这不同于我们证明过的 SHVZK，SHVZK 要求验证者诚实，而 NIZK 则不再对验证者有任何不现实的要求，因为验证者不参与交互，所谓要求诚实的验证者这个问题就不复存在。

注：如果验证者 Bob 不诚实会怎样？那么 Bob 有可能抽取出 Alice 的知识。但是对于三步 Schnorr 协议而言，它是否满足「零知识」，目前还处于未知状态。我们在系列三中只证明了它满足一个比较弱的性质：SHVZK。

但是，当 Schnorr 协议摇身一变，变成非交互零知识证明系统之后，就真正的「零知识」了。

然而，可能你的问题也来了，这个论断听起来似乎有道理，请问能证明吗？时间到了，“翠花，上模拟器”怎么用模拟器大法来构造一个「理想世界」呢？大家可以想一下，我们之前使用过「时间倒流」，还有修改「随机数传送带」超能力来让「模拟器」来作弊。可是没有交互了，这就意味着：「时间倒流」超能力不能用；Bob 的随机数传送带也不存在了，「篡改传送带」这个超能力也不能用！

但模拟器总要具备某种「超能力」，从而能够构建信任的「根基」

（如果模拟器在没有超能力的情况下具备作弊能力，那相当于证明了协议的不可靠性）。可能大家现在已经猜出来了，模拟器要在「随机预言机」上动手脚。先考虑下构造一个「理想世界」来证明「零知识」。在理想世界中，模拟器「绑架」了负责提供预言的「精灵」，当 Bob 向精灵索要一个随机数的时候，精灵并没有给一个真随机数，而是给 Zlice（模拟器假扮的 Alice）提前准备好的一个数（也符合一致性分布，保证不可区分性），「精灵」无可奈何地返回 Bob 一个看起来随机，但实际上有后门的数字。所谓后门，就是这个数字是 Zlice 自己提前选择好的。

• 第一步：Zlice 随机选择 z，随机选择c，计算 R'=z*G - c*PK 。

• 第二步：Zlice 将 c 与 (m, R') 写入精灵的表格。

• 第三步：Zlice 将签名 (c, z) 发送给 Bob。

• 第四步：Bob 计算 R=z*G - c*PK，并向精灵发送 (m, R)，精灵返回 c’。请注意，这里 Bob 计算出来的 R 和 Zlice 计算出来的 R' 是相等。

• 第五步：Bob 验证 c ?= c'，看看精灵传回来的随机数和对方发过来的随机数是否相等。如果相等，则验证签名通过；否则，则验证失败。

通过绑架「精灵」，Zlice 同样可以提前预知随机数，这和时间倒流能达到同样的效果。我们已经证明了模拟器 Zlice 的「存在性」，于是我们上面已经证明了 NIZK。接下来我们证明这个这个协议的「可靠性」。设想在另一个「理想世界」中，一个叫做「抽取器」的玩意儿，也同样绑架了精灵。当无辜 Alice 的向「精灵」索要一个随机数时，「精灵」返回了一个 c1，「抽取器」从精灵的表格中偷窥到了c1，当 Alice 计算出来 z1 之后，然后这时候「抽取器」仍然可以发动「时间倒流」超能力，让 Alice 倒退到第二步，再次向「精灵」要一个随机数，Alice 发送的字符串显然和第一次发送的字符串是相同的，(R, m)。按道理，因为 (R, m) 已经写在精灵表格的「左栏」里，所以一个诚实的「精灵」应该返回 c1。但是，「抽取器」绑架了精灵，他把表格中对应 (R, m) 这一行的「右栏」改成了一个不同的数 c2。当 Alice 计算出另一个 z2 之后，抽取器就完成了任务，通过下面的方程计算出 Alice 的私钥 sk：

Fiat-Shamir 变换 —— 从 Public-Coin 到 NIZK

不仅仅对于 Schnorr 协议，对于任意的 「Public-Coin 协议」，都可以用 Fiat-Shamir 变换来把整个协议「压缩」成一步交互，也就是一个非交互式的证明系统，这个变换技巧最早来自于 Amos Fiat 与 Adi Shamir 两人的论文『How to Prove Yourself: Practical Solutions to Identification and Signature Problems.』，发表在 1986 年的 Crypto 会议上[5]。也有一说，这个技巧来源于 Manuel Blum[6].

重复一遍，在 Public-coin 协议中，验证者 Bob 只做一类事情，就是产生一个随机数，然后挑战 Alice 。通过 Fiat-Shamir 变换，可以把 Bob 每一次的「挑战行为」用一次「随机预言」来代替。而在具体实现中，随机预言需要用一个具有密码学安全强度的 Hash 函数（不能随便选，一定要采用密码学安全的 Hash），而 Hash 函数的参数应该是之前所有的上下文输入。下面是一个示例图，大家可以迅速理解这个 Fiat-Shamir 变换的做法。

前面提到，在非交互式证明系统中，需要引入一个第三方来构建信任的「根基」，使得 Bob 可以完全相信由 Alice 所构造的证明。在这里，第三方就是那个「精灵」，用学术黑话就是「随机预言」（Random Oracle）。这个精灵并不是一个真实存在的第三方，而是一个虚拟的第三方，它同时存在于「现实世界」与「理想世界」。在「现实世界」中，精灵是一个负责任的安静美男子，而在「理想世界」中，它会被「模拟器」绑架。Public-Coin 协议还有一个好听的名字， 「Arthur-Merlin 游戏」 ……

看上图，左边的“白袍”就是 Merlin（魔法师梅林），中间拿剑的帅哥就是 King Arthur（亚瑟王），两个角色来源于中世纪欧洲传说——亚瑟王的圆桌骑士。Arthur 是一个不耐烦的国王，他随身携带一个硬币，而 Merlin是一个有着无限制计算能力的神奇魔法师，然后魔法师想说服国王相信某个「论断」为真，于是魔法师会和国王进行到对话，但是由于国王比较懒，他每次只会抛一个硬币，然后「挑战」魔法师，而魔法师需要及时应对，而且需要让国王在 k 轮之后能够相信自己的论断。由于 Merlin 有魔法，所以亚瑟王抛的硬币都能被 Merlin 看到[7]。这与我们在『系列一』中提到的交互式证明系统（Interactive Proof System，简称 IP）有些神似，但又不同。IP 由 Goldwasser，Micali 与 Rackoff（简称GMR）在 1985 年正式提出，它的证明能力覆盖很大一类的计算复杂性问题。而不同的地方在于：在 IP 的定义中，证明者 Prover 和 验证者 Verifier 都是可以抛硬币的图灵机，Verifier 可以偷偷抛硬币，并对 Prover 隐藏；而在 Arthur-Merlin 游戏中，国王只能抛硬币，不仅如此，而且抛硬币的结果总会被 Merlin 知道。但是，Fiat-Shamir 变换只能在「随机预言模型」下证明安全，而用 Hash 函数实现随机预言的过程是否安全是缺少安全性证明的。不仅如此，「随机预言模型」下安全的协议可能是有不安全的，已经有人找到了一些反例[8]；更不幸的是，S. Goldwasser 与 Y. Tauman 在 2003 年证明了 Fiat-Shamir 变换本身也是存在安全反例的[9]。但是这并不意味着 Fiat-Shamir 变换不能用，只是在使用过程中要非常小心，不能盲目套用。尽管如此，人们无法抵挡 Fiat-Shamir 变换的诱惑，其使用极其广泛。值得一提的是，最热的通用非交互零知识证明 zkSNARK 的各种方案中，Fiat-Shamir 变换比比皆是。比如大家可能耳熟能详的 Bulletproofs（子弹证明），此外还有一些暂时还不那么有名的通用零知识证明方案，比如 Hyrax，Ligero，Supersonic，Libra 等（我们后续会抽丝剥茧，逐一解读）。

小心：Fiat-Shamir 变换中的安全隐患

在 Fiat-Shamir 变换中，要尤其注意喂给 Hash 函数的参数，在实际的代码实现中，就有这样的案例，漏掉了 Hash 函数的部分参数：

比如在 A, Hash(A), B, Hash(B) 中，第二个 Hash 函数就漏掉了参数A，正确的做法应该是A, Hash(A), B, Hash(A,B)。这一类的做法会引入严重的安全漏洞，比如在瑞士的电子投票系统 SwissPost-Scytl 中，就在 Fiat-Shamir 变换的实现代码中多次漏掉了本来应该存在的参数，导致了攻击者不仅可以随意作废选票，还可以任意伪造选票，达到舞弊的目的[10]。因此在工程实现中，请务必注意。细心读者也许会回看一下 Schnorr 签名，大家会发现 Schnorr 签名中的 Hash 算法似乎也漏掉了一个参数 PK，并不是严格的 Fiat-Shamir 变换，这被称为 Weak Fiat-Shamir 变换[11]，不过这个特例并没有安全问题[3]，请未成年人不要随意模仿。最近一些学者开始在标准模型下研究如何严格证明 Fiat-Shamir 变换的安全性，目前要么引入额外的强安全假设，要么针对某个特定协议进行证明，但似乎进展并不大。

交互的威力

话说在1985年，当 GMR 三人的论文历经多次被拒之后终于被 STOC’85 接受，另一篇类似的工作也同时被 STOC'85 接受，这就是来自于匈牙利罗兰大学的 László Babai，与来自以色列理工的 Shlomo Moran 两人撰写的论文『Arthur-Merlin Games: A Randomized Proof System, and a Hierarchy of Complexity Classes』[7]，引入了 Public-coin 交互式协议（顾名思义，Verifier 只公开抛硬币）。

国王 Arthur 的方法很简单，通过反复地「随机」挑战来检验 Merlin 的论断，这符合我们前面讲述过的直觉：采用随机挑战来构建信任的「根基」。Babai 在论文中证明了一个有趣的结论：AM[k]=AM[2]，其中 k 表示交互的次数，交互多次产生的效果居然和交互两次等价。所谓交互两次是指：Arthur 发一个挑战数，然后 Merlin 回应。注：还有一类的问题属于 MA，这一类问题的交互顺序与 AM不同，MA中是 Merlin 先给出证明，然后 Arthur 抛硬币检验。已证明：MA 能处理的问题是 AM 的子集。不仅如此，Babai 还大胆猜测： AM[poly] 与 IP 是等价的。这是一个神奇的论断：国王很懒，他只需要通过抛多项式次硬币，就能成功挑战魔法师，而这种方式的表达能力居然完全等价于 GMR 描述的交互式证明系统 IP。果不其然，在 STOC'86 会议上，来自 S. Goldwasser 与 M. Sipser 的论文证明了这一点，AM[poly] == IP[12]。

这意味着：反复公开的「随机挑战」威力无穷，它等价于任意的交互式证明系统。但是 AM[poly] 和别的计算复杂性类的关系如何，是接下来的研究热点。三年后，1989 年11月底，距今恰好三十年，年轻的密码学家 Noam Nisan 发出了一封邮件，把自己的临时学术结论发给了几个密码学家，然后他就跑去南美洲度假了。可是他不曾想到，这一个邮件会引爆历史上一场激烈的学术竞赛，M. Blum, S. Kannan, D. Lipton, D. Beaver, J. Feigenbaum, H. Karloff, C. Lund 等等一大群精英开始加入战斗，他们没日没夜地互相讨论，并且竞相发布自己的研究成果，终于在12月26号，刚好一个月，Adi Shamir 证明了下面的结论：

AM[poly] == IP == PSPACE

它解释了「有效证明」这个概念的计算理论特征，并且解释了「交互式证明系统」这个概念所能涵盖的计算能力。注：NP 类 是 PSPACE 类的子集，前者大家比较熟悉，后者关联游戏或者下棋中的制胜策略[13]。而 L. Babai 于是写了一篇文章，名为「Email and the unexpected power of interaction」（电子邮件与交互的始料未及的威力）[14]，详细阐述了这一整个月在「邮件交互」中精彩纷呈的学术竞赛，以及关于「交互证明」的来龙去脉。

公共参考串 —— 另一种「信任根基」

除了采用「随机预言机」之外，非交互零知识证明系统采用「公共参考串」（Common Reference String），简称「CRS」，完成随机挑战。它是在证明者 Alice 在构造 NIZK 证明之前由一个受信任的第三方产生的随机字符串，CRS 必须由一个受信任的第三方来完成，同时共享给 Alice 和 验证者 Bob。是的，你没看错，这里又出现了「第三方」！虽然第三方不直接参与证明，但是他要保证随机字符串产生过程的可信。而产生 CRS 的过程也被称为「Trusted Setup」，这是大家又爱又恨的玩意儿。显然，在现实场景中引入第三方会让人头疼。CRS 到底用来做什么？Trusted Setup 的信任何去何从？这部分内容将留给本系列的下一篇。

未完待续

非交互式零知识证明 NIZK 的「信任根基」也需要某种形式的随机「挑战」，一种「挑战」形式是交给「随机预言精灵」；另一种「挑战」是通过 Alice 与 Bob 双方共享的随机字符串来实现。两种挑战形式本质上都引入了第三方，并且两者都必须提供可以让「模拟器」利用的「后门」，以使得让模拟器在「理想世界」中具有某种「优势」，而这种优势在「现实世界」中必须失效。NIZK 散发着无穷魅力，让我不时惊叹，在过去三十多年里，先驱们所探寻到的精妙结论，同时还有如此之多的未知角落，在等待灵感之光的照射。本系列文章在 Github 上的项目仓库收到了第一个 Pull Request，来自Jingyu Hu(colortigerhu)，只改了个把字，但那一瞬间，我感受到了生命力。知识交流，思想碰撞，很迷人，不是吗？

Everyone we interact with becomes a part of us.

与我们交往互动的每一个人都是我们自身的一部分。

—— Jodi Aman

致谢：特别感谢 丁晟超，刘巍然 ，陈宇的专业建议和指正，感谢安比实验室小伙伴们(p0n1, even, aphasiayc, Vawheter, yghu, mr)的修改建议。

致谢：自Nisan起密码学研究竞赛轶事参考自邓老师的文章[13]。

参考文献

[1] Schnorr, Claus-Peter. "Efficient signature generation by smart cards." Journal of cryptology 4.3 (1991): 161-174.

[2] Paillier, Pascal, and Damien Vergnaud. "Discrete-log-based signatures may not be equivalent to discrete log." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2005.[3] Pointcheval, David, and Jacques Stern. "Security arguments for digital signatures and blind signatures." Journal of cryptology 13.3 (2000): 361-396.[4] Maxwell, Gregory, Andrew Poelstra, Yannick Seurin, and Pieter Wuille. "Simple schnorr multi-signatures with applications to bitcoin." Designs, Codes and Cryptography 87, no. 9 (2019): 2139-2164. [5] Fiat, Amos, and Adi Shamir. "How to prove yourself: Practical solutions to identification and signature problems." Conference on the Theory and Application of Cryptographic Techniques. Springer, Berlin, Heidelberg, 1986.[6] Bellare, Mihir, and Phillip Rogaway. "Random Oracles Are Practical: a Paradigm for Designing Efficient Protocols."  Proc. of the 1st CCS (1995): 62-73.[7] László Babai, and Shlomo Moran. "Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes." Journal of Computer and System Sciences 36.2 (1988): 254-276.m[8] Canetti, Ran, Oded Goldreich, and Shai Halevi. "The random oracle methodology, revisited." Journal of the ACM (JACM)51.4 (2004): 557-594.[9] Shafi Goldwasser, and Yael Tauman . "On the (in) security of the Fiat-Shamir paradigm." 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.. IEEE, 2003.[10] Lewis, Sarah Jamie, Olivier Pereira, and Vanessa Teague. "Addendum to how not to prove your election outcome: The use of nonadaptive zero knowledge proofs in the ScytlSwissPost Internet voting system, and its implica tions for castasintended verifi cation." Univ. Melbourne, Parkville, Australia (2019).[11] Bernhard, David, Olivier Pereira, and Bogdan Warinschi. "How not to prove yourself: Pitfalls of the fiat-shamir heuristic and applications to helios." International Conference on the Theory and Application of Cryptology and Information Security. Springer, Berlin, Heidelberg, 2012.[12] Goldwasser, Shafi, and Michael Sipser. "Private coins versus public coins in interactive proof systems." Proceedings of the eighteenth annual ACM symposium on Theory of computing. ACM, 1986.[13]  Papadimitriou, Christos H. "Games against nature." Journal of Computer and System Sciences 31.2 (1985): 288-301.[14] Babai, László. "E-mail and the unexpected power of interaction." Proceedings Fifth Annual Structure in Complexity Theory Conference. IEEE, 1990.[15] Yi Deng. "零知识证明：一个略显严肃的科普."   https://zhuanlan.zhihu.com/p/29491567

导读：假如A要向B证明自己拥有某个房间的钥匙，该房间只能用钥匙打开锁，好处在于，在整个证明的过程中，B始终不能看到钥匙的样子，从而避免了钥匙的泄露。

 3. 产业动态

密码学如何为偿付能力提供保障

导读：零知识证明于 20 世纪 80 年代中叶提出。在过去的几年中，这一技术得到了突飞猛进的发展，已经应用于商业领域。

德勤企业区块链解决方案“ EduScrypt”引入零知识证明隐私技术

文 | 林中路

火星财经APP（微信：hxcj24h）一线消息，德勤近日与以色列科技初创公司QEDIT合作，为其企业区块链解决方案“EduScrypt”引入了隐私技术，以帮助企业跟踪，共享和验证员工身份，而无需透露任何潜在的机密信息。 

QEDIT是一家企业区块链隐私技术开发商，开发了零知识证明（ZKP）技术，帮助企业在共享账本环境中控制业务数据。采用零知识证明（ZKP）技术，可以让使用者能够证明其拥有秘密而不泄露秘密本身。目前，该技术在区块链领域的应用正在不断扩展，除了一些隐私币种（如Zcash）选择了零知识证明，一些商业区块链也在积极吸纳这种技术。

今年5月7日，QEDIT获得了由蚂蚁金服参投的1000万美元的投资，蚂蚁金服还将把QEDIT的零知识证明（ZKP）技术纳入其区块链项目。应用 QEDIT ZKP 的其他合作伙伴包括软件巨头 VMWare 和美国再保险集团的子公司 RGAX 等。

导读：通过采用隐私技术，德勤的企业区块链解决方案可以帮助企业跟踪，共享和验证员工身份，而无需透露任何潜在的机密信息。

与Coda 创始人谈话：零知识证明如何实现区块链减肥
 

区块链行业流行一句话「Don’t trust, verify」，然而实际上，并不是每个交易者都会亲自参与验证，因为验证者必须是一个全节点，而成为全节点成本并不低。新型加密货币协议 Coda 通过使用 ZK-SNARKs 零知识证明实现了一种人人可成全节点和验证人的加密货币网络。

采访 / 撰文：LeftOfCenter

每个人都在说区块链世界中的底层公链赛道缺乏创新的亮点，每个等待主网上线的公链新手都面临着巨大的挑战。你确定这样的信息是准确的？实际上，有不少新锐项目正在快速浮出水面，比如这个：今年 4 月，来自硅谷的区块链公司 O(1) Labs 获得了 1500 万美元融资，不乏明星风投机构付出真金白银，包括 Accomplice、Coinbase Ventures、Paradigm、General Catalyst 和 Dragonfly Capital。

那么，O(1) Labs 究竟有何独到之处能够获得这些区块链顶级风投的青睐？

事实上，O(1) Labs 的核心优势是旗下产品 Coda。作为一种新型的加密货币协议，它宣称可将区块链从几百 GB 压缩到只有几条推文的大小，从而以同等性能达到支持手机和浏览器运行全节点，最终为越来越臃肿的区块链「减肥」。

Coda 表示，之所以能实现这一点，得益于其核心技术优势，即使用 ZK-SNARKs 零知识证明压缩数据的解决方案。

也许你听过将 SNARK 技术应用于安全和隐私保护，但你可能不知道 SNARK 还能被用于数据压缩，而它的高级版「SNARK 递归组合」则可更加高效的为区块链减肥。ZK-SNARKs 零知识证明，原本是以一种隐私和安全实现为人所知，比如著名的安全隐私货币 Zcash 就是使用的该技术，然而，Coda 却将零知识证明用于数据压缩，最终实现区块链扩容和高度去中心化的加密网络。

以上这个介绍读起来就几句话，但是如若从根本解释清楚其原理及实现方式，却需要多篇世界顶级密码学家论文的解释和证明。

好在链闻记者近日在 Dragonfly Capital 于北京举行的 Dragonfly Capital Crypto Summit 上见到了 Coda 创始人兼 CEO Evan Shapiro。我们抓住了他，与他共同乘坐大巴车前往某一会议的途中，在北京拥堵的三环路上，用了 40 分钟时间，请 Evan Shapiro 用最简单易懂的语言，向链闻的读者说清楚：

• ZK-SNARKs 零知识证明的运作原理是什么？
• 零知识证明的高阶版 SNARK 递归组合到底是一种什么神奇的存在？
• 以及，为什么说「Snarketplace」零知识证明市集是 Coda 经济模型中最有意思的部分？

导读：Coda 通过使用 ZK-SNARKs 零知识证明实现了一种人人可成全节点和验证人的加密货币网络。

                                                                                                         来源：学习区块链