5.4 以太坊原始碼詳解4

摘要： MPT(實現快速查詢以節省儲存空間)  背景 Trie：用於快速檢索的多叉樹，查詢速度快、但是需要耗費大量的儲存空間 Patricia Trie：耗費的空間更小 Merkle Tree：Merkle樹是一種用於快速驗證內容完整性的資料結構，其基本原...

MPT(實現快速查詢以節省儲存空間) 

背景

• Trie：用於快速檢索的多叉樹，查詢速度快、但是需要耗費大量的儲存空間
• Patricia Trie：耗費的空間更小
• Merkle Tree：Merkle樹是一種用於快速驗證內容完整性的資料結構，其基本原理是分別計算樹的葉 ⼦ 結點的 hash值，然後把葉 ⼦ 結點的 hash值拼接在 ⼀ 起，再計算 ⼀ 次 hash作為其 ⽗ 結點的 hash值，依次向上直到根結點，根結點的hash值稱為Merkle Root。 可以看出，如果想要獲得相同的Merkle Root，所有 ⼦ 結點的內容都必須相 同，這樣就可以 ⽤ 來驗證樹的內容有沒有被篡改

概念

• MPT：MPT融合了 了 上 ⾯ 面 3種資料結構，但是 ⼜ 又有 ⼀ 一些細微的差別。
• MPT是 ⽤ 用來檢索位元組資料的，因此是 16叉樹，分別代表0x0~0xF。

結構

MPT定義4種結點型別：

1. 空結點（NULL）
2. 分 ⽀ 支結點（ branch node）：包含16個分 ⽀ 支，以及 1個value
3. 擴充套件結點（extension node）：只有1個子結點
4. 葉子結點（leaf node）：沒有 ⼦ 子結點，包含 ⼀ 一個 value

HP編碼

• MPT樹中另外一個重要的概念是一個特殊的十六進位制字首(hex-prefix, 
  HP)編碼，用來對key進行編碼。因為字母表是16進位制的，所以每個節點可能有16個孩子。因為有兩種[key,value]節點(葉節點和擴充套件節點)，引進一種特殊的終止符標識來標識key所對應的是值是真實的值，還是其他節點的hash。如果終止符標記被開啟，那麼key對應的是葉節點，對應的值是真實的value。如果終止符標記被關閉，那麼值就是用於在資料塊中查詢對應的節點的hash。無論key奇數長度還是偶數長度，HP都可以對其進行編碼。最後我們注意到一個單獨的hex字元或者4bit二進位制數字，即一個nibble。
• HP編碼很簡單。一個nibble被加到key前（下圖中的prefix），對終止符的狀態和奇偶性進行編碼。最低位表示奇偶性，第二低位編碼終止符狀態。如果key是偶數長度，那麼加上另外一個nibble，值為0來保持整體的偶特性。

原始碼分析

• 以太坊中的MPT的實現原始碼：trie/trie.go以及trie/node.go。trie.go主要實現struct 
  Trie以及MPT樹的各種操作：查詢，新增，刪除。node.go實現了四種節點以及從持久化資料庫中解析node。理解了Node的實現，Trie的實現很容易理解。有關MPT中的四種節點，node.go的實現如下：

  type (
  // 分支節點
  fullNode struct {
  Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
  flagsnodeFlag
  }
  // 實現葉子節點和擴充套件節點
  shortNode struct {
  Key[]byte
  Valnode
  flags nodeFlag
  }
  hashNode[]byte
  valueNode []byte
  )
  // 每個節點的雜湊資訊
  type nodeFlag struct {
  hashhashNode // cached hash of the node (may be nil)
  genuint16// cache generation counter
  dirty bool// whether the node has changes that must be written to the database
  }

  總結
• MPT是以太坊用來儲存“狀態”的資料結構，綜合了Trie，Patrica Trie以及Merkletree的優點
• MPT的key是用HEX編碼，在持久化儲存時，會轉換為HP編碼。以太坊的go語言實現中，用fullNode表達分支節點，用shortNode表示葉子節點和擴充套件節點。

• 學院Go語言視訊主頁

  ofollow,noindex" target="_blank">https://edu.csdn.net/lecturer/1928

• 清華團隊帶你實戰區塊鏈開發

• 掃碼獲取海量視訊及原始碼   QQ群：721929980