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
复制代码
的计算和验证过程很有趣，有几个关键技巧：
首先 Bob 必须给出一个「随机」挑战数，然后 Bob 在椭圆曲线上同态地检查
z
复制代码
。如果我们把挑战数
c
复制代码
看成是一个未知数，那么
r+a*c=z
复制代码
可以看成是一个一元一次方程，其中
r
复制代码
与
a
复制代码
是方程系数。请注意在
c
复制代码
未知的前提下，如果
r + a*x = r' + a'*x
复制代码
要成立，那么根据 Schwatz-Zippel 定理，极大概率上
r=r'
复制代码
，
a=a'
复制代码
都成立。也就是说， Alice 在
c
复制代码
未知的前提下，想找到另一对不同的
r'
复制代码
,
a'
复制代码
来计算
z
复制代码
骗过 Bob 是几乎不可能的。这个随机挑战数
c
复制代码
实现了
r
复制代码
和
a
复制代码
的限制。虽然 Bob 随机选了一个数，但是由于 Alice 事先不知道，所以 Alice 不得不使用私钥
a
复制代码
来计算
z
复制代码
。这里的关键：
c
复制代码
必须是个随机数。
Bob 验证是在椭圆曲线群上完成。Bob 不知道
r
复制代码
，但是他知道
r
复制代码
映射到曲线上的点
R
复制代码
；Bob 也不知道
a
复制代码
，但是他知道
a
复制代码
映射到曲线群上的点
PK
复制代码
，即
a*G
复制代码
。通过同态映射与Schwatz-Zippel 定理，Bob 可以校验
z
复制代码
的计算过程是否正确，从而知道 Alice 确实是通过
r
复制代码
和
a
复制代码
计算得出的
z
复制代码
，但是又不暴露
r
复制代码
与
a
复制代码
的值。
还有，在协议第一步中产生的随机数
r
复制代码
保证了
a
复制代码
的保密性。因为任何一个秘密当和一个符合「一致性分布」的随机数相加之后的和仍然符合「一致性分布」。
证明零知识
我们这里看一下 Schnorr 协议如何证明一个弱一些的「零知识」性质—— Special Honest Verifier Zero-Knowledge「SHVZK」：
SHVZK 要求协议中的 Bob 的行为不能不按常理出牌，比如他必须按协议约定，在第二步时，去传送带上取一个新鲜的随机数，并且立即使用。而通常意义上的「零知识」是不会对 Bob 做任何要求，所以我们说这里是一个弱一些的性质。虽然目前 Schnorr 协议不能证明完全的「零知识」，但经过添加一些协议步骤，就可以达到完全零知识的目的，细节这里不展开。以后我们在讨论 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 的知识，但是让对方「无所察觉」。
当年 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 系统中，随机数被不明所以的工程师写成了一个固定不变的值，这样相当于直接赋予了黑客「超能力」，而这是在「现实世界」中。或者说，黑客在不需要「时间倒流」的情况下就能实现「抽取器」。
转播
