資訊專欄INFORMATION COLUMN
摘要：是以太坊存儲數據的核心數據結構，它是由和結合的一種樹形結構，理解有助于我們更好的理解以太坊的數據存儲。所以就有了樹壓縮前綴樹，后面會介紹到，也被稱為，中文名稱默克爾樹，主要用于數據集較大時的文件校驗。
??MPT(Merkle Patricia Tries)是以太坊存儲數據的核心數據結構，它是由Merkle Tree和Patricia Tree結合的一種樹形結構，理解MPT有助于我們更好的理解以太坊的數據存儲。在了解MPT數據結構之前，我們需要先來看看基本的Tree結構和Merkle Tree、Patricia Tree。
Trie字典樹??Trie樹，又稱前綴樹或字典樹，是一種有序樹，用于保存關聯數組，其中的鍵通常是字符串。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。
上圖是一棵Trie樹，表示了字符串集合{“a”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn”} ，從上圖中我們可以看出Trie樹的特點：
根節點不包含字符，除根節點外的每一個子節點都包含一個字符。
從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。
每個節點的所有子節點包含的字符互不相同。
但是從上面的結構也可以看出一個問題：高度不可控，如下圖所示。所以就有了Patricia樹（壓縮前綴樹），后面會介紹到
Merkle Tree，也被稱為Hash Tree，中文名稱：默克爾樹，主要用于數據集較大時的文件校驗。其主要特點為：
葉節點存儲著數據塊的Hash（如：文件塊、一段數據集）
非葉子節點（包括中間節點和根節點）存儲著對應子節點Hash值串聯字符串之后的Hash值。
解釋：
1、在最底層，和哈希列表一樣，我們把數據分成小的數據塊，有相應地哈希和它對應；
2、往上走，并不是直接去運算根哈希，而是把相鄰的兩個哈希合并成一個字符串，然后運算這個字符串的哈希，這樣每兩個哈希就結婚生子，得到了一個”子哈希“。如果最底層的哈希總數是單數，那到最后必然出現一個單身哈希，這種情況就直接對它進行哈希運算，所以也能得到它的子哈希再往上推，依然是一樣的方式，可以得到數目更少的新一級哈希，
3、最終必然形成一棵倒掛的樹，到了樹根的這個位置，這一代就剩下一個根哈希了，我們把它叫做 Merkle Root。
??對于這種數據結構，在實際應用中會有哪些應用場景了，舉個例子，我們知道現在從網上下載文件，很多都是P2P下載，文件會切分成很多小的數據塊，每個數據塊從不同的來源上下載，這些機器可以認為是不穩定或不可信的，文件下載完之后我們需要校驗文件的完整性，這時我們總不能把文件再次切分然后分別計算它的Hash和下載前的Hash做對比吧，這時就需要用到Merkle Tree。
??在下載前，先從可靠的源獲得文件的Merkle Tree樹根，下載后，在合并文件之前先對比小文件的Hash是否一樣，如果一樣就認為是可靠的，如果不一樣，就判定文件被損壞，從新的來源重新下載，文件合并之后，計算小數據塊的Hash并最終計算根Hash，也成為Merkle Root，然后對比根Hash是否一致。這樣就避免了對整個文件進行Hash計算，因為當文件太大時，這種計算是很耗時。
??Patricia樹，或稱Patricia trie，或crit bit tree，壓縮前綴樹，是一種更節省空間的Trie。對于基數樹的每個節點，如果該節點是唯一的兒子的話，就和父節點合并。
??上面我們介紹了Merkle Tree和Patricia Tree，而MPT（Merkle Patricia Tree），顧名思義就是這兩者的結合。MTP樹種的節點包含空節點、葉子節點、擴展節點和分支節點。
Nibble：它是key的基本單元，是一個四元組（四個bit位的組合例如二進制表達的0010就是一個四元組）
空節點**：簡單的表示空，在代碼中是一個空串。
葉子節點（leaf）：只有兩個元素，分別為key和value，表示為[key,value]的一個鍵值對，其中key是key的一種特殊十六進制編碼，value是value的RLP編碼。
擴展節點（extension）：也是[key，value]的一個鍵值對，但是這里的value是其他節點的hash值，這個hash可以被用來查詢數據庫中的節點。也就是說通過hash鏈接到其他節點。
分支節點（branch）：分支節點有17個元素，回到Nibble，四元組是key的基本單元，四元組最多有16個值。所以前16個必將落入到在其遍歷中的鍵的十六個可能的半字節值中的每一個。第17個是存儲那些在當前結點結束了的節點(例如， 有三個key,分別是 (abc ,abd, ab) 第17個字段儲存了ab節點的值)
這里還有一些知識點需要了解的，為了將MPT樹存儲到數據庫中，同時還可以把MPT樹從數據庫中恢復出來，對于Extension和Leaf的節點類型做了特殊的定義：如果是一個擴展節點，那么前綴為0，這個0加在key前面。如果是一個葉子節點，那么前綴就是1。同時對key的長度就奇偶類型也做了設定，如果是奇數長度則標示1，如果是偶數長度則標示0。
以太坊的每一個區塊頭，并非只包含一棵MPT樹，而是包含了三棵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
MPT樹種還有一個重要的概念：特殊的十六進制前綴(hex-prefix, HP)編碼來對key編碼，我們先來了解一下編碼定義規則：
RAW 原始編碼，對輸入不做任何變更
HEX 十六進制編碼
RAW編碼輸入的每個字符分解為高4位和低4位。比如key=>"bob",b的ASCII十六進制編碼為0x62，o的ASCII十六進制編碼為0x6f，分解成高四位和第四位，16表示終結 0x10，最終編碼結果為[6 2 6 15 6 2 16]，
如果是葉子節點，則在最后加上Hex值0x10表示結束
如果是分支節點不附加任何Hex值
HEX-Prefix 十六進制前綴編碼
輸入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]
官方有一個詳細的結構的示例：
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/24478.html
摘要：是以太坊中存儲區塊數據的核心數據結構，它和融合一個樹形結構，理解結構對之后學習以太坊區塊以及智能合約狀態存儲結構的模塊源碼很有幫助。 MPT(Merkle Patricia Tries)是以太坊中存儲區塊數據的核心數據結構，它Merkle Tree和Patricia Tree融合一個樹形結構，理解MPT結構對之后學習以太坊區塊header以及智能合約狀態存儲結構的模塊源碼很有幫助。 首...
摘要：前言以太坊是一個巨大的狀態機，在網絡中，每一個全節點都保存著以太坊狀態機的全部歷史，只要愿意，我們可以查詢到任何時刻的狀態黃皮書中，而賬戶狀態便是其中的狀態，這部分功能由主要由代碼中的包提供基本概念賬戶地址在以太坊中，無論是外部賬戶還是合約 前言 以太坊是一個巨大的狀態機，在網絡中，每一個全節點都保存著以太坊狀態機的全部歷史，只要愿意，我們可以查詢到任何時刻的狀態(黃皮書中World ...
摘要：加密經濟網絡中的底層公鏈是比比特幣更像比特幣的價值存儲平臺。這一點將會在經濟模型設計中講到，敬請期待在技術實現上，我們也充分對比了比特幣模型和以太坊模型的優劣，從中繼承了比特幣協議對狀態為核心的優秀架構。 Nervos 加密經濟網絡中的底層公鏈 CKB 是比比特幣更像比特幣的價值存儲平臺。（這一點將會在經濟模型設計中講到，敬請期待～）在技術實現上，我們也充分對比了比特幣 UTXO 模型...
摘要：以太坊發布加密貨幣網絡年月初文章在上宣布以太坊首次向比特幣社群宣布以太坊。銷售所得首先用于償還日益增加的法律債務，回報開發者們數月以來的努力，以及資助以太坊的持續開發。以太坊安全審查開始于年末，持續到年上半年。 以太坊歷史最近歷史記錄，請查看Taylor Gerring博客發帖。 誕生2013年末Vitalik Buterin第一次描述了以太坊，作為他研究比特幣社群的成果，不久后，Vi...
摘要：基于以太坊項目，以太坊團隊目前運營了一個公開的區塊鏈平臺以太坊網絡。主要特點以太坊區塊鏈底層也是一個類似比特幣網絡的網絡平臺，智能合約運行在網絡中的以太坊虛擬機里。以太坊采用交易作為執行操作的最小單位。 以太坊將比特幣針對數字交易的功能進一步進行了拓展，面向更為復雜和靈活的應用場景，支持了智能合約這一重要特性。 以太坊項目簡介 以太坊：項目最初的目標是打造以個智能合約的平臺，該平臺支持...
閱讀 3596·2023-04-26 02:24
閱讀 931·2023-04-25 14:47
閱讀 2478·2021-11-24 11:16
閱讀 1711·2021-11-24 09:38
閱讀 1571·2021-11-18 10:07
閱讀 2061·2021-09-22 15:49
閱讀 1589·2019-08-30 15:55
閱讀 875·2019-08-26 13:38
