MPT(Merkle Patricia Tree)

简介

MPT(是trie前缀数的变种)是以太坊用到的一种数据结构，在每个区块的头部中都会包含3个root值，分别为stateRoot、txTrieRoot、receiptTrieRoot，这三个值都是通过MPT得到的树的根值。

image.png

1. stateRoot
   状态树随着时间的变化在更新，它的path是 sha3(ethereumAddress) , value是 rlp(ethereumAccount),stateRoot的值就是状态树的根hash值

其中rlp是以太坊上用到的一种编解码方法

2. txTrieRoot
   每个块都有一个单独的transaction树，它的path是 rlp(transactionIndex)，其中transactionIndex是被挖到时在该块中的序列。所以它的值直到被旷工挖到时才能确定。块被挖到后该树就不会更新。

3. receiptTrieRoot
   每个块都有自己的一个receipt树，它的path是 rlp(transactionIndex)，其中transactionIndex是被挖到时在该块中的序列。不会更新

它可以存储任何（key,value）形式的数据，它保证对于任意（key,value）拥有同一个hash值，插入、查找以及删除的时间复杂度在O(lgn)

它提供了认证数据结构，有Merkle本身的特性，对于给定的路径通过root hash都可以进行认证，任意子节点的改变都会影响到root hahs的值

节点类型

1. NULL (represented as the empty string，空节点)
2. branch A 17-item node [ v0 ... v15, vt ]（分支节点）
3. leaf A 2-item node [ encodedPath, value ]（叶子节点）
4. extension A 2-item node [ encodedPath, key ]（扩展节点）

那如何区分叶子节点和扩展节点呢
MPT在对key编码时，会增加最多4位的nibble用作标志位，第三位表示是否是结束符，第四位表示hex编码的字节的奇偶数。
如下图所示

image.png

另外当偶数的时候，需要在4位nibble后再增加4位的0

例子

('do', 'verb'), ('dog', 'puppy'), ('doge', 'coin'), ('horse', 'stallion')

1. 将key转换为字节并用16进制表示

<64 6f> : 'verb'
<64 6f 67> : 'puppy'
<64 6f 67 65> : 'coin'
<68 6f 72 73 65> : 'stallion'

2. 构建得到的MPT为

rootHash: [ <16>, hashA ]
hashA:    [ <>, <>, <>, <>, hashB, <>, <>, <>, hashC, <>, <>, <>, <>, <>, <>, <>, <> ]
hashC:    [ <20 6f 72 73 65>, 'stallion' ]
hashB:    [ <00 6f>, hashD ]
hashD:    [ <>, <>, <>, <>, <>, <>, hashE, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'verb' ]
hashE:    [ <17>, hashF ]
hashF:    [ <>, <>, <>, <>, <>, <>, hashG, <>, <>, <>, <>, <>, <>, <>, <>, <>, 'puppy' ]
hashG:    [ <35>, 'coin' ]