系统学习区块链

现在有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值。

不投资毋宁死

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

谢谢阅读

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

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