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

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

前綴樹Trie

前綴樹（又稱字典樹），通常來說，一個前綴樹是用來存儲字符串的。前綴樹的每一個節點代表一個字符串（前綴）。每一個節點會有多個子節點，通往不同子節點的路徑上有着不同的字符。子節點代表的字符串是由節點本身的原始字符串，以及通往該子節點路徑上所有的字符組成的。如下圖所示：

image-20201231160000592

Trie的結點看上去是這樣子的：

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

其中 [Ia, Ib, ... I*] 在本文中我們將其稱為結點的 索引數組 ，它以 key 中的下一個字符為索引，每個元素I*指向對應的子結點。 value 則代表從根節點到當前結點的路徑組成的key所對應的值。如果不存在這樣一個 key，則 value 的值為空。

前綴樹的性質：

  1. 每一層節點上面的值都不相同；

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

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

  4. 當存在一個節點，其內容很長（如一串很長的字符串），當樹中沒有與他相同前綴的分支時，為了存儲該節點，需要創建許多非葉子節點來構建根節點到該節點間的路徑，造成了存儲空間的浪費。

壓縮前綴樹Patricia Tree

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

image-20201231133805927

圖中可以很容易看出數中所存儲的鍵值對：

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

默克爾樹Merkle Tree

Merkle樹看起來非常像二叉樹，其葉子節點上的值通常為數據塊的哈希值，而非葉子節點上的值，所以有時候Merkle tree也表示為Hash tree，如下圖所示：

image-20201230225028932

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

所以我們可以簡單總結出merkle Tree 有以下幾個性質：

  • 校驗整體數據的正確性
  • 快速定位錯誤
  • 快速校驗部分數據是否在原始的數據中
  • 存儲空間開銷大（大量中間哈希）

以太坊的改進方案

使用[]byte作為key類型

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

Nibble ：是 key 的基本單元，是一個四元組（四個 bit 位的組合例如二進制表達的 0010 就是一個四元組）

在Trie模塊對外提供的接口中，key類型是[]byte。但在內部實現里，將key中的每個位元組按高4位和低4位拆分成了兩個位元組。比如你傳入的key是：

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

Trie內部將這個key拆分成：

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

Trie內部的編碼中將拆分後的每一個位元組稱為 nibble

如果使用一個完整的 byte 作為 key 的最小單位，那麼前文提到的索引數組的大小應該是 256（byte作為數組的索引，最大值為255，最小值為0）。而索引數組的每個元素都是一個 32 位元組的哈希,這樣每個結點要佔用大量的空間。並且索引數組中的元素多數情況下是空的，不指向任何結點。因此這種實現方法佔用大量空間而不使用。以太坊的改進方法，可以將索引數組的大小降為 16（4個bit的最大值為0xF，最小值為 0），因此大大減少空間的浪費。

新增類型節點

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

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

此外，為了將 MPT 樹存儲到數據庫中，同時還可以把 MPT 樹從數據庫中恢復出來，對於 Extension 和 Leaf 的節點類型做了特殊的定義：如果是一個擴展節點，那麼前綴為 0，這個 0 加在 key 前面。如果是一個葉子節點，那麼前綴就是 1。同時對key 的長度就奇偶類型也做了設定，如果是奇數長度則標示 1，如果是偶數長度則標示 0。

以太坊中使用到的MPT樹結構

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

image-20201231141329137

這兩個區塊頭中，state root、tx root、 receipt root分別存儲了這三棵樹的樹根，第二個區塊顯示了當賬號 17 5的數據變更(27 -> 45)的時候，只需要存儲跟這個賬號相關的部分數據，而且老的區塊中的數據還是可以正常訪問。

key編碼規則

三種編碼方式分別為：

  1. Raw編碼（原生的字符）；
  2. Hex編碼（擴展的16進制編碼）；
  3. Hex-Prefix編碼（16進制前綴編碼）；

Raw編碼

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

例如一條key為「cat」，value為「dog」的數據項，其Raw編碼就是[‘c’, ‘a’, ‘t’]，換成ASCII表示方式就是[63, 61, 74]

Hex編碼

Hex編碼用於對內存中MPT樹節點key進行編碼.

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

半位元組，在計算機中，通常將8位二進制數稱為位元組，而把4位二進制數稱為半位元組。 高四位和低四位，這裡的「位」是針對二進制來說的。比如數字 250 的二進制數為 11111010，則高四位是左邊的 1111，低四位是右邊的 1010。

從Raw編碼向Hex編碼的轉換規則是：

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

例如：字符串 「romane」 的 bytes 是 [114 111 109 97 110 101]，在 HEX 編碼時將其依次處理：

i key[i] key[i]二進制 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]

// 源碼實現
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 // 最後一位存入標示符 代表是hex編碼
	return nibbles
}

Hex-Prefix編碼

數學公式定義：

image-20201231170415071

Hex-Prefix 編碼是一種任意量的半位元組轉換為數組的有效方式，還可以在存入一個標識符來區分不同節點類型。 因此 HP 編碼是在由一個標識符前綴和半位元組轉換為數組的兩部分組成。存入到數據庫中存在節點 Key 的只有擴展節點和葉子節點，因此 HP 只用於區分擴展節點和葉子節點，不涉及無節點 key 的分支節點。其編碼規則如下圖：

image-20201231164209626

前綴標識符由兩部分組成：節點類型和奇偶標識，並存儲在編碼後位元組的第一個半位元組中。 0 表示擴展節點類型，1 表示葉子節點，偶為 0，奇為 1。最終可以得到唯一標識的前綴標識：

  • 0：偶長度的擴展節點
  • 1：奇長度的擴展節點
  • 2：偶長度的葉子節點
  • 3：奇長度的葉子節點

當偶長度時，第一個位元組的低四位用0填充，當是奇長度時，則將 key[0] 存放在第一個位元組的低四位中，這樣 HP 編碼結果始終是偶長度。 這裡為什麼要區分節點 key 長度的奇偶呢？這是因為，半位元組 1 和 01 在轉換為 bytes 格式時都成為<01>，無法區分兩者。

例如，上圖 「以太坊 MPT 樹的哈希計算」中的控制節點1的key 為 [ 7 2 6 f 6 d]，因為是偶長度，則 HP[0]= (00000000) =0，H[1:]= 解碼半位元組(key)。 而節點 3 的 key 為 [1 6 e 6 5]，為奇長度，則 HP[0]= (0001 0001)=17。

HP編碼的規則如下：

  • key結尾為0x10，則去掉這個終止符
  • key之前補一個四元組這個Byte第0位區分奇偶信息，第 1 位區分節點類型
  • 如果輸入key的長度是偶數，則再添加一個四元組0x0在flag四元組後
  • 將原來的key內容壓縮，將分離的兩個byte以高四位低四位進行合併

十六進制前綴編碼相當於一個逆向的過程，比如輸入的是[6 2 6 15 6 2 16]，

根據第一個規則去掉終止符16。根據第二個規則key前補一個四元組，從右往左第一位為1表示葉子節點，

從右往左第0位如果後面key的長度為偶數設置為0，奇數長度設置為1，那麼四元組0010就是2。

根據第三個規則，添加一個全0的補在後面，那麼就是20.根據第三個規則內容壓縮合併，那麼結果就是[0x20 0x62 0x6f 0x62]

HP 編碼源碼實現:

func hexToCompact(hex []byte) []byte {
	terminator := byte(0) //初始化一個值為0的byte，它就是我們上面公式中提到的t
	if hasTerm(hex) {     //驗證hex有後綴編碼，
		terminator = 1         //hex編碼有後綴，則t=1
		hex = hex[:len(hex)-1] //此處只是去掉後綴部分的hex編碼
	}
	////Compact開闢的空間長度為hex編碼的一半再加1，這個1對應的空間是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 長度為奇數，則邏輯上說明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:]    //此時獲取的hex編碼無前綴無後綴
	}
	decodeNibbles(hex, buf[1:]) //將hex編碼映射到compact編碼中
	return buf                  //返回compact編碼
}

以上三種編碼方式的轉換關係為：

  • Raw編碼：原生的key編碼，是MPT對外提供接口中使用的編碼方式，當數據項被插入到樹中時，Raw編碼被轉換成Hex編碼；
  • Hex編碼：16進制擴展編碼，用於對內存中樹節點key進行編碼，當樹節點被持久化到數據庫時，Hex編碼被轉換成HP編碼；
  • HP編碼：16進制前綴編碼，用於對數據庫中樹節點key進行編碼，當樹節點被加載到內存時，HP編碼被轉換成Hex編碼；

如下圖：

image-20201231150011417

以上介紹的MPT樹，可以用來存儲內容為任何長度的key-value數據項。倘若數據項的key長度沒有限制時，當樹中維護的數據量較大時，仍然會造成整棵樹的深度變得越來越深，會造成以下影響：

  • 查詢一個節點可能會需要許多次 IO 讀取，效率低下；
  • 系統易遭受 Dos 攻擊，攻擊者可以通過在合約中存儲特定的數據，「構造」一棵擁有一條很長路徑的樹，然後不斷地調用SLOAD指令讀取該樹節點的內容，造成系統執行效率極度下降；
  • 所有的 key 其實是一種明文的形式進行存儲；

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

優勢：

  • 傳入MPT接口的 key 是固定長度的（32位元組），可以避免出現樹中出現長度很長的路徑；

劣勢：

  • 每次樹操作需要增加一次哈希計算；
  • 需要在數據庫中存儲額外的sha3(key)與key之間的對應關係；

完整的編碼流程如圖：

image-20201231150520220

MPT輕節點

上面的MPT樹，有兩個問題：

  • 每個節點都包含有大量信息，並且葉子節點中還包含有完整的數據信息。如果該MPT樹並沒有發生任何變化，並且沒有被使用，則會白白佔用一大片空間，想像一個以太坊，有多少個MPT樹，都在內存中，那還了得。
  • 並不是任何的客戶端都對所有的MPT樹都感興趣，若每次都把完整的節點信息都下載下，下載時間長不說，並且會佔用大量的磁盤空間。

解決方式

為了解決上述問題，以太坊使用了一種緩存機制，可以稱為是輕節點機制，大體如下：

  • 若某節點數據一直沒有發生變化，則僅僅保留該節點的32位hash值，剩下的內容全部釋放
  • 若需要插入或者刪除某節點，先通過該hash值db中查找對應的節點，並加載到內存，之後再進行刪除插入操作

輕節點中添加數據

內存中只有這麼一個輕節點，但是我要添加一個數據，也就是要給完整的MPT樹中添加一個葉子節點，怎麼添加？大體如下圖所示：

image-20210101204824090

到此以太坊的MPT樹的基礎講解結束。

參考

//mindcarver.cn

//github.com/blockchainGuide 文章及視頻學習資料

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

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

//ethfans.org/toya/articles/588

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

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

//arxiv.org/pdf/1909.11590.pdf

Tags:

VirMach 便宜 VPS

QNews

QNews