作者：郭宇    安比实验室

本文已更新至Github

https://github.com/sec-bit/learning-zkp/blob/master/zkp-intro/4/zkp-rom.md

“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 用下面这个式子来计算这个挑战数，从而达到去除协议第二步的目的。

c = Hash(PK, R)

其中 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 的过程：

m = "白日依山尽，黄河入海流"

c = Hash(m, R)

这里为了保证攻击者不能随意伪造签名，正是利用了离散对数难题（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 算法， 请大家记住他们的算法复杂度大约都是 ​[3]，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[4]，可以实现更灵活地支持多签和聚合。

而采用 Hash 函数的方法来把一个交互式的证明系统变成非交互式的方法被称为 Fiat-Shamir 变换[5]，它由密码学老前辈 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 自己提前选择好的。