MPT铡恕，全稱Merkle Patricia Trie，以太坊中用來存儲(chǔ)用戶賬戶的狀態(tài)及其變更脏答、交易信息趾疚、交易的收據(jù)信息∫栽蹋看其全稱便大概知道MPT融合了MerkleTree，Trie辛孵，Patricia Trie這三種數(shù)據(jù)結(jié)構(gòu)的有點(diǎn)，從而最大限度地快速實(shí)現(xiàn)查找功能并節(jié)省空間。

前塵舊事

Trie

Trie儿奶，又稱為字典樹或者前綴樹 (prefix tree)喜滨，屬于查找樹的一種。它與平衡二叉樹的主要不同點(diǎn)包括：

• 每個(gè)節(jié)點(diǎn)數(shù)據(jù)所攜帶的 key 不會(huì)存儲(chǔ)在 Trie 的節(jié)點(diǎn)中冶匹，而是通過該節(jié)點(diǎn)在整個(gè)樹形結(jié)構(gòu)里位置來體現(xiàn)(下圖中標(biāo)注出完整的單詞习劫，只是為了演示Trie的原理)；
• 同一個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)嚼隘，共享該父節(jié)點(diǎn)的 key 作為它們各自 key 的前綴诽里，因此根節(jié)點(diǎn) key 為空；
• 待存儲(chǔ)的數(shù)據(jù)只存于葉子節(jié)點(diǎn)和部分內(nèi)部節(jié)點(diǎn)中飞蛹，非葉子節(jié)點(diǎn)幫助形成葉子節(jié)點(diǎn) key 的前綴谤狡。

通俗地講，以Trie存儲(chǔ)英文單詞為例卧檐，只需要把每個(gè)單詞按字母拆分然后在樹上進(jìn)行查找墓懂，找深度和單詞長(zhǎng)度相同為止。eg：

Trie存儲(chǔ)英文單詞

Patricia Trie

就以上面的Trie??來看霉囚，對(duì)于節(jié)點(diǎn)5這個(gè)只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)來說捕仔，其實(shí)沒有必要衍生出節(jié)點(diǎn)9來構(gòu)造存儲(chǔ)inn，我們完全可以把這種只有一個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)和其子節(jié)點(diǎn)合并為一個(gè)節(jié)點(diǎn)來節(jié)省存儲(chǔ)空間。
這就是基于Trie改進(jìn)后的Patricia Trie榜跌，又被稱為 RadixTree 或緊湊前綴樹 (compact prefix tree)闪唆，是一種空間使用率經(jīng)過優(yōu)化的 Trie。

Patricia Trie??

Merkle Tree

MerkleTree斜做，通常也被稱作Hash Tree苞氮，顧名思義，就是存儲(chǔ)hash值的一棵樹瓤逼。之前在公鏈開發(fā)中有涉及到Merkle Tree理解和代碼實(shí)現(xiàn),在此不再贅述笼吟。

MPT

概念理解

MPT 是 Ethereum 自定義的 Trie 型數(shù)據(jù)結(jié)構(gòu)。以上面存儲(chǔ)英文單詞的Trie為例霸旗，一個(gè)Trie實(shí)際上就是一個(gè)26叉樹贷帮。而MPT在以太坊里是用來檢索字節(jié)數(shù)據(jù)的，因此這里的MPT實(shí)際上是一個(gè)16叉樹诱告，分別代表0x0 - 0xf撵枢。

MPT節(jié)點(diǎn)一共有四個(gè)類型：

• 空節(jié)點(diǎn)(NULL)
• 分支節(jié)點(diǎn)(branch node):17個(gè)分 ，包含16個(gè)bytes(0x0-0xf)以及1個(gè)value
• 擴(kuò)展節(jié)點(diǎn)(extension node):只有1個(gè)子結(jié)點(diǎn)
• 葉子節(jié)點(diǎn)(leaf node):沒有子節(jié)點(diǎn)精居，包含1個(gè)value

針對(duì)MPT樹的理解锄禽，可以借助他山之石，畢竟站在巨人的肩膀上會(huì)看得更遠(yuǎn)靴姿。我們這里主要目的是研讀以太坊源碼沃但，對(duì)概念的理解就不再展開敘述。

關(guān)于MPT佛吓，wiki里也給出了一個(gè)簡(jiǎn)單的示例??宵晚，可以去看看。

廢話少說擼代碼

基本操作

接下來就直搗黃龍维雇，來看看以太坊源碼是如何實(shí)現(xiàn)MPT的淤刃。
首先，來看MPT樹幾種節(jié)點(diǎn)的定義(./trie/node.go)吱型。

// MPT幾種節(jié)點(diǎn)結(jié)構(gòu)
type (
    // 分支節(jié)點(diǎn)逸贾，它的結(jié)構(gòu)體現(xiàn)了原生trie的設(shè)計(jì)特點(diǎn)
    fullNode struct {
        // 17個(gè)子節(jié)點(diǎn)，其中16個(gè)為0x0-0xf;第17個(gè)子節(jié)點(diǎn)存放數(shù)據(jù)
        Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
        // 緩存節(jié)點(diǎn)的Hash值唁影，同時(shí)標(biāo)記dirty值來決定節(jié)點(diǎn)是否必須寫入數(shù)據(jù)庫(kù)
        flags    nodeFlag
    }
    // 擴(kuò)展節(jié)點(diǎn)和葉子節(jié)點(diǎn)耕陷，它的結(jié)構(gòu)體現(xiàn)了PatriciaTrie的設(shè)計(jì)特點(diǎn)
    // 區(qū)別在于擴(kuò)展節(jié)點(diǎn)的value指向下一個(gè)節(jié)點(diǎn)的hash值(hashNode)；葉子節(jié)點(diǎn)的value是數(shù)據(jù)的RLP編碼(valueNode)
    shortNode struct {
        Key   []byte
        Val   node
        flags nodeFlag
    }
    //節(jié)點(diǎn)哈希据沈，用于實(shí)現(xiàn)節(jié)點(diǎn)的折疊(參考MerkleTree設(shè)計(jì)特點(diǎn))
    hashNode  []byte
    //存儲(chǔ)數(shù)據(jù)
    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ù)據(jù)庫(kù)加載一個(gè)已經(jīng)存在的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é)點(diǎn)的插入操作
    node    當(dāng)前的節(jié)點(diǎn)
    prefix  當(dāng)前已處理完的key(節(jié)點(diǎn)共有的前綴)
    key     當(dāng)前未處理的key(完整key = prefix + key)
    value   當(dāng)前插入的值

    bool    返回函數(shù)是否改變了MPT樹
    node    執(zhí)行插入后的MPT樹根節(jié)點(diǎn)
*/
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é)點(diǎn)发皿，首先計(jì)算共有前綴
        matchlen := prefixLen(key, n.Key)
        // If the whole key matches, keep this short node as is
        // and only update the value.
        // 1.1如果共有前綴和當(dāng)前的key一樣，說明節(jié)點(diǎn)已經(jīng)存在  只更新節(jié)點(diǎn)的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構(gòu)造形成一個(gè)分支節(jié)點(diǎn)(fullNode)
        branch := &fullNode{flags: t.newFlag()}
        var err error
        // 1.3將原來的節(jié)點(diǎn)拆作新的后綴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é)點(diǎn)作為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é)點(diǎn)為根節(jié)點(diǎn)
        if matchlen == 0 {
            return true, branch, nil
        }
        // Otherwise, replace it with a short node leading up to the branch.
        // 1.6 如果有共有的前綴穴墅，則拆分原節(jié)點(diǎn)產(chǎn)生前綴葉子節(jié)點(diǎn)為根節(jié)點(diǎn)
        return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil

    case *fullNode:
        // 2 若果是分支節(jié)點(diǎn)，則直接將新數(shù)據(jù)插入作為子節(jié)點(diǎn)
        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é)點(diǎn)温自，直接返回該值得葉子節(jié)點(diǎn)作為根節(jié)點(diǎn)
        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é)點(diǎn) 表示當(dāng)前節(jié)點(diǎn)還未加載到內(nèi)存中玄货，首先需要調(diào)用resolveHash從數(shù)據(jù)庫(kù)中加載節(jié)點(diǎn)
        rn, err := t.resolveHash(n, prefix)
        if err != nil {
            return false, nil, err
        }
        // 4.2然后在該節(jié)點(diǎn)后插入新節(jié)點(diǎn)
        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é)點(diǎn)的插入操作是一個(gè)不斷遞歸調(diào)用insert函數(shù)的過程悼泌。從根節(jié)點(diǎn)開始不斷向下找松捉，直到找到可以插入的節(jié)點(diǎn)為止。雖然代碼我作了詳細(xì)的注釋馆里，我們還是通過一個(gè)簡(jiǎn)單??來理解下這個(gè)插入過程隘世。

• a.在空節(jié)點(diǎn)的MPT插入第1個(gè)節(jié)點(diǎn)node1(b621411,40),由于當(dāng)前MPT樹節(jié)點(diǎn)為空，這里走的是代碼里的3操作鸠踪。此時(shí)直接返回leafNode1作為根節(jié)點(diǎn)丙者，因?yàn)楫?dāng)前MPT只有一個(gè)葉子節(jié)點(diǎn)

• b.0接著插入第2個(gè)節(jié)點(diǎn)node2(a543918,100),此時(shí)當(dāng)前的節(jié)點(diǎn)為葉子節(jié)點(diǎn)node1，這里走的是代碼1.2操作营密。首先需要構(gòu)造一個(gè)分支節(jié)點(diǎn)branchNode1:

• b.1然后將原來的節(jié)點(diǎn)node1插入到branchNode1(代碼1.3操作)蔓钟；并把新的節(jié)點(diǎn)插入到branchNode1后(代碼1.4操作)。這是遞歸調(diào)用insert函數(shù)進(jìn)入下一步時(shí)的當(dāng)前節(jié)點(diǎn)便成為了branchNode1卵贱，相當(dāng)于將問題轉(zhuǎn)換為代碼2.

插入node2(a543918, 100)

• b.2 上面已經(jīng)知道node1，node2并沒有共同前綴侣集。因此键俱，此時(shí)代碼里走的是1.5將brenchNode1返回作為根節(jié)點(diǎn)

• c.0若此時(shí)的node2為(b6a7521, 100),比較node1，node2發(fā)現(xiàn)兩個(gè)節(jié)點(diǎn)有共同的前綴b6,此時(shí)需要構(gòu)造一個(gè)擴(kuò)展節(jié)點(diǎn)shortNode1(節(jié)點(diǎn)value指向下一個(gè)節(jié)點(diǎn)hash)存儲(chǔ)兩個(gè)節(jié)點(diǎn)的共同前綴世分，然后再構(gòu)造一個(gè)brenchNode2來連接node1编振，node2

node2(a6a7521, 100)

• c.1 此時(shí)由于擁有共同節(jié)點(diǎn)，所以要返回的根節(jié)點(diǎn)為原節(jié)點(diǎn)拆分的存儲(chǔ)共同前綴的節(jié)點(diǎn)(代碼1.6)

同樣臭埋，節(jié)點(diǎn)的delete操作與insert邏輯互逆踪央，也是通過不斷地遞歸調(diào)用delete函數(shù)直到找到應(yīng)該刪除的節(jié)點(diǎn)，然后要看情況合并刪除節(jié)點(diǎn)后只有一個(gè)子節(jié)點(diǎn)的父節(jié)點(diǎn)瓢阴。

// 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é)點(diǎn)
func (t *Trie) delete(n node, prefix, key []byte) (bool, node, error) {
    switch n := n.(type) {
    case *shortNode:
        // 如果是葉子節(jié)點(diǎn)或擴(kuò)展節(jié)點(diǎn)畅蹂，首先獲取與當(dāng)前節(jié)點(diǎn)的共同前綴
        matchlen := prefixLen(key, n.Key)
        // 刪除節(jié)點(diǎn)不存在，不需要?jiǎng)h除 MPT樹不變
        if matchlen < len(n.Key) {
            return false, n, nil // don't replace n on mismatch
        }
        // 刪除節(jié)點(diǎn)為當(dāng)前共有節(jié)點(diǎn)(即根節(jié)點(diǎn))荣恐，刪除后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é)點(diǎn)這里不會(huì)為空液斜，因?yàn)橹辽儆?個(gè)擁有key值得子節(jié)點(diǎn) 取其子節(jié)點(diǎn)
        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))
    }
}

那怎么獲取存儲(chǔ)在MPT上的數(shù)據(jù)呢累贤？繼續(xù)看代碼：

// Get returns the value for key stored in the trie.
// The value bytes must not be modified by the caller.
// 獲取MPT上存儲(chǔ)的數(shù)據(jù)
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上存儲(chǔ)的數(shù)據(jù)
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é)點(diǎn)
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
        }
        // 擴(kuò)展節(jié)點(diǎn)繼續(xù)遞歸找到葉子節(jié)點(diǎn)
        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é)點(diǎn)
        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é)點(diǎn)，先從數(shù)據(jù)庫(kù)里加載出當(dāng)前節(jié)點(diǎn)再繼續(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編碼

序列化主要是用來把內(nèi)存中的數(shù)據(jù)放到數(shù)據(jù)庫(kù)中少漆，反序列化則反之臼膏。以太坊 MPT的序列化主要用到了Compat編碼和RLP編碼。

RLP編碼前面已經(jīng)介紹過,這里簡(jiǎn)單看一下Compat編碼示损。

Compat編碼渗磅，又叫hex prefix編碼(HP)，它是基于hex編碼检访。所以首先要明白Hex編碼是怎么一回事始鱼。

Hex編碼：當(dāng)[key， value]數(shù)據(jù)插入MPT時(shí)烛谊，這里的key必須經(jīng)過特殊編碼以保證能以16進(jìn)制形式按位進(jìn)入fullNode.Children[]风响。由于Children數(shù)組最多容納16個(gè)字節(jié)點(diǎn)，所以以太坊這里定義了Hex編碼方式將1bytes的字符大小限制在4bit(16進(jìn)制)以內(nèi)丹禀。trie給出的Hex編碼方式如下：

Hex編碼

從圖上可以看出状勤，Hex編碼主要有兩步：

• 1.將1個(gè)byte的高低4bit分別放到2個(gè)byte里，形成新的byte[]
• 2.在新byte[]后再追加1個(gè)byte來標(biāo)記當(dāng)前byte[]為Hex格式

Compat編碼：主要作用用來將Hex格式的字符串恢復(fù)到keybytes格式双泪，同時(shí)加入當(dāng)前Compat格式的標(biāo)記位持搜，還要考慮奇偶不同長(zhǎng)度Hex字符串下避免引入多余的bytes。

Compat編碼

從圖上可以看出焙矛，Compat編碼主要有兩步：

• 1.將Hex格式的尾部標(biāo)記byte去掉葫盼，然后將每2nibble的數(shù)據(jù)合并到1個(gè)byte

• 2.判斷Hex編碼長(zhǎng)度，如果輸入 Hex 格式字符串有效長(zhǎng)度為偶數(shù)村斟，偶數(shù)標(biāo)志位0010贫导，這樣新增1byte來放置compat標(biāo)志位就為00100000；反之將Hex字符串第一個(gè)nibble放置在標(biāo)記位低4bit蟆盹，加上奇數(shù)標(biāo)志位0011的compat標(biāo)志位就為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編碼串轉(zhuǎn)化為Compact編碼
func hexToCompact(hex []byte) []byte {
    // 如果最后一位是16，terminator為1逾滥，否則為0
    terminator := byte(0)
    // 包含terminator的節(jié)點(diǎn)為葉子節(jié)點(diǎn)
    if hasTerm(hex) {
        terminator = 1
        // 1.0將Hex格式的尾部標(biāo)記byte去掉
        hex = hex[:len(hex)-1]
    }
    // 定義Compat字節(jié)數(shù)組
    buf := make([]byte, len(hex)/2+1)
    // 標(biāo)志位默認(rèn)
    buf[0] = terminator << 5 // the flag byte
    if len(hex)&1 == 1 {
        // 如果Hex長(zhǎng)度為奇數(shù)峰档，修改標(biāo)志位為odd flag
        buf[0] |= 1 << 4 // odd flag
        // 然后把第1個(gè)nibble放入buf[0]低四位
        buf[0] |= hex[0] // first nibble is contained in the first byte
        hex = hex[1:]
    }
    // 1.1然后將每2nibble的數(shù)據(jù)合并到1個(gè)byte
    decodeNibbles(hex, buf[1:])
    return buf
}
// Compact編碼轉(zhuǎn)化為Hex編碼串
func compactToHex(compact []byte) []byte {
    base := keybytesToHex(compact)
    // delete terminator flag

    /*這里base[0]有4中情況
      00000000  擴(kuò)展節(jié)點(diǎn)偶數(shù)位
      00000001  擴(kuò)展節(jié)點(diǎn)奇數(shù)位
      00000010  葉子節(jié)點(diǎn)偶數(shù)位
      00000011  葉子節(jié)點(diǎn)偶數(shù)位
    */

    if base[0] < 2 {
        // 如果是擴(kuò)展節(jié)點(diǎn)，去除最后一位
        base = base[:len(base)-1]
    }
    // apply odd flag
    // 如果是偶數(shù)位chop=2寨昙，否則chop=1
    chop := 2 - base[0]&1
    //去除compact標(biāo)志位讥巡。偶數(shù)位去除2個(gè)字節(jié)，奇數(shù)位去除1個(gè)字節(jié)（因?yàn)槠鏀?shù)位的低四位放的是nibble數(shù)據(jù)）
    return base[chop:]
}

// 將key字符串進(jìn)行Hex編碼
func keybytesToHex(str []byte) []byte {
    l := len(str)*2 + 1
    //將一個(gè)keybyte轉(zhuǎn)化成兩個(gè)字節(jié)
    var nibbles = make([]byte, l)
    for i, b := range str {
        nibbles[i*2] = b / 16
        nibbles[i*2+1] = b % 16
    }
    //末尾加入Hex標(biāo)志位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編碼解碼轉(zhuǎn)為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
}

這里涉及到一個(gè)葉子節(jié)點(diǎn)的判斷hasTerm舔哪，使用compact編碼的規(guī)格：

MPT序列化

了解了MPT編碼方式之后欢顷，來看看涉及MPT編碼存儲(chǔ)的一個(gè)簡(jiǎn)單流程。我們?cè)趖rie_test.go里的insert測(cè)試函數(shù)來看看MPT編碼存儲(chǔ)的邏輯捉蚤。

func TestInsert(t *testing.T) {

    // 1.創(chuàng)建一個(gè)空的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.調(diào)用Commit函數(shù)進(jìn)行序列化
    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é)點(diǎn)數(shù)據(jù)存儲(chǔ)到數(shù)據(jù)庫(kù)中
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é)點(diǎn)的實(shí)現(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é)點(diǎn)的實(shí)現(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é)點(diǎn)進(jìn)行哈希
    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é)點(diǎn)向下折疊為hash node刹泄，同時(shí)返回用計(jì)算出的散列初始化的原始節(jié)點(diǎn)的副本以替換原始節(jié)點(diǎn)。
/*
    node    MPT根節(jié)點(diǎn)
    db      存儲(chǔ)的數(shù)據(jù)庫(kù)
    force   true 當(dāng)節(jié)點(diǎn)的RLP字節(jié)長(zhǎng)度小于32也對(duì)節(jié)點(diǎn)的RLP進(jìn)行hash計(jì)算
            根節(jié)點(diǎn)調(diào)用為true以保證對(duì)根節(jié)點(diǎn)進(jìn)行哈希計(jì)算
    return:
    node    入?yún)經(jīng)過哈希折疊后的hashNode
    node    hashNode被賦值了的同時(shí)未被哈希折疊的入?yú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é)點(diǎn) 當(dāng)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é)點(diǎn)替換成他們的Hash
    collapsed, cached, err := h.hashChildren(n, db)
    if err != nil {
        return hashNode{}, n, err
    }
    // 將所有節(jié)點(diǎn)都換算完hash的hashNode存入數(shù)據(jù)庫(kù)
    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é)點(diǎn)替換成他們的hash怎爵，可以看到cache變量接管了原來的Trie樹的完整結(jié)構(gòu)
// collapsed變量把子節(jié)點(diǎn)替換成子節(jié)點(diǎn)的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
        // 當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)或擴(kuò)展節(jié)點(diǎn)，將collapsed.Key從Hex編碼轉(zhuǎn)換為Compat編碼
        collapsed, cached := n.copy(), n.copy()
        collapsed.Key = hexToCompact(n.Key)
        cached.Key = common.CopyBytes(n.Key)

        //循環(huán)調(diào)用hash算法將collapsed中子節(jié)點(diǎn)全換成子節(jié)點(diǎn)的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é)點(diǎn)鳖链，遍歷將子節(jié)點(diǎn)全換成子節(jié)點(diǎn)的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é)點(diǎn)姆蘸，直接返回
        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é)點(diǎn)存儲(chǔ)
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()
    // 調(diào)用rlp.Encode方法對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行編碼
    if err := rlp.Encode(&h.tmp, n); err != nil {
        panic("encode error: " + err.Error())
    }
    // 如果編碼后的值 < 32 并且沒有要求強(qiáng)制保存(根節(jié)點(diǎn))，直接存儲(chǔ)在父節(jié)點(diǎn)中
    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 存儲(chǔ)到數(shù)據(jù)庫(kù)中
    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ù)據(jù)庫(kù)存儲(chǔ)的key為node經(jīng)過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.調(diào)用hash函數(shù)作了三個(gè)操作：一是保留了原有的樹形結(jié)構(gòu)到cached芙委，二是計(jì)算了原有樹形結(jié)構(gòu)的hash并把其存到hashed里逞敷，三是在有子節(jié)點(diǎn)的節(jié)點(diǎn)調(diào)用了hashChildren函數(shù)來遞歸地將所有子節(jié)點(diǎn)變?yōu)樗麄兊墓Ｖ怠?/p>

• 2.hashChildren用于遍歷每一個(gè)節(jié)點(diǎn)，其中又嵌套調(diào)用了hash函數(shù)來計(jì)算節(jié)點(diǎn)的哈希值灌侣，hashChildren與hash函數(shù)相互調(diào)用正好遍歷了整個(gè)MPT樹結(jié)構(gòu)推捐。

• 3.store函數(shù)對(duì)節(jié)點(diǎn)做RLP編碼，并將節(jié)點(diǎn)存儲(chǔ)到數(shù)據(jù)庫(kù)中

MPT反序列化

其實(shí)在之前看insert函數(shù)源碼時(shí)就涉及到了MPT反序列化侧啼。當(dāng)時(shí)遇到當(dāng)前節(jié)點(diǎn)為hashNode時(shí)牛柒，需要調(diào)用t.resolveHash函數(shù)從數(shù)據(jù)庫(kù)取出當(dāng)前節(jié)點(diǎn)來進(jìn)行操作，這個(gè)過程便是MPT節(jié)點(diǎn)的反序列化痊乾。

// 根據(jù)hashNode取出對(duì)應(yīng)的節(jié)點(diǎn)
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.
// 從內(nèi)存中檢索緩存的MPT節(jié)點(diǎn)哪审，如果在內(nèi)存緩存中找不到任何節(jié)點(diǎn)蛾魄，則返回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
    }

    // 真正根據(jù)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é)點(diǎn)的RLP編碼湿滓。
func decodeNode(hash, buf []byte, cachegen uint16) (node, error) {

    //空節(jié)點(diǎn)
    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 {
    // 這里根據(jù)rlpList的長(zhǎng)度來判斷節(jié)點(diǎn)類型滴须，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)
    }
}

到這里叽奥，就根據(jù)分辨出的節(jié)點(diǎn)類型來解碼描馅。decodeShort和decodeFull邏輯大致相同，我們以decodeShort為例來深入了解下解碼邏輯而线。

// 針對(duì)shortNode的解碼方式
func decodeShort(hash, elems []byte, cachegen uint16) (node, error) {

    // kbuf -- compact key;rest -- 節(jié)點(diǎn)的value
    kbuf, rest, err := rlp.SplitString(elems)
    if err != nil {
        return nil, err
    }
    flag := nodeFlag{hash: hash, gen: cachegen}
    // 1.將key從conmpact編碼轉(zhuǎn)換為Hex字符串
    key := compactToHex(kbuf)
    // 2.根據(jù)是否包含終結(jié)符號(hào)(16--00010000)來判斷是否為葉子節(jié)點(diǎn)
    if hasTerm(key) {
        // value node
        // 包含16，是葉子節(jié)點(diǎn)
        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é)點(diǎn)
    r, _, err := decodeRef(rest, cachegen)
    if err != nil {
        return nil, wrapError(err, "val")
    }
    return &shortNode{key, r, flag}, nil
}
...
// 解析剩余節(jié)點(diǎn)
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.
        // 根據(jù)RLP編碼規(guī)則 len(buf) - len(rest)為類型加內(nèi)容的長(zhǎng)度
        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
        }

        // 遞歸調(diào)用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ù)據(jù)類型為hash值恋日，構(gòu)造一個(gè)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ù)據(jù)結(jié)構(gòu)

MPT的東西源碼里還真不少膀篮，以至于都忘記來看看其數(shù)據(jù)結(jié)構(gòu)了。

// 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é)點(diǎn)的數(shù)據(jù)庫(kù)
    db           *Database
    // MPT根節(jié)點(diǎn)
    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都會(huì)自增1
    // cachelimit 緩存限制值 
    //      當(dāng)trie.cachegen-node.cachegen > cachelimit 移除節(jié)點(diǎn)
    cachegen, cachelimit uint16
}

加密的MPT

為了避免使用太長(zhǎng)的key導(dǎo)致訪問時(shí)間太久誓竿，以太坊用security_trie對(duì)上述trie作了一個(gè)封裝，使得最后所有的key都轉(zhuǎn)換成keccak256算法計(jì)算的hash值谈截。同時(shí)在數(shù)據(jù)庫(kù)里映射存儲(chǔ)了對(duì)應(yīng)的原有key筷屡。

type SecureTrie struct {
    // MPT樹
    trie             Trie
    // 緩存key經(jīng)過keccak256后的哈希值
    hashKeyBuf       [common.HashLength]byte
    // 映射hash值和原有key的關(guān)系
    secKeyCache      map[string][]byte
    // self
    secKeyCacheOwner *SecureTrie // Pointer to self, replace the key cache on mismatch
}

與MPT類似涧偷，SecureTrie也有g(shù)et，delete毙死，commit等操作燎潮，這里就不再贅述。

說起來扼倘，以太坊有關(guān)MPT的實(shí)現(xiàn)源碼還真不少确封。還有很多細(xì)節(jié)還沒有去看，作為理解以太坊MPT再菊，這些已經(jīng)足夠了爪喘。

以太坊四棵樹

以太坊的每一個(gè)區(qū)塊頭里都包含著三顆樹的根節(jié)點(diǎn)：

• 1. transactionsRoot,交易樹
• 2. receiptsRoot,收據(jù)樹
• 3. stateRoot,狀態(tài)樹

還有一顆樹在以太坊賬戶account里，每一個(gè)account都包含nonce,balance,storageRoot,codeHash四個(gè)子項(xiàng)纠拔，其中便有第四棵樹的根節(jié)點(diǎn)：

• 4. storageRoot秉剑，存儲(chǔ)樹，它是所有合約數(shù)據(jù)存儲(chǔ)的地方

MPT是以太坊特有的自己構(gòu)造的樹結(jié)構(gòu)稠诲。今天侦鹏，已經(jīng)將MPT的基本機(jī)制和源碼實(shí)現(xiàn)看完了。

更多以太坊源碼解析請(qǐng)移駕全球最大同性交友網(wǎng),覺得有用記得給個(gè)小star哦??????

.
.
.
.

互聯(lián)網(wǎng)顛覆世界吕粹，區(qū)塊鏈顛覆互聯(lián)網(wǎng)!

--------------------------------------------------20180926 01:19