6.5 Merkle Patricia樹

Merkle Patricia樹（MPT）是一種經過改良的、融合了默克爾樹和前綴樹兩種樹結構優點的數據結構，是以太坊中用來組織管理賬戶數據、生成交易集合哈希的重要數據結構。在以太坊每個區塊頭中，存有三個根值：StateRoot（用于存儲所有賬戶狀態）、TransactionsRoot（用于存儲區塊中的交易數據）、和ReceiptsRoot（用于存儲區塊中的接收賬戶數據），它們都使用了MPT數據結構。所有在以太坊中使用的默克爾樹實際上都是MPT。

MPT是默克爾樹和前綴樹的結合，其結構具有以下特性：

高安全性：每個唯一鍵值對唯一映射到根的哈希值。難以破解（除非攻擊者有2¹²⁸的算力）。

易修改性：增、刪、改鍵值對的時間復雜度是對數級別。

MPT在以太坊數據結構中發揮的作用：

存儲任意長度的key-value鍵值對數據。

提供了一種快速計算所維護數據集哈希標識的機制。

提供了快速狀態回滾的機制。

提供了一種稱為默克爾證明的證明方法，進行輕節點的擴展，實現簡單支付驗證。

6.5.1 快速狀態回滾

在公鏈的環境下，采用POW算法可能會造成分叉而導致區塊鏈狀態進行回滾。在以太坊中，由于出塊時間短，這種分叉的概率很大，區塊鏈狀態回滾的現象很頻繁。所謂的狀態回滾指的是：

1）區塊鏈內容發生了重組織，鏈頭發生切換。

2）區塊鏈的全局狀態（賬戶信息）需要進行回滾，即對之前的操作進行撤銷。

MPT提供了一種機制，可以在區塊發生碰撞時零延遲地完成全局狀態的回滾。這種優勢的代價就是需要浪費存儲空間去冗余地存儲每個節點的歷史狀態。

每個節點在數據庫中的存儲都是值驅動的。當一個節點的內容發生了變化，其哈希相應改變，而MPT將哈希作為數據庫中的索引，也就實現了對于每一個值在數據庫中都有一條確定的記錄。MPT是根據節點哈希來關聯父子節點的，因此，每當一個節點的內容發生變化，最終對于父節點來說，改變的只是一個哈希索引值；父節點的內容也由此改變，產生了一個新的父節點，遞歸地將這種影響傳遞到根節點。最終，一次改變對應創建了一條從被改節點到根節點的新路徑，而舊節點依然可以根據舊根節點通過舊路徑訪問得到。

6.5.2 簡單支付驗證（SPV）

簡單支付驗證，即Simple Payment Verification，簡稱SPV。SPV的目標是不運行全節點也可以驗證支付（交易的存在性檢查和交易是否重號的檢查）。

SPV充分利用了區塊的結構信息及默克爾樹的強大搜索能力，從而能實現對交易信息的快速定位。SPV節點是一種輕節點，節點只需要維護鏈中所有的區塊頭信息（一個區塊頭的大小通常為幾十個字節，普通的移動終端設備完全能夠承受），在驗證交易是否存在時不保存所有交易，也不會下載整個區塊，只是保存區塊頭。它使用認證路徑或者默克爾路徑來驗證交易存在于區塊中，而不必下載區塊中所有的交易。

默克爾證明，即一個輕節點向一個全節點發起一次證明請求，詢問全節點在完整的默克爾樹中是否存在一個指定的節點；全節點向輕節點返回一個默克爾證明路徑，由輕節點進行計算，驗證其存在性。

SPV強調的是驗證支付，不是驗證交易。這兩個概念是不同的。驗證支付比較簡單，只需要判斷用于支付的那筆交易是否被驗證過，以及得到網絡多少次確認（即有多少個區塊疊加）。而驗證交易則復雜得多，需要驗證賬戶余額是否足夠支出、是否存在雙重支付、交易腳本是否通過等問題，一般這個操作是由全節點的礦工來完成。