http://www.7klian.com

什么是稀疏默克尔树多值证明

将 Kumquat 哈希获得 2aab…6f791
固然默克尔树的多值证明晰实节减了一些存储空间,但个中一些数据可以用其他方法获得,所以移除这些数据可以进一步节减存储空间。(译者注:可通过其他方法获得的数据,就不需要存储在证明中,只要在需要时可以或许获得即可)

对比于单条证明时总共需要的 9 其中间分支哈希值,默克尔多值证明只需要 7 个哈希值,这就节减了存储空间。

从上图可以看出,3 个证明总共包括 9 其中间分支的哈希值(即由绿色标出的部门):每条证明有 3 个哈希值。将这 3 个证明组合成如下图所示的布局,即成多值证明:

将e336…ed14 和 a6e4…87df 哈希获得 6ff9…8e3d
稀疏的多值证明
科普 | 什么是默克尔截顶

稀疏默克尔树多值证明(Sparse Merkle multiproofs)是对默克尔树截顶(Merkle pollard)的一种替代方案,可在为证明一棵默克尔树上存在多个值时提供空间上较为节省的证明。什么是默克尔证明、默克尔树截顶,我已在前一篇··文章中表明过了;推荐您先阅读并领略这些观念再来阅读本文。接下来,,文本将用下图的默克尔树来表明多值证明:

将c0b7…da30 和 6ff9…8e3d 哈希获得 d576…ffd9

稀疏的默克尔树多值证明将需要包括的哈希值数量从 9 个淘汰到了 3 个。证明结果沟通时,稀疏的多值证明也比默克尔截顶更有效,因为后者需要 6 个哈希值。

稀疏多值证明最早由 Vitalik Buterin 提出。
比拟稀疏多值证明与默克尔截顶
多值证明(multiproof)就是把一棵默克尔树中的一组证明打包在一起,从而节减存储空间。譬喻,下面是上图所示默克尔树的 3 条默克尔证明:

实现样例
从上表中可以看出,稀疏的多值证明比默克尔树截顶节减更多的存储空间,那么为什么还要利用默克尔树截顶呢?因为稀疏的多值证明相对付默克尔树截顶,拥有一些差异的特性,主要有以下几点:
· 稀疏的多值证明的巨细是可变的,而默克尔树截顶在给定默克尔树和总证明数时,其证明巨细是牢靠的
· 稀疏的多值证明在生成及验证证明时,需要更多的内存和 CPU 周期

值得留意的是,多值证明的节减量是近似值,因为能节减几多取决于被证明的值在默克尔树中的位置以及可以被移除的中间分支哈希值个数。
将bc4f…8d3f 和 59a0…421d哈希获得 9c15…5dec
· 稀疏的多值证明很难并行地生成和验证
将d596…66ef 和 9c15…5dec 哈希获得 c0b7…da30

将Peach 哈希获得 59a0…421d
验证者获得稀疏的多值证明后,为了验证那些值是默克尔树的一部门,需要执行以下的步调(在默克尔树中,依照从左到右,从上到下的顺序):
https://github.com/wealdtech/go-merkletree/ 提供了稀疏的默克尔树多值证明的 Go 语言实现 。

多值证明
下图比拟了默克尔树中值和证明的数量变革时,默克尔树截顶和默克尔树中稀疏的多值证明在存储默克尔证明时可以节省的空间存储量:

至此可以把最终获得的哈希值与默克尔树的根哈希值做较量,假如二者一致,则认定所有的值都在该默克尔树中。
将 2aab…6f79 和 45cf…14d9哈希获得 a6e4…87df
总的来说,还要看单个应用的需求来抉择哪个更符合。可是这两种要领都比单独的默克尔证明节减更多的存储空间,因此当需要对同一棵默克尔树提供多个证明时,可以思量利用这两种要领。
· 在多值证明要领中,所有值的证明都是一起生成、一起获得验证的;而在截顶要领中,各个值的证明是别离生成、别离验证的(译者注:生成及验证时,对截顶来说,详细是哪个值,只需要这个值和相关的证明即可,对付多值证明,则需要把要验证的多个值,以及多个值对应的证明都拿出来)

移除这些哈希值后,可以获得 默克尔树中稀疏的多值证明,如下图所示:

以上图的默克尔树多值证明为例,很多中间分支的哈希值都可以被计较出来。好比验证者将已知的值 Banana 和 Peach 通过哈希函数计较后,可以获得哈希值 bc4F…8d3f 和 59a0…421d。对付与根节点相连的两个节点的哈希值 c0b7…da30 和 6ff9…8e3d,可以通过其孩子节点(与两个节点直接相连的,并处于上方的节点)的哈希值计较出来。因为孩子节点的哈希值要么是证明中包括的,要么可以通过再上一层的哈希值计较出来。下图中黄色的节点标志了这 4 个可由计较获得的哈希值:

将 Banana 哈希获得 bc4f…8d3f

译者注:网络是一台富状态(stateful)的世界计较机,其状态包罗状态余额、生意业务流水号(nonce)、合约代码及合约存储内容等。在技能上,这些状态数据是靠一种叫做 “默克尔树” 的布局来组织的,因此,以太坊世界状态及其会见、更新,便可表达为一棵默克尔树及其会见、更新。同样地,所有跟默克尔树相关的数据证明及验证操纵,都可以在以太坊协议的语境下被领略为状态的证明及验证操纵。实际上,默克尔树是我们领略、操作、改造以太坊协议不行或缺的一环。本文先容了一种可以证明多个值存在于同一棵默克尔树上的要领,因此也可以说,这就是在先容如何证明多个以太坊状态附属于同一时刻的世界状态的要领。

(译者注:“将某个值哈希”指:将值作为哈希函数的输入,获得随机的一串输出)
· 一些环境下,因为用于传输信息的编码系统差异,大概会导致稀疏的多值证明比默克尔树截顶需要更多的空间;因此发起利用之前做一下测试

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

相关文章阅读