freeBuf
主站

分类

漏洞 工具 极客 Web安全 系统安全 网络安全 无线安全 设备/客户端安全 数据安全 安全管理 企业安全 工控安全

特色

头条 人物志 活动 视频 观点 招聘 报告 资讯 区块链安全 标准与合规 容器安全 公开课

官方公众号企业安全新浪微博

FreeBuf.COM网络安全行业门户,每日发布专业的安全资讯、技术剖析。

FreeBuf+小程序

FreeBuf+小程序

零知识证明是零信任吗?
2021-08-04 13:43:11

如果只是为了回答标题问题,两个字就可以:不是

但还是想顺便说说,零知识证明(ZKP)究竟是什么。

虽然零知识证明和零信任这两个词,都带有“零”,都与“信任”有关,但并不是一回事。两者本质上都要增强「信任」,但在增强「信任」的过程中,零知识证明强调不泄露知识;零信任强调不要过度授权。简单说,零知识是为了隐藏知识;零信任是为了控制信任。关于零信任架构可参考《零信任架构》NIST标准草案

零知识证明解决了信任与隐私的矛盾:既通过「证明」提升「信任」,又通过「零知识」保护「隐私」。是两全其美的方案。

本文更想表达的观点其实是:探索零知识证明的过程,可以探索到安全的本质

以笔者目前认知,安全之终极定义,不是启发式的CIA三性,而是采用形式化验证的可证明安全——上帝(“模拟者”)与科学(数学、计算复杂度)完美结合的推演过程

一、了解零知识证明

01零知识证明的定义

零知识证明(ZKP,Zero-Knowledge Proof)的定义为:证明者(prover)能够在不向验证者(verifier)提供任何有用信息的情况下,使验证者(verifier)相信某个论断是正确的。

根据定义,零知识证明具有以下三个重要性质:

完备性(Completeness):

只要证明者拥有相应的知识,那么就能通过验证者的验证,即证明者有足够大的概率使验证者确信。

(关于这里提到的“概率”,详见后面的“色盲游戏”)

可靠性(Soundness):

如果证明者没有相应的知识,则无法通过验证者的验证,即证明者欺骗验证者的概率可以忽略。

零知识性(Zero-Knowledge):

证明者在交互过程中仅向验证者透露是否拥有相应知识的陈述,不会泄露任何关于知识的额外信息

从定义中,还可以提取到两个关键词:“不泄露信息”+“证明论断有效”。再浓缩一下就是:隐藏+证明

所以,零知识证明的核心目的是:隐藏证明需要它隐藏的各类秘密。(感觉很矛盾是吧)

02零知识证明的源头

零知识证明是1984年由Goldwasser、Micali、Rackoff三个人提出,论文题目是《The Knowledge Complextiy of Interactive Proof Systems》《交互式证明系统中的知识复杂性》)。

1628055770_610a28daef0a25a26a022.jpg!small?1628055771442

从上图的左上角可以看到,这篇论文其实发表在1989年。原因在于这篇论文的思想太过超前,以至于从1984年写出初稿到1989年正式被采纳发表,经历了整整五年时间。正是由于零知识证明这项开创性工作,Goldwasser和Micali两人在2012年分享了图灵奖——计算机领域最高奖项,也有“计算机界的诺贝尔奖”之称。

03零知识证明的核心价值:消灭可信第三方

当互联⽹电⼦商务和在线交易蓬勃发展到今天,可信第三方(TTP,Trusted Third Party)几乎不可或缺。但大家体会不到的事实是,可信第三方引入了巨大的「信任成本」。对第三方的过度信任,会带来严重的「隐私泄露」、「单点失效」、「个⼈信息滥⽤」等问题。虽然学术界也提出“半可信第三方”(Semi-trusted Third Party)以放宽条件,但是"半可信" 仍不解决根本问题。根本问题是能否取消第三方

那么,如果取消了可信第三方,还能保证交易的公平性吗?想象⼀下这个交易场景:⼀个买家拎着现⾦箱⼦,另⼀个卖家也拎着⼀个箱⼦,装着某种贵重货物。在电影中的情节⾥,买卖双⽅会坐在⼀个桌⼦两侧,双⽅倒数3-2-1,然后同时把箱⼦推给对⽅。当然双⽅最好都带武器,防⽌对⽅耍赖。除了买家、卖家,并没有任何第三⽅在场,两⽅也互不信任。容易理解,任何⼀⽅都不愿先出⼿,把⾃⼰的箱⼦交给对⽅,因为担心对⽅拿到箱⼦后⽴即跑路,导致自己钱货两空的结局。

时间走到2008年,⽐特币横空出世,中本聪给出了⼀种天才设计:在⼀个可以⽆任何准⼊许可的P2P⽹络中,采取区块链技术,以⼀种⾮常公平的⽅式进⾏去中心化记账。

我们可以从另⼀个⻆度来理解中本聪的创新:比特币实现了⼀种分布式协议,它以去中心化的方式,「模拟」出了一个「虚拟」的「可信第三⽅」

而对于零知识证明也可以这样理解:零知识证明实现了一类密码学理论技术,它基于一些安全假设,「模拟」出了⼀个虚拟的可信第三方

可见,「零知识证明」的一个重要作用是消灭可信第三方。换句话说,零知识证明提供的「信任」,能够代替一个「可信第三方」

需要注意的是:「零知识证明」取代的并非是「第三方」,而是「可信第三方」。

04零知识证明的经典示例:色盲游戏

零知识证明背后的逻辑并不复杂。下面给出交互式零知识证明的经典示例——色盲游戏,以帮助理解零知识证明的概念。详见参考资料[1]。

色盲游戏

参与者:Alice是色盲,Bob不是色盲

Bob手上有两个大小、形状完全一样的球,但颜色不同:一个蓝色,另一个红色。

由于Alice是色盲,所以Alice无法分辨这两个球是否是一样的。

Bob需要向Alice证明这两个球是不一样的

在这个游戏中:

Alice被称为验证者:他需要验证Bob的陈述正确与否;

Bob被称为证明者:他需要证明自己的陈述(存在两个颜色不一样的球)。

采取零知识证明方式:Bob需要在Alice不能获知两个球的颜色的情况下,向Alice证明这两个球的颜色是不一样的这个事实,这与零知识证明的定义是相符合的。

零知识证明方法如下:

Alice当着Bob的面拿起两个球,左手拿蓝球,右手拿红球(当然,Alice并不知道拿的是篮球还是红球,因为她是色盲);

Alice然后将双手放到背后,这样Bob就看不到Alice手上的球了;

Alice在背后随机交换左右手上的球,并在心里默默记住自己的交换方式;

交换完成后,Alice将手伸出,并询问Bob“两个球是否交换过位置?”;

如果Bob能看到球上的颜色,那么每次Alice换过球的位置后,Bob都能正确回答出Alice的问题。1628056223_610a2a9fd9d46eb3d1852.png!small?1628056224511

分析推理过程如下:

第一次:假设Alice确实交换了两个手中的球。

如果Bob回答对了,Alice仍然不会完全相信Bob可以区分这两个球的颜色,因为Bob有50%的概率蒙对;

所以,即使Bob回答对了,Alice还要进行第二次测试;

如果Bob回答错了,那么Alice可以肯定Bob不能区分两个球的颜色。此项测试就可以终止了。1628056268_610a2acc3bf7fa60836fa.png!small?1628056268658

第二次:假设这一次Alice并没有交换两个手中球的位置,然后Alice问Bob是否交换了球的位置。

如果Bob回答对了,那么Alice有75%的概率相信Bob可以区分两个球的颜色;

当然,Alice还可以进行第三次测试;

如果Bob回答错了,那么Alice可以肯定Bob不能区分两个球的颜色。

此项测试就此终止。1628056289_610a2ae17f3e5b6637bdc.png!small?1628056289898

下图给出了上述情况的概率树:1628056360_610a2b28c3062dfa7e471.png!small?1628056361180

概率计算结果如下:

第一次Bob回答正确时,Alice可以说Bob陈述的断言为真的概率为50%;

如果Bob第二次又回答正确,那么Alice可以说Bob陈述为真的概率达75%;

如果第三次又正确,概率将达到87.5%;……

如果连续n次Bob都通过了测试,则Alice以1-(1/2)^n 的概率认为 Bob 说的是真的,这两个球的确是有红蓝两种颜色。

这个示例中的零知识证明,是一种基于概率的验证方式(即概率证明,而非确定性证明),验证者(verifier)基于一定的随机性向证明者(prover)提出问题,如果证明者都能给出正确回答,则说明证明者大概率拥有他所声称的“知识”。

看看这个示例是如何满足零知识证明的定义中的三性

完备性:如果Bob拥有分辨球颜色的知识,则Bob每次都会正确回答。

可靠性:如果Bob不具备分辨球颜色的知识,则Bob无法总是回答正确。

零知识性:直到最后,Alice也无法得知两球的具体颜色,因为Bob从未透露这个信息。

二、领悟信任与安全

01信任的产生机理

零知识证明是怎么「凭空产生了信任」?

零知识证明的信任,基于比较客观的理论

一类是基础理论

如「数论与代数」、「数理逻辑」、「计算理论」等;

另一类是安全假设

如「离散对数难题」等。

如果我们信任这些基础理论(数学、逻辑),也信任安全假设没有被攻破,那么我们确实可以得出下面的结论:零知识证明实现了一类密码学理论技术,它基于一些安全假设,「模拟」出了⼀个虚拟的可信第三方。

2016年《经济学人》提出「区块链是信任机器」。仔细思考信任的推导机制,可以发现:

区块链:解决的是「分布式计算的信任」;

零知识证明:解决的是「数据的信任」;

形式化验证:解决的是「逻辑的信任」。

上述三点:逻辑 <-> 计算 <-> 数据,共同构成一个闭环,也许才能真正实现「信任机器」这一构想。

总之,任何「信任」都需要基于某些信任基础(如可信计算基(Trusted Computing Base)),任何「安全」都有安全性假设

信任的最后一环是「形式化验证」。形式化验证实际上是为逻辑、流程或业务进行形式化建模,你可以理解为用一种数学语言进行描述,模型就是一些数学概念(或数学对象),比如集合、代数、范畴等等。然后所有的形式化验证都在用「显式」的或「隐式」的方式「严格证明」某个结论(或者叫做定理)。

而理解零知识证明理论的核心,是理解「模拟」这个概念。上面我们提到了两个「模拟」:一个是区块链,另一个是零知识证明。再来回顾一下:

比特币实现了⼀种分布式协议,它以去中心化的方式,「模拟」出了一个「虚拟」的「可信第三方」

零知识证明实现了一类密码学理论技术,它基于一些安全假设,「模拟」出了⼀个虚拟的可信第三方

他们之所以可信,是因为他们能够「模拟出可信第三方」。这个模拟过程都是可以形式化的,并且是可证明的。如今,模拟(Simulation)安全性证明已是密码学界的共识,也是基本的形式化工具,没有经过证明/验证的模拟是无法让大家接受的。

理论上,所有客观标准都能进行验证,大到一个安全协议,小到一行代码,都能采用形式化验证的方法。恰好笔者曾经研究过可证明安全,从那些密码学安全性证明中体会到了「模拟」与「可证明安全」中所表达出的神奇理念。从某种程度上,可以领会到「安全」之真谛。

如果对模拟、安全、不可区分性等形式化验证的方法感兴趣,请参考资料[6],它将带你到另一个存在「上帝」的「平行世界」,横跨科学与哲学问题。

02证明 vs. 验证

零知识证明的实现可以通过三段旅程来描述:(详见参考资料[3])

隐藏秘密之旅:单向功能

证明秘密之旅:同态映射

构建通用零知识证明之旅:证明NPC问题的多项式

「零知识证明」中的「证明」与其定义中的「验证」是何关系?这涉及到证明存在的意义。所有的证明,都体现了「证明」与「验证」的「不对称性」。

证明:可能是一个非常耗费算力,或者脑力的活动,无论是耗时几百年的「费马大定理」,还是比特币中的 POW 证明,这些证明都凝结了在寻找证明过程中所消耗的能量。

证明过程可能是超乎寻常的复杂,偶尔需要天才横空出世。

验证:一定(或者应该)是一个非常简单的、机械的、在有效时间内(多项式复杂度)且能终止的活动。

某种意义上,「证明」与「验证」这种不对称性,真正体现了证明的意义,展示了零知识证明的价值。关于这一部分,详见参考资料[2]。

03信任 vs. 隐私

从根本上讲,信任是个好东西。我们创建了信用体系,可以向我们信任的人和组织提供信贷;依靠名声、信誉记录等,也能够与我们不信任的人开展业务

但是,信任通常是建立在牺牲隐私的基础之上的。为了互相信任,通常必须放弃一些隐私。而且信任通常与你的身份信息密切相关。

而零知识证明恰恰是一种两全其美的方案:既通过「证明」提升「信任」,又通过「零知识」保护隐私

04匿名 vs. 假名

对于隐私的理解,其实分两种:

第一种是匿名(Anonymous),意思是用户不用透露任何和自己相关的信息,好比是学校的表白墙,你永远无法知道到底是谁写了上去,反正字就是写在了上面。

第二种是假名(Pseudonymous),意思是用户通过自己创造的假名来发表信息,好比是贴吧,如果你不了解这个用户,你无法建立网名到实名的联系,你也就不知道发帖的人是谁。

目前,大多数当前的区块链技术只是假名。如比特币中每个用户都会随机生成自己的公钥(假名)地址来收款。这种公钥地址其实是一种假名,一旦在哪里实名制认证过,就可以把网名和实名关联起来,毫无隐私可言。

如果黑客或政府可以将真实姓名与网络地址相关联,那么可以通过链接区块链交易追溯到用户交易时的身份。尽管区块链被赞誉为完美安全方案,但知情人士都知道这种弱点。事实上,世界各地的执法机构一直在利用这一漏洞来抓住犯罪分子。

这就好比有人用网名在贴吧上发帖子喷人,然后被人用密保找到了手机号,再用手机号找到了注册的实名,从而被人肉是一个道理。

零知识证明可以弥补这种匿名缺陷。利用零知识证明创建信任的社会,是一个更加注重个人隐私的社会。它会把隐私控制权真正转移到消费者手上,而不是将其交给政府或组织等。

三、零知识证明的应用

零知识证明定义中有两个关键词:“不泄露信息”、“证明论断有效”。基于这两个特点,直接扩展出零知识证明在区块链上的两大应用场景:(详见参考资料[1])

隐私:在隐私场景中,我们可以借助零知识证明的“不泄露信息”特性,在不泄漏交易细节(接收方、发送方、交易余额)的情况下,证明区块链上的资产转移是有效的。

扩容:在扩容场景中,不太关注零知识证明技术的“不泄露信息”这个特性,更加关注“证明论断有效”这个特性。由于链上资源是有限的,所以我们需要把大量的计算迁移到链下进行,因此需要有一种技术能够证明这些在链下发生的动作是可信的,零知识证明正好可以帮助我们做链下可信计算的背书。

端到端的通讯加密:用户之间可以互相发消息,但是不用担心服务器拿到所有的消息记录,同时消息也可以按照服务器的要求,出示相应的零知识证明,比如消息的来源、发送的目的地。

身份认证:用户可以向网站证明,他拥有私钥,或者知道某个只要用户自己才知道的秘密答案,而网站并不需要知道这个私钥和秘密,但是网站可以通过验证这个零知识证明, 从而确认用户的身份。

去中心化存储:服务器可以向用户证明他们的数据被妥善保存,并且不泄露数据的任何内容。

信用记录:信用记录是另一个可以充分发挥零知识证明优势的领域,用户可以有选择性的向另一方出示自己的信用记录,同时证明信用记录的真实性。

更多的例子,可以是任何形式的数据共享、数据处理、数据传输

2019年7月,美国国防部高级研究计划局(DARPA)发布了一份加密验证和评估信息安全保障(SIEVE)项目的广泛机构公告(HR001119S0076)。该项目寻求在零知识证明方面最先进的技术,目标是在不泄露秘密信息的前提下验证军事能力。该项目关注的是网络安全和网络空间作战方面用于验证军事能力的零知识证明,包括概率和不确定分支条件在内的大型复杂的证明。项目研究分为三个技术领域:构建有用的零知识语句;构建高效的零知识证明生成编译器;后量子零知识研究。

参考资料

[1]《零知识证明介绍》,吴寿鹤;

[2]《初识「零知识」与「证明」》

[3]《一文读懂零知识证明背后的简单逻辑》,李画;

[4]《zkPoD:区块链,零知识证明与形式化验证,实现无中介、零信任的公平交易》,郭宇;

[5]《浅谈零知识证明:背景与起源》,东泽;

[6]《从「模拟」理解零知识证明:平行宇宙与时光倒流》,郭宇;

作者:柯善学整编 来源:公众号 网络安全观

本文作者:, 转载请注明来自FreeBuf.COM

# 零知识证明
被以下专辑收录,发现更多精彩内容
+ 收入我的专辑
评论 按热度排序

登录/注册后在FreeBuf发布内容哦

相关推荐
\
  • 0 文章数
  • 0 评论数
  • 0 关注者
文章目录
登录 / 注册后在FreeBuf发布内容哦
收入专辑