摘要:本文开篇通过3个通俗易懂的例子,来介绍零知识证明的概念,同时介绍零知识证明的一般过程。然后,阐述分析零知识证明的特点和分类。

一、3个零知识证明例子

1、万圣节糖果

       故事是这样的,万圣节到来,Alice和Bob分别领取到了一定数量的糖果。但是他们很想他们是否收到了相同数量的糖果,但是又不想让对方知道自己收到了几个糖果,因为如果对方发现自己的糖果数量多了的话就要跟对方分享,所以不能泄露自己糖果数量。

现在我们假设,他们袋子里可能装有10、20、30个或40个糖果。

        这时Bob想了个办法,为了比较他们拥有的糖果数量,Bob拿到4条钥匙和盒子,盒子上分别写上10、20、30、40分别对应糖果的数量。Bob最后只保留了自己糖果数量跟盒子数字一样的钥匙,其他3把钥匙就丢了(假设Bob只保留了写着20的盒子的钥匙)。

        然后,这个时候,Alice在4张纸上,其中一张写上“+”,另外三张写上“-”。然后,把写有“+”的纸张放到跟自己糖果数量是相同数字的盒子里,其余纸张放到其他盒子(假设Alice把“+”放到写着30的盒子)。这时候,Bob回来后用手上的钥匙打开写着20的盒子,看里面放的纸张写着是“+”还是“-”。

  • 如果纸张上写着“+”,说明两个人的糖果数量一致
  • 如果纸张上写着“-”,说明两个人糖果数量不一致,但是不知道对方的具体糖果数量。

        这里Bob看到纸张上写着“-”,这意味着两人的糖果数量不一样,但是Bob无法知道Alice的糖果数量。这时候,Alice看到Bob手上拿着一张写“-”的值,那她也知道两人的糖果数量不一样,但是也无法知道对方拥有糖果的数量。

这个过程就是一个零知识证明。

2、洞穴

        接下来,我们看另一个更经典的洞穴例子,如下图所示。

        R和S之间存在一道密门,并且只有知道咒语的人才能打开。Peggy知道咒语并想对Victor证明,但证明过程中不想泄露咒语。他该怎么办呢?

1)首先Victor走到P,Peggy走到R或者S。

2)Victor走到Q,然后让Peggy从洞穴的一边或者另一边出来。

3)如果Peggy知道咒语,就能正确地从Victor要求的那一边出来。

        Victor重复上述过程很多次,直到他相信Peggy确实知道打开密门的咒语为止。

        在这里,Peggy是证明方,Victory是验证方。Peggy通过上述方法证明了自己确实知道咒语,但是没有像Victory透露任何咒语的相关信息,这一过程也就是零知识证明。

3、数独

        第三个例子,我们介绍一个数独游戏。我们知道数独是一种逻辑性的数字填充游戏,玩家必须以数字添进每一格,而每行、每列和每个宫(即3×3的大格)有1至9所有数字,且不重复。游戏设计者会提供一部分数字,使得谜题只有一个答案,如下图所示。

        下面,我们也设计一个九宫格谜题,同时向其他人证明我们拥有这个谜题的答案,但是不告诉其他人具体答案的信息

        下面,我们用扑克牌上的1-9表示数字,并画一个9×9的九宫格,如下图所示。

        然后,我们在九宫格上正面向上放一部分数字(扑克牌上的数字),接下来,我们就开始向其他人证明,我们确实有这个九宫格谜题的答案,但是不想对方透露任何信息。

        接下来,我们把自己知道的九宫格答案的数字分布,分别选取对应的扑克牌(数字相同),然后背面向上放置在对应的位置上(对方无法看到数字),如下图所示。

        接下来,我们把每一列的扑克放到一起,如下图,然后把扑克牌顺序打乱。

        同样的,我们把每一行的扑克放到一起,如下图,同样也把扑克牌顺序打乱

        最后,我们把3×3大格里的扑克放到一起,如下图,同样也把扑克牌顺序打乱。

        最终,我们得到如下图的27个扑克牌集合。这时候让对方检查,他会发现,每一份的扑克牌里面数字都是1-9没有重复,也就是说,满足了数独的答案要求。而我们也在没有告诉对方数独答案的情况下,证明了自己已经拥有数独的谜题答案。

二、零知识证明概念

        上面,我们用3个通俗易懂的例子介绍了零知识证明的概念。下面,我们用正式介绍零知识证明。

        零知识证明(Zero—Knowledge Proof),是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。它指的是证明者能够在不向验证者提供任何有用的信息的情况下,使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议,即两方或更多方完成一项任务所需采取的一系列步骤。证明者向验证者证明并使其相信自己知道或拥有某一消息,但证明过程不能向验证者泄漏任何关于被证明消息的信息。大量事实证明,零知识证明在密码学中非常有用。如果能够将零知识证明用于验证,将可以有效解决许多问题。

三、零知识证明的一般过程

        证明方和验证方拥有相同的某一个函数或一系列的数值。零知识证明的一般过程如下:

1)证明方向验证方发送满足一定条件的随机值,这个随机值称为“承诺”。

2)验证方向证明方发送满足一定条件的随机值,这个随机值称为“挑战”。

3)证明方执行一个秘密的计算,并将结果发送给验证方,这个结果称为“响应”。

4)验证方对响应进行验证,如果验证失败,则表明证明芳不具有他所谓的“知识”,退出此过程。否则继续从1)开始,重复执行这个过程t次。

        如果每一次验证方都验证成功,则验证方就相信证明方拥有某种知识。而且此过程中,验证方没有得到关于这个知识的任何一点信息。

 

四、零知识证明的特点

        根据零知识证明的定义和有关例子,可以得出零知识证明具有以下三个特点

1)完备性。如果证明方和验证方都是诚实的,并遵循证明过程的每一步,进行正确的计算,那么这个证明一定是成功的,验证方一定能够接受证明方。

2)合理性。没有人能够假冒证明方,使这个证明成功。

3)零知识性。证明过程执行完之后,验证方只获得了“证明方拥有这个知识”这条信息,而没有获得关于这个知识本身的任何一点信息。

 

五、零知识证明分类

        到目前为止,具有应用前景的零知识证明工具可以分类两类:

  • 一类证明慢、验证快、证明体积小
  • 另一类证明快、验证快、证明体积小大

        第一类由于验证快,不占用空间的特点,很快得到区块链开发者的青睐,同时随着ZCash的迅速传播,其使用的zk-SNARKs协议也越来越受关注。

        第二类证明快的特点使得其在移动设备,嵌入式设备的部署成为可能,而隔离见证等技术有望缓解其证明体积较大的问题,在区块链领域的也是前途无量。

关注我的微信公众号(shuwoom的博客),每周定期推送文章:

打赏

发表评论

电子邮件地址不会被公开。