请选择 进入手机版 | 继续访问电脑版

Hi,Tokens

 找回密码
 立即注册
查看: 768|回复: 3

零知识证明资料汇编

[复制链接]

724

主题

1091

帖子

4057

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
4057
发表于 2018-4-22 15:09:34 | 显示全部楼层 |阅读模式
当今密码学世界中最酷炫的一件事,莫过于那些优美又神秘的专有名词。我们可以自由的以这些术语给朋克乐队或 Tumbirs 博客起名字,像是“硬核谓词(hard-core predicate)”、“陷门函数(trapdoor function)”,或“不可差分密码分析(impossible differential cryptanalysis)”等热词都受到追捧。 当然,我今天要提到的这个术语热度绝不亚于前面三者,它就是“零知识(zero knowledge)”。
事实上太过受欢迎也不一定是件好事,因为”零知识“概念如此吸引眼球,也导致许多理解错误和误用。许多人将零知识和“非常非常安全”划上等号,并将它与加密系统或匿名网络挂钩——但这是不正确的,这与真正的零知识协议毫无关系。
这一切都说明 “零知识证明” 是密码学家所设计出来最强大的工具之一,同时理解的人也相对较少。接下来,我将试着(尽可能)以 非数学 领域的表述方式,介绍什么是“零知识证明”,并解释到底是什么使得它如此特别。同时在此篇和下篇文章中,我们会谈及一些常用的零知识证明协议。
零知识起源
“零知识”的概念最早在80年由麻省理工学院的研究人员 Shafi Goldwasser,Silvio Micali 和 Charles Rackoff 所提出。当时这些人正在研究与交互证明系统相关的问题——即一种理论系统,使得甲方(证明者)可以和乙方(验证者)交换信息,并借此说服乙方接受(通过验证)某个数学论述为真 [作者注1]。
在Goldwasser等人之前,这个领域的研究工作主要聚焦在加强证明系统的可靠性(Soundness)。也就是说原先大家都假设,会有恶意的证明者试图耍手段,误导验证者接受错误的论述。但 Goldwasser 等人却从另一个角度思考了这个问题:如果我们压根就不相信 验证者,该怎么办?
更具体的来说,他们更关心信息泄露的问题。他们抛出了这样的思考:“在验证者的验证过程中,究竟会获取多少单纯验证论述真假无需知道的额外信息。”
这里要强调一下,这个问题不是单纯的理论思考,而是在真实、具体的应用中,会面到临的问题。
我们举个例子,假设今天在真实世界有个客户端想要使用密码登录web服务器,在“真实世界”的标准操作流程中,包含将密码以哈希形式储存在客户端。我们可以将”登录“这个动作视作某种证明——也就是我们要能够提供一串输入,这串输入经过哈希运算后的值与密码的哈希相同(因为哈希运算的单向性,这串输入只能是我们的密码)。但这有个问题是:客户端实际上 知道 我们的密码。
大多数系统以这种绝对最糟糕的方式进行“证明”——客户端直接将原始密码发送给服务器,服务器重新计算密码哈希并将其与存储值进行比较。这里的问题很明显:在协议结束时,服务器已经取得我们的明文密码。 因此,保障现代密码安全很大程度上要祈祷服务器不会遭受攻击。
Goldwasser,Micali 和 Rackoff 等人提出了一种全新的方法来完成“证明”。如果零知识证明真的可行,它将允许我们在证明某些数学陈述为真的同时,保证 不会有任何不相关的信息 被透露出去。
一个“真实世界中”的案例
目前为止,我们的讨论还比较抽象。为了让大家能有更具体的概念,现在我们举个“真正的”(脑洞微开的)零知识证明例子。
请大家配合我想象一下,现在我是个电信业巨头,并且打算部署一个新的蜂窝电信网络。这个网络架构图如下(图一)。图中的每个顶点代表一个无线电塔,每一条连线(边)代表无线电塔信号 两两重叠 的区域,这意味着连线上的信号会互相干扰。
这种重叠的情况是有问题的,这表示来自相邻电塔的信号会互相混淆。幸好在设计之初我预见这个问题,现在通信网络允许传递三种波段的信号,这样就避免了临近电塔信号干涉的问题。
不过现在我们有了新的挑战!这个挑战来自我该如何部署不同的波段,使得相邻的每两个电塔不具有相同波段。我们现在用不同颜色来表示不同波段,可以很快找到一种解决方案如下图二所示:
当然,很多人可能已经发现我刚才是在讲述著名的算法问题——三色问题(graph three-coloring)。大家也就知道,这个问题有趣的地方在:某些非常庞大的网路中,我们很难找到解,甚至连证明问题 有解 都办不到。事实上三色问题——特别是指这种给定图形是否有解的决策问题,已经被归类为NP完全问题
如果只是上面给的这种示例图,我们用手就能轻松找出解。但如果今天我的无线通信网路规模特别复杂而庞大,我以我所能调配的计算资源都无法找到解答的情况下,我该怎么办?我还可以把这个问题 外包 给拥有更庞大算力的人呀!比如我会去找我在谷歌的朋友帮忙。
但这又会导致另一个问题。
假设谷歌动用了大量的算力来帮我找寻有效的着色方法。当然,在我确实得到有效着色方法之前,我是不打算付钱给谷歌的。同样对谷歌来说,在我付款之前,谷歌也不愿意给我着色方法的副本。因此我俩就会陷入僵局。
在现实生活中,可能有点常识都能解决这个困境,但这涉及律师和账户托管。不过今天这篇博客不是表述现实生活,而是关于密码学的。如果你曾经看过任何加密相关文章,你可能知道,解决这种困境的正确方法,就是 想出一个绝对疯狂的技术手段
一种疯狂的技术手段(用帽子!)
谷歌的工程师向Micali 等人在麻省理工进行了咨询。他们想出了一种非常聪明而优雅,甚至不需要任何计算机的方法来打破上述的僵局。我们只需要一个大仓库、大量的蜡笔和纸张。噢,对了,我们还需要一堆的帽子![作者注2]
下面是运作原理。
首先,我先进入仓库,在地板上铺满纸张,并在空白的纸上画出电塔图。接下来我离开仓库,换谷歌工程师进入仓库。谷歌工程师先从一大堆的蜡笔中,随机选定三个颜色(与上面的例子一样,我们假设随机选中红色/蓝色/紫色),并在纸上照着他们的解决方案上色。请注意,用哪种颜色上色并不重要,只要上色的方案是有效的就行!
谷歌工程师们上色结束后,在离开仓库前,他们会先用帽子把每个纸上的电塔盖住。所以当我回到仓库的时候,我会看到如下图三:
显然的,这种方法保障了谷歌着色方法的秘密性。但这样对我一点帮助都没有!我不知道他们是不是进行了有效着色,或是他们根本没有着色?
为了消除我的疑虑,谷歌工程师们决定给我机会“挑战”他们的着色方案。我被允许——随机选择图上的一条边(两个相邻帽子中间的一条线),然后要求谷歌工程师揭开两边覆盖着的帽子,让我看到他们着色方案中的一小部分,如图四:
产生两种结果:
  • 如果两个点颜色相同(或是根本没有被着色!),我就可以确信谷歌工程师们对我撒谎。因此我也很清楚我不需要付钱。
  • 如果两个点颜色不同,那么谷歌工程师 可能没有 撒谎。
第一种情况很单纯(我不付钱!),第二种情况下我要进行更多考虑。即使我刚才进行了一轮观察,毕竟我只揭开两顶帽子,只看到两个点,仍然不能保证谷歌工程师给我的方法是有效的。假如图上有 E 条不同边,在目前条件下谷歌仍有很大的可能是给了我一个无效的着色方案。实际上,在经过一次揭帽观察后,我仍有高达 (E-1)/E 的概率会被骗(假如有1000条边,有99.9%的概率这个方案无效。)
好在谷歌决定让我们再一次、重新进行观察!
我再次走出仓库,他们重新铺上新的纸张,并把空白的电塔图画上。谷歌工程师再次从大量蜡笔中随机选出三种颜色进行着色。他们再次完成有效着色方案,但使用新的三种随机颜色。
接着帽子又被盖上啦。我走进仓库再一次进行“挑战”,选择一条新的、随机的边。上述逻辑再一次适用。不过这次情况稍好,我会对谷歌工程师们多了那么一点点信心,相信他们没有对我撒谎。因为如果他们要欺骗我,他们必须连续两次都这么幸运。这当然有可能发生——但发生的可能性相对较低。现在谷歌连续两次都骗到我的概率为 [(E-1)/E] * [(E-1)/E](在1000条边的情况下,大约有99.8%的可能性,还是很高)。
不过不用担心,我们不只可以进行两次挑战。事实上,我们可以不断的重复上述的挑战,直到我们相信谷歌给出了有效的着色方案。
切记不要盲目信我的话。感谢 Javascript,你可以通过简单的代码自己验证上面的逻辑。提醒下,我永远无法完全相信谷歌工程师是诚实的——我被骗的概率总会存在,即使概率很小。但经过大量的迭代后(E^2),我最终可以将信心提升到一个程度,那时候谷歌只剩下微不足道的概率可能骗到我——这概率低到我可以安全地把钱交给谷歌。
而且你需要知道的是,在这个过程中谷歌同样受到保护。即使我试图在挑战的过程中推敲出他们正确的着色方案,那也不要紧。因为谷歌在每一次迭代前随机更换三种新的颜色,这让我的小手段失效了。我获得的讯息对我毫无帮助,每次挑战的结果也无法被串联起来。
是什么让它“零知识”?
我对你声称,这种挑战不会泄露任何关于谷歌着色方案的信息,但请你们不要这么轻易放过我!现代密码学第一条守则就是:永远不要在未经证明的情况下相信一个人的宣称。
Goldwasser, Micali 和 Rackoff提出三个零知识证明的特性,任何零知识都必须满足。简单来说:
  • 完整性(Completeness)。如果谷歌说的真话,那么他们最终能说服我(至少让我相信可能性非常高)。
  • 安全性(Soundness)。只有当他们说的是真话时,谷歌才有可能说服我。
  • 零知识性(Zero-knowledgeness)(没错,就这么叫)。我无法从中习得任何关于谷歌解决方案的信息。
我们已经讨论了完整性的论点。只要重复足够多次挑战,这个协议最终能够说服我(伴随极低的失误可能);安全性也很容易说明,因为如果谷歌试图欺骗我,会有很大的概率会被我发现。
最难说明的就是“零知识性”。为此,我们必须进行一项非常奇怪的思想试验。
思想试验(时光机?)
我们要从一个疯狂的假设开始。假如谷歌工程师并没有大家想象中厉害,他们花了数周时间,仍然没有想出着色问题的解决办法。而现在只剩下12小时他们就得展示了!他们已经感受到了绝望。绝望使人疯狂,他们决定 诱导 我相信他们已经完成有效的着色,实际上他们并没有完成。
他们的想法是潜入 GoogleX 研究室,并“借用”谷歌的时光机的原型机。最初他们想将时间倒退几年,主要可以获得更多时间来解决着色问题。不幸的是,与大多数谷歌原型机一样,这个时光机也有限制——它只能倒退 四分半钟 的时间。
虽然使用时光机获得更多工作时间的想法已经不可行,但这有限的功能已经足够欺骗我。

-我不知道这里到底发生了什么,但看起来好厉害的样子-
这个计划要命的简单!因为谷歌工程师们 实际上不知道 正确的着色方案,他们只能直接从大量蜡笔中随机选出颜色来涂,然后盖上帽子。如果他们足够幸运,我在挑战时选中不同颜色点,他们就可以松口气,然后继续进行挑战,以此类推。
然而不可避免的,我总会在某次挑战时揭开两顶帽子,然后发现两个相同 颜色的点!如果按照正常挑战规则,谷歌工程师们就原地崩溃了,而这也是时光机派上用场的时候。任何时候谷歌工程师们发现自己身处尴尬的情况(被我找到同色点),他们可以轻松挽回颓势。只要其中一个工程师按下时光机按钮,让时间倒退大约四分钟,然后他们再以新的完全随机方式着色。接着时间正常前进,挑战将继续进行。
实际上,时光机让谷歌工程师可以挽回在欺骗过程中的任何失误,同时让我误以为这个挑战过程完全符合规则。从谷歌工程师的角度来看,造假被挑战出来的情况只有1/3,所以整个挑战时间只会比诚实情况下(他们有有效解答)的挑战时间稍微长一点;从我的角度来看,我只会认为这是完全公平的挑战,因为我不知道时光机的存在。
最后一点,也是最重要的一点。在我的眼中,因为我压根不知道有时光机存在,所以我看到的每一次挑战结果,我都会认定这就是真实的!而统计结果也完全一致。值得再呼吁一次,在时光机作弊的情境下,谷歌工程师们绝对不知道正确着色方案
我到底想说什么?
请注意,我们刚才举得是一个计算机仿真 的例子。在现实世界中,时间当然不能倒退,也没有人能用时光机器骗我,所以基于帽子的挑战协议是合理且可靠的。这表示在 E^2 轮挑战后,我应该相信盖着的图是被正确着色的,同时谷歌工程师们也遵守协议规则。
方才我们展示的是,如果时间不只能够前进——特别的是谷歌能“倒退”我的时间,那即使他们没有正确的着色方案,他们仍然能使挑战正常进行。
从我的角度出发,这两种情况有什么区别?当我们考虑从这两种情况下的统计分布,会发现根本没有区别,两者都表达了相同量级的有效信息。
信不信,这恰好证明了一件非常重要的事情!
具体来讲,假设我(验证者)在正常挑战协议过程中,有办法“提取”关于谷歌正确着色方案相关信息。那么当我被时光机糊弄的时候,我的“提取”策略应该仍然有效。但从我的角度来看,协议运行结果在统计学上毫无二致,我根本无法区别。
因此如果我在“公平的挑战”和“时光机实验”下,所能得到的信息量相同;且谷歌在“时光机实验”中投入的信息量为零,则证明即使在公平的挑战下,也不会透露任何相关信息给验证者知道。
又或是这恰好说明计算机科学家有时光机??是的,我们有。(请务必保密......)
抛开帽子(也抛开时光机)
当然在现实世界我们不会想用帽子来进行协议,谷歌(可能)也没有真正意义上的时光机。
为了将整件事情串起来,我们先把这个协议放到数字世界。这需要我们构建一个相当于“帽子”功能的等价物——它既能隐藏数字价值,又能同时“绑定”(或“承诺”)创建者,这使得事实被公布后他也不能不认账。
幸运的是,我们恰好有这种完美的工具。这就是所谓数字承诺方案。这个方案允许一方在保密的情况下“承诺”给出的信息,然后再“公开”承诺的信息。这种承诺可以有很多结构组成,包含(强)加密哈希函数。[作者注3]
我们现在有了承诺方案,也就有一切电子化运行零知识证明的要素。首先证明者(Prover)可以将每个点以数字信息形式”着色“(例如以数字0,1,2),然后为每个数字信息生成数字承诺。这些数字承诺会发送给验证者(Verifier),当验证者进行挑战的时候,证明者只需要展示对应的两个点的承诺值就行。
所以我们已经设法消除帽子了。但如何证明这个过程是零知识的?
我们现在身处数字世界,不再需要一台时光机证明与此相关的事。其中的关键在于数字世界中,零知识证明协议不是在两个 之间运行的,而是在两方不同的计算机程序 上运行的(或是更规范地说,是概率图灵机)。
我们现在可以证明下面的定理:如果你能做出一套程序,使得验证者(计算机)能够在挑战过程中”提取“额外的有用信息,则我们就有办法在程序中加入“时光机”的功能,使得它能够在证明者没有投入任何信息的情况下(译者注:即谷歌工程师没有正确解),从“假”的挑战过程获得等量的额外信息。
因为我们现在讨论的是计算机程序,回退、回滚等倒退时间的操作根本不是难事。实际上,我们在日常使用上就不断在回滚程序。比如带有快照功能的虚拟机软件。

-通过虚拟机快照进行回滚的例子示意图。一台初始虚拟机继续执行,回滚到一个初始的快照中,然后分叉到另一条新路径中执行-
即使你没有复杂的虚拟机软件,任何计算机程序也都可以回滚到先前状态。我们只需要重新启动程序,并提供完全相同的输入即可。只要输入的所有参数(包含随机数)都是相同的,程序将永远按照相同的执行路径操作。这意味着我们可以从头开始运行程序,并在需要的时间点进行“分叉(forking)”。
最终我们得到以下定理。如果存在任何的验证者计算机(Verifier)程序,它可以通过与证明者的协议交互过程中提取信息,那么证明者计算机(Prover)同样可以通过程序回滚来”欺骗“验证者——即证明者无法通过挑战,却以回滚的方式作弊。我们已经在上面给出了相同的逻辑:如果验证者程序能从真实的协议中提取信息,那么它也应该能从模拟的、会回滚的协议中获取等量的信息。又因为模拟的协议根本没有放入有效信息,因此没有可提取的信息。所以验证者计算机能提取的信息一定始终为零。
这,到底在说什么?
让我们回顾一下。根据我们上面的分析,可以知道这个协议是完整且可靠的。该可靠性的论点在我们知道没有人玩弄时间的前提下都是站得住脚的。也就是说,只要验证者计算机正常运行,并且保证没有人在进行回滚作弊的话,协议是完整且可靠的。
同时我们也证明这种协议是零知识的。我们已经证明了任何能成功提取信息的验证者程序,也一定能从回滚的协议运行中提取信息,而后者是没有信息放入的。这明显自相矛盾,间接论证该协议在任何情况下都不会泄露信息。
这一切有个重要的好处。比如在谷歌工程师向我证明他们有正确的着色方案后,我也无法将这个证明过程转传给其他人用以证明同样的事(如,法官),这使得伪造协议证明变成了不可能的事。因为法官也不能保证我们的视频是真是假,不能保证我们没有使用时光机不断回滚修改 证明。所以零知识证明只有在我们自己参与的情况下才有意义,同时我们可以确定这是实时发生的。
证明所有的NP问题!
如果你能坚持看到这儿,我敢打包票你已经准备好迎接一个大新闻!就是我们讲了半天的三色电信网络网络,其实并不有趣——至少,本身不咋地。
真正有意思的地方在于,三色问题属于NP完全问题。简单来说,这件事的奇妙之处在于任何其他的NP问题都可以转化为这个问题的实例。在一次不经意的尝试下,Goldreich, Micali 和 Wigderson 发现“有效的”零知识证明大量存在于这类问题的表述中。其中许多问题比分配蜂窝网格问题有趣得多。你只需要在NP问题中找到想要证明的论述,比如上面的哈希函数示例,然后转化为三色问题。然后再进行数字版的帽子协议就行啦!
总结
当然,单纯为了兴趣来运行这项协议,对任何人来说都是疯狂而近乎愚蠢的——因为这样做的成本包含原始状态和证人的规模大小、转化为图形的花费,以及理论上我们必须运行E^2 次才能说服某人这是有效的。
理论上说这个协议是“高效率的”,因为证明的总成本会是输入状态的多项式,但其实不然。
所以我们迄今展示的,是要表达这种证明是“可能的”。接下来我们仍然需要找到更多的实例来支撑零知识证明的可用性。
下一章节,我们会特别谈及一些被实际用于各种有效论述证明的方法。我们也会举出一些真实场景中的例子。另外,因应读者要求,我也会聊聊为什么我不是很喜欢SRP(安全远程密码协议)。
注解:
作者注1:形式上,交互证明系统的目标是要说服验证者,使得验证者相信某特定字符串属于某种语言。在该系统中,通常证明者的权利非常大(无限的),而验证者的计算能力是有限的。
作者注2:本文中举的例子基于Goldwasser, Micali和Rackoff的原始解决方案,而帽子方法则是基于Silvio Micali的解释。我个人只供献了一些愚蠢的失误。
作者注3:我们可以通过哈希函数来构造一个数字承诺的例子。为了承诺一个值“x”,我们需要生成一段(长度适合)的随机字符串,这段随机字符又叫做“盐”。然后输出数字承诺*C = Hash(salt || x)*。必须公开“x”和“盐”,才能通过承诺验证。任何人都可以通过重新计算哈希来检查承诺是否有效。这对于函数本身的某些(适当强度)假设是安全的。

原文链接: https://blog.cryptographyengineering.com/2014/11/27/zero-knowledge-proofs-illustrated-primer/
作者: Matthew Green
翻译&校对: IAN LIU & Elisa

回复

使用道具 举报

724

主题

1091

帖子

4057

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
4057
 楼主| 发表于 2018-4-22 15:10:37 | 显示全部楼层
快速回顾,以及更多关于零知识的介绍
首先,简要回顾一下。
上一篇文章我们将零知识证明定义为两个计算机程序(或图灵机)之间的相互作用,互动双方分别称为证明者和验证者,证明者试图说服验证者某些数学陈述是真实的。 我们还介绍了一个具体的例子:Goldreich,Micali和Wigderson 提出的一个很有意思的协议, 平面图三色问题的零知识证明。
在上一篇中我们描述了任何零知识证明都必须满足的三个关键属性:
  • 完整性(completeness):如果证明者是诚实的,那么她最终会说服验证者。
  • 可靠性(Soundness):证明者只能说服验证者该陈述是否属实。
  • 零知识性(Zero-knowledgeness):除了知道陈述是真实的,验证者不知道任何额外的信息。
真正的挑战来自如何定义最后一个属性。 你如何判断验证者无法获取除了陈述之外的任何信息呢?
如果您没有读过前一篇文章,我可以告诉你一个由 Goldwasser,Micali和Rackoff 三人提出一个非常赞的方案。 他们认为一个协议如果满足对于每一个可能的验证者,可以证明一个叫“模拟器”的算法的存在,并且这个算法有一些非常特殊的属性,就认为它满足零知识证明
机械地来看,模拟器就像一个特殊的证明者。 不过与真正的证明者不同,后者以一些能够证明陈述真实性的特定信息开始, 模拟器则不会 [作者注1]。然而模拟器必须能够“欺骗”每一个验证者使他们相信该陈述是真实的,同时产生与真实证明者在统计意义学上相同(或者说无法区分)的输出结果副本。
逻辑流程非常清晰:由于模拟器没有“知识”能被提取,因此显然验证者在与之交互后无法获得任何有价值的信息。 此外,如果交互的信息副本与使用正常证明者运行的真实协议的分布相同,那么验证者对于真正的证明者的验证结果不会比对于模拟器的验证结果更精确。 (如果更精确,那么这意味着模拟器与真正的证明者的分布在统计学上是不相同的。)因此,验证者无法从真实的协议运行中提取有用的信息。
这令人难以置信,更糟的是,这似乎还是矛盾的! 我们要求一个协议是完全可靠的,这意味着一个伪造的证明者除非具备特定的信息证明某个陈述的真实性,否则他无法欺骗验证者接受,但是我们也要求存在一个算法 (模拟器),可以从字面上作弊。 显然这两个属性不能同时存在。
解决方案是这两个属性(可靠性和“可作弊”的算法) 同时存在。
为了构建模拟器,我们可以对验证者执行那些在现实世界中永远不可能做到的事情。 前一篇文章中给出的例子是使用“时光机”。也就是说,“模拟器”可以回滚验证者程序的执行,以达到'欺骗'它的目的。 因此,在这个可以倒转验证者时间的世界里,很容易证明模拟器的存在。 而在现实世界中当然不可能做到。 这个“伎俩”使我们绕开了上面所说的矛盾。
最后提醒下,为了说明所有这些想法,我们介绍了一个由 Goldreich,Micali和Wigderson(GMW)设计的通用零知识证明。该协议使我们能够以零知识证明某张图符合三色问题。当然,三色问题的零知识证明并不是非常有趣。 GMW结果的真正意义是理论上的。由于已知三染色问题属于NP完全问题,所以GMW协议可用于证明 NP问题中的任何陈述。 这是相当厉害的。
我来稍微详细地解释下:
  • 如果存在可以在多项式时间内验证证人(解决方案)的任何 决策问题(即可以用是/否回答的问题),则:
  • 我们可以通过(1)将问题转化为三色问题的一个实例,以及(2)运行 GMW 协议来证明 [作者注1]。
这个令人兴奋的结果使我们能够交互式零知识证明NP问题中的每个陈述。唯一的问题是它几乎无法使用。
理论付诸实践
如果你是一个实践主义者,那么你可能不会认同这个零知识证明。因为实际上使用这个方法 的代价非常昂贵并且很愚蠢。很可能你会将问题以布尔电路来表示,当且仅当有正确的输入,电路输出结果就为真。然后你又得把电路翻译成图表,导致工作量爆炸式增加。 最后你还需要运行成本很高的 GMW 协议。
所以实际上没有人会这样做。 这被认为是“可行性”结果。 一旦你认为某个事情有可行性,下一步就是提高效率。
其实我们几乎每天都会使用零知识证明。 在这篇文章中,我将花一些时间来讨论更具实际意义的零知识证明。 不过我需要做一些背景介绍。
证明vs知识证明
深入讨论之前,还有一个概念需要确认。 具体来说,我们需要讨论当我们实施零知识证明时,我们在证明什么。
我解释下。 概括地讲,可能有两类陈述需要用零知识证明。 粗略地说,分成如下几部分。
有关“事实”的陈述。 例如,我可能希望证明“一个特定的图可以进行三染色”或“数字N是一个合数”。 这些都是关于内在属性的陈述。
关于我个人知识的陈述。 此外,我可能希望证明我知道某些信息。这类陈述的例子有:“我知道这个图的三染色方案”,或者“我知道N的因式分解”。这不仅仅证明某个情况是真实的,而且实际上依赖于证明者所知道的信息。
认识到这两种陈述之间存在巨大差异是很重要的!例如,即使你不知道完整的因式分解,也可能证明数字 N 是合数。因此,仅仅证明第一个陈述并不等于同时证明了第二个陈述。
第二类证据被称为“知识证明”。这对证明我们在现实生活中使用的各种陈述非常有用。本篇我们将主要关注它。
Schnorr 身份识别协议
我们已经介绍了一些必要的背景知识,现在我们继续来看看 Claus-Peter Schnorr 在20世纪80年代发明一个的特定的并且非常有用的知识证明。Schnorr 协议乍一看有些奇怪,但实际上它是我们现代许多签名方案的基础。
然而,Schnorr 关注的并不是数字签名,而是身份识别。具体来说,我们假设 Alice 已经将公钥对外发布,然后想要证明她拥有与该公钥对应的私钥。这是我们在真实世界的协议中遇到的很确切问题,例如 SSH 公钥,所以它的意义还是存在的。
Schnorr首先假设公钥有一种非常具体的格式。具体来说,令 p 为素数,令 g 为素数 q 的循环群的生成元。 为了生成密钥对,Alice 首先选择 1到q 之间的随机整数 a,然后计算密钥对:
(如果你对公钥加密比较了解,可能会注意到这是用于 Diffie-HellmanDSA签名 算法的相同类型的密钥。这不是巧合,它对这个协议意义很大。)
Alice将自己的私钥保留,但她可以随意对外发布公钥。当她想证明她的私钥加密的信息时,她与Bob进行以下的交互协议:
这里面涉及的知识点很多,所以我们花点时间剖析一下。
首先,我们应该问自己协议是否完整。这通常是最简单的可以验证的属性:如果Alice诚实地执行协议,Bob是否应该对结果满意? 在这种情况下,通过进行一些代入替换就可以很容易地看到完整性:
可靠性证明
比较难证明的属性是可靠性。主要是因为对于知识证明的可靠性还没有很好的定义。请记住,这里(可靠性)我们想要说明的是:
如果Alice可以让Bob信服,那么她必定知道私钥 a .
看看上面的方程很容易理解,Alice欺骗协议的唯一方法是知道私钥a。但这并不能作为问题的证明。
当谈到知识证明的可靠性时,有一个非常好的方法。就像我们上面讨论的模拟器一样,我们需要证明一个特定算法的存在。这种算法被称为“信息提取器 ”,就是它字面的意思。信息提取器(或简称为“提取器”)是一种特殊类型的验证者,与证明者交互。并且如果证明者成功完成了证明,提取器应该能够提取证明者的私钥。
这回答了上面的问题。为证明知识证明的可靠性,我们必须表明对应每个可能的证明者都存在一个提取器。
当然,这与零知识协议似乎是矛盾的, 我们不应该能够从证明者那里获取私钥。
幸运的是,我们已经用“模拟器”解决了这个难题。 我们采取同样的方法:在正常协议运行期间,提取器不需要开启。如果我们允许随意回退证明者,就可以直接让提取器开始运作了。在这种情况下,我们将使用“倒带”来回退证明者的执行并提取私钥。
Schnorr 协议的提取器非常聪明,也非常简单。我们用协议交互图来说明它。 Alice(证明者)在左边,提取器在右边:
这里的关键点是,通过回退Alice的执行,提取器可以“欺骗”Alice使用相同的 k 来制作两个不同的证明副本。 这通常不会发生在真正的协议运行中,因为Alice每次执行协议都会使用新的 k
如果提取器可以欺骗Alice做这件事,那么他可以通过下面的简单方程式来获取Alice的私钥:
这需要引起我们的注意了,因为这引出了 Schnorr 协议中的严重漏洞。 如果你不小心在协议的两次不同运行中使用相同的 k,攻击者就可能获取您的私钥! 如果你用了一个有问题的随机数发生器,这很可能会发生。
事实上经验丰富的人会注意到,这类似于这一次对 ECDSA 或 DSA 签名的系统(带有有问题的随机数发生器)的攻击! 而且这也不是巧合。 (EC)DSA 签名机制本来就是基于Schnorr 协议。 讽刺的是,DSA 的开发者设法保留了 Schorr 协议家族的这个弱点,同时 又放弃了让 Schnorr 协议如此好用的安全性证明。
对一个诚实的验证者证明零知识
现在我们证明完 Schnorr 签名是完整和可靠的,还需证明其是“零知识”的。 还记得吗?要证明零知识性,通常我们需要一个模拟器来完成,它可以与任何可能的验证者进行交互,并生成一个证明的结果“模拟”副本,即使模拟器不知道对应的私钥,也要证明它是知道的。
标准 Schnorr 协议中并没有这样的模拟器,马上我就会解释原因。相反,为了让证明顺利开展,我们需要做一个特定的假设。这就是:验证者需要“诚实”。也就是说,我们需要假设,验证者会正确运行协议里它要证明的部分,也就是说,它将仅使用随机数生成器来挑选它的尝试值 “c”,并且不会基于任何我们提供的输入来挑选这个值 。只要保证这一点,我们就可以开始构建模拟器了。
模拟器的工作方式是这样的。
假设我们试图证明我们知道某个公钥的私钥 a,但是我们实际并不知道 a 的值。 模拟器假设验证者会选择某个 c 值来尝试,而且前提是诚实的验证者只会根据它的随机数发生器来选择数值 c,而不是基于证明者的任何输入。
  • 首先输出初始信息 作为证明者的第一条消息,并找出验证者选择的尝试值c。
  • 回退验证者(验证器),并在 范围内选取一个随机整数 z
  • 计算 并输出 为证明者的新初始消息。
  • 验证者再次尝试 c 时,输出值 z
请注意,副本将被视为对 a 值有效且分布均匀的知识证明。 验证者会接受这个输出作为对a值有效的知识证明,哪怕模拟器一开始并不知道私钥 a
这证明了如果我们可以回退验证者(器) ,那么(正如在本系列的第一篇文章中一样),我们总能“欺骗”验证者相信我们掌握了某个值的信息,哪怕在我们其实并不知道。 由于我们协议的统计分布与真实协议相同,意味着协议对一个诚实的验证者而言必然是零知识。
从交互到 非交互
到目前为止,我们已经解释类如何使用 Schnorr 协议来交互地证明与公钥对应的私钥 a 的信息。 这是一个非常有用的协议,但只有验证者在线并愿意与我们交互时才有效。
一个容易想到的问题是我们是否可以在非交互的情况下使用该协议。具体而言,你不在线的情况下,我可以完成证明吗。这种证明被称为 非交互式零知识证明(NIZK)。将 Schnorr 协议转化为非交互式证明看起来是相当困难的,因为该协议从根本上依赖于验证者随机的尝试。不过好在我们可以使用一个聪明的技巧。
这项技术是 Fiat 和 Shamir 在20世纪80年代开发的。 他们发现,如果你有一个靠谱的散列函数,你可以通过使用散列函数挑选尝试值来将交互式协议转换为非交互式协议。
具体而言,证明公钥对应的私钥a的改进后的知识证明协议如下:
  • 证明者选择 (就像在交互协议中那样)。
  • 现在,证明者计算一个尝试值 其中 是散列函数,并且M是(可选的)任意的消息字符串。
  • 计算 (就像在交互协议中那样)。
这里的结果是散列函数在没有和验证者交互的情况下挑选出了尝试值 c。原则上,如果散列函数“足够强”(意思是它是一个随机预言器),那么结果是证明者在非交互的情况下完成了 a 的知识证明,可以把结果发给验证者了。而且这种方式相对简单。
这个协议特别巧妙的是,它不仅仅是一个知识证明,也是一个签名机制。 也就是说,如果将消息放入(可选)值 M 中,将获得一个只有拥有私钥 a 的人能生成的签名。 由此产生的协议被称为 Schnorr 签名机制,它也是现实中像 EdDSA 这样密钥方案的基础。
好了,终于结束了。
这篇文章确实有点长了,尽管我还没说完。 希望在第三篇文章中有更多的时间交流,不过估计要三年后了。

作者注1:在这个定义中,陈述必须是真实的。

原文链接: https://blog.cryptographyengineering.com/2017/01/21/zero-knowledge-proofs-an-illustrated-primer-part-2/
作者: Matthew Green
翻译&校对: Pony小马 & Elisa

回复

使用道具 举报

724

主题

1091

帖子

4057

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
4057
 楼主| 发表于 2018-4-22 15:11:15 | 显示全部楼层
干货 | zkSNARKs(零知识证明)简述
hongji   

zkSNARKs 的成功实现让我们印象深刻,因为你可以在不执行,甚至不知道执行的具体内容是什么的情况下确定某个计算的结果是否正确 -- 而你唯一知道的信息就是它正确的完成了。但是不幸的是,大多数关于 zkSNARKs 的解释都浮于表面,而且他们往往会遗留下一些『魔法』,并暗示只有最聪明的人才能懂得 zkSNARKs 是如何工作的。实际上,zkSNARKs 可以总结为 4 个简单的技术,本篇博客将会逐一解释这些技术。任何懂得 RSA 加密系统工作原理的人都会对当前使用的 zkSNARKs 有一个更好的理解和认识。让我们拭目以待!
先做一个简单的摘要,我们当前使用的 zkSNARKs 包含 4 个主要的部分(在接下来的文章里我们会详细解释每个部分):
A) 编码成一个多项式问题
把需要验证的程序编写成一个二次的多项式方程:t(x) h(x) = w(x) v(x),当且仅当程序的计算结果正确时这个等式才成立。证明者需要说服验证者这个等式成立。
B) 简单随机抽样
验证者会选择一个私密评估点 s 来将多项式乘法和验证多项式函数相等的问题简化成简单乘法和验证等式 t(s)h(s) = w(s)v(s) 的问题。
这样做不但可以减小证明的大小,还可以大量的减小验证所需的时间。
C) 同态(Homomorphic)编码 / 加密
译者注:在1978年,Ron Rivest,Leonard Adleman,以及 Michael L. Dertouzos 就以银行为应用背景提出了同态加密的概念,当时使用的单词是 homomorphism,也就是和抽象代数的同态是一个单词。现在一般都使用 homomorphic encryption,国内密码学圈子基本也都称作同态加密。Ron Rivest 和 Leonard Adleman 分别就是著名的RSA算法中的 R 和 A(还有一位是 Adi Shamir)。
补充(来自白老师):同胚和同态在数学上不是一个意思。同胚指连续变形下的不变性,同态指映射下代数运算关系的保持性。
我们使用一个拥有一些同态属性的(并不是完全同态的,至少在实际使用中有一些不是同态的)编码 / 加密函数 E。这个函数允许证明者在不知道 s 的情况下计算 E(t(s)), E(h(s)), E(w(s)), E(v(s)),她只知道 E(s) 和一些其他有用的加密信息。
D) 零知识
证明者通过乘以一个数来替换 E(t(s)), E(h(s)), E(w(s)), E(v(s)) 的值,这样验证者就可以在不知道真实的编码值的情况下验证他们正确的结构了。
困难的问题在于对一个随机的私密数 k(k 不等于 0)来说,校验 t(s)h(s) = w(s)v(s) 和校验 t(s)h(s) k = w(s)v(s) 几乎是完全一样的,而不同点则是如果你只接收到了 (t(s)h(s) k) 和 w(s)v(s) 那么从中获取到 t(s)h(s) 或者 w(s)v(s) 的值就几乎不可能了。
当然了,这些都只是表面的部分,是为了让你更好的理解 zkSNARKs 的本质,现在让我们开始详细的讲解这些知识点。
RSA 和 零知识证明
现在让我们快速的回想一下 RSA 是如何工作的,先不管那些琐碎的细节。想想看,我们经常用一个数字对一些数字取模,而并不是所有的整数。这里的等式 “a + b ≡ c (mod n)” 等价于 “(a + b) % n = c % n”。注意,“(mod n)” 这个部分并不是应用在 “c” 上面的,而是应用在 “≡” 以及相同等式所以其他的 “≡” 上面。虽然这样非常难以阅读,但是我保证尽量少用他们。接着让我们回到 RSA:
证明者提供了下面的数字:
  • p,q:两个随机的私密素数
  • n := p q
  • d:1 < d < n – 1 的随机数
  • e:d e ≡ 1 (mod (p-1)(q-1))
公钥是 (e, n),私钥是 d。素数 p 和 q 可以丢弃,但是不能暴露。
消息 m 通过下面的公式加密:

c = E(m) 通过下面的公式解密:

因为,并且 m 的指数就是对 (p-1)(q-1) 这一组数取模,这样我们就得到了(译者注可以由费马小定理和中国剩余定理推出)。而且 RSA 的安全性是基于假设:n 不能被轻易有效的因式分解,d 不能通过 e 计算得到(如果我们知道 p 和 q 的话,就可以轻易得到我们想要的值)。
RSA 的一个牛逼的特性是同态乘法。通常来讲,如果你可以交换两个操作的顺序而不影响计算结果,那么我们就说这两个操作是同态的。在同态加密中,这就是你可以对加密数据进行计算的一个属性。完全同态加密是存在的,但是现在还没有应用到实际中,它能够对任何基于加密数据的程序完成计算。在这里对于 RSA 来说,我们只谈论 group multiplication。更准确的说就是:,用文字描述就是:两个加密信息的乘积等于两个信息乘积的加密。
这个同态的特性已经有一些乘法的零知识证明了:证明者知道一些私密的数字 x 和 y,并计算出了它们的乘积,但是只给验证者发送加密的版本:a = E(x), b = E(y) 以及 c = E(x y)。验证者检验等式 (a b) % n ≡ c % n 是否成立,此时验证者只知道加密版的乘积以及乘积是否被正确的计算,但是她不知道两个乘数和真正的乘积。如果你用加法来替代乘法,那就是一个主要操作为添加余额的区块链方向了。
交互式验证
我们已经对零知识这个概念有了一定的了解了,现在让我们着重看一下 zkSNARKs 的另一个主要的特性:简明性(succinctness)。之后你会看到这个简明性是 zkSNARKs 更牛逼的部分,因为零知识部分的实现就是因为这一特定编码,而这个特定的编码是一个有限形式的同态编码。
SNARKs 是 ** *succinct non-interactive arguments of knowledge * 的缩写。一般都通用设置之所以叫做交互式协议,是因为这里有一个证明者和一个验证者,证明者想要通过交换信息的方式让验证者相信一个表达式(比如 f(x) = y)。一般来说,没有证明者可以让验证者相信一个错误的表达式(可靠性),而且对于证明者来说一定存在一个确定的策略让验证者相信任何真实的表达式(完整性)**。SNARKs 各个部分的的意义如下:
  • Succinct:比起真正需要计算的长度来说,我们发送的信息大小是很小的
  • Non-interactive:没有或者只有很少很少的交互。对于 zkSNARKs 来说就是在证明者向验证者发送一条信息之后的过程。此外,SNARKs 还常常拥有叫做『公共验证者』的属性,它的意思是在没有再次交互的情况下任何人都可以验证,这对于区块链来说是至关重要的。
  • Arguments:验证者只对计算能力有限的证明者有效。拥有足够计算能力的证明者可以创造出关于错误表达式的(注意,只要拥有足够的计算能力,任何公钥加密系统都可以被破解)证明和参数。这也叫做『计算可靠性』,相对的还有『完美可靠性』。
  • of Knowledge:对于证明者来说在不知道一个叫做证据witness)(比如一个哈希函数的原象或者一个确定 Merkle-tree 节点的路径)的情况下,构造出一组参数和证明是不可能的。
如果你添加了零知识的前缀,那么在交互中你就需要一个性质,即验证者除了知道表达式的正确与否之外其他一无所知。尤其是验证者不能知道 *witness string *-- 稍后我们会详细解释这是什么。
先举个例子,让我们考虑下面的交易验证计算:当且仅当是账户 Merkle-trees(pre 和 post 状态)的根哈希,s 和 r 是发送者和接收者账户,是 Merkle-tree 的证明(当 v 从 s 的余额中转移到 r 的余额的过程中,能够证明在中 s 的余额至少是 v 并且他们的哈希结果是而不是),这些条件都成立时,成立。
如果我们知道所有输入的话,验证 f 的计算相对来说是比较容易的。因为我们可以将 f 转换成一个 zkSNARK,这时只有是公开的,就是 witness string。零知识的性质现在使得验证者能够检查证明者是否知道一些 witness,这些 witness 可以通过一个方式将根哈希从转成,而这样的转换又不影响正常的交易,但是验证者却不知道到底是谁发送了多少钱给谁。
关于零知识的部分相对正式的定义(仍然缺乏一些细节)就是:存在一个模拟器,它可以生成一些设置字段,但是却不知道私密的 witness,它还可以和验证者交互 -- 但是外部的观察者却不能分辨出哪个与验证者进行的交互,哪个是与证明者进行的交互。
NP 和 简化的复杂性理论
为了了解 zkSNARKs 能用于哪些问题和计算,我们不得不基于复杂的理论定义一些说法。如果你不知道什么是 “witness” 的话,那么即使『读』完零知识证明你也不会知道它是什么,并且你也不会了解到为什么 zkSNARKs 只适用于特定的多项式问题,如果真是这样的话,那么你就可以跳过本节了。
P 和 NP
首先,我们限制函数只能输出 0 和 1,并称这样的函数为问题(problems)。因为你可以单独的查询一个长长的结果的每一位(bit),所以这不是一个真正的限制,但是这样可以让定理变的简单一点。现在我们想衡量解决一个给定的问题(计算函数)到底有多『难』。对于一个数学函数 f 的特定机器的实现 M,给定一个输入 x,我们可以计算出这个函数 f 需要的步数 -- 这就叫做 x 在 M 上的执行时间,这里的『步数』其实不太重要。因为程序对于更大的输入往往会需要更多的步数,而这个执行时间则是用输入值的大小或者说长度(bit 的数量)来衡量。这就是例如『算法』的来源 -- 这就是一个当输入值大小为 n 时,至多需要个步数的算法。这里的『程序』和『算法』广义上是相同的。
执行时间至多为的程序也叫做 “polynomial-time programs”(多项式时间问题)。
在复杂性理论中有两个主要的类别,他们就是 P 问题和 NP 问题:
  • P 问题是具有多项式时间的一类问题
虽然 k 的指数对于一些问题来说确实非常大,但是实际上对于那些非人造的,k 不大于 4 的 P 问题仍然被认为是可以『解决的』的问题。要确认一笔比特币的交易就是一个 P 问题,因为经过评估它需要一个多项式时间(并且只能输出 0 和 1)。简单的说就是,如果你只是计算一些值而不去『搜索』,那么这个问题就是 P 问题。但是如果你不得不搜索一些东西,那么你就会进入到另一个叫做 NP 问题的类别中。
NP 类问题
几乎所有的 NP 类问题都是 zkSNARKs,今天在实际中使用的 zkSNARKs 在通常意义上讲都属于 NP 问题。而我们目前还不知道的是,有没有不属于 NP 问题的 zkSNARKs 存在。
所有的 NP 问题都有一个特定的结构,这个特定的结构来自于 NP 问题的定义:
  • NP 问题是 L(含有多项式时间的程序 V)的一类问题, 这个程序 V 可以在给定一个多项式尺度的叫做因子的 witness 的情况下验证这个因子。更正式的说就是: 当且仅当一些多项式尺度的字符串 w(被称作 witness)满足 V(x, w) = 1 时,L(x) = 1 成立。
让我们来看一个 NP 问题的例子,比如说一个布尔函数可满足性问题(SAT)。首先让我们先来定义一下布尔函数:
  • 任何变量 都是一个布尔函数(我们也会使用其他的字母来设变量)
  • 如果 f 是一个布尔函数,那么 ¬f 也是一个布尔函数(否命题)
  • 如果 f 和 g 都是布尔函数,那么 (f ∧ g) 和 (f ∨ g) 也都是布尔函数(∧ 是且, ∨ 是或)
字符串也是一个布尔函数。
如果可以给变量赋一个真值,然后布尔函数判断为 true(¬true 就是 false,¬false 就是 true,true ∧ false 是 false 等等一些普通的规则),我们就说这个布尔函数是可满足的,可满足性问题 SAT 就是所有可满足函数的集合。
  • 当且仅当 f 是一个可满足函数且不是 0 时,SAT(f) := 1 成立
上面的例子就不是可满足的,因此它不属于 SAT。证明一个给定公式满足定义并且同时确保它赋值的变量也是可满足的就是一个可以在多项式时间内被解决的问题。
P = NP ?
如果你将 NP 问题定义为长度为 0 的 witness strings,那么你会发现这就是 P 问题。因此 每个 P 问题其实都是 NP 问题。在复杂性理论研究中有一个主要的任务就是发掘出这两类问题的不同 -- 即一个不属于 P 的 NP 问题。在这里似乎是很显然的,但是如果你可以再一般情况下证明它,那么你可以获得 1 百万美元**。额外说一句,如果你可以反向证明,即 P 和 NP 是等价的,也可以获得那笔奖金。而数字货币领域有朝一日能够证明的概率很大。我这么说的原因是,比起一个哈希函数的碰撞或者根据地址找到私钥来说,找到一个工作难题解决办法的证明显然更容易一点。这些都是 NP 问题,因为你刚已经证明了 P = NP,那么对于这些 NP 问题来说就一定存在一个多项式时间的程序。但是本文就不讨论了,虽然大部分研究者都认为 P 问题和 NP 问题并不是等价的。
NP 完全问题
让我们再回到 SAT。这个看起来简单的问题有个有趣的特性就是它并不仅是 NP 问题,还是 NP 完全问题。『完全』这个词在这里和『图灵完备』是一个意思。这意味着它是 NP 中最难的问题,但是更重要的是 NP 完全的定义——任何 NP 问题的输入都可以用下面的方法转换成一个同样的 SAT 的输入:
所有 NP 问题 L 都有一个在多项式时间可计算的『还原函数(reduction function)』f:
  • L(x) = SAT(f(x))
这样的一个还原函数不能被看成一个编译器:编译器是可以将一些编程语言写的源代码等价的转换成另一种编程语言的机器,也就是拥有语义行为的机器语言。因为 SAT 是 NP 完全的,所以这样一个还原对于任何可能的 NP 问题都是存在的,比如给定一个合适的 block hash,验证一笔比特币交易是否合法。这里还可以将一笔交易转换成一个布尔函数的还原函数,因此当且仅当这个交易是合法的时候这个布尔函数就是可满足的。
还原示例
为了弄明白这样一个还原的方法,让我们先考虑评估多项式的问题。首先,让我们定义一个由整数常量,变量,加法,减法,乘法和(正确匹配的)括号构成的多项式(类似于布尔函数)。现在让我们考虑下面的问题:
  • 如果 f 是一个变量都来自于集合 {0, 1} 的多项式,并且其中包含一个零项,那么 PolyZero(f) := 1
现在我们就可以构建出一个从 SAT 到 PolyZero 的还原方法了,同时这也说明了 PolyZero 也是一个 NP 完全问题(验证它是否属于 NP 就当是留给你们的小练习啦)。
在一个布尔函数的结构要素上是可以定义一个还原函数 r 的。对于任何布尔函数 f,r(f) 的值拥有相同的变量个数,并且当且仅当为 0 时为 true,这里 true 是 1,false 是 0,并且 r(f) 只假设了来自集合 {0, 1} 的变量值 0 或者 1:

有些人可能会假设将 r((f ∧ g)) 定义为 r(f) + r(g),但是那样的话多项式的结果就会超出集合 {0, 1} 了。
使用函数 r,((x ∧ y) ∨¬x) 被转换成了 (1 – (1 – (1 – x))(1 – (1 – y))(1 – (1 – x))。
注意,对于 r 来说,每一个替换规则都满足了之前声明的目的,因此 r 也正确的实现了还原:
  • 当且仅当 r(f) 含有集合 {0, 1} 中的一个 0 时,SAT(f) = PolyZero(r(f)) 或者说 f 是可满足的
Witness preserving
从这个例子中你可以看出还原函数只定义了如何转换输入,但是当你仔细看的时候(或者阅读完如何完成一个可用的还原证据之后)你就会知道如何将一个可用 witness 和 输入一起转换。在我们的例子中,我们只定义了如何将函数转换为多项式,但是不知道如何将我们解释的证据转换成满足赋值的 witness。这个 witness 在同一时间转换对于交易来说不是必要的,但是通常都会包含。而这对于 zkSNARKs 来说是至关重要的,因为对于证明者来说他唯一的任务就是让验证者相信有这样一个 witness 存在,并且还不会暴露任何有关 witness 的信息。
Quadratic Span Programs
在上一部分中,我们看到了 NP 问题的计算是如何被相互化简的,尤其是那些 NP 完全问题,那些 NP 完全问题基本上又都再次形成了其他的 NP 问题——包括交易验证问题。那么对我们来说找到一个对所有 NP 问题都通用的 zkSNARKs 就变的很容易了:我们只需要选择适合的 NP 完全问题。所以如果我们想展示如何使用 zkSNARKs 来验证交易的话,那么展示如何处理这个确定的 NP 完全问题就是一个有效的方法,并且比从理论上解释更容易让人接受。
接下来就是基于论文GGPR12**(这里面链接的技术报告比原文的干货更多)来谈了,这篇论文的作者发现了一个叫做 Quadratic Span Programs(QSP)的问题,这个问题完全就是为 zkSNARKs 准备的。一个 Quadratic Span Program 是由一组多项式和寻找给定多项式倍数的线性组合任务构成。此外,输入字符串的每个单独的 bit 都限制了你能够使用的多项式。详细来说(通常来讲 GSPs 限制不是那么严格,但是我们就是需要这种限制的版本,因为后面我们会用到)就是:
对于输入长度为 n 的在域 F 上的 QSP 问题由下面这些部分构成:
  • 一组域 F 上的多项式
  • 域 F 上的一个多项式 t(目标多项式)
  • 一个单射函数 f:{(i, j) | 1 ≤ i ≤ n, j ∈ {0, 1}} → {1, …, m}
这里的任务很粗糙,就是给多项式乘以一个因子并把它们加起来(也叫做『线性组合』)使得它们的总和是 t 的倍数。对于每一个二进制输入字符串 u 来说,函数 f 限制了可以被使用的多项式,或者更严格的讲就是它们必须是线性组合的因子。正式的表示就是:
一个输入 u 会被 QSP 接受(或验证)当且仅当来自域 F 的元组满足:
  • 如果 k = f(i, u) 那么 (u 是 u 的第 i 位)
  • 如果 k = f(i, 1 - u) 那么
  • 目标多项式 t 整除

注意,在这里当 2n 小于 m 时,选择元组 a 和 b 仍然是有很大的自由度的。这就意味着 QSP 只对特定大小的输入是有价值的——这个问题可以通过使用非均匀复杂度来解决,非均匀复杂度这个话题今天我们不会深入的讲解,我们只需要知道当输入值很小时,我们的密码学也能良好运转。
做一个和布尔函数可满足性的类比,你可以看到因子作为被赋值的变量,或者说是 NP 问题的 witness。因为 QSP 是属于 NP 的,那么所有的验证者都必须(只要她知道因子)检查多项式 t 是否能够整除,这也是一个多项式时间的问题。
这里我们不会讨论如何将通用计算和线路问题简化成 QSP 问题,因为这对于我们了解基本概念没有任何帮助,我们只需要知道 QSP 是 NP 完全(或者说比一些非均匀分布的像 NP/poly 问题更完全)的就好了。实际上,这个简化是一个『工程』部分——必须要使用一种很聪明的方法才能让 QSP 问题尽可能的小并且有一些其他的优良特性。
关于 QSP 我们已知的一件事是如何更有效的验证它们:这个验证任务就是检验一个多项式能否整除另一个多项式。如果证明者可以提供一个满足的多项式 h,那么这个任务就被转变成了检验一个多项式恒等式,换句话说就是检验,其实就是检验某个特定的多项式是否是零多项式。虽然这看起来似乎很简单,但是我们接下来要使用的多项式相当巨大(阶数大概是原始电路控制级的 100 倍),以至于获得两个多项式的乘积并不是一件容易的事。
所以相比于真正的去计算以及它们的乘积,验证者只需要选择一个私密的随机点(这个点是 zCash 中 “toxic waste” 的一部分),然后对所有的 k 计算,并通过它们以及来验证等式:。所有这一系列的多项式加法,标量乘法和一个多项式乘积都可以被简化成域上的乘法和加法。
只在一个单点而不是在路径的所有点上验证多项式恒等式会降低安全性,但是证明者唯一可以作弊的情况是当不是零多项式时,即使证明者成功的获得了多项式的一个零项,但是她也不知道 s,并且比起 s(域中元素的数量)可能的值,0 的数量是很少的,所以实际中只在一个单点验证也是非常安全的。
zkSNARK 详解
现在让我们来详细的描述一下 QSP 上的 zkSNARK。它在开始设置阶段会执行每一个单独的 QSP。在 zCash 中,交易验证者的线路是固定的,因此 QSP 的多项式也是固定的,这个 QSP 在设置阶段只允许被执行一次,然后在所有的只有输入 u 不同的交易上复用。这个开始的设置会生成一个公共参考串(common reference string,CRS),验证者选择一个随机且私密的域元素,并在这个点加密多项式的值。验证者使用一些特定的加密方法 E 并在 CRS 中把公布出来。CRS 同时还包含一些可以让验证更有效率以及添加零知识属性的值。这里使用的加密方法 E 有一个明确的同构属性,这个属性可以让证明者在不知道的情况下计算出
如何使用零知识来简单估计一个多项式
首先让我们先来看一种简单的情况,即一个多项式在私密点上的加密估值,而不是完整的 QSP 问题。
为此,我们选择一个群(这里通常会使用椭圆曲线)和一个生成器 g。对于群中的元素 g,如果存在一个数字 n(群的顺序)使得列表包含群中的所有元素,那么我们就称 g 为『生成器』。加密方法很简单:。现在验证者选择一个私密域元素 s 并把它作为 CRS 的一部分公布出来
  • —— d 是所有多项式的最高阶
之后,s 就可以(确切的说是一定要)被忘记了。这就是 zCash 中说的『有毒废料(toxic waste)』,因为如果有人恢复了有毒废料和之后挑选的一些私密值,那么通过找到多项式中的零项,他就可以随意的伪造证据了。
在不知道 s 的情况下,证明者可以使用这些值对任意多项式 f 计算 E(f(s)):假设我们的多项式是要计算 E(f(s)) 的话,我们可以得到,这些值我们都可以从公开的 CRS 中获取,而不需要知道确定的 s。
这里唯一的问题是当 s 被销毁之后,验证者无法验证证明者是否正确的计算出了这个多项式。因此我们还需要选择另一个私密的域元素并公开下面的『转移』值:

设置阶段之后会随着 s 一起被销毁掉,验证者和证明者都不知道这个值。但是使用这些加密的值,证明者可以轻易的计算出 E(α f(s)),用上面的例子就是:。所以证明者只要公布 A := E(f(s)) 和 B := E(α f(s))),那么验证者就可以验证这些值是否匹配了。要验证是否匹配就要用到我们的另一个主要的手法『配对函数』e 了。椭圆曲线和配对函数一定要一起选择,那么 x 和 y 就会满足下面的式子:

使用这个配对函数,验证者就可以去检验了——注意一点, 验证者是知道的,因为它是 CRS 中的一部分。为了明确这个方法是可用的,且证明者没有作弊,让我们来看下面的等式:
然而,还有一个更重要的问题是证明者能否提供满足而不是的 A 和 B。这个问题的答案是『我们希望他不能』。严格地说,我们称之为『d 次方指数知识假设』,而且我们也不知道一个想作弊的证明者能不能做到这一点。这个假设同时也是其他用来证明公钥加密方案安全性的类似的假设的拓展,而这些假设似乎也不能确认他们到底是不是正确的。
实际上,上面的协议并不是真的要让验证者检验证明者提供的多项式,验证者其实只需要在点 s 上验证『几个』多项式就可以了。QSP 问题的 zkSNARK 还包含另外一个值,这个值可以让验证者确认证明者是否真的求出了正确的多项式。
这里的这个示例告诉我们验证者并不需要求出完整的多项式来证明这一点,仅仅使用配对函数就可以了。下一步我们就要添加零知识的部分了,这样验证者就不能构建任何关于 f(s) 值了,甚至连 E(f(s)) 这种加密信息也不行。
为此,证明者会挑选一个随机的然后发送,而不是。如果我们假设这个加密算法是不能被破解的,那么零知识的属性就很明显了。现在我们需要验证两个事情:1. 证明者确实可以计算出这些值。2. 验证者的结果依然为 true。
对于第一件事来说,注意:,同样的,
第二件事的话,因为验证者唯一要做的事情就是验证她接收到的 A 和 B 满足基于某个 a 的等式:A = E(a) 以及 B = E(α a)。这里的 a 显然满足 a = δ + f(s),实际上就是 a = f(s)。
好的,现在我们总算知道了一点关于在验证者不知道那个值的情况下,证明者是如何在一个加密的私密点上面计算出多项式加密值的。接下来让我们把这些应用到 QSP 问题中吧。
QSP 问题的 SNARK
还记得吗,在 QSP 问题中我们有一些多项式,目标多项式 t(最高阶为 d)以及一个二进制的输入字符串 u。证明者会找到(这些值都取决于 u)和多项式 h:

在上一节中我们已经解释了 CRS 是如何生成的。现在我们选择一个私密数字 s 和并把它们公布出来:

因为我们没有单个的多项式,而对于当前问题来说这一列多项式是固定的,所以我们也需要马上把推出的多项式公布出来:

我们还需要一个之后要用的的私密数字(它们会被用来验那些多项式是推算出来的,而不是任意的多项式),然后把它们公布出来:

这就是完整的 CRS。在实际的实现过程中,CRS 中的一些元素并不是必须的,但是那样会让我们的表达式变得很复杂。
现在证明者还需要做什么呢?她使用上面解释过的还原函数来找到多项式 h 和这些值。这里有一点非常重要,就是要使用一个 witness-preserving reduction(可以看上面的解释),因为只有到那个时候才能和 reduction 一起被计算出来,否则将会非常非常困难。为了描述证明者发送给验证者的证明,我们不得不再看一下 QSP 的定义。
这里有一个限制这些值的单射函数。因为相对来说 m 是比较大的,所以对于任何输入,函数 f 的输出的都不会包含这些数字。而这些下标没有被限制,所以我们就把他们叫,然后基于中的所有下标 k 定义。对于等式来说,我们的证明将由下面的式子构成:

最后一个等式用来检验是否使用了正确的多项式(这一部分还没有讲到,不过其他的例子会说到它)。要注意的是,我们所有的加密值,证明者只需要知道 CRS 就可以全部推算出来。
而验证者现在要做的还有这些:
因为 k 不是一个 "free" 的下标,所以的值可以通过输入 u(验证者也知道这个 u 的值,其实这就是要被校验的值)直接计算得出,验证者还可以通过 v 计算出总和:
  • 这里的 k 包含所有的『不在』 中的下标
有了上面的式子,验证者就可以通过配对函数 e(别害怕...(译者注:讲道理,还是有点怕...))来确认下面的等式了:

要了解这里关键概念的知识,你必须要知道配对函数是允许我们在加密信息上进行一些有限的计算的:首先我们可以使用任意多次的加法,但是不能使用乘法。其次这个加法是来自加密方法本身的加同态,乘法则是通过配对函数的两个参数来实现的。所以基本上就是在加密空间中用 1 乘以 W’,然后和乘以 W 做比较。回想一下上面的定义你就会发现 W 和 W’ 应该就是 E(w(s)) 和 E(α w(s))(如果证明者提供的是正确的证明)。
如果你还记得上面关于如何在一个私密点上推算多项式的话,这三个首先要检查的点基本上就可以确认证明者确实知道一些用 CRS 中的部分构造的多项式。第二个条目往往是用来确保证明者使用的是正确的多项式 v 和 w,而不是任意的多项式。而它背后的逻辑则是除了从中获取精确的值之外,证明者没办法计算出加密组合。因为在 CRS 中是隔离的,并不是 CRS 中的一部分,只有在和多项式组合起来的时候才知道的值。而将它们『混合』起来的唯一方法则是通过同样的加密 γ。
假设证明者提供了一个正确的证明,让我们检验一下等式是否满足。左边和右边的部分分别是:

第三个条目本质上就是检验了,这也是 QSP 问题主要的条件。有一个需要注意的是,要将加密值的乘法转换成非加密值的加法,因为
添加零知识
就像我在开头说的,零知识证明(zkSNARKS)最牛逼的特性其实不是零知识本身,而是一种简洁性。从现在开始我们将会看到如何添加这个零知识的属性,下面的一节将会着重介绍简洁性。零知识的思路是这样的,就是证明者现在通过一个随机私密的值来进行『移位』,然后再在其他的等式中『移位回来』以取得平衡。证明者会选择,然后在证明中执行下面的替换:
  • 来替换
  • 来替换
通过这两个替换,和 W 这两个包含 witness 因子编码的值基本上就变成了无法区别的随机值,因此要从 witness 中提取出来也不可能。大部分的等式检验对修改都是『免疫』的,而我们要确保正确的值就是 H 或者说是 h(s)。那我们就要确保:
  • ,或者说是

这两个等式成立。修改之后,我们得到:

然后将结果展开,我们就可以用 h(s) 来替换了:

在输入和 Witness 大小之间取一个折中的值
就像你在上面这些小节中看到的一样,我们的证明由一个群(就是一个椭圆曲线)的 7 个元素组成。而且验证者的工作就是检验一些配对函数的等式是否成立以及计算
这样一个跟随输入大小的线性任务。最主要的是,在这个验证过程中,既不需要 witness 字符串的大小,又不需要计算工作量来验证 QSP(没有 SNARKs)。这就意味着 SNARKs 的校验是个很复杂的问题,而简单的问题往往都是一样的。造成这个结果的主要原因则是,因为我们只在一个单独的点上面检验了多项式的一致性,而不是全部的点。多项式可以变的非常非常复杂,但是一个点始终是一个点。而唯一能影响到验证结果的参数就是安全性的等级(比如群的大小)和输入值的最大尺寸。
减小第二个参数是可行的,将输入值的一部分移动到 witness 中:我们不验证函数 f(u, w),u 是输入,w 是 witness,而是做一次 hash,然后验证:

这样就意味着我们可以用一个 hash 来代表输入 h(u) 了(这样就会变的更短),除了验证 f(x, w),我们还需要验证某个值 x 的 hash 等于 H(u)(这样的话,那 x 极有可能就等于 u 了)。这样就将原始输入 u 移动到 witness 字符串中了,这样虽然会增大 witness 的大小,但是输入值的大小就减小为一个常数了。
这简直太厉害了,因为这意味着我们可以在常数时间内完成对任何复杂表达式的检验。
和 Ethereum 的关系
因为验证计算是 Ethereum 区块链的核心,所以 zkSNARKs 和 Ethereum 关系紧密相连。有了 zkSNARKs,我们不但可以完成任何人都可证实的私密的计算,而且还可以高效的完成。
虽然 Ethereum 使用了一个图灵完备的虚拟机,但是当前在 Ethereum 上实现一个 zkSNARK 还是不可能的。从概念上讲,验证者的任务似乎很简单,但是配对函数是真的很难计算,而且在单个区块中还会消耗更多的 gas。椭圆曲线的乘法相对来讲已经非常复杂了,而配对函数将这个复杂度又增加了一个级别。
像 zCash 这种现存的 zkSNARK 系统对每一个任务都使用的是同样的问题,circuit 计算。在 zCash 中,就是交易验证。在 Ethereum 上,zkSNARKs 将不会只单单做一个计算问题,而是让所有的人都能够在不发布一个新的区块链的情况下构建他们自己的 zkSNARK 系统。每一个添加到 Ethereum 上的 zkSNARK 系统都需要进行一个新的私密的可信任的准备阶段(一些可以复用,一些不能),比如生成一个新的 CRS。像为一个『通用虚拟机』添加 zkSNARK 系统将会变的可能。这样的话当你使用一个新的实例时,你就不需要重新设置了,因为你将不再需要为 Ethereum 上新的智能合约发布一个新的区块链。
将 zkSNARKs 结合到 Ethereum 上
在 Ethereum 上启用 zkSNARKs 有很多种方式。所有的方式都可以为配对函数和椭圆曲线操作(其他必要的操作都很简单)减小真实的损耗,因此我们也要减小这些操作消耗的 gas。
  • 提升(确保)EVM 的性能
  • 只在确定的配对函数和椭圆曲线乘法上提升 EVM 的性能
第一项在长期显然会得到很好的回报,但是实现起来难度比较大。我们现在已经在对 EVM 添加一些新的功能和限制了,例如更好的支持及时编译以及在现存实现下最小改动的解释器的实现。当然也不排除直接用 eWASM 来替换 EVM。
第二项则可以通过强制所有的 Ethereum 客户端执行一个确定的配对函数和确定的椭圆曲线乘法的叫做预编译合约的东西来实现。这样做的好处就是实现起来既简单又快速。而缺点呢则是这样做我们就会固定在一个确定的的配对函数和一个确定的椭圆曲线上。所有 Ethereum 上新的客户端都不得不再实现一遍这个预编译合约。所有,如果有什么新的进展,或者有人可以找到更好的 zkSNARKs 的方法,更好的配对函数,更好的椭圆曲线,又或者发现了椭圆曲线,配对函数和 zkSNARK 的一些缺点,那么我们就会添加到新的预编译合约中。

原文链接: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
作者: Christian Reitwiessner
翻译: 杨文涛

回复

使用道具 举报

724

主题

1091

帖子

4057

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
4057
 楼主| 发表于 2018-4-22 15:29:21 | 显示全部楼层
一个更优的零知识证明:Bulletproofs Lilymoana



在2015年我们宣布机密交易(CT)作为侧链Elements Alpha的主要特征。该特征用Pedersen commitments取代了交易金额,这种一种隐藏金额的加密工具,同时保留了任何人验证在特定交易内余额的能力。
CT面临的主要难题是让它交易变得非常大而且验证缓慢,因为它要求每个交易输出包含一个rangeproof,这是一种零知识证明,证明金额太小而不会溢出。普通数字签名小于100个字节,并且只需不到100微秒的时间就可以验证,而 rangeproofs的大小是几千个字节,并需要几个毫秒才能验证。实际上,rangeproofs是使用它们的任何交易中绝大部分的交易数据。
尽管我们的rangeproofs,基于Borromean环形签名,在文献中是最快的和最小的,但对于我们需要的范围大小(range sizes)和无信任的环境下,它们仍然非常的大。
自从2015年来,我们一直都在努力提高rangeproofs的效率。在2017年初,Adam Back发现rangeproofs减小了24%,不过验证速度并没有提高。在这段期间,我们曾向我们的朋友和同事,密码学家Dan Boneh和在斯坦福大学的BenediktBünz提到这个问题,他们对改善的空间都相当的有信心。
他们最终震惊了我们。
更小,更快,更强健
根据Bootle等人在2016年基于离散对数的零知识证明的空间效率方面的改进,Bulletproofs是一种更加空间高效的零知识证明的形式。重要的是,为了我们的目的,这些证明还具有对提交值如Pedersen commitments和公钥的原生支持。这让我们可以在通用的零知识框架下实现诸如rangeproofs之类的功能,而不用在零知识中实现复杂的椭圆曲线算法。
更强健。为了限制交易大小,我们老版本的rangeproofs限制输出范围大小为2^32。这限制了输出大约到43 BTC,不过这可以通过将证明的粒度从1聪减少到10聪或者100聪来增加,或者通过从零开始增加最小值来增加。这些调整是可能的,但是使用了显示的金额,限制了系统提供的隐私。
这些32位的rangeproofs大小大约为2.5 KiB。使用Adam的优化,它们将有2 KiB 的大小。使用Bulletproofs,它们应该是610字节。有了这么小的大小,我们可以将范围(range)加倍到64位,从而无需进行任何的非隐私调整。这样的话,就会将610字节增加到1220字节,是吗?不是,实际上,64位的Bulletproof rangeproofs 仅仅只有674字节。
更小。我们将范围(range)的大小增加了一倍,但证明的大小只增加了64个字节的原因是:它们以对数级增长。这是通过使用Bootle等人在2016年论文中的内部产品参数的变体来完成的。(Jonathan Bootle也帮助了Benedikt和Dan开发Bulletproofs。 )具体来说,论文中描述的对数大小的内部产品参数在Bulletproofs中进一步降低了,从6log(N)曲线点降到2log(N)。
相同的技巧可以将一个交易内多个rangeproofs整合到一个中,同样只会增加很少的字节数。2个rangeproofs的整合是738字节,4个则是802字节,8个是866字节。8个64位经典rangeproofs将会超过40000字节。
更快。这种节省空间很大,但是我们对该技术的初步分析显示验证速度会比老版的rangeproofs慢。似乎验证一个64位的证明需要超过200个标量点乘法,每个都是繁重的50微秒事务,而老版的rangeproofs只需要128个标量点乘法。
但是经过进一步的分析后,我们可以组合很多乘法,将总数减少到147个。更重要的是,我们意识到,与老版的rangeproofs不同,这些乘法都是不依赖对方的,所以我们可以在一个批量中完成它们。作为我们汇总签名工作的一部分,我们知道如何快速批量相乘。 我和Pieter Wuille,Greg Maxwell,Jonas Nick,Peter Dettman在这个问题上花费了几个月的时间,最终将147个乘法的速度降低到每个只需15.5微秒,让Bulletproof的总验证时间降到2.3 ms,而老版的证明需要5.8 ms。
在速度上已经不仅增加了一倍,而且由于我们的批量乘法随着你提供的点越多速度越快,所以整合的性能数字就更加令人印象深刻。8个64位Bulletproofs的整合可以在11.5 ms内验证完,而对于老版的证明需要46.8 ms,速度超过了4倍。
不过它能变得更好。Bulletproofs支持非常高效的批量验证形式。在我们需要完成的147次乘法中,其中130次在每个Bulletproof中使用相同的点,这意味着在批量验证期间,这130次乘法是可以组合的,剩下只有17次是新的乘法。实际上,这种小成本仅仅以对数级增加:对于2个范围(ranges)的整合,每个额外的证明需要19个额外的点,而4个范围(ranges)的整合,每个证明需要21个点。
注意我们引入了两个相似但是独立的概念:整合(aggregation)是指证明程序将多个rangeproofs组合成1个;而批量处理(batching)是指验证程序同时检测多个单独的证明。
这意味着两个64位的rangeproofs可以在2.7 ms内完成验证,或者每个范围(range)1.4 ms。500个rangeproofs可以在130 ms内完成验证,或者每个范围(range)0.26 ms,这比老版的证明提高了23倍。不过由于整合,它还可以变的更加可观。500个8个一整合的rangeproofs(一共是4000个范围(ranges))可以在305 ms内验证完,或者每个范围 76 微秒,比老版的rangeproofs提高了75倍。
随着日益高效的标量点乘法不再是主导效应,这种影响最终会围绕64个证明的整合最大化。在这一点上,我们可以以每个范围(range)46微秒来批量验证,速度提高了125倍。作为参考,椭圆曲线数字签名算法(ECDSA)签名大约需要55微秒,所以在这种级别的整合下,rangeproofs甚至不是交易验证的主要部分。当然,我们不太可能在区块链上看见64个输出交易,不过这种速度在非区块链环境中(如 Provisions
)是可能的。
这种验证同样也是节约内存的,验证单个rangeproof需要 100 KiB,随着大小而增加减。
你可以证明任何事情(如果它是真的话)
Bulletproofs比rangeproofs更加的通用。它们可以被用来在零知识中证明任意的陈述。它们与SNARKsSTARKs相当,不过它们原生支持椭圆曲线(EC)公钥和Pedersen commitments(因此通常不需要在程序中实现EC算法)。此外,与SNARK不同的是,Bulletproofs在无信任环境的标准猜想下拥有完整的128位安全性。与STARK不同,它们在典型的计算机硬件上足以快速证明和验证合理大小的问题。
作为一个具体的例子,考虑SHA2压缩功能的一次运行。我们的证明程序需要少于 30 MiB的内存和大约21秒来证明SHA2原像的知识。验证需要大约23 MiB的内存和75 ms,但是我们可以用大约每个证明5 ms和13.4 KiB批量验证额外的证明。
我们的证明程序比SNARK更节省内存:在相同的系统中,SHA2的一个SNARK证明只需要4秒但是要75 MiB内存。验证时,每个电路需要大量的一次性预计算(需要被证明的陈述),然后只需要3-5 ms和很少的内存就可以验证。这些数字不会随着电路的增加而增加,所以对于超过几千门的电路,即使与我们的批量验证相比,SNARK也明显是赢家。不幸的是,这是以可信赖的环境和新的加密猜想为代价的。
在证明程序和验证程序上,Bulletproofs仍有很大的优化空间。
验证任意陈述句的能力——不管是Bulletproofs,SNARKs或者STARKs,都有很多的应用。它可以用于实现普通的数字签名,包括(可追踪的)环形签名和阈值签名,对于大型环来说,在验证时间和证明大小方面它都比传统方案要高效。它的使用不限于此,它还可以用来可靠的销售数独问题,可以用于多方计算,即使有秘密数据的情况下还是可以证明每方都是诚实行事。(特别是在MuSig这样的多重签名方案中,这允许使用确定性的随机数生成,而不需要签名者维护状态或容易受到随机重用攻击。)它还可以用来证明哈希原像(preimages)。
后一种应用,哈希原像,是特别有趣的,因为它可以用来创建零知识Merkle证明,包含在大规模集合(有数百万甚至数十亿元素)的高效证明。我们将在未来的文章中探讨这一点。
总结
  • Bulletproofs是通用零知识证明(类似SNARKs)
  • 它们可以用来扩展多方协议,如多重签名或零知识应急支付
  • Bulletproofs提供了一个更加高效的CT rangeproofs版本(批量验证时,速度提高超过23倍)
  • 这些rangeproofs可以在交易中进行整合,然而大小只以对数级增长
  • 通过充分的整合,例如Provisions,批量验证的速度比老版的证明快了超过130倍
我们很感谢Bootle等人开发的内部产品参数,它引导了我们。同样也感谢Benedikt Bünz和Dan Boneh,我们的合著者,他们做了大量的创造性工作。感谢Sean Bowe和Daira Hopwood为优化算术电路而做的研究。
链接
翻译作者: 许莉
原文地址: Bulletproofs Faster Rangeproofs and Much More



回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|Hi,Tokens  |网站地图

GMT+8, 2019-12-14 04:33 , Processed in 0.079085 second(s), 4 queries , File On.

Powered by Discuz! X3.3

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表