读心术：从零知识证明中提取「知识」——探索零知识证明系列(3)

给任意一个有限域上的整数 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的计算和验证过程很有趣，有几个关键技巧：
首先 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必须是个随机数。Bob 验证是在椭圆曲线群上完成。Bob 不知道r，但是他知道r映射到曲线上的点R；