mpt以太坊

『壹』 以太坊技術系列-以太坊數據結構

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

既然是基於賬戶的模型，我們需要通過賬戶地址找到賬戶的狀態。就像通過銀行卡號可以找到你在銀行中的各種信息一樣。最簡單的想法當然是一個簡單的哈希表 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顆全局賬戶樹，交易樹和收據樹則是維護本區塊內的交易或收據。

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