MPT，全稱Merkle Patricia Trie，以太坊中用來存儲用戶賬戶的狀態(tài)及其變更、交易信息、交易的收據信息?？雌淙Q便大概知道MPT融合了MerkleTree，Trie，Patricia Trie這三種數(shù)據結構的有點，從而最大限度地快速實現(xiàn)查找功能并節(jié)省空間。
前塵舊事
Trie
Trie，又稱為字典樹或者前綴樹 (prefix tree)，屬于查找樹的一種。它與平衡二叉樹的主要不同點包括：
- 每個節(jié)點數(shù)據所攜帶的 key 不會存儲在 Trie 的節(jié)點中，而是通過該節(jié)點在整個樹形結構里位置來體現(xiàn)(下圖中標注出完整的單詞，只是為了演示Trie的原理)；
- 同一個父節(jié)點的子節(jié)點，共享該父節(jié)點的 key 作為它們各自 key 的前綴，因此根節(jié)點 key 為空；
- 待存儲的數(shù)據只存于葉子節(jié)點和部分內部節(jié)點中，非葉子節(jié)點幫助形成葉子節(jié)點 key 的前綴。
通俗地講，以Trie存儲英文單詞為例，只需要把每個單詞按字母拆分然后在樹上進行查找，找深度和單詞長度相同為止。eg：
Trie存儲英文單詞
Patricia Trie
就以上面的Trie??來看，對于節(jié)點5這個只有一個子節(jié)點的節(jié)點來說，其實沒有必要衍生出節(jié)點9來構造存儲inn，我們完全可以把這種只有一個子節(jié)點的節(jié)點和其子節(jié)點合并為一個節(jié)點來節(jié)省存儲空間。
這就是基于Trie改進后的Patricia Trie，又被稱為 RadixTree 或緊湊前綴樹 (compact prefix tree)，是一種空間使用率經過優(yōu)化的 Trie。
Patricia Trie??
Merkle Tree
MerkleTree，通常也被稱作Hash Tree，顧名思義，就是存儲hash值的一棵樹。之前在公鏈開發(fā)中有涉及到Merkle Tree理解和代碼實現(xiàn),在此不再贅述。
MPT
概念理解
MPT 是 Ethereum 自定義的 Trie 型數(shù)據結構。以上面存儲英文單詞的Trie為例，一個Trie實際上就是一個26叉樹。而MPT在以太坊里是用來檢索字節(jié)數(shù)據的，因此這里的MPT實際上是一個16叉樹，分別代表0x0 - 0xf。
MPT節(jié)點一共有四個類型：
- 空節(jié)點(NULL)
- 分支節(jié)點(branch node):17個分 ，包含16個bytes(0x0-0xf)以及1個value
- 擴展節(jié)點(extension node):只有1個子結點
- 葉子節(jié)點(leaf node):沒有子節(jié)點，包含1個value
針對MPT樹的理解，可以借助他山之石，畢竟站在巨人的肩膀上會看得更遠。我們這里主要目的是研讀以太坊源碼，對概念的理解就不再展開敘述。
關于MPT，wiki里也給出了一個簡單的示例??，可以去看看。
廢話少說擼代碼
基本操作
接下來就直搗黃龍，來看看以太坊源碼是如何實現(xiàn)MPT的。
首先，來看MPT樹幾種節(jié)點的定義(./trie/node.go)。
// MPT幾種節(jié)點結構
type (
// 分支節(jié)點，它的結構體現(xiàn)了原生trie的設計特點
fullNode struct {
// 17個子節(jié)點，其中16個為0x0-0xf;第17個子節(jié)點存放數(shù)據
Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
// 緩存節(jié)點的Hash值，同時標記dirty值來決定節(jié)點是否必須寫入數(shù)據庫
flags nodeFlag
}
// 擴展節(jié)點和葉子節(jié)點，它的結構體現(xiàn)了PatriciaTrie的設計特點
// 區(qū)別在于擴展節(jié)點的value指向下一個節(jié)點的hash值(hashNode)；葉子節(jié)點的value是數(shù)據的RLP編碼(valueNode)
shortNode struct {
Key []byte
Val node
flags nodeFlag
}
//節(jié)點哈希，用于實現(xiàn)節(jié)點的折疊(參考MerkleTree設計特點)
hashNode []byte
//存儲數(shù)據
valueNode []byte
)
接著來看看MPT樹幾種重要的更新操作：新建，插入，查找等。首先看新建：./trie/trie.go
// New creates a trie with an existing root node from db.
//
// If root is the zero hash or the sha3 hash of an empty string, the
// trie is initially empty and does not require a database. Otherwise,
// New will panic if db is nil and returns a MissingNodeError if root does
// not exist in the database. Accessing the trie loads nodes from db on demand.
func New(root common.Hash, db *Database) (*Trie, error) {
if db == nil {
panic("trie.New called without a database")
}
trie := &Trie{
db: db,
originalRoot: root,
}
// 如果根哈希不為空，說明是從數(shù)據庫加載一個已經存在的MPT樹
if root != (common.Hash{}) && root != emptyRoot {
rootnode, err := trie.resolveHash(root[:], nil)
if err != nil {
return nil, err
}
trie.root = rootnode
}
//否則，直接返回的是新建的MPT樹
return trie, nil
}
接著，來看MPT樹的插入操作。
/*
insert MPT樹節(jié)點的插入操作
node 當前的節(jié)點
prefix 當前已處理完的key(節(jié)點共有的前綴)
key 當前未處理的key(完整key = prefix + key)
value 當前插入的值
bool 返回函數(shù)是否改變了MPT樹
node 執(zhí)行插入后的MPT樹根節(jié)點
*/
func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
if len(key) == 0 {
if v, ok := n.(valueNode); ok {
return !bytes.Equal(v, value.(valueNode)), value, nil
}
return true, value, nil
}
switch n := n.(type) {
case *shortNode:
// 如果是葉子節(jié)點，首先計算共有前綴
matchlen := prefixLen(key, n.Key)
// If the whole key matches, keep this short node as is
// and only update the value.
// 1.1如果共有前綴和當前的key一樣，說明節(jié)點已經存在 只更新節(jié)點的value即可
if matchlen == len(n.Key) {
dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
if !dirty || err != nil {
return false, n, err
}
return true, &shortNode{n.Key, nn, t.newFlag()}, nil
}
// Otherwise branch out at the index where they differ.
// 1.2構造形成一個分支節(jié)點(fullNode)
branch := &fullNode{flags: t.newFlag()}
var err error
// 1.3將原來的節(jié)點拆作新的后綴shortNode插入
_, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
if err != nil {
return false, nil, err
}
// 1.4將新節(jié)點作為shortNode插入
_, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
if err != nil {
return false, nil, err
}
// Replace this shortNode with the branch if it occurs at index 0.
// 1.5 如果沒有共有的前綴，則新建的分支節(jié)點為根節(jié)點
if matchlen == 0 {
return true, branch, nil
}
// Otherwise, replace it with a short node leading up to the branch.
// 1.6 如果有共有的前綴，則拆分原節(jié)點產生前綴葉子節(jié)點為根節(jié)點
return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil
case *fullNode:
// 2 若果是分支節(jié)點，則直接將新數(shù)據插入作為子節(jié)點
dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
if !dirty || err != nil {
return false, n, err
}
n = n.copy()
n.flags = t.newFlag()
n.Children[key[0]] = nn
return true, n, nil
case nil:
// 3 空節(jié)點，直接返回該值得葉子節(jié)點作為根節(jié)點
return true, &shortNode{key, value, t.newFlag()}, nil
case hashNode:
// We've hit a part of the trie that isn't loaded yet. Load
// the node and insert into it. This leaves all child nodes on
// the path to the value in the trie.
// 4.1哈希節(jié)點 表示當前節(jié)點還未加載到內存中，首先需要調用resolveHash從數(shù)據庫中加載節(jié)點
rn, err := t.resolveHash(n, prefix)
if err != nil {
return false, nil, err
}
// 4.2然后在該節(jié)點后插入新節(jié)點
dirty, nn, err := t.insert(rn, prefix, key, value)
if !dirty || err != nil {
return false, rn, err
}
return true, nn, nil
default:
panic(fmt.Sprintf("%T: invalid node: %v", n, n))
}
}
不難看出，MPT樹節(jié)點的插入操作是一個不斷遞歸調用insert函數(shù)的過程。從根節(jié)點開始不斷向下找，直到找到可以插入的節(jié)點為止。雖然代碼我作了詳細的注釋，我們還是通過一個簡單??來理解下這個插入過程。
- a.在空節(jié)點的MPT插入第1個節(jié)點node1(b621411,40),由于當前MPT樹節(jié)點為空，這里走的是代碼里的3操作。此時直接返回leafNode1作為根節(jié)點，因為當前MPT只有一個葉子節(jié)點
| leafNode1 | b621411 | 40 |
|---|
- b.0接著插入第2個節(jié)點node2(a543918,100),此時當前的節(jié)點為葉子節(jié)點node1，這里走的是代碼1.2操作。首先需要構造一個分支節(jié)點branchNode1:
| 0 | 1 | 2 | 3 | ... | a | b | ... | f | value |
|---|
- b.1然后將原來的節(jié)點node1插入到branchNode1(代碼1.3操作)；并把新的節(jié)點插入到branchNode1后(代碼1.4操作)。這是遞歸調用insert函數(shù)進入下一步時的當前節(jié)點便成為了branchNode1，相當于將問題轉換為代碼2.
插入node2(a543918, 100)
b.2 上面已經知道node1，node2并沒有共同前綴。因此，此時代碼里走的是1.5將brenchNode1返回作為根節(jié)點
c.0若此時的node2為(b6a7521, 100),比較node1，node2發(fā)現(xiàn)兩個節(jié)點有共同的前綴b6,此時需要構造一個擴展節(jié)點shortNode1(節(jié)點value指向下一個節(jié)點hash)存儲兩個節(jié)點的共同前綴，然后再構造一個brenchNode2來連接node1，node2
node2(a6a7521, 100)
- c.1 此時由于擁有共同節(jié)點，所以要返回的根節(jié)點為原節(jié)點拆分的存儲共同前綴的節(jié)點(代碼1.6)
同樣，節(jié)點的delete操作與insert邏輯互逆，也是通過不斷地遞歸調用delete函數(shù)直到找到應該刪除的節(jié)點，然后要看情況合并刪除節(jié)點后只有一個子節(jié)點的父節(jié)點。
// delete returns the new root of the trie with key deleted.
// It reduces the trie to minimal form by simplifying
// nodes on the way up after deleting recursively.
// 刪除節(jié)點
func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
switch n := n.(type) {
case *shortNode:
// 如果是葉子節(jié)點或擴展節(jié)點，首先獲取與當前節(jié)點的共同前綴
matchlen := prefixLen(key, n.Key)
// 刪除節(jié)點不存在，不需要刪除 MPT樹不變
if matchlen < len(n.Key) {
return false, n, nil // don't replace n on mismatch
}
// 刪除節(jié)點為當前共有節(jié)點(即根節(jié)點)，刪除后MPT為空
if matchlen == len(key) {
return true, nil, nil // remove n entirely for whole matches
}
// The key is longer than n.Key. Remove the remaining suffix
// from the subtrie. Child can never be nil here since the
// subtrie must contain at least two other values with keys
// longer than n.Key.
// key > n.key,從key中刪除剩余的后綴
// 子節(jié)點這里不會為空，因為至少有2個擁有key值得子節(jié)點 取其子節(jié)點
dirty, child, err := t.delete(n.Val, append(prefix, key[:len(n.Key)]...), key[len(n.Key):])
if !dirty || err != nil {
return false, n, err
}
switch child := child.(type) {
case *shortNode:
// Deleting from the subtrie reduced it to another
// short node. Merge the nodes to avoid creating a
// shortNode{..., shortNode{...}}. Use concat (which
// always creates a new slice) instead of append to
// avoid modifying n.Key since it might be shared with
// other nodes.
return true, &shortNode{concat(n.Key, child.Key...), child.Val, t.newFlag()}, nil
default:
return true, &shortNode{n.Key, child, t.newFlag()}, nil
}
case *fullNode:
dirty, nn, err := t.delete(n.Children[key[0]], append(prefix, key[0]), key[1:])
if !dirty || err != nil {
return false, n, err
}
n = n.copy()
n.flags = t.newFlag()
n.Children[key[0]] = nn
// Check how many non-nil entries are left after deleting and
// reduce the full node to a short node if only one entry is
// left. Since n must've contained at least two children
// before deletion (otherwise it would not be a full node) n
// can never be reduced to nil.
//
// When the loop is done, pos contains the index of the single
// value that is left in n or -2 if n contains at least two
// values.
pos := -1
for i, cld := range n.Children {
if cld != nil {
if pos == -1 {
pos = i
} else {
pos = -2
break
}
}
}
if pos >= 0 {
if pos != 16 {
// If the remaining entry is a short node, it replaces
// n and its key gets the missing nibble tacked to the
// front. This avoids creating an invalid
// shortNode{..., shortNode{...}}. Since the entry
// might not be loaded yet, resolve it just for this
// check.
cnode, err := t.resolve(n.Children[pos], prefix)
if err != nil {
return false, nil, err
}
if cnode, ok := cnode.(*shortNode); ok {
k := append([]byte{byte(pos)}, cnode.Key...)
return true, &shortNode{k, cnode.Val, t.newFlag()}, nil
}
}
// Otherwise, n is replaced by a one-nibble short node
// containing the child.
return true, &shortNode{[]byte{byte(pos)}, n.Children[pos], t.newFlag()}, nil
}
// n still contains at least two values and cannot be reduced.
return true, n, nil
case valueNode:
return true, nil, nil
case nil:
return false, nil, nil
case hashNode:
// We've hit a part of the trie that isn't loaded yet. Load
// the node and delete from it. This leaves all child nodes on
// the path to the value in the trie.
rn, err := t.resolveHash(n, prefix)
if err != nil {
return false, nil, err
}
dirty, nn, err := t.delete(rn, prefix, key)
if !dirty || err != nil {
return false, rn, err
}
return true, nn, nil
default:
panic(fmt.Sprintf("%T: invalid node: %v (%v)", n, n, key))
}
}
那怎么獲取存儲在MPT上的數(shù)據呢？繼續(xù)看代碼：
// Get returns the value for key stored in the trie.
// The value bytes must not be modified by the caller.
// 獲取MPT上存儲的數(shù)據
func (t *Trie) Get(key []byte) []byte {
res, err := t.TryGet(key)
if err != nil {
log.Error(fmt.Sprintf("Unhandled trie error: %v", err))
}
return res
}
// TryGet returns the value for key stored in the trie.
// The value bytes must not be modified by the caller.
// If a node was not found in the database, a MissingNodeError is returned.
// 獲取MPT上存儲的數(shù)據
func (t *Trie) TryGet(key []byte) ([]byte, error) {
key = keybytesToHex(key)
value, newroot, didResolve, err := t.tryGet(t.root, key, 0)
if err == nil && didResolve {
t.root = newroot
}
return value, err
}
// 遍歷MPT節(jié)點
func (t *Trie) tryGet(origNode node, key []byte, pos int) (value []byte, newnode node, didResolve bool, err error) {
switch n := (origNode).(type) {
case nil:
return nil, nil, false, nil
case valueNode:
return n, n, false, nil
case *shortNode:
// key不存在
if len(key)-pos < len(n.Key) || !bytes.Equal(n.Key, key[pos:pos+len(n.Key)]) {
// key not found in trie
return nil, n, false, nil
}
// 擴展節(jié)點繼續(xù)遞歸找到葉子節(jié)點
value, newnode, didResolve, err = t.tryGet(n.Val, key, pos+len(n.Key))
if err == nil && didResolve {
n = n.copy()
n.Val = newnode
n.flags.gen = t.cachegen
}
return value, n, didResolve, err
case *fullNode:
// 遞歸尋找葉子節(jié)點
value, newnode, didResolve, err = t.tryGet(n.Children[key[pos]], key, pos+1)
if err == nil && didResolve {
n = n.copy()
n.flags.gen = t.cachegen
n.Children[key[pos]] = newnode
}
return value, n, didResolve, err
case hashNode:
// hash節(jié)點，先從數(shù)據庫里加載出當前節(jié)點再繼續(xù)尋找
child, err := t.resolveHash(n, key[:pos])
if err != nil {
return nil, n, true, err
}
value, newnode, _, err := t.tryGet(child, key, pos)
return value, newnode, true, err
default:
panic(fmt.Sprintf("%T: invalid node: %v", origNode, origNode))
}
}
MPT的序列化
Compat編碼
序列化主要是用來把內存中的數(shù)據放到數(shù)據庫中，反序列化則反之。以太坊 MPT的序列化主要用到了Compat編碼和RLP編碼。
RLP編碼前面已經介紹過,這里簡單看一下Compat編碼。
Compat編碼，又叫hex prefix編碼(HP)，它是基于hex編碼。所以首先要明白Hex編碼是怎么一回事。
Hex編碼：當[key， value]數(shù)據插入MPT時，這里的key必須經過特殊編碼以保證能以16進制形式按位進入fullNode.Children[]。由于Children數(shù)組最多容納16個字節(jié)點，所以以太坊這里定義了Hex編碼方式將1bytes的字符大小限制在4bit(16進制)以內。trie給出的Hex編碼方式如下：
Hex編碼
從圖上可以看出，Hex編碼主要有兩步：
- 1.將1個byte的高低4bit分別放到2個byte里，形成新的byte[]
- 2.在新byte[]后再追加1個byte來標記當前byte[]為Hex格式
Compat編碼：主要作用用來將Hex格式的字符串恢復到keybytes格式，同時加入當前Compat格式的標記位，還要考慮奇偶不同長度Hex字符串下避免引入多余的bytes。
Compat編碼
從圖上可以看出，Compat編碼主要有兩步：
1.將Hex格式的尾部標記byte去掉，然后將每2nibble的數(shù)據合并到1個byte
2.判斷Hex編碼長度，如果輸入 Hex 格式字符串有效長度為偶數(shù)，偶數(shù)標志位0010，這樣新增1byte來放置compat標志位就為00100000；反之將Hex字符串第一個nibble放置在標記位低4bit，加上奇數(shù)標志位0011的compat標志位就為0011xxxx。
大概了解了原理之后就可以看源碼了(./trie/encoding.go)
// Trie keys are dealt with in three distinct encodings:
//
// KEYBYTES encoding contains the actual key and nothing else. This encoding is the
// input to most API functions.
//
// HEX encoding contains one byte for each nibble of the key and an optional trailing
// 'terminator' byte of value 0x10 which indicates whether or not the node at the key
// contains a value. Hex key encoding is used for nodes loaded in memory because it's
// convenient to access.
//
// COMPACT encoding is defined by the Ethereum Yellow Paper (it's called "hex prefix
// encoding" there) and contains the bytes of the key and a flag. The high nibble of the
// first byte contains the flag; the lowest bit encoding the oddness of the length and
// the second-lowest encoding whether the node at the key is a value node. The low nibble
// of the first byte is zero in the case of an even number of nibbles and the first nibble
// in the case of an odd number. All remaining nibbles (now an even number) fit properly
// into the remaining bytes. Compact encoding is used for nodes stored on disk.
// Hex編碼串轉化為Compact編碼
func hexToCompact(hex []byte) []byte {
// 如果最后一位是16，terminator為1，否則為0
terminator := byte(0)
// 包含terminator的節(jié)點為葉子節(jié)點
if hasTerm(hex) {
terminator = 1
// 1.0將Hex格式的尾部標記byte去掉
hex = hex[:len(hex)-1]
}
// 定義Compat字節(jié)數(shù)組
buf := make([]byte, len(hex)/2+1)
// 標志位默認
buf[0] = terminator << 5 // the flag byte
if len(hex)&1 == 1 {
// 如果Hex長度為奇數(shù)，修改標志位為odd flag
buf[0] |= 1 << 4 // odd flag
// 然后把第1個nibble放入buf[0]低四位
buf[0] |= hex[0] // first nibble is contained in the first byte
hex = hex[1:]
}
// 1.1然后將每2nibble的數(shù)據合并到1個byte
decodeNibbles(hex, buf[1:])
return buf
}
// Compact編碼轉化為Hex編碼串
func compactToHex(compact []byte) []byte {
base := keybytesToHex(compact)
// delete terminator flag
/*這里base[0]有4中情況
00000000 擴展節(jié)點偶數(shù)位
00000001 擴展節(jié)點奇數(shù)位
00000010 葉子節(jié)點偶數(shù)位
00000011 葉子節(jié)點偶數(shù)位
*/
if base[0] < 2 {
// 如果是擴展節(jié)點，去除最后一位
base = base[:len(base)-1]
}
// apply odd flag
// 如果是偶數(shù)位chop=2，否則chop=1
chop := 2 - base[0]&1
//去除compact標志位。偶數(shù)位去除2個字節(jié)，奇數(shù)位去除1個字節(jié)（因為奇數(shù)位的低四位放的是nibble數(shù)據）
return base[chop:]
}
// 將key字符串進行Hex編碼
func keybytesToHex(str []byte) []byte {
l := len(str)*2 + 1
//將一個keybyte轉化成兩個字節(jié)
var nibbles = make([]byte, l)
for i, b := range str {
nibbles[i*2] = b / 16
nibbles[i*2+1] = b % 16
}
//末尾加入Hex標志位16 00010000
nibbles[l-1] = 16
return nibbles
}
// hexToKeybytes turns hex nibbles into key bytes.
// This can only be used for keys of even length.
// 將hex編碼解碼轉為key字符串
func hexToKeybytes(hex []byte) []byte {
if hasTerm(hex) {
hex = hex[:len(hex)-1]
}
if len(hex)&1 != 0 {
panic("can't convert hex key of odd length")
}
key := make([]byte, len(hex)/2)
decodeNibbles(hex, key)
return key
}
func decodeNibbles(nibbles []byte, bytes []byte) {
for bi, ni := 0, 0; ni < len(nibbles); bi, ni = bi+1, ni+2 {
bytes[bi] = nibbles[ni]<<4 | nibbles[ni+1]
}
}
// prefixLen returns the length of the common prefix of a and b.
func prefixLen(a, b []byte) int {
var i, length = 0, len(a)
if len(b) < length {
length = len(b)
}
for ; i < length; i++ {
if a[i] != b[i] {
break
}
}
return i
}
// hasTerm returns whether a hex key has the terminator flag.
func hasTerm(s []byte) bool {
return len(s) > 0 && s[len(s)-1] == 16
}
這里涉及到一個葉子節(jié)點的判斷hasTerm，使用compact編碼的規(guī)格：
| hex char | bits | node | path length |
|---|---|---|---|
| 0 | 0000 | extension | even(偶數(shù)) |
| 1 | 0001 | extension | even(偶數(shù)) |
| 2 | 0010 | leaf(terminator) | odd(奇數(shù)) |
| 3 | 0011 | leaf | odd(奇數(shù)) |
MPT序列化
了解了MPT編碼方式之后，來看看涉及MPT編碼存儲的一個簡單流程。我們在trie_test.go里的insert測試函數(shù)來看看MPT編碼存儲的邏輯。
func TestInsert(t *testing.T) {
// 1.創(chuàng)建一個空的MPT樹
trie := newEmpty()
updateString(trie, "doe", "reindeer")
updateString(trie, "dog", "puppy")
updateString(trie, "dogglesworth", "cat")
exp := common.HexToHash("8aad789dff2f538bca5d8ea56e8abe10f4c7ba3a5dea95fea4cd6e7c3a1168d3")
root := trie.Hash()
if root != exp {
t.Errorf("exp %x got %x", exp, root)
}
trie = newEmpty()
updateString(trie, "A", "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa")
exp = common.HexToHash("d23786fb4a010da3ce639d66d5e904a11dbc02746d1ce25029e53290cabf28ab")
// 2.調用Commit函數(shù)進行序列化
root, err := trie.Commit(nil)
if err != nil {
t.Fatalf("commit error: %v", err)
}
if root != exp {
t.Errorf("exp %x got %x", exp, root)
}
}
...
// Commit writes all nodes to the trie's memory database, tracking the internal
// and external (for account tries) references.
// 序列化MPT樹，并將所有節(jié)點數(shù)據存儲到數(shù)據庫中
func (t *Trie) Commit(onleaf LeafCallback) (root common.Hash, err error) {
if t.db == nil {
panic("commit called on trie with nil database")
}
// 3.折疊MPT節(jié)點的實現(xiàn)
hash, cached, err := t.hashRoot(t.db, onleaf)
if err != nil {
return common.Hash{}, err
}
t.root = cached
t.cachegen++
return common.BytesToHash(hash.(hashNode)), nil
}
// 折疊MPT節(jié)點的實現(xiàn)
func (t *Trie) hashRoot(db *Database, onleaf LeafCallback) (node, node, error) {
if t.root == nil {
return hashNode(emptyRoot.Bytes()), nil, nil
}
h := newHasher(t.cachegen, t.cachelimit, onleaf)
defer returnHasherToPool(h)
// 4.將節(jié)點進行哈希
return h.hash(t.root, db, true)
}
繼續(xù)深入到hash函數(shù)里來分析：
// hash collapses a node down into a hash node, also returning a copy of the
// original node initialized with the computed hash to replace the original one.
// 將節(jié)點向下折疊為hash node，同時返回用計算出的散列初始化的原始節(jié)點的副本以替換原始節(jié)點。
/*
node MPT根節(jié)點
db 存儲的數(shù)據庫
force true 當節(jié)點的RLP字節(jié)長度小于32也對節(jié)點的RLP進行hash計算
根節(jié)點調用為true以保證對根節(jié)點進行哈希計算
return:
node 入參n經過哈希折疊后的hashNode
node hashNode被賦值了的同時未被哈希折疊的入參n
*/
func (h *hasher) hash(n node, db *Database, force bool) (node, node, error) {
// If we're not storing the node, just hashing, use available cached data
if hash, dirty := n.cache(); hash != nil {
if db == nil {
return hash, n, nil
}
// 移除節(jié)點 當trie.cachegen-node.cachegen > cachelimit
if n.canUnload(h.cachegen, h.cachelimit) {
// Unload the node from cache. All of its subnodes will have a lower or equal
// cache generation number.
cacheUnloadCounter.Inc(1)
return hash, hash, nil
}
if !dirty {
return hash, n, nil
}
}
// Trie not processed yet or needs storage, walk the children
// 將所有子節(jié)點替換成他們的Hash
collapsed, cached, err := h.hashChildren(n, db)
if err != nil {
return hashNode{}, n, err
}
// 將所有節(jié)點都換算完hash的hashNode存入數(shù)據庫
hashed, err := h.store(collapsed, db, force)
if err != nil {
return hashNode{}, n, err
}
// Cache the hash of the node for later reuse and remove
// the dirty flag in commit mode. It's fine to assign these values directly
// without copying the node first because hashChildren copies it.
cachedHash, _ := hashed.(hashNode)
switch cn := cached.(type) {
case *shortNode:
cn.flags.hash = cachedHash
if db != nil {
cn.flags.dirty = false
}
case *fullNode:
cn.flags.hash = cachedHash
if db != nil {
cn.flags.dirty = false
}
}
return hashed, cached, nil
}
// hashChildren replaces the children of a node with their hashes if the encoded
// size of the child is larger than a hash, returning the collapsed node as well
// as a replacement for the original node with the child hashes cached in.
// 把所有的子節(jié)點替換成他們的hash，可以看到cache變量接管了原來的Trie樹的完整結構
// collapsed變量把子節(jié)點替換成子節(jié)點的hash值。
func (h *hasher) hashChildren(original node, db *Database) (node, node, error) {
var err error
switch n := original.(type) {
case *shortNode:
// Hash the short node's child, caching the newly hashed subtree
// 當前節(jié)點為葉子節(jié)點或擴展節(jié)點，將collapsed.Key從Hex編碼轉換為Compat編碼
collapsed, cached := n.copy(), n.copy()
collapsed.Key = hexToCompact(n.Key)
cached.Key = common.CopyBytes(n.Key)
//循環(huán)調用hash算法將collapsed中子節(jié)點全換成子節(jié)點的hash值
if _, ok := n.Val.(valueNode); !ok {
collapsed.Val, cached.Val, err = h.hash(n.Val, db, false)
if err != nil {
return original, original, err
}
}
return collapsed, cached, nil
case *fullNode:
// Hash the full node's children, caching the newly hashed subtrees
collapsed, cached := n.copy(), n.copy()
// 分支節(jié)點，遍歷將子節(jié)點全換成子節(jié)點的hash值
for i := 0; i < 16; i++ {
if n.Children[i] != nil {
collapsed.Children[i], cached.Children[i], err = h.hash(n.Children[i], db, false)
if err != nil {
return original, original, err
}
}
}
cached.Children[16] = n.Children[16]
return collapsed, cached, nil
default:
// Value and hash nodes don't have children so they're left as were
// 沒有子節(jié)點，直接返回
return n, original, nil
}
}
// store hashes the node n and if we have a storage layer specified, it writes
// the key/value pair to it and tracks any node->child references as well as any
// node->external trie references.
// MPT節(jié)點存儲
func (h *hasher) store(n node, db *Database, force bool) (node, error) {
// Don't store hashes or empty nodes.
if _, isHash := n.(hashNode); n == nil || isHash {
return n, nil
}
// Generate the RLP encoding of the node
h.tmp.Reset()
// 調用rlp.Encode方法對這個節(jié)點進行編碼
if err := rlp.Encode(&h.tmp, n); err != nil {
panic("encode error: " + err.Error())
}
// 如果編碼后的值 < 32 并且沒有要求強制保存(根節(jié)點)，直接存儲在父節(jié)點中
if len(h.tmp) < 32 && !force {
return n, nil // Nodes smaller than 32 bytes are stored inside their parent
}
// Larger nodes are replaced by their hash and stored in the database.
// 如果編碼后的值 > 32 存儲到數(shù)據庫中
hash, _ := n.cache()
if hash == nil {
hash = h.makeHashNode(h.tmp)
}
if db != nil {
// We are pooling the trie nodes into an intermediate memory cache
hash := common.BytesToHash(hash)
db.lock.Lock()
// 數(shù)據庫存儲的key為node經過RLP編碼后的hash值
db.insert(hash, h.tmp, n)
db.lock.Unlock()
// Track external references from account->storage trie
if h.onleaf != nil {
switch n := n.(type) {
case *shortNode:
if child, ok := n.Val.(valueNode); ok {
h.onleaf(child, hash)
}
case *fullNode:
for i := 0; i < 16; i++ {
if child, ok := n.Children[i].(valueNode); ok {
h.onleaf(child, hash)
}
}
}
}
}
return hash, nil
}
這里的大概邏輯是這樣的：
1.調用hash函數(shù)作了三個操作：一是保留了原有的樹形結構到cached，二是計算了原有樹形結構的hash并把其存到hashed里，三是在有子節(jié)點的節(jié)點調用了hashChildren函數(shù)來遞歸地將所有子節(jié)點變?yōu)樗麄兊墓Ｖ怠?/p>
2.hashChildren用于遍歷每一個節(jié)點，其中又嵌套調用了hash函數(shù)來計算節(jié)點的哈希值，hashChildren與hash函數(shù)相互調用正好遍歷了整個MPT樹結構。
3.store函數(shù)對節(jié)點做RLP編碼，并將節(jié)點存儲到數(shù)據庫中
MPT反序列化
其實在之前看insert函數(shù)源碼時就涉及到了MPT反序列化。當時遇到當前節(jié)點為hashNode時，需要調用t.resolveHash函數(shù)從數(shù)據庫取出當前節(jié)點來進行操作，這個過程便是MPT節(jié)點的反序列化。
// 根據hashNode取出對應的節(jié)點
func (t *Trie) resolveHash(n hashNode, prefix []byte) (node, error) {
cacheMissCounter.Inc(1)
hash := common.BytesToHash(n)
// 通過hash解析出node的RLP值
if node := t.db.node(hash, t.cachegen); node != nil {
return node, nil
}
return nil, &MissingNodeError{NodeHash: hash, Path: prefix}
}
看來真正的解碼操作在database類里，循著線索繼續(xù)深入。
// node retrieves a cached trie node from memory, or returns nil if none can be
// found in the memory cache.
// 從內存中檢索緩存的MPT節(jié)點，如果在內存緩存中找不到任何節(jié)點，則返回nil。
func (db *Database) node(hash common.Hash, cachegen uint16) node {
// Retrieve the node from cache if available
db.lock.RLock()
node := db.nodes[hash]
db.lock.RUnlock()
if node != nil {
return node.obj(hash, cachegen)
}
// Content unavailable in memory, attempt to retrieve from disk
enc, err := db.diskdb.Get(hash[:])
if err != nil || enc == nil {
return nil
}
// 真正根據hash接觸node的函數(shù)
return mustDecodeNode(hash[:], enc, cachegen)
}
...
func mustDecodeNode(hash, buf []byte, cachegen uint16) node {
n, err := decodeNode(hash, buf, cachegen)
if err != nil {
panic(fmt.Sprintf("node %x: %v", hash, err))
}
return n
}
...
// decodeNode parses the RLP encoding of a trie node.
// 解析MPT節(jié)點的RLP編碼。
func decodeNode(hash, buf []byte, cachegen uint16) (node, error) {
//空節(jié)點
if len(buf) == 0 {
return nil, io.ErrUnexpectedEOF
}
elems, _, err := rlp.SplitList(buf)
if err != nil {
return nil, fmt.Errorf("decode error: %v", err)
}
switch c, _ := rlp.CountValues(elems); c {
// 這里根據rlpList的長度來判斷節(jié)點類型，2為shortNode，17的話是fullNode
case 2:
n, err := decodeShort(hash, elems, cachegen)
return n, wrapError(err, "short")
case 17:
n, err := decodeFull(hash, elems, cachegen)
return n, wrapError(err, "full")
default:
return nil, fmt.Errorf("invalid number of list elements: %v", c)
}
}
到這里，就根據分辨出的節(jié)點類型來解碼。decodeShort和decodeFull邏輯大致相同，我們以decodeShort為例來深入了解下解碼邏輯。
// 針對shortNode的解碼方式
func decodeShort(hash, elems []byte, cachegen uint16) (node, error) {
// kbuf -- compact key;rest -- 節(jié)點的value
kbuf, rest, err := rlp.SplitString(elems)
if err != nil {
return nil, err
}
flag := nodeFlag{hash: hash, gen: cachegen}
// 1.將key從conmpact編碼轉換為Hex字符串
key := compactToHex(kbuf)
// 2.根據是否包含終結符號(16--00010000)來判斷是否為葉子節(jié)點
if hasTerm(key) {
// value node
// 包含16，是葉子節(jié)點
val, _, err := rlp.SplitString(rest)
if err != nil {
return nil, fmt.Errorf("invalid value node: %v", err)
}
return &shortNode{key, append(valueNode{}, val...), flag}, nil
}
// 3.解析剩下的節(jié)點
r, _, err := decodeRef(rest, cachegen)
if err != nil {
return nil, wrapError(err, "val")
}
return &shortNode{key, r, flag}, nil
}
...
// 解析剩余節(jié)點
func decodeRef(buf []byte, cachegen uint16) (node, []byte, error) {
kind, val, rest, err := rlp.Split(buf)
if err != nil {
return nil, buf, err
}
switch {
case kind == rlp.List:
// 'embedded' node reference. The encoding must be smaller
// than a hash in order to be valid.
// 根據RLP編碼規(guī)則 len(buf) - len(rest)為類型加內容的長度
if size := len(buf) - len(rest); size > hashLen {
err := fmt.Errorf("oversized embedded node (size is %d bytes, want size < %d)", size, hashLen)
return nil, buf, err
}
// 遞歸調用decodeNode解析函數(shù)
n, err := decodeNode(nil, buf, cachegen)
return n, rest, err
case kind == rlp.String && len(val) == 0:
// empty node
return nil, rest, nil
case kind == rlp.String && len(val) == 32:
// 數(shù)據類型為hash值，構造一個hashNode返回
return append(hashNode{}, val...), rest, nil
default:
return nil, nil, fmt.Errorf("invalid RLP string size %d (want 0 or 32)", len(val))
}
}
MPT數(shù)據結構
MPT的東西源碼里還真不少，以至于都忘記來看看其數(shù)據結構了。
// Trie is a Merkle Patricia Trie.
// The zero value is an empty trie with no database.
// Use New to create a trie that sits on top of a database.
//
// Trie is not safe for concurrent use.
// MPT
type Trie struct {
// 保存節(jié)點的數(shù)據庫
db *Database
// MPT根節(jié)點
root node
// MPT根哈希
originalRoot common.Hash
// Cache generation values.
// cachegen increases by one with each commit operation.
// new nodes are tagged with the current generation and unloaded
// when their generation is older than than cachegen-cachelimit.
// cachegen -- Cache generation values,緩存生成值。每次執(zhí)行commit操作
// cachegen都會自增1
// cachelimit 緩存限制值
// 當trie.cachegen-node.cachegen > cachelimit 移除節(jié)點
cachegen, cachelimit uint16
}
加密的MPT
為了避免使用太長的key導致訪問時間太久，以太坊用security_trie對上述trie作了一個封裝，使得最后所有的key都轉換成keccak256算法計算的hash值。同時在數(shù)據庫里映射存儲了對應的原有key。
type SecureTrie struct {
// MPT樹
trie Trie
// 緩存key經過keccak256后的哈希值
hashKeyBuf [common.HashLength]byte
// 映射hash值和原有key的關系
secKeyCache map[string][]byte
// self
secKeyCacheOwner *SecureTrie // Pointer to self, replace the key cache on mismatch
}
與MPT類似，SecureTrie也有get，delete，commit等操作，這里就不再贅述。
說起來，以太坊有關MPT的實現(xiàn)源碼還真不少。還有很多細節(jié)還沒有去看，作為理解以太坊MPT，這些已經足夠了。
以太坊四棵樹
以太坊的每一個區(qū)塊頭里都包含著三顆樹的根節(jié)點：
- transactionsRoot,交易樹
- receiptsRoot,收據樹
- stateRoot,狀態(tài)樹
還有一顆樹在以太坊賬戶account里，每一個account都包含nonce,balance,storageRoot,codeHash四個子項，其中便有第四棵樹的根節(jié)點：
- storageRoot，存儲樹，它是所有合約數(shù)據存儲的地方
MPT是以太坊特有的自己構造的樹結構。今天，已經將MPT的基本機制和源碼實現(xiàn)看完了。
更多以太坊源碼解析請移駕全球最大同性交友網,覺得有用記得給個小star哦??????
.
.
.
.
互聯(lián)網顛覆世界，區(qū)塊鏈顛覆互聯(lián)網!
--------------------------------------------------20180926 01:19
