秘密区块链当中的sie:理解Merkle pollards

  在加密货币的世界中,Merkle树被用作一种有效的方法来证明在一个大值集合中以最小的存储空间存在一个特定的值。本文介绍了Merkle树,并展示了如何通过存储多个级别的分支 (称为“Merkle pollards”)来显著减少对同一棵树的重复证明。

  哈希

  哈希函数将可变大小的数据块(在本例中是水果的名称)转换为固定大小的值(称为“哈希值”)。下面是一个显示“Apple”和“Orange”哈希值的例子:

  

  哈希函数有各种各样的功能,但最重要的是, 即使稍微不同的值也会产生非常不同的哈希值,而且从哈希值返回到值在数学上非常困难(通常意味着没有比猜测哈希值并查看匹配的方法更快)。

  Merkle树

  Merkle树是一种将多个值及其哈希值组合在一起以将它们缩减为单个固定大小值的方法。

  树的顶部是值,称为“叶”。将每个叶哈希以创建顶级分支,将相邻的分哈希值在一起以创建中间分支。最终,这将产生一个哈希值,称为Merkle根。下面是一个Merkle树的图形示例:

  

  上面的例子显示了一个具有8个值和4个级别的树;根在底部,标记为0xd576…ffd9。

  如前所述,即使是稍微不同的值也会生成非常不同的哈希值。此更改将对树的所有级别产生后续影响,并最终生成不同的根。例如,将单个值“Peach”更改为“Pear”会导致Merkle树发生如下所示的变化:

  

  单个更改对树的影响(以灰色显示)

  Merkle树是可复制的: 给定相同的值以相同的顺序,Merkle树的分支和根总是具有相同的哈希值。

  Merkle路径

  Merkle路径就是从值到Merkle根的哈希值集合。下面的例子显示了值“Peach”的Merkle路径:

  

  Peach的Merkle路径

  Merkle证明

  Merkle证明是一种证明某个值是一组数据的一部分而不需要公开任何其他值的方法。

  

  Merkle证明

  Merkle证明需要三样东西:一个值(用红色表示)、中间哈希值(用绿色表示)和Merkle根(用蓝色表示)。对于每个值,都有一组不同的中间哈希值。

  区块链中通常使用Merkle证明来表明一个值在一个集合中,而不需要将整个集合存储在区块链上。例如,以太坊代币合约可能具有白名单特性,允许选择帐户购买代币。与其将每个白名单上的帐户都存储在区块链上(如果白名单上有成千上万个帐户,那么这将非常昂贵),还不如创建帐户的Merkle树,只存储在区块链的根上。

  注意Merkle路径中的哈希值与最后两个图所示的证明中的哈希值之间的关系:证明中的每个哈希值都是树中同一级别路径中的哈希值的兄弟级。这生动地展示了证明提供了为值重新创建路径的能力,这就是为什么最终结果将是Merkle根。

  如上所述,使用Merkle证明的一些好处是:

  · 与存储值相比,所需的链上存储要小得多

  · 完整的值集不会通过在链上公开存储

  · 通过确认一个证明来确认一组值中存在一个特定值的成本比对照该集合进行检查要低(更快和更便宜)

  重复证明

  在上面的示例中,每个帐户只发送验证它们是否在白名单上所需的单个证明。Merkle树的另一种用途是作为知识的概率证明(通常称为STARKs)的一部分,其中每个证明都增加了Merkle树的创建者(称为“证明者”)知道构成树的所有值的可能性。在这种情况下,验证者通常对包含数万甚至数十万值的单个Merkle树生成数百个证明。Merkle的根和证明一起发送给验证者以确认它们的有效性。

  在我们的原始示例的上下文中检查重复证明,下面是针对同一棵树的三个证明:

  

  使用相同的Merkle根进行重复证明

  可以看到,发送Merkle根(一次)加上证明总共需要发送10个哈希值:一个哈希值用于根,三个哈希值用于每个证明。

  这更有效吗?可以看到,在树的第一层,只有两个值c0b7…da30和6 ff9……8e3d,证明总共发送了三个哈希值(每个证明一个)。

  

  使用扩展的Merkle根进行重复证明

  可以看到,总共发送扩展的Merkle根(一次)和证明现在涉及到发送9个哈希值:根3个哈希值,每个证明2个哈希值。虽然这种减少看起来很小,但随着证明数量的增加,它会显著增加。

  Merkle pollards

  我们把延伸的Merkle根称为Merkle pollards。它被定义为Merkle根加上若干层中间分支。Merkle pollards是树根以上形成该pollards的分支数(一棵树的Merkle pollards阶数为0,相当于树根)。一级Merkle pollard包含一级中间分支,如下图所示:

  

  2阶Merkle pollards包含两层中间分支,如下图所示:

  

  Merkle pollards在许多重复证明的情况下对同一Merkle树使用Merklepollard减少这两个证明的大小和时间验证证明。计算Merkle pollards最优阶数的数学就是证明数以2为底对数的底数。下面是一个低阶表,以及由此节省的空间和时间:

  

  Merkle pollard的好处在不同的订单使用节省的Merkle pollard可以迅速增加。例如,使用Merkle pollards将使用564KB的Merkle根的测试完全证明减少到346KB,减少了40%。在转递和核查证明所花的时间内也看到了减少。

  更多区块链信息:www.qukuaiwang.com.cn/news

文章内容系本站作者个人观点,不代表本站对其观点赞同或支持,文章的版权归该作者所有。如需转载,请注明文章来源。本文地址:http://www.cis.net.cn/kejikuaixun/43138.html
留言与评论(共有 条评论)
验证码:

最新文章

理解Merkle pollards

科技快讯
在加密货币的世界中,Merkle树被用作一种有效的方法来证明在一个大值集合中以最小的存储空间存在一个特定的值。本文介绍了Merkle树,并展示了如何通过存储多个级别的分支(称为“Merklepolla

波场TRX:抄袭达人、炒作圣手,靠营销上位,具有控盘风险

科技快讯
前言:作为公链中的老大哥,以太坊面对挑战与蹭热度已是家常便饭。2017年4月,波场币创始人孙宇晨在推特上列举了波场币优于以太坊的7条理由,言外之意:波场币力压以太坊。对此,V神并没有置之不理,也发了一条推特反唇相讥,直指波场白皮书抄袭的事实。能赢得V神的回怼,可见波场币这一次热度蹭得非常成功,吸引了新一批看向波场币的目光。一、

注册送100USDT,100%赠金靠谱不? 1月22日行情分析。

科技快讯
近期很多平台都推出了合约奖励、还有合约盈利奖励,最近有个交易平台-币虎交易平台,也推出了合约奖励,注册送100USDT,并且首次充值可以获得100%的充值赠金。后期还将开通合约大赛,总奖励金额达到500万。这个活动力度还是比较大的。但是圈哥了解了一下发现,这个平台的合约只有20倍和30倍,还是有一点大的,稍微不

百晓生说币7/30数字货币行情分析:比特币多、空交战进入尾声,盘变在即

科技快讯
今日行情分析BTC多、空交战持续6天,中间出现过ETF利空依然势均力敌,仔细回顾几天交手,从6200到8500压力区,卖盘部分解套回调至8200后持续横盘,此轮急拉已经不是简单的比特币ETF刺激,可能另有所图,特别是最近几天回调至低于8200后迅速拉升态度坚决,可以看出买盘和卖盘目前价位达成短

1.22比特币半死不活的走势,给你带来的是利润还是?

科技快讯
行情又是这样半死不活的样子,看了我真的没有分析的欲望,一直不到一百个点多的区间震荡,虽然早就预料到了最近会是小区间震荡的行情,但是没有想到这个行情区间竟然小到这样的地步,还好昨天把仓位加大了不少,盈利还可以。不然几十个点的利润真的是不知

王团长日记348篇:1998年的时候,我在干吗?

科技快讯
下午的时候,跑到FIBOS办公室玩了玩,他们在南京下关区,现在下关区撤销后,属于鼓楼区管辖。都在南京,离我们不远,开车20分钟就到了,以前一直微信约了好久,被各种各样的事情耽搁了,没去成。趁着下午比较清闲,就跑过去蹭茶喝,红茶,挺香的。到FIBOS公司的时候下午3点半左右,一眼扫过去,有几十个人,都在认真的码代码,很忙碌,现在在区块链行业能踏踏

数字货币浪潮

科技快讯
数字货币以及爱惜欧领域的重大创新,让区块链的红利初现。在巨利之下,每个人都可能成为它的“布道者”和“受道者”,这将推动区块链技术的迅速落地。虽然关于数字货币,尤其是爱惜欧争议重重,但是泡沫之下,我们不能否认的是,区块链在数字货币、爱惜欧等领域的重大创新,巨大地提升了不管是对企业、还是对个人的驱动力,区块链的红利正在迅

R3区块链联盟考虑在俄罗斯成立办事处

科技快讯
翻译:Annie_Xu俄罗斯支付服务公司及联盟成员Qiwi称,领导全球金融机构区块链联盟的金融创新公司R3也许在俄罗斯成立办事处。Qiwi代表说,R3考虑2017年秋天在俄罗斯莫斯科成立新的办事处,预计员工十人。总

区块链加速电子游戏行业的发展

科技快讯
传统上,电子游戏职业生涯涉及编程、设计、测试和市场营销等领域。Cryptogames通过将玩家包括在游戏社区中,从而拓宽了这些视野。让我们来看看其中的一些游戏,以及它们是如何帮助扩展区块链的视频游戏生涯的。BUFF,关于如何运作的真相想象一个游戏可以让你赚大钱,激动不。BUFF项目就实现了这样一个生态系统。BUFF的目标是提供一个

加拿大首个受监管的比特币信托获得共同基金信托的法律地位

科技快讯
加拿大一受监管信托在法律上被认可为共同基金信托,使合格投资者可以通过政府支持的节税投资计划投资该信托。这项投资获得了安大略省证券委员会和不列颠哥伦比亚证券委员会的批准。共同基金信托的法律地位9月10日FirstBlock资本公司宣布,他们的旗舰产品FBCBitcoinTrust已经获得共同基金信托的法律地位。该信托成为首