死磕以太坊源碼分析之MPT樹-上

死磕以太坊源碼分析之MPT樹-上

前綴樹Trie

前綴樹（又稱字典樹），通常來說，一個(gè)前綴樹是用來存儲(chǔ)字符串的。前綴樹的每一個(gè)節(jié)點(diǎn)代表一個(gè)字符串（前綴）。每一個(gè)節(jié)點(diǎn)會(huì)有多個(gè)子節(jié)點(diǎn)，通往不同子節(jié)點(diǎn)的路徑上有著不同的字符。子節(jié)點(diǎn)代表的字符串是由節(jié)點(diǎn)本身的原始字符串，以及通往該子節(jié)點(diǎn)路徑上所有的字符組成的。如下圖所示：

image-20201231160000592

Trie的結(jié)點(diǎn)看上去是這樣子的：

[ [Ia, Ib, … I*], value]

其中 [Ia, Ib, ... I*] 在本文中我們將其稱為結(jié)點(diǎn)的 索引數(shù)組 ，它以 key 中的下一個(gè)字符為索引，每個(gè)元素I*指向?qū)?yīng)的子結(jié)點(diǎn)。 value 則代表從根節(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)的路徑組成的key所對應(yīng)的值。如果不存在這樣一個(gè) key，則 value 的值為空。

前綴樹的性質(zhì)：

  1. 每一層節(jié)點(diǎn)上面的值都不相同；

  2. 根節(jié)點(diǎn)不存儲(chǔ)值；除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符，代表的字符串是由節(jié)點(diǎn)本身的原始字符串，以及通往該子節(jié)點(diǎn)路徑上所有的字符。

  3. 前綴樹的查找效率是O(m)，m為所查找節(jié)點(diǎn)的長度，而哈希表的查找效率為O(1)。且一次查找會(huì)有 m 次 IO開銷，相比于直接查找，無論是速率、還是對磁盤的壓力都比較大。

  4. 當(dāng)存在一個(gè)節(jié)點(diǎn)，其內(nèi)容很長（如一串很長的字符串），當(dāng)樹中沒有與他相同前綴的分支時(shí)，為了存儲(chǔ)該節(jié)點(diǎn)，需要?jiǎng)?chuàng)建許多非葉子節(jié)點(diǎn)來構(gòu)建根節(jié)點(diǎn)到該節(jié)點(diǎn)間的路徑，造成了存儲(chǔ)空間的浪費(fèi)。

壓縮前綴樹Patricia Tree

基數(shù)樹（也叫基數(shù)特里樹或壓縮前綴樹）是一種數(shù)據(jù)結(jié)構(gòu)，是一種更節(jié)省空間的前綴樹，其中作為唯一子節(jié)點(diǎn)的每個(gè)節(jié)點(diǎn)都與其父節(jié)點(diǎn)合并，邊既可以表示為元素序列又可以表示為單個(gè)元素。 因此每個(gè)內(nèi)部節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)最多為基數(shù)樹的基數(shù) r ，其中 r 為正整數(shù)， x 為 2 的冪， x≥1 ，這使得基數(shù)樹更適用于對于較小的集合（尤其是字符串很長的情況下）和有很長相同前綴的字符串集合。

image-20201231133805927

圖中可以很容易看出數(shù)中所存儲(chǔ)的鍵值對：

  • 6c0a5c71ec20bq3w => 5
  • 6c0a5c71ec20CX7j => 27
  • 6c0a5c71781a1FXq => 18
  • 6c0a5c71781a9Dog => 64
  • 6c0a8f743b95zUfe => 30
  • 6c0a8f743b95jx5R => 2
  • 6c0a8f740d16y03G => 43
  • 6c0a8f740d16vcc1 => 48

默克爾樹Merkle Tree

Merkle樹看起來非常像二叉樹，其葉子節(jié)點(diǎn)上的值通常為數(shù)據(jù)塊的哈希值，而非葉子節(jié)點(diǎn)上的值，所以有時(shí)候Merkle tree也表示為Hash tree，如下圖所示：

image-20201230225028932

在構(gòu)造Merkle樹時(shí)，首先要計(jì)算數(shù)據(jù)塊的哈希值，通常，選用SHA-256等哈希算法。但如果僅僅防止數(shù)據(jù)不是蓄意的損壞或篡改，可以改用一些安全性低但效率高的校驗(yàn)和算法，如CRC。然后將數(shù)據(jù)塊計(jì)算的哈希值兩兩配對（如果是奇數(shù)個(gè)數(shù)，最后一個(gè)自己與自己配對），計(jì)算上一層哈希，再重復(fù)這個(gè)步驟，一直到計(jì)算出根哈希值。

所以我們可以簡單總結(jié)出merkle Tree 有以下幾個(gè)性質(zhì)：

  • 校驗(yàn)整體數(shù)據(jù)的正確性
  • 快速定位錯(cuò)誤
  • 快速校驗(yàn)部分?jǐn)?shù)據(jù)是否在原始的數(shù)據(jù)中
  • 存儲(chǔ)空間開銷大（大量中間哈希）

以太坊的改進(jìn)方案

使用[]byte作為key類型

在以太坊的Trie模塊中，key和value都是[]byte類型。如果要使用其它類型，需要將其轉(zhuǎn)換成[]byte類型（比如使用rlp進(jìn)行轉(zhuǎn)換）。

Nibble ：是 key 的基本單元，是一個(gè)四元組（四個(gè) bit 位的組合例如二進(jìn)制表達(dá)的 0010 就是一個(gè)四元組）

在Trie模塊對外提供的接口中，key類型是[]byte。但在內(nèi)部實(shí)現(xiàn)里，將key中的每個(gè)字節(jié)按高4位和低4位拆分成了兩個(gè)字節(jié)。比如你傳入的key是：

[0x1a, 0x2b, 0x3c, 0x4d]

Trie內(nèi)部將這個(gè)key拆分成：

[0x1, 0xa, 0x2, 0xb, 0x3, 0xc, 0x4, 0xd]

Trie內(nèi)部的編碼中將拆分后的每一個(gè)字節(jié)稱為 nibble

如果使用一個(gè)完整的 byte 作為 key 的最小單位，那么前文提到的索引數(shù)組的大小應(yīng)該是 256（byte作為數(shù)組的索引，最大值為255，最小值為0）。而索引數(shù)組的每個(gè)元素都是一個(gè) 32 字節(jié)的哈希,這樣每個(gè)結(jié)點(diǎn)要占用大量的空間。并且索引數(shù)組中的元素多數(shù)情況下是空的，不指向任何結(jié)點(diǎn)。因此這種實(shí)現(xiàn)方法占用大量空間而不使用。以太坊的改進(jìn)方法，可以將索引數(shù)組的大小降為 16（4個(gè)bit的最大值為0xF，最小值為 0），因此大大減少空間的浪費(fèi)。

新增類型節(jié)點(diǎn)

前綴樹和merkle樹存在明顯的局限性，所以以太坊為MPT樹新增了幾種不同類型的樹節(jié)點(diǎn)，通過針對不同節(jié)點(diǎn)不同操作來解決效率以及存儲(chǔ)上的問題。

  1. 空白節(jié)點(diǎn) ：簡單的表示空，在代碼中是一個(gè)空串
  2. 分支節(jié)點(diǎn) ：分支節(jié)點(diǎn)有 17 個(gè)元素，回到 Nibble，四元組是 key 的基本單元，四元組最多有 16 個(gè)值。所以前 16 個(gè)必將落入到在其遍歷中的鍵的十六個(gè)可能的半字節(jié)值中的每一個(gè)。第 17 個(gè)是存儲(chǔ)那些在當(dāng)前結(jié)點(diǎn)結(jié)束了的節(jié)點(diǎn)(例如， 有三個(gè) key,分別是 (abc ,abd, ab) 第 17 個(gè)字段儲(chǔ)存了 ab 節(jié)點(diǎn)的值)
  3. 葉子節(jié)點(diǎn)：只有兩個(gè)元素，分別為 key 和 value
  4. 擴(kuò)展節(jié)點(diǎn) ：有兩個(gè)元素，一個(gè)是 key 值，還有一個(gè)是 hash 值，這個(gè) hash 值指向下一個(gè)節(jié)點(diǎn)

此外，為了將 MPT 樹存儲(chǔ)到數(shù)據(jù)庫中，同時(shí)還可以把 MPT 樹從數(shù)據(jù)庫中恢復(fù)出來，對于 Extension 和 Leaf 的節(jié)點(diǎn)類型做了特殊的定義：如果是一個(gè)擴(kuò)展節(jié)點(diǎn)，那么前綴為 0，這個(gè) 0 加在 key 前面。如果是一個(gè)葉子節(jié)點(diǎn)，那么前綴就是 1。同時(shí)對key 的長度就奇偶類型也做了設(shè)定，如果是奇數(shù)長度則標(biāo)示 1，如果是偶數(shù)長度則標(biāo)示 0。

以太坊中使用到的MPT樹結(jié)構(gòu)

  • State Trie 區(qū)塊頭中的狀態(tài)樹
    • key => sha3(以太坊賬戶地址 address)
    • value => rlp(賬號內(nèi)容信息 account)
  • Transactions Trie 區(qū)塊頭中的交易樹
    • key => rlp(交易的偏移量 transaction index)
    • 每個(gè)塊都有各自的交易樹，且不可更改
  • Receipts Trie 區(qū)塊頭中的收據(jù)樹
    • key = rlp(交易的偏移量 transaction index)
    • 每個(gè)塊都有各自的交易樹，且不可更改
  • Storage Trie 存儲(chǔ)樹
    • 存儲(chǔ)只能合約狀態(tài)
    • 每個(gè)賬號有自己的 Storage Trie
image-20201231141329137

這兩個(gè)區(qū)塊頭中，state root、tx root、 receipt root分別存儲(chǔ)了這三棵樹的樹根，第二個(gè)區(qū)塊顯示了當(dāng)賬號 17 5的數(shù)據(jù)變更(27 -> 45)的時(shí)候，只需要存儲(chǔ)跟這個(gè)賬號相關(guān)的部分?jǐn)?shù)據(jù)，而且老的區(qū)塊中的數(shù)據(jù)還是可以正常訪問。

key編碼規(guī)則

三種編碼方式分別為：

  1. Raw編碼（原生的字符）；
  2. Hex編碼（擴(kuò)展的16進(jìn)制編碼）；
  3. Hex-Prefix編碼（16進(jìn)制前綴編碼）；

Raw編碼

Raw編碼就是原生的key值，不做任何改變。這種編碼方式的key，是MPT對外提供接口的默認(rèn)編碼方式。

例如一條key為“cat”，value為“dog”的數(shù)據(jù)項(xiàng)，其Raw編碼就是['c', 'a', 't']，換成ASCII表示方式就是[63, 61, 74]

Hex編碼

Hex編碼用于對內(nèi)存中MPT樹節(jié)點(diǎn)key進(jìn)行編碼.

為了減少分支節(jié)點(diǎn)孩子的個(gè)數(shù)，將數(shù)據(jù) key 進(jìn)行半字節(jié)拆解而成。即依次將 key[0],key[1],…,key[n] 分別進(jìn)行半字節(jié)拆分成兩個(gè)數(shù)，再依次存放在長度為 len(key)+1 的數(shù)組中。 并在數(shù)組末尾寫入終止符 16。算法如下：

半字節(jié)，在計(jì)算機(jī)中，通常將8位二進(jìn)制數(shù)稱為字節(jié)，而把4位二進(jìn)制數(shù)稱為半字節(jié)。 高四位和低四位，這里的“位”是針對二進(jìn)制來說的。比如數(shù)字 250 的二進(jìn)制數(shù)為 11111010，則高四位是左邊的 1111，低四位是右邊的 1010。

從Raw編碼向Hex編碼的轉(zhuǎn)換規(guī)則是：

  • Raw編碼輸入的每個(gè)字符分解為高 4 位和低 4 位
  • 如果是葉子節(jié)點(diǎn)，則在最后加上Hex值0x10表示結(jié)束
  • 如果是分支節(jié)點(diǎn)不附加任何Hex值

例如：字符串 “romane” 的 bytes 是 [114 111 109 97 110 101]，在 HEX 編碼時(shí)將其依次處理：

i key[i] key[i]二進(jìn)制 nibbles[i*2]=高四位 nibbles[i*2+1]=低四位
0 114 01110010 0111= 7 0010= 2
1 111 01101111 0110=6 1111=15
2 109 01101101 0110=6 1101=13
3 97 01100001 0110=6 0001=1
4 110 01101110 0110=6 1110=14
5 101 01100101 0110=6 0101=5

最終得到 Hex(“romane”) = [7 2 6 15 6 13 6 1 6 14 6 5 16]

// 源碼實(shí)現(xiàn)
func keybytesToHex(str []byte) []byte {
    l := len(str)*2 + 1
    var nibbles = make([]byte, l)
    for i, b := range str {
        nibbles[i*2] = b / 16   // 高四位
        nibbles[i*2+1] = b % 16 // 低四位
    }
    nibbles[l-1] = 16 // 最后一位存入標(biāo)示符 代表是hex編碼
    return nibbles
}

Hex-Prefix編碼

數(shù)學(xué)公式定義：

image-20201231170415071

Hex-Prefix 編碼是一種任意量的半字節(jié)轉(zhuǎn)換為數(shù)組的有效方式，還可以在存入一個(gè)標(biāo)識(shí)符來區(qū)分不同節(jié)點(diǎn)類型。 因此 HP 編碼是在由一個(gè)標(biāo)識(shí)符前綴和半字節(jié)轉(zhuǎn)換為數(shù)組的兩部分組成。存入到數(shù)據(jù)庫中存在節(jié)點(diǎn) Key 的只有擴(kuò)展節(jié)點(diǎn)和葉子節(jié)點(diǎn)，因此 HP 只用于區(qū)分?jǐn)U展節(jié)點(diǎn)和葉子節(jié)點(diǎn)，不涉及無節(jié)點(diǎn) key 的分支節(jié)點(diǎn)。其編碼規(guī)則如下圖：

image-20201231164209626

前綴標(biāo)識(shí)符由兩部分組成：節(jié)點(diǎn)類型和奇偶標(biāo)識(shí)，并存儲(chǔ)在編碼后字節(jié)的第一個(gè)半字節(jié)中。 0 表示擴(kuò)展節(jié)點(diǎn)類型，1 表示葉子節(jié)點(diǎn)，偶為 0，奇為 1。最終可以得到唯一標(biāo)識(shí)的前綴標(biāo)識(shí)：

  • 0：偶長度的擴(kuò)展節(jié)點(diǎn)
  • 1：奇長度的擴(kuò)展節(jié)點(diǎn)
  • 2：偶長度的葉子節(jié)點(diǎn)
  • 3：奇長度的葉子節(jié)點(diǎn)

當(dāng)偶長度時(shí)，第一個(gè)字節(jié)的低四位用0填充，當(dāng)是奇長度時(shí)，則將 key[0] 存放在第一個(gè)字節(jié)的低四位中，這樣 HP 編碼結(jié)果始終是偶長度。 這里為什么要區(qū)分節(jié)點(diǎn) key 長度的奇偶呢？這是因?yàn)?，半字?jié) 1 和 01 在轉(zhuǎn)換為 bytes 格式時(shí)都成為<01>，無法區(qū)分兩者。

例如，上圖 “以太坊 MPT 樹的哈希計(jì)算”中的控制節(jié)點(diǎn)1的key 為 [ 7 2 6 f 6 d]，因?yàn)槭桥奸L度，則 HP[0]= (00000000) =0，H[1:]= 解碼半字節(jié)(key)。 而節(jié)點(diǎn) 3 的 key 為 [1 6 e 6 5]，為奇長度，則 HP[0]= (0001 0001)=17。

HP編碼的規(guī)則如下：

  • key結(jié)尾為0x10，則去掉這個(gè)終止符
  • key之前補(bǔ)一個(gè)四元組這個(gè)Byte第0位區(qū)分奇偶信息，第 1 位區(qū)分節(jié)點(diǎn)類型
  • 如果輸入key的長度是偶數(shù)，則再添加一個(gè)四元組0x0在flag四元組后
  • 將原來的key內(nèi)容壓縮，將分離的兩個(gè)byte以高四位低四位進(jìn)行合并

十六進(jìn)制前綴編碼相當(dāng)于一個(gè)逆向的過程，比如輸入的是[6 2 6 15 6 2 16]，

根據(jù)第一個(gè)規(guī)則去掉終止符16。根據(jù)第二個(gè)規(guī)則key前補(bǔ)一個(gè)四元組，從右往左第一位為1表示葉子節(jié)點(diǎn)，

從右往左第0位如果后面key的長度為偶數(shù)設(shè)置為0，奇數(shù)長度設(shè)置為1，那么四元組0010就是2。

根據(jù)第三個(gè)規(guī)則，添加一個(gè)全0的補(bǔ)在后面，那么就是20.根據(jù)第三個(gè)規(guī)則內(nèi)容壓縮合并，那么結(jié)果就是[0x20 0x62 0x6f 0x62]

HP 編碼源碼實(shí)現(xiàn):

func hexToCompact(hex []byte) []byte {
    terminator := byte(0) //初始化一個(gè)值為0的byte，它就是我們上面公式中提到的t
    if hasTerm(hex) {     //驗(yàn)證hex有后綴編碼，
        terminator = 1         //hex編碼有后綴，則t=1
        hex = hex[:len(hex)-1] //此處只是去掉后綴部分的hex編碼
    }
    ////Compact開辟的空間長度為hex編碼的一半再加1，這個(gè)1對應(yīng)的空間是Compact的前綴
    buf := make([]byte, len(hex)/2+1)
    ////這一階段的buf[0]可以理解為公式中的16*f(t)
    buf[0] = terminator << 5 // the flag byte
    if len(hex)&1 == 1 {     //hex 長度為奇數(shù)，則邏輯上說明hex有前綴
        buf[0] |= 1 << 4 ////這一階段的buf[0]可以理解為公式中的16*（f(t)+1）
        buf[0] |= hex[0] // first nibble is contained in the first byte
        hex = hex[1:]    //此時(shí)獲取的hex編碼無前綴無后綴
    }
    decodeNibbles(hex, buf[1:]) //將hex編碼映射到compact編碼中
    return buf                  //返回compact編碼
}

以上三種編碼方式的轉(zhuǎn)換關(guān)系為：

  • Raw編碼：原生的key編碼，是MPT對外提供接口中使用的編碼方式，當(dāng)數(shù)據(jù)項(xiàng)被插入到樹中時(shí)，Raw編碼被轉(zhuǎn)換成Hex編碼；
  • Hex編碼：16進(jìn)制擴(kuò)展編碼，用于對內(nèi)存中樹節(jié)點(diǎn)key進(jìn)行編碼，當(dāng)樹節(jié)點(diǎn)被持久化到數(shù)據(jù)庫時(shí)，Hex編碼被轉(zhuǎn)換成HP編碼；
  • HP編碼：16進(jìn)制前綴編碼，用于對數(shù)據(jù)庫中樹節(jié)點(diǎn)key進(jìn)行編碼，當(dāng)樹節(jié)點(diǎn)被加載到內(nèi)存時(shí)，HP編碼被轉(zhuǎn)換成Hex編碼；

如下圖：

image-20201231150011417

以上介紹的MPT樹，可以用來存儲(chǔ)內(nèi)容為任何長度的key-value數(shù)據(jù)項(xiàng)。倘若數(shù)據(jù)項(xiàng)的key長度沒有限制時(shí)，當(dāng)樹中維護(hù)的數(shù)據(jù)量較大時(shí)，仍然會(huì)造成整棵樹的深度變得越來越深，會(huì)造成以下影響：

  • 查詢一個(gè)節(jié)點(diǎn)可能會(huì)需要許多次 IO 讀取，效率低下；
  • 系統(tǒng)易遭受 Dos 攻擊，攻擊者可以通過在合約中存儲(chǔ)特定的數(shù)據(jù)，“構(gòu)造”一棵擁有一條很長路徑的樹，然后不斷地調(diào)用SLOAD指令讀取該樹節(jié)點(diǎn)的內(nèi)容，造成系統(tǒng)執(zhí)行效率極度下降；
  • 所有的 key 其實(shí)是一種明文的形式進(jìn)行存儲(chǔ)；

為了解決以上問題，以太坊對MPT再進(jìn)行了一次封裝，對數(shù)據(jù)項(xiàng)的key進(jìn)行了一次哈希計(jì)算，因此最終作為參數(shù)傳入到MPT接口的數(shù)據(jù)項(xiàng)其實(shí)是(sha3(key), value)

優(yōu)勢：

  • 傳入MPT接口的 key 是固定長度的（32字節(jié)），可以避免出現(xiàn)樹中出現(xiàn)長度很長的路徑；

劣勢：

  • 每次樹操作需要增加一次哈希計(jì)算；
  • 需要在數(shù)據(jù)庫中存儲(chǔ)額外的sha3(key)與key之間的對應(yīng)關(guān)系；

完整的編碼流程如圖：

image-20201231150520220

MPT輕節(jié)點(diǎn)

上面的MPT樹，有兩個(gè)問題：

  • 每個(gè)節(jié)點(diǎn)都包含有大量信息，并且葉子節(jié)點(diǎn)中還包含有完整的數(shù)據(jù)信息。如果該MPT樹并沒有發(fā)生任何變化，并且沒有被使用，則會(huì)白白占用一大片空間，想象一個(gè)以太坊，有多少個(gè)MPT樹，都在內(nèi)存中，那還了得。
  • 并不是任何的客戶端都對所有的MPT樹都感興趣，若每次都把完整的節(jié)點(diǎn)信息都下載下，下載時(shí)間長不說，并且會(huì)占用大量的磁盤空間。

解決方式

為了解決上述問題，以太坊使用了一種緩存機(jī)制，可以稱為是輕節(jié)點(diǎn)機(jī)制，大體如下：

  • 若某節(jié)點(diǎn)數(shù)據(jù)一直沒有發(fā)生變化，則僅僅保留該節(jié)點(diǎn)的32位hash值，剩下的內(nèi)容全部釋放
  • 若需要插入或者刪除某節(jié)點(diǎn)，先通過該hash值db中查找對應(yīng)的節(jié)點(diǎn)，并加載到內(nèi)存，之后再進(jìn)行刪除插入操作

輕節(jié)點(diǎn)中添加數(shù)據(jù)

內(nèi)存中只有這么一個(gè)輕節(jié)點(diǎn)，但是我要添加一個(gè)數(shù)據(jù)，也就是要給完整的MPT樹中添加一個(gè)葉子節(jié)點(diǎn)，怎么添加？大體如下圖所示：

image-20210101204824090

到此以太坊的MPT樹的基礎(chǔ)講解結(jié)束。

參考

https://mindcarver.cn

https://github.com/blockchainGuide 文章及視頻學(xué)習(xí)資料

https://eth.wiki/en/fundamentals/patricia-tree

https://ethereum.github.io/yellowpaper/paper.pdf#appendix.D

https://ethfans.org/toya/articles/588

https://learnblockchain.cn/books/geth/part3/mpt.html

https://blog.ethereum.org/2015/11/15/merkling-in-ethereum/

https://arxiv.org/pdf/1909.11590.pdf

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容