一文让你读懂什么是零知识证明(ZKP, Zero Knowledge Proofs)

西瓜妹 百科
2019-11-05 17:10:45

  

前言:零知识证明是一种特殊的交互式证明,其中证明者知道问题的答案,他需要向验证者证明“他知道答案”这一事实,但是要求验证者不能获得答案的任何信息。

 

来源:pixabay

 

当今密码学世界中最酷炫的一件事,莫过于那些优美又神秘的专有名词。“零知识”就是这样一个热词,受尽追捧。

 

可太过受欢迎也未必是件好事,俗话说,人怕出名猪怕壮,因为“零知识”的概念如此吸引眼球,以至于导致了许多的错误理解和误用。许多人将零知识和“非常非常安全”划上了等号,还将它与加密系统或匿名网络联系起来——这些东西实上与真正的零知识协议毫无关系。

 

零知识证明是密码学家设计出来的最强大的工具之一,但同时,理解它的人也不多。今天,我将试着以通俗易懂的表达方式来介绍什么是“零知识证明”,并解释到底是什么让它如此特别。

 

一、零知识的起源

在上世纪80年代初,“零知识”的概念最早由麻省理工学院的研究人员 Shafi Goldwasser, Silvio Micali和Charles Rackoff 所提出。当时他们正在研究与交互证明系统相关的问题,这系统使得甲方(证明者)可以和乙方(验证者)交换信息,并借此说服乙方接受(通过验证)某个数学论述为真 。

 

Shafi Goldwasser, Silvio Micali and Charles Rackoff  |  维基百科、IACR

零知识证明这个问题不是单纯的理论思考,而是在真实、具体的应用中,会面到临的问题。

 

我举个例子,在现实生活中,大家用账号密码的方式登录微信、微博等社交软件时,在输入密码后,APP会把你的密码发送给服务器(当然,这里应该会加密后再发送的),然后和服务器中的密码进行比对,一样的话,就可以成功登陆了。

 

可这里有个问题。大家发现了吗?实际上,服务器知道我们的密码。

 

大多数系统就是以这样糟糕的方式进行“证明”的,因此,如何保障密码安全呢?可能只有祈祷服务器不会遭受攻击了。


二、一个“真实世界”的案例

上面那样讨论,可能还比较抽象。为了让大家能有更具体的概念,现在我们举个“真正的”零知识证明例子。请大家配合我想象一下,现在我是一个电信业巨头,跟随“一带一路”,积极参与到非洲地区的电信网络建设中来。现在我要部署一个新的蜂窝电信网络。(这里我还是解释一下为什么叫蜂窝网络吧。大家看下面第一张图,是移动网络拓扑图,有没有很像下边的蜂窝呢?对!名字就是这样来的)

 

蜂窝网络  作者:Mozzerati  |  维基百科

https://zh.wikipedia.org/wiki/%E8%9C%82%E7%AA%9D%E7%BD%91%E7%BB%9C#/media/File:Frequency_reuse.svg

 

真正的蜂窝 作者:umsiedlungen  |  Pixabay

 

而今天为了方便讲述,把网络架构图这样展示,如下。图中的每个顶点代表一个无线电塔,每一条连线代表无线电塔信号两两重叠的区域,这意味着连线上的信号会互相干扰。(相邻两个电塔(小区),信号频率相同,产生的同信道干扰)。

 

为了避免这样的干扰,在设计网络架构时,我就想到了用三种不同的频率来部署。

不过现在,我有了新的挑战!这个挑战来自我该如何部署不同的频率,使得相邻的每两个电塔不具有相同频率。我们现在用不同颜色来表示不同频率,可以很快找到一种解决方案如下图所示。

 

可能有很多了解过的朋友已经发现,我刚才讲的就是著名的算法问题——三色问题。大家也就知道,这个问题有趣的地方在:某些非常庞大的网路中,我们很难找到解,甚至连证明问题有解都办不到。

如果只是上面给的这种示例图,我们用手就能轻松找出解。但如果今天我的无线通信网络规模特别复杂而庞大,我以我所能调配的计算资源都无法找到解答的情况下,我该怎么办?我还可以把这个问题“外包”给拥有更庞大算力的人呀!比如去找谷歌帮忙啊。


但这又会导致一个问题。谷歌找到了有效着色方法,因此耗费了大量的算力。不过在我得到有效方法之前,我是不打算付钱的。同样,谷歌在收到钱之前,也不会愿意给我着色方法的副本的。以此,我们双方陷入了僵局。(这里不讨论现实中情况,毕竟律师和账户托管可以解决。但我们今天是来表述密码学的,所以解决困境,需要疯狂一点的技术手段。)

 

三、一种疯狂的技术手段

现在有一个大仓库、大量的蜡笔和纸张。哦,对了,还得有C位选手——帽子!

下面是运作原理。

1、我进入仓库,在地板上铺满纸张,并在空白的纸上画出电塔图;

2、谷歌工程师进来,蜡笔中随机选三种颜色,然后照着他们已经算出来的解决方案进行着色(颜色不重要,方案有效就行)。着色完成后,每个纸上的电塔用帽子盖住,然后离开仓库。

我回到仓库,看到下图。很显然,谷歌的方案我是看不出来的,我也不知道他们的方案是否有效。

为了消除我的疑虑,谷歌工程师告诉我,可以随机选择其中一条线,然后要求他们揭开对应的帽子,这样我就能看到他们着色方案的一小部分了。如下所示。

谷歌工程师方案没问题的话,这两种颜色一定是不相同的。但我这时候会想,万一只是碰巧呢?在目前条件下谷歌仍有很大的可能是给了我一个无效的着色方案。假设一共有X条边,在仅仅是经过以此揭开帽子的观察后,我仍有高达 (X-1)/X 的概率被骗。

 

好了,谷歌也不想浪费了大量算力的方案,却得不到付款。就让我再一次,重新进行观察。

刚刚的运作原理,谷歌工程师再按照方案做一遍,只是蜡笔的颜色,换了。

 

我这时候再随机选择一条线,然后谷歌工程师揭开帽子,进行验证。这次情况会好些,我对他们有了更多的信心,但骗我的概率依然存在,概率为 [(X-1)/X]* [(X-1)/X](在1000条线的情况下,大约有99.8%的可能性,还是比较高。)

 

不过好在,这个挑战可以一直进行下去,不断重复以上操作,直到我们相信为止。

 

不过还是别这样了,太麻烦了,这时候还是写段代码来验证以上逻辑更加方便。事实上,我被骗的概率是一直存在的,但我可以把这概率降低到一个程度(进行X^2次挑战),那时候,谷歌只剩下微不足道的概率可以骗我,这概率低到我大可以放心付款。

 

 

在这整个过程中,不只有我需要保护,谷歌也需要。所以,在我进行“无数次”挑战时(随机选出一条线来验证的过程),我是无法推敲谷歌耗费了大量的算力得出的着色方案的,因为每次验证后,他们都会换三种颜色。我获得的信息,对我来说,毫无帮助,每次挑战的结果也无法被串联起来。这就是零知识证明。

 

四、零知识证明特性

零知识证明有三个特性,任何零知识都必须满足。简单来说:

1、完整性(Completeness)。如果谷歌说的真话,那么他们最终能说服我(至少让我相信可能性非常高)。

2、安全性(Soundness)。只有当他们说的是真话时,谷歌才有可能说服我。

3、零知识性(Zero-knowledgeness)。我无法从中获得任何关于谷歌解决方案的信息。

 

 

五、区块链上的零知识证明

比特币和以太坊都是用公共地址来代替当事方的真实身份,使交易部分匿名,公众只知道发送和接收的地址以及交易的数量。然而,可以通过区块链上可用的各种信息(如交互记录)找出地址的真实身份,因此存在暴露隐私的可能。

 

零知识证明,可以在发送方、接收方和其他交易细节都保持匿名的情况下,保证交易有效。

 

ZCash可能是成功实现零知识证明的最著名的区块链项目之一。Zcash实现了ZKP的修改版本,被称为zk-SNARKS,代表Zero-Knowledge Succinct Non-Interactive Argument of Knowledge(零知识简明非交互式知识证明)。具体技术细节,大家可以自行查看哦。

 

关于零知识证明,还有一个非常经典的例子,可以更好的帮助大家理解:阿里巴巴被强盗抓住,为了保命,他需要向强盗证明自己拥有打开石门的口令,同时又不能把密码告诉强盗。他想出一个解决办法,先让强盗离开自己一箭之地,距离足够远让强盗无法听到口令,足够近让阿里巴巴无法在强盗的弓箭下逃生。如果强盗举起左手,阿里巴巴就使用口令将石门打开,如果举起右手,就将石门关闭。阿里巴巴就在这个距离下向强盗展示了石门的打开和关闭。如果每次都能正确打开和关闭大门,则证实阿里巴巴确实知道石门的密码。

 

这个整个过程就是零知识证明,即证明者能够在不向验证者提供任何有用信息(石门的口令)的情况下,使验证者相信某个论断(阿里巴巴知道打开石门的方法)是正确的。

 

好了,关于零知识证明就说到这里了,全文试着用两个例子来试图向大家说明什么是零知识证明,希望大家看了之后,能对零知识证明有一定了解。

 

 

延伸阅读

The Incredible Machine(来自:Medium  作者:Aviv Zohar)

https://medium.com/qed-it/the-incredible-machine-4d1270d7363a

 

参考

1、A Few Thoughts on Cryptographic Engineering(Matthew Green,约翰·霍普金斯大学的密码学家、教授)

https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/

2、A Few Thoughts on Cryptographic Engineering, Part 2(Matthew Green,约翰·霍普金斯大学的密码学家、教授)

https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2/

3、一文读懂区块链中的零知识证明(BFTF技术社区联盟)https://www.odaily.com/post/5133827


本文地址: https://www.xiguacaijing.com/news/baike/2019/15642.html
声明:本文经授权发布,除注明来源外,均为西瓜财经用户投稿,不代表西瓜财经立场。转载请注明:西瓜财经(xiguacaijing.com)
提醒:投资有风险,入市需谨慎。若内容涉及投资建议,仅供参考勿作为投资依据。谨防以“区块链”名义进行非法集资。
赞助商