Zero-knowledge Proof,是一种神奇的非传统知识证明系统,在区块链和安全领域被认为有应用的前景。除了一些基于加密方法的证明系统,ZKP还有一些非常巧妙的交互式证明场景。

Introduction

零知识证明的核心在于:如何在不向验证者提供有关证明本身的任何信息的前提下,向验证者证明你所阐述的断言(可以是一个数学定理,也可以是你的任何论断)?这一需求在数据隐私方面可能是越来越重要的——很多服务需要提供一些凭证,但我们只想告诉别人“我们拥有数据”,而不是分享这些数据本身。

“零知识”是指证明者在向验证者证明断言的时候,除了让验证者信服“断言为真”意外,不提供给验证者任何额外信息——验证者甚至不能在接受证明的过程中获得任何与断言有关的信息(甚至是其他任何信息?),也更加不能独自复现证明——这和传统的数学证明系统是不同的。零知识证明在一些场景中已经使用了很久:法庭上的实现“XX证明”(不在场证明?)在庭审和被告之间的问答,就比较类似零知识证明:想要通过非直接的方式让他人信服,被告就必须要持续地回答询问——如果他在说谎,那么很快他就会露出马脚。在交互式证明中,用到的就是这种思想:设计一个交互规则,一个并不真的拥有证明的人在这个规则下以一定的概率被揭穿,那么我们就可以通过多次进行这样的交互来让我们的“信服程度”达到任意的高度。

那问题就来了,如果我有办法能够揭穿说谎者,我为什么不直接问一些说谎者一定不能回答的问题?我的理解(可能是错的)是:允许蒙混过关阻止了验证者从交互中提取(必然的)知识。如果验证者提出的问题说谎者一定无法回答,那么验证者就能从证明者的回答中提取与论断有关的知识——而允许验证发生遗漏则打断了这种必然的联系,因为在传统证明系统看来,这些有漏洞的提问并不说明任何(必然的)知识,也不能说明通过者一定拥有证明——尽管这一概率可以无限地小。

Examples

The Cave of AliBaba

最经典的例子,如图[1]。Bob向Alice证明自己拥有一个门的钥匙——这个门处在一个“口”型迷宫的中间,不能被外面的人看到。Bob并不想透露给Alice任何有关钥匙的信息,于是他可以这样向Alice进行证明:Alice站在出口处,每次随机指定迷宫两侧的一侧出口,让Bob从Alice指定的出口出来。而Bob则可以同样随机地从一侧出口进去,不过必须要从Alice指定的一侧出来。如果Bob真的有钥匙的话,他应该可以随意地通过任意多次这样的测试——尽管他并不是每次测试都需要用到钥匙,如果Bob和Alice选择了同一个方向的话(因此每次蒙混过关的概率都为50%)。

alibaba

Red-Green Color Blindness

如何向一个红绿色盲证明一个绿球和一个红球实际上是不同的?这和上一个例子其实差不多,让红绿色盲双手分别持绿球和红球,背到身后去(不让验证者看到)。之后他随机地选择交换双手上的球,或者不交换球,然后让一个正常人回答两个球是否被色盲交换了——因为正常人很容易就能区分两个球,因此也就能准确地看出色盲的选择。虽然色盲可能认为正常人是以50%的概率猜的,不过我们可以不断重复这一过程来说服色盲两个球是不同的。

A Homework Problem

一个难一些的问题。

Suppose that n is the product of two large primes, and that s is given. Peggy wants to prove to Victor, using a zero knowledge protocol, that she knows a value of x with $x^2 = s$ mod n. Peggy and Victor do the following:

  1. Peggy chooses three random integers $r_1, r_2, r_3$ with $r_1r_2r_3$ = x mod n.
  2. Peggy computes $x_i = r_i^2$, for i = 1, 2, 3 and sends $x_1, x_2, x_3$ to Victor.
  3. Victor checks that $x_1x_2x_3 = s$ mod n.

Design the remaining steps of this protocol so that Victor is at least 99% convinced that Peggy is not lying.

Google上还有一些简化的问题,例如只有$x_1, x_2$的情况。直接思考交互证明过程比较困难,其实可以直接考虑:如果Peggy并没有这个s在模n下的根x,她要怎么在这个机制中作弊?

为了实现“零知识”,这一机制产生了$x_i$,使得Victor每次都能够验证乘积是否为s。因为模数下求根的困难性,他并不能知道与$r_i$和x有关的信息。作为这一结果的代价,Peggy是可以作弊的:她可以根本没有所有的$r_i$和x,而是直接构造出给Victor验证用的$x_i$,例如随机产生两个$r_i, r_j$以及它们的平方$x_i, x_j$ mod n,然后求逆元直接解出第三个$x_k$,使得$x_k=(x_ix_j)^{-1}s$ mod n。

因此剩余的验证过程也就清楚了:Victor从三个$x_i$中随机抽取两个,询问它们的根$r_i$,然后验证关系$r_i^2 = x_i$。Victor当然不能三个值都问,不然他就计算出x的值了。因为模数下求根的困难性,Peggy不能获得$x_k$对应的根$r_k$——于是她只能祈祷Victor提问的时候没有问到这个凑出来的$r_k$,不过这一概率只有$\frac{1}{3}$。因此重复这一过程,很快Victor就能够得到满意的结果。