# Merkle Patricia Tree
[TOC]
###### tags: `blockchain` `Ethereum` `Data Structure`

# Intro
- 是一種經過改良的、融合了Merkle tree (hash tree)和Radix tree 的優點的數據結構
- 可以理解為把帳本分割成無數個小的資料塊，每個資料塊像是一棵樹中的無數葉片，而我們把每兩個相鄰的葉片合併成一個字串，並算出該字串的 Hash 值。經過無數次後，會得到一個包含了所有區塊資料的 Hash 值，稱為「Merkle Root」

# Radix trie 前綴樹
- 是一種有序樹，用於保存關聯數組
- 與Binary Search Tree 不同，每個節點數據所攜帶的 key 不會存儲在 Trie 的節點中，而是通過該節點在整個樹形結構里位置來體現

## 優勢
- 花費時間較短
- 相比於 Hash list，使用前綴樹來進行查詢擁有共同前綴key的數據時十分高效
- 例如在字典中查找前綴為pre的單詞，對於哈希表來說，需要遍歷整個表 => O(n)
- 然而對於前綴樹來說，只需要在樹中找到前綴為pre的節點，且遍歷以這個節點為根節點的子樹即可。
- 但是對於最差的情況（前綴為空串),仍然需要遍歷整棵樹 => O(n)
- 相比於哈希表，在前綴樹不會存在哈希沖突的問題。
## 劣勢
- 直接查找效率低下
- 前綴樹的查找效率是O(m)，m為所查找節點的key長度
- 而哈希表的查找效率為O(1)。且一次查找會有m次I/O
- 可能會造成空間浪費
- 如果有一個字元串很長，且跟其他字元串沒有公共前綴，就會形成這樣的一棵極其不平衡的樹

# Patricia trie
- 對於 Radix tree 的每個節點，如果該節點是唯一的兒子的話，就和父節點合並

# Merkle tree
- 也被稱作Hash Tree，存儲hash值的一棵樹
- Merkle tree葉子節點的value是數據內容，或者是數據的哈希值，再將相鄰兩個節點的哈希值合並成一個字元串，然後計算這個字元串的哈希，得到的就是這兩個節點的父節點的哈希值
:::danger
Q. 區塊鏈P2P網路中，如果需要傳輸的數據很大，就需要同時從多個機器上下載數據，而且很可能有些機器是不穩定(可能下載速度很慢)或者不可信的(需要重新下載)，如何驗證之？
:::

:::success
為了校驗數據的完整性，更好的辦法是把大的文件分割成小的數據塊。
如果小塊數據在傳輸過程中損壞了，那麼只要重新下載這一塊數據就行了，不用重新下載整個文件。
:::

:::danger
怎麼確定小的數據塊沒有損壞？
:::

:::success
只需要為每個數據塊做Hash，因此，在下載到真正數據之前，我們會先下載一個Hash列表
:::

:::danger
怎麼確定這個Hash列表正確的？
:::

:::success
把每個小塊數據的Hash值拼到一起，然後對這個長字元串在作一次Hash運算，這樣就得到Hash列表的根Hash(Top Hash or Root Hash)。
下載數據的時候，首先從可信的數據源得到正確的根Hash，就可以用它來校驗Hash列表了，然後通過校驗後的Hash列表校驗數據塊。
若兩棵樹的根哈希一致，則這兩棵樹的結構、節點的內容必然相同
:::

## 優勢
- 快速重哈希
- 當樹節點內容發生變化時，能夠在前一次哈希計算的基礎上，僅僅將被修改的樹節點進行哈希重計算，便能得到一個新的根哈希用來代表整棵樹的狀態

## 應用
- 採用Merkle tree，可以在公鏈環境下擴展一種“輕節點”
- 輕節點的特點是對於每個區塊，僅僅需要存儲約80個位元組大小的區塊頭數據，而不存儲交易列表，回執列表等數據。
- 透過輕節點，可以實現在非信任的公鏈環境中驗證某一筆交易是否被收錄在區塊鏈賬本的功能，能讓區塊鏈能夠運行在個人PC，智能手機等擁有小存儲容量的終端上
- 對於輕節點來說，驗證一條交易只需要驗證包含該交易的路徑即可，並不需要把所有交易的Hash全部重新算一遍。

# MPT（Merkle Patricia Tree）
- 只需要保存一個root(hash)，即可還原出完整的樹結構
- A Patricia Merkle Trie provides a cryptographically authenticated data structure that can be used to store all (key, value) bindings.
## MPT 的 4種節點
- 葉子節點（leaf）
- 表示為 [key,value] 的一個鍵值對。
- 擴展節點（extension）
- 也是[key，value]的一個鍵值對
- 這裡的value是其他節點的hash值，通過hash鏈接到其他節點
- 分支節點（branch）
- 因為MPT樹中的key被編碼成一種特殊的16進制的表示，再加上最後的value，所以分支節點是一個長度為17的list
- 如果有一個[key,value]對在這個分支節點終止，最後一個元素代表一個值，即分支節點既可以搜索路徑的終止也可以是路徑的中間節點
- 分支節點的父親必然是 extension node
- 擴展節點合併相同的前綴，故該節點減少了層高和存儲空間
- 空節點
- 用null表示

# Reference
- [以太坊MPT数据结构](https://it007.blog.csdn.net/article/details/86551694?spm=1001.2101.3001.6650.19&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-19-86551694-blog-79992072.pc_relevant_multi_platform_whitelistv1_exp2&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-19-86551694-blog-79992072.pc_relevant_multi_platform_whitelistv1_exp2&utm_relevant_index=25)