学习
实践
活动
专区
工具
TVP
写文章

系统学习区块链

现在有3组经过哈希和RLP处理过的key/value对(0x表示十六进制),如下:

我们的任务就是要把这3对key/value用一棵MPT树组织起来。

首先是第1对:

此时,该MPT只有这一个叶子节点,所以整个MPT就是这个样子吗?

不对,其实是这样的:

两者有什么区别?仔细瞧瞧。

没错,key的前面加了个20,为什么呢?因为MPT对key还有这么一套规矩:

1.如果节点是扩展节点,且key长度为偶数,key加前缀00;

2. 如果节点是扩展节点,且key长度为奇数,key加前缀1;

3. 如果节点是叶子节点,且key长度为偶数,key加前缀20;

4. 如果节点是叶子节点,且key长度为奇数,key加前缀3;

(注:key长度的奇偶性的单位是半字节—nibble,一个16进制数字就是一个nibble。)

这套规矩的主要目的是识别扩展节点和叶子节点,同时,将key的长度补足成偶数,便于处理。这个节点是叶子节点,且key长32个nibble,所以前面加了20。

然后再把第2对加到树上。因为第1对的key是以0开头,第2对的key是以c开头,两个并不一样,所以得构造一个分支节点,然后把这两个叶子节点放到这个分支节点下,如图:

分支节点有0到f共16个分支,第1个叶子节点的key以0开头,所以在0号分支下,因为key最前面的0已经在分支节点表达,所以,后面的叶子节点的key是以0x4485开头,同时,长度因为少了1位,变成奇数,所以前缀加了个3,最终变成0x34485…。同理,第2个叶子节点在c号分支下,且key变为0x389ef…。

相对应的,分支节点的数组的0号元素存储了第1个叶子节点的哈希值,c号元素存储了第2个叶子节点的哈希值。数组的其他元素都是空的。同时,分支节点的value值也是空的,因为没有要存储的信息。

最后,我们再把第3对加上去。因为第3对和第2对的key前面几位都相同,所以需要引入一个扩展节点,然后在扩展节点下再引入一个分支节点,将两者的叶子节点挂在下面,如图:

第2和第3个节点的key相同的部分,是c89,因为c已经在第一个分支节点表达,所以剩下的89就在扩展节点表达,同时按照上面说的规则,在89前面加上00,于是扩展节点的key为0x0089。

扩展节点的value部分存储的是一个哈希,这个哈希是将它下面的分支节点的所有数据进行RLP编码,然后再做哈希得出来的值。同时,第一个分支节点的数组的C号元素的哈希值也必须重新计算了,因为它现在等于下面这个扩展节点的哈希值。第二个分支节点以及下面挂的两个叶子节点的原理跟上面一样,不再细述。

到此为止,整棵MPT树还缺少一个东西,那就是根哈希。根哈希其实很简单,就是对最上面的那个节点做哈希即可。以太坊合约账户里的storageRoot存储的就是根哈希而已。

最后,我们以第2对key/value(0xc89efd...,0x101360...)为例,来看看这棵MPT树的具体用处:

首先是存在性证明,因为,如果key或value值稍微有变动,通过一层层的哈希,会导致根哈希大相径庭;

其次是寻址,我们通过这个key值,可以一步步地找到对应的value,key的第一位是c,于是找到分支节点的c号元素,然后在c号下找到下挂的扩展节点,89已经在扩展节点表达,继续往下,找到扩展节点下挂的分支节点,在e号元素下找到最终的叶子节点,这里面就存储了value值。

不投资毋宁死

自由,就是拥有选择的权利,而每一次选择都是一次投资。

谢谢阅读

✬如果你喜欢这篇文章,欢迎分享到朋友圈✬

评论功能现已开启,灰常接受一切形式的吐槽和赞美☺

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181006G03O9D00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

关注

腾讯云开发者公众号
10元无门槛代金券
洞察腾讯核心技术
剖析业界实践案例
腾讯云开发者公众号二维码

扫码关注腾讯云开发者

领取腾讯云代金券