亚洲免费专区,91成人在线播放,亚洲蜜桃怡红在线

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

前綴樹Trie

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

image-20201231160000592

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

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

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

前綴樹的性質(zhì)：

每一層節(jié)點上面的值都不相同；
根節(jié)點不存儲值；除根節(jié)點外每一個節(jié)點都只包含一個字符，代表的字符串是由節(jié)點本身的原始字符串，以及通往該子節(jié)點路徑上所有的字符。
前綴樹的查找效率是 $O(m)$ ， $m$ 為所查找節(jié)點的長度，而哈希表的查找效率為 $O(1)$ 。且一次查找會有 m 次 IO開銷，相比于直接查找，無論是速率、還是對磁盤的壓力都比較大。
當存在一個節(jié)點，其內(nèi)容很長（如一串很長的字符串），當樹中沒有與他相同前綴的分支時，為了存儲該節(jié)點，需要創(chuàng)建許多非葉子節(jié)點來構建根節(jié)點到該節(jié)點間的路徑，造成了存儲空間的浪費。

壓縮前綴樹Patricia Tree

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

image-20201231133805927

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

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

默克爾樹Merkle Tree

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

image-20201230225028932

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

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

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

以太坊的改進方案

使用[]byte作為key類型

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

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

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

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

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

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

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

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

新增類型節(jié)點

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

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

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

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

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

image-20201231141329137

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

key編碼規(guī)則

三種編碼方式分別為：

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

Raw編碼

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

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

Hex編碼

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

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

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

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

Raw編碼輸入的每個字符分解為高 4 位和低 4 位
如果是葉子節(jié)點，則在最后加上Hex值0x10表示結束
如果是分支節(jié)點不附加任何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]

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

Hex-Prefix編碼

數(shù)學公式定義：

image-20201231170415071

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

image-20201231164209626

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

0：偶長度的擴展節(jié)點
1：奇長度的擴展節(jié)點
2：偶長度的葉子節(jié)點
3：奇長度的葉子節(jié)點

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

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

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

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

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

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

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

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

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

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 長度為奇數(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:]    //此時獲取的hex編碼無前綴無后綴
    }
    decodeNibbles(hex, buf[1:]) //將hex編碼映射到compact編碼中
    return buf                  //返回compact編碼
}

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

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

如下圖：

image-20201231150011417

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

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

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

優(yōu)勢：

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

劣勢：

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

完整的編碼流程如圖：

image-20201231150520220

MPT輕節(jié)點

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

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

解決方式

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

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

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

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

image-20210101204824090

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

參考

https://mindcarver.cn

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

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

前綴樹Trie

壓縮前綴樹Patricia Tree

默克爾樹Merkle Tree