以太坊mpt樹檢驗

Ⅰ 以太坊解讀——Recursive Length Prefix協議圖解(上)

在以太坊中，採用了一種名為Recursive Length Prefix(RLP)的方法對交易、賬號、合約等基礎的數據結構進行序列化處理，從而實現對鏈上數據的網路傳輸和持久化存儲。RLP作為最為底層的編碼方法，其重要性是不言而喻。因此，網上介紹RLP的文章也不少，但是由於RLP是二進制編碼，又涉及到嵌套結構，造成編碼過程的可讀性較差，在學習中過程中，也一直沒有找到完整的、易於理解的說明，總是繞在各種規則之中，且不能"自拔"，著實有點無奈。所以，在本文中，採用圖形化的解釋和舉例的方法，幫助大家理解RLP嵌套等特點、編解碼過程等。

和其他的序列化協議不同，RLP只支持兩種數據類型：
1）byte數組，可以是二進制數組，當然也可以是字元串；
2）byte數組的數組，也就是列表。並支持列表內的嵌套。
對於其他的數據類型，RLP都不支持，需要用戶自己先轉化為數組和列表的類型。

從RLP的命名中就可以看出兩個關鍵字：一個是遞歸Recursive和前綴Prefix。首先，關於遞歸，也就是嵌套結構，結構上非常接近「樹」，在Ethereum WiKi中，更是直接地採用樹的items來進行命名，葉子節點(leaf tress)來存儲「byte數組」，嵌套的節點就是一個樹的分叉(branching trees)。

比如，需要是對如下對象進行RLP的編碼，該對象中包含一個字元數組的列表、一個單個字元的字元數組、一個空字元數組。

< <[cat],[dog]>, [0xbf], [] >

將該對象展開為樹的結構，就如下圖。其中[0xbf]和[]屬於字元數組。<[cat], [dog]>屬於列表，可以嵌套展開，再根據各個節點，進行編碼。然後，對於不同長度的數組和列表，編碼的方法略有不同，這個也就是Length Prefix相關的內容，和「編碼過程」相關的內容，在第二節進行詳細地說明。

關於為什麼以太坊需要單獨設計一種序列化協議，目前還沒有找到官方的描述。但與其他序列化方法相比，RLP協議具有一些直接的優點，比如：

1）在以太坊中，最小貨幣單位為1 Wei，並且1 ETH = 10^18 Wei，所以在編碼中，需要考慮對很大的整數類型的序列化，在RLP中採用去除前導零(leading zero)的大端big-endian方式，可以有效處理大整數；

2）使用了靈活的長度前綴來表示數據的實際長度，並且使用遞歸的方式能編碼相當大的數據；

3）為了實現在鏈上節點的「共識Consensus」，防止出現數據的不一致，以太坊中並不支持浮點數類型，所以一般的序列化協議也不適用。

編碼的過程就是將嵌套結構(nested sequence)的樹形結構，添加長度前綴(Length Prefix)後，轉化為順序結構(flat sequence)的過程。添加長度前綴的目的，就是在反序列化時，可以根據長度前綴(Length Prefix)，將(flat sequence)重構出樹的結構(nested sequence)。

關於前綴的生成規則，《Ethereum Yellow Paper》[2]給出了非常形式化的數學符號描述，漂亮是非常漂亮，可惜不是人類的語言，非常難於理解和表達。網上大部分文章的寫法也是引用了Yellow Paper中的5個文字形式上的描述，把原文和翻譯一並給出如下：

將上面這個「長度」Length Prefix的編碼規則，通過「決策樹」可以圖形化的表達如下圖。

首先，根據編碼的類型，進行分類，分為「位元組數組」和「列表」兩類；第二，根據不同的長度，編碼的長度前綴不同。若待編碼對象的長度小於56，就是把長度和「前綴字元」進行求和，佔用一個位元組。反之，待編碼對象的長度大於56，其前綴需要多個位元組，第一個位元組，求出「長度」所佔的位元組數，再加上「前綴字元」，比如：長度為56，佔用1位元組。然後對「長度」進行編碼，其實也是一個嵌套的過程。

還是以上文中的例子，該編碼對象，已經完成了「樹的構建」，然後根據「長度前綴」的原則，對樹的各個項目進行長度前綴的計算。

< <[cat],[dog]>, [0xbf], [] >

-對於<[cat],[dog]>屬於嵌套數組，需要對內部各項非常進行長度編碼的計算
  `對於[cat]，屬於字元數組，且長度為3，其對應的長度為0x80+3 = 0x83
  `對於[dog]，屬於字元數組，且長度為3，其對應的長度為0x80+3 = 0x83
  `<[cat],[dog]>整體上，其長度前綴為0xc0 + 2(新增的兩個子項的長度所佔用的位元組)+6(待編碼字元的長度)=0xC8
- 對於[0xbf], 屬於字元數組，且長度為1，其對應的長度為0x80+1 = 0x81
- 對於[dog]，屬於字元數組，且長度為3，其對應的長度為0x80+3 = 0x83
- 對於[]，屬於字元數組，且長度為0，其對應的長度為0x80+0=0x80
總體上，增加的「長度編碼」的位元組數為6，加上原來的長度為10，所以整個對象的長度前綴為0xC0+16d=0xD0。所以最後的編碼結果為：
D0 C8 83636174 83646F67 81B7 83646F67 80

解碼過程將在 《以太坊解讀——Recursive Length Prefix協議圖解(下)》 一文中，給出圖形化的解讀說明。

Ⅱ 以太坊技術系列-以太坊數據結構

本篇文章和大家介紹一下以太坊的數據結構，上篇文章我們提到，以太坊為了實現智能合約這一功能，使用了基於賬戶的模型。我們來看看以太坊中數據結構。

既然是基於賬戶的模型，我們需要通過賬戶地址找到賬戶的狀態。就像通過銀行卡號可以找到你在銀行中的各種信息一樣。最簡單的想法當然是一個簡單的哈希表 key是賬戶地址 value是賬戶狀態。但這里有個問題解決不了。

輕節點如何校驗賬戶合法性？

上篇我們說過，區塊鏈中有2類節點，全節點和輕節點，輕節點只會存儲block header，所以輕節點如何才能校驗賬號是否合法呢？

這個思路和我們平時用的md5校驗一致，我們會對區塊內的信息進行hash運算從而得出區塊內信息唯一確定的值，區塊鏈所有節點中這個值都是相同的。

在這個過程中我們用到了一種數據結構Merkle Tree（哈希樹），我們先看下Merkle Tree（哈希樹）的示意圖。

上篇文章說到區塊鏈中的鏈表(哈希鏈)和我們平時常見鏈表不同的是將指針從地址改為了hash指，這里也一樣，哈希樹和二叉樹的區別有2個

1.將地址改為了哈希值

2.只有葉子節點存儲數據

回到之前的問題輕節點是如何校驗1個賬戶或交易是否是在鏈上的呢？

整個流程如上圖所示

1.輕節點需要判斷1個賬號是否合法

2.輕節點由於只存儲block header，所以拿到1個賬號的時候會向全節點發出請求

3.全節點存儲了所有賬戶狀態，將賬戶路徑中的需要計算用到的hash值返回給輕節點

4.輕節點本地進行計算根hash值，如果計算結果和自己存儲一致則賬戶合法，不一致則不合法。

那以太坊中的賬戶信息的數據結構就是這樣嗎？

直接用這樣的數據結構來存儲賬戶信息會有2個問題

查找困難

生成hash值不確定

第1個問題應該比較容易發現，在這個樹中尋找1個賬號需要的復雜度是O(n),因為沒有任何順序。

第2個問題其實也是因為無序導致的，無序的組合每個節點針對同一批賬戶生成的hash值不一致，這就導致無法達成共識。

既然2個問題都和順序有關，那我們類似二叉排序樹一樣，使用哈希排序樹是不是就可以解決問題了呢？

使用排序樹後會帶來另外1個問題

插入困難

因為要維持樹是有序的，很可能帶來樹結構的很大變動。

以太坊中使用了另外一種數據結構字典樹。和哈希樹不同，字典樹應該是很多地方都有使用。我們簡單來看下字典樹的結構。

字典樹能夠較好地解決哈希樹的2個缺點1.查找困難 2.生成的hash值不確定以及排序二叉樹的1個缺點 插入困難。

但字典樹我們可以看到可能樹的深度可能由於部分元素導致整棵樹深度非常深。

這時我們可以進一步優化，將相同路徑進行壓縮。這就是壓縮字典樹。

將哈希樹和壓縮字典樹結合，就可以得到以太坊存儲賬戶的最終數據結構-MPT。

將壓縮字典樹裡面的指針從地址改為指針，並且將數據存儲在葉子節點中即可。

介紹完狀態樹的數據結構，我們接下來討論1個問題，區塊中存儲的賬戶狀態是什麼樣的范圍。有2種選擇。

只保存當時區塊中產生交易的賬戶狀態。

保存全局所有的賬戶。

我們可以看下這2種方式，無非就是空間和時間的平衡，只保存當前區塊產生的交易意味著是做懶載入(需要的時候才去尋找賬戶)，在區塊鏈中這個代價是非常大的，因為尋找的賬戶之前從未交易過，這樣會遍歷整個區塊鏈。另外一種保存全局的賬戶方式雖然看起來空間消耗較大，但查找快捷，而且空間的問題我們可以通過其他方式優化。所以最終以太坊選擇了第2種每個區塊都報錯全局所有賬戶的方式。

我們來看下以太坊中是如何保存狀態樹的。

可以看到以太坊中雖然每個區塊都保存了全部賬戶，但是會將未發生變化的賬戶狀態指向前1個節點，本身只存儲發生變化的狀態，這樣可以較大程度優化空間佔用。

介紹完以太坊中比較復雜的狀態樹後，我們繼續來看看以太坊中的另外兩棵樹，交易樹和收據樹。

首先介紹一下，為什麼需要交易樹&收據樹。

1.交易樹

雖然以太坊是基於賬戶的模型，但是就像銀行不僅會存儲銀行卡的余額，還會存儲卡中的每筆錢怎麼來的以及怎麼花的。交易樹中就存儲著當前區塊中的包含的所有交易。

2.收據樹

由於智能合約的引入增加了不少復雜性，所以以太坊用收據樹存儲著一些交易操作的額外信息。比如交易過程中執行日誌就包含在收據樹中方便查詢。收據樹和交易樹是一一對應的。每發生一次交易就會有一次收據。

和狀態樹不同交易樹和收據樹只維護當前區塊內發生的交易，因為當時區塊發生交易時不需要再去查找另外1個交易，也就之前需要可能遍歷整個區塊鏈的查找操作了。

由於以太坊中的出塊速度較快，我們進行一些查詢一些符合條件交易的時候會面臨大量數據遍歷困難的問題。收據樹中引入了布隆過濾器可以幫助我們有效緩解這一困難。

布隆過濾器將大集合中每個元素進行hash運算映射到1個較小的集合，這時再來1個元素要判斷是否在大集合的時候，不需要遍歷整個大集合，而是去進行hash運算去小集合中尋找是否存在，如果不存在，肯定不在大集合中，如果存在則不能說明任何問題。

如上圖所示，布隆過濾器只能證明某1個元素不在集合中，不能證明1個元素在結合中。

以太坊中如果我們要在較多區塊中尋找某1個交易，則可以利用布隆過濾器，過濾掉肯定不存在目標交易的區塊，然後進入收據樹內繼續利用布隆過濾器篩選，剩下的才是可能的目標交易的交易，進行一一比對即可。

我們介紹了以太坊的核心數據結構，狀態樹&交易樹&收據樹，他們都是使用相同的數據結構-哈希壓縮字典樹。但狀態樹是維護1顆全局賬戶樹，交易樹和收據樹則是維護本區塊內的交易或收據。

介紹完數據結構後，後面我們會用幾篇文章來介紹以太坊中的一些核心演算法，比如共識機制，挖礦演算法等。

Ⅲ 006：MPT與RLP|《ETH原理與智能合約開發》筆記

待字閨中開發了一門區塊鏈方面的課程：《深入淺出ETH原理與智能合約開發》，馬良老師講授。此文集記錄我的學習筆記。

課程共8節課。其中，前四課講ETH原理，後四課講智能合約。
第二課分為三部分：

這篇文章是第二課第二部分的學習筆記：MPT與RLP。

MPT，Merkle Patricia Tree，結合了Merkle Tree（默克爾樹）和 Patricia Tree（帕特里夏樹）的一種數據結構。
RLP，Recursive Length Prefix，一種編碼方法。

這是兩個非常重要的數據結構，在以太坊的區塊和交易中都有用到。

先分別介紹一下Merkle Tree 和 Patricia Tree。
Merkle Tree 和 Patricia Tree Merkle Tree 和 Patricia Tree
默克爾樹的解釋：對每一個交易計算其散列值（Hash），再對兩個散列值求他們的散列值。如果是奇數個，就把最後一個重復一次。最後得到的一個散列值就是默克爾樹根的值。如圖，交易1、1、2、3的散列值分別是HASH0、HASH1、HASH2、HASH3。HASH0和HASH1結合在一起計算散列值得HASH01，HASH2和HASH3結合在一起計算散列值得HASH23，接下來HASH01、HASH23結合在一起，計算散列值得HASH0123。

採用默克爾樹的好處是可以方便的判斷一個交易是否在區塊中。

Patricia Tree，可稱為壓縮前綴樹。如上圖右半部分。相同的前綴在同一分支中，後面一同的部分分叉出來，如test和toast，都有相同的t，est和oast在兩個分支中。

這個結構的好處是節省空間，因為每一級的鍵值可以是多個字元。

了解了Merkle Tree 和 Patricia Tree後，再來看這兩者混合後的產物——MPT。
這里的原理知識單獨來看不易理解，和具體的例子結合起來才更容易理解，此處先放上課件截圖。在後面的例子中再做說明。
Merkle Patricia Tree 規格 Merkle Patricia Tree 規格
在MPT中，還涉及到三個小的編碼標准。主要規則如圖。下面結合兩個例子說明一下。
三個編碼標准 三個編碼標准
HEX編碼的例子：從ASCII碼表中可以查出，b的十六進制編碼為62，o的十六進制編碼為6F，F在十六進制中就是15的意思。因為這是個葉子節點，最後加上0x10表示結束，也就是16。所以最後的編碼為[6 2 6 15 6 2 16]

HEX-Prefix編碼的例子：[6 2 6 15 6 2 16]，將其最後的0x10去掉，[6 2 6 15 6 2]。前面補一個四元組，其中（倒數）第0位是區分奇偶信息的，[6 2 6 15 6 2]是偶數位，第0位是0；第1位是區分節點類型的，這是葉子節點，第1位是1。所以這個四元組就是0010是2。「如果輸入key的長度是偶數則再添加一個四元組0x0在flag四元組之後。」，所以，最終的前綴是0x20。本例最終的結果，[32 98 111 98]，即[0x20, 0x62, 0x6F, 0x62]

下面是綜合性的例子，通過它可以很方便地理解前面的理論知識。值得多看幾篇，仔細休會。

初始的key-value對為：

其中，<>中的數據為key的16進制編碼。
MPT.jpg MPT.jpg
因為4組數據都有公共的6，所以這個節點的值為6，長度為1，奇數；節點類型：擴展節點；所以前綴就是0001，即1。

這是個擴展節點，它的值是一個Hashvalue，它指向一個分支節點。Hashvalue，具體指的是分支節點RLP編碼的結果的散列值。（RLP見下小節）

分支節點。上面4組數據的第2位是4和8兩種情況。在4的位置上存的是下面的擴展節點的散列值，在8的位置上存的是下面的葉子節點的散列值。

葉子節點。以68開頭的只有一個了。所以這個節點上的四元組就是6f727365了。它是偶數位。前綴是0x20（同前文HEX-Prefix編碼的例子）。這個葉子節點的value值為'stallion'。

擴展節點。在64之後，公共的部分是6f，這個擴展節點的key即為6f，前綴為0000，即00。這個擴展節點的value存放的是一個hashvalue，指向下一個節點，一個分支節點。

分支節點。646f已經表達完，這個節點的value值就是646f對應的值，'verb'。

除此之外，646f之後就是6，所以在這個分支節點的6位置上有一個散列值，指向下一個節點。

擴展節點。在646f6之後，公共的部分是7，其長度為1，奇數。所以前綴為0001。這個節點的value是一個散列值，指向下一個節點。

分支節點。646f67已經表達完，這個節點的value值就是646f67對應的值，'puppy'。

除此之外，646f67之後就是6，所以在這個分支節點的6位置上有一個散列值，指向下一個節點。

葉子節點。key為5，value為'coin'。長度為1，奇數，前綴0011，即3。

整個分析過程結束。可結合上圖和前文的理論多加復習。

這小節也是理論性較強，通過例子可以方便理解。先放上課件，再根據我的理解舉更多的例子。同樣，學習方法也是理論和例子配合學習。其中，list的例子在下篇文章的上機實驗部分再列舉。 RLP的編碼標准 RLP的編碼標准 再舉幾個例子 再舉幾個例子

Ⅳ 以太坊架構是怎麼樣的

以太坊最上層的是DApp。它通過Web3.js和智能合約層進行交換。所有的智能合約都運行在EVM（以太坊虛擬機）上，並會用到RPC的調用。在EVM和RPC下面是以太坊的四大核心內容，包括：blockChain, 共識演算法，挖礦以及網路層。除了DApp外，其他的所有部分都在以太坊的客戶端里，目前最流行的以太坊客戶端就是Geth（Go-Ethereum）