Schnorr 协议

引用：https://zhuanlan.zhihu.com/p/80104796

模拟条件

通常，我们定义安全会采用这样一种方式，首先列出一些安全事件，然后说明：如果一个系统安全，那么列出来的安全事件都不会发生。但是零知识证明并不是通过给出一个不允许发生的事件列表来定义，而是直接给出了一个最极致的模拟条件。所谓模拟条件是指，通过模拟方法来实现一个理想世界，使之与现实世界不可区分；而由于在理想世界中不存在知识，所以可以推导出结论：现实世界满足零知识。

模拟器能模拟出一个和现实世界外表一模一样的理想世界，然后模拟器在这个世界中可以轻松地骗过任何一个对手，让对方无法分辨自己是在现实世界中，还是理想世界中。因为模拟器手里没有那个秘密 w，理想世界是零知识的。又因为两个世界的不可区分性，所以我们可以得出结论：Alice 的交互协议是零知识的。

零知识证明的属性

任何零知识证明都必须满足的三个关键属性：

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

可靠性和完备性有一种对称性。可靠性保证了恶意的 Alice 一定失败，而完备性保证了诚实的 Alice 一定成功。

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

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

如何证明 Alice 知道一个秘密？

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

简洁的 Schnorr 协议

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

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

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

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

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

第三步：Alice 根据挑战数计算 z=r+c*SK=r+c*a，同时把 z 发给 Bob。 Alice\stackrel{z}{\longrightarrow}Bob

第四步：Bob通过下面的式子进行检验： z*G ?= R + c*PK = rG + c*(aG)

如果这个式子成立，那么就能证明 Alice 确实有私钥 a 。可是，这是为什么呢？

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

1. 首先 Bob 必须给出一个随机挑战数，然后 Bob 在椭圆曲线上同态地检查 z 。如果我们把挑战数 c 看成是一个未知数，那么 z=r+c*a 可以看成是一个一元一次方程，其中 r 与 a 是方程系数。请注意在 c未知的前提下，如果 r+c*x=r'+c'*x 要成立，极大概率上 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」：SHVZK 要求协议中的 Bob 的行为不能不按常理出牌，比如他必须按协议约定，在第二步时，去传送带上取一个新鲜的随机数，并且立即使用。而通常意义上的零知识是不会对 Bob 做任何要求，所以我们说这里是一个弱一些的性质。

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

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

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

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

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

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

第五步：Bob通过下面的式子进行检验：z*G ?= R' + c*PK = z*G-c*PK+c*PK

注意：Bob不能区分它在现实世界中还是在理想世界中，而在理想世界中Alice是零知识的，而现实世界和理想世界不可区分，所以现实世界也是零知识的。

可靠性证明

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

再次求助模拟器，让他在可以发挥超能力的理想世界中，去检验 Alice 的知识。设想在平行宇宙中，有两个世界，一个是叫做理想世界，另一个叫做现实世界。理想世界有趣的地方在于它是被模拟器模拟出来的，同时模拟器可以在理想世界中放入带有超能力的 NPC。这次把 Alice 的两个分身同时放入理想世界与现实世界。

假设你扮演 Bob 的角色，你想知道和你对话的 Alice 是否真的是可靠的。 于是把你放入理想世界，借助一个具有超能力的 NPC，你可以把对面的 Alice 的知识抽取出来。可以想象一下，一个作弊的 Alice，她肯定没有知识，没有知识也就不可能在理想世界中让 NPC 抽取到任何东西。然而在现实世界中，你无法借助 NPC，当然也就看不到 Alice 的知识，也就不会和零知识性质冲突。因为两个世界发生的事件是不可区分的，我们可以得到这样的结论：在现实世界中，Alice 一定是存在知识的。

我们需要为这个交互会话定义一个模拟算法，该算法可以模拟出一个理想世界，其中有一个特殊的角色叫做抽取器(Extractor)，也就是我们前面说的 NPC，它能够通过超能力来抽取Alice 的知识，但是让对方无所察觉。

我们来证明一下 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 的认证方案:

第一步：Alice 仍然是选择一个随机数 k ，并将 k 映射到椭圆曲线上，得到点 K，然后发送给 Bob。Alice\stackrel{K=k*G}{\longrightarrow}Bob

第二步：Bob 需要产生两个随机数，c 和 e，然后交给 Alice。 Alice\stackrel{(c,e)}{\longleftarrow}Bob

第三步：Alice 计算 s，s=(c+SK*e)/k=(c+a*e)/k 并且发送给 Bob，他来验证 s 的计算过程是否正确。s*K?=c*G+e*PK

如果 Alice 在两次交互过程中使用了同一个 K ，那么 Bob 可以通过发送两个不同的 c 和 c'， 来得到 s 和 s' :

然后通过下面的公式算出私钥 a ：

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

请注意，这并不是 Schnorr 协议（或 ECDSA 协议）的设计缺陷，恰恰相反，这是 Schnorr 协议设计比较精巧的地方，它从原理上保证了协议的可靠性。

非交互式零知识证明

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

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

回顾 Schnorr 协议

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

如何把一个三步的 Schnorr 协议变成一步。

看一下 Schnorr 协议的第二步，Bob 需要给出一个随机的挑战数 c，这里我们可以让 Alice 用下面这个式子来计算这个挑战数，从而达到去除协议第二步的目的。 c = Hash(PK, R)

第一步，Alice选取一个随机数 r，这个随机数需要映射到椭圆曲线群上，rG。计算 c 和 z=r+c*a。Alice\stackrel{(R,z)}{\longrightarrow}Bob

第二步，Bob计算 c ，通过下面的式子进行检验：z*G ?= R + c*PK = rG + c*(aG)

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

1. Alice 在产生承诺 R 之前，没有办法预测 c，即使 c 最终变相是 Alice 挑选的。
2. c 通过 Hash 函数计算，会均匀分布在一个整数域内，而且可以作为一个随机数。

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

Schnorr 签名方案

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

我首先要证明我的身份，那么这个简单，这正是 Schnorr 协议的功能，能够向对方证明我拥有私钥这个陈述。并且这个证明过程是零知识的：不泄露关于私钥的任何知识。

注意：m为信息。

第一步，Alice选取一个随机数 r，这个随机数需要映射到椭圆曲线群上，rG。计算 c=hash(m,R) 和 z=r+c*a。 Alice\stackrel{(c,z)}{\longrightarrow}Bob

第二步，Bob计算 R'=z*G-(c*PK) ，通过下面的式子进行检验：c?=hash(m,R') 。

在这里还有一个优化，Alice 发给 Bob 的内容不是 (R,z)，而是 (c,z) ，这是因为 R 可以通过 c , z 计算出来。

而采用 Hash 函数的方法来把一个交互式的证明系统变成非交互式的方法被称为 Fiat-Shamir 变换。

随机预言机（Random Oracle）

在 Schnorr 签名方案中，Hash 函数担负起了挑战者的角色，这个角色有一个非常学术的名字：随机预言机（Random Oracle。

为什么用的是 Hash 函数呢？这是因为在现实世界中，真正的随机预言机不存在！为什么呢？ 事实上，一个 Hash 函数不可能产生真的随机数，因为 Hash 函数是一个确定性算法，除了参数以外，再没有其它随机量被引入。

而一个具有密码学安全强度的 Hash 函数似乎可以充当一个伪随机预言机。那么合并后的安全协议需要额外增加一个很强的安全假设，这就是：假设：一个密码学安全的 Hash 函数可以近似地模拟传说中的随机预言机。

因为这个假设无法被证明，所以我们只能信任这个假设，或者说当做一个公理来用。插一句， Hash 函数的广义抗碰撞性质决定了它的输出可以模拟随机数，同时在很多情况下（并非所有），对 Hash 函数实施攻击难度很高，于是许多的密码学家都在大胆使用。

零知识证明

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

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

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

先考虑下构造一个理想世界来证明零知识。在理想世界中，模拟器绑架了负责提供预言的精灵，当 Bob 向精灵索要一个随机数的时候，精灵并没有给一个真随机数，而是给 Zlice（模拟器假扮的 Alice）提前准备好的一个数（也符合一致性分布，保证不可区分性），精灵无可奈何地返回 Bob 一个看起来随机，但实际上有后门的数字。所谓后门，就是这个数字是 Zlice 自己提前选择好的。

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

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

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

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

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

已经证明了模拟器 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 变换来把整个协议压缩成一步交互，也就是一个非交互式的证明系统。在 Public-coin 协议中，验证者 Bob 只做一类事情，就是产生一个随机数，然后挑战 Alice 。通过 Fiat-Shamir 变换，可以把 Bob 每一次的挑战行为用一次随机预言来代替。

而在具体实现中，随机预言需要用一个具有密码学安全强度的 Hash 函数（不能随便选，一定要采用密码学安全的 Hash），而 Hash 函数的参数应该是之前所有的上下文输入。下面是一个示例图，大家可以迅速理解这个 Fiat-Shamir 变换的做法。

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

除了采用「随机预言机」之外，非交互零知识证明系统采用「公共参考串」（Common Reference String），简称「CRS」，完成随机挑战。它是在证明者 Alice 在构造 NIZK 证明之前由一个受信任的第三方产生的随机字符串，CRS 必须由一个受信任的第三方来完成，同时共享给 Alice 和 验证者 Bob。

是的，你没看错，这里又出现了「第三方」！虽然第三方不直接参与证明，但是他要保证随机字符串产生过程的可信。而产生 CRS 的过程也被称为「Trusted Setup」，这是大家又爱又恨的玩意儿。