Merkle Tree是區塊鏈中一個基本組成部分。雖然理論上也可以沒有Merkle Tree來構建區域鏈， 但是需要直接創建包含每筆交易的巨型數據塊頭，從長遠考慮，這樣做會帶來巨大的擴展性挑戰，除了超級計算機，最後所有其它人都無法使用區塊鏈。有了Merkle Tree，區塊鏈才可以在所有PC和筆記本，智能手機甚至物聯網設備上運行。本文主要針對區塊鏈中數據完整性和交易真實性驗證方式進行簡要介紹和記錄，以幫助自己和區塊鏈入門者快速瞭解區塊鏈中這些核心概念和原理。
什麼是Merkle Tree
Merkle Tree也稱為Hash Tree，由Ralph Merkle於1979年提出並命名，是基於Hash的數據結構，它是一種樹結構，每個葉節點是數據塊的Hash，每個非葉節點是其子節點的Hash。Merkle Tree可以高效和安全地實現較大的數據內容驗證，它是Hash List和Hash Chain的泛化。Merkle Tree通常實現為二叉樹，如下圖所示。但Merkle Tree也可以實現節點包含多個子節點的。
Merkle Tree有哪些用途
Mekle Tree被用於分佈式系統中，可用於驗證計算機之間存儲，處理和傳輸的任何類型數據，確保在P2P網絡中收到的數據塊沒有被破壞或者篡改，甚至有沒有發送假數據塊。Merkle tree已經被用於以下場景：
- Bitcoin和Etheruem
- Git和Mercurial版本控制
- IPFS，Btrfs，ZFS文件系統
- P2P網絡(BT)
- Certificate Transparency framework
- 數字簽名：Merkle Signature Scheme
- NoSQL：Apache Cassandra, Riak, and Dynamo
- Trusted Platform(TPM)
為什麼不直接將數據塊拼成一個大塊在計算Hash
Hash Function：實現數據完整性驗證最簡單的方法是對整個數據進行Hash，通常對於提供下載的文件，發佈者會同時分發一個checksum值，用戶下載完成後對文件用同樣的Hash算法計算checksum，如果用戶計處的值與發佈者值不同，表明文件已經損壞或者被篡改過，Hash算法保證了數據中任意bit被修改都會造成整個Hash值的改變。這裡不會詳細講解Hash算法，常用的Hash算法有md5，sha1，sha2，通常使用sha2進行Hash運算，如果權驗證數據是否損壞，可以使用安全性較低的校驗和算法(CRC)。
Hash List：p2p被設計成一個分佈式網絡傳輸系統，在使用p2p網絡傳輸文件時，文件被分割成大量小數據塊，客戶端會同時從其它p2p客戶機下載數據塊，由於網絡中不穩定性和不可信的存在，需要對每個數據塊進行完整性驗證，當其中某塊數據損壞時，只重傳某塊數據而不用重新下載整個文件。為了完成數據塊的驗證，在文件下載前先獲取所有數據塊的Hash列表，再將所有Hash列表進行Hash得到一個根Hash，將客戶端計算的根Hash與可信根Hash比較來驗證Hash列表的完整性。
Merkle Tree：Hash List可認為是一種樹高為2的N叉Merkle Tree，實現原理與Hash List類似，將數據分割成小的Block，並計算數據塊的Hash，將相鄰兩個Hash合併後再計算出父Hash，Hash(Hash(DataBlock1) | Hash(DataBlock2))，再將新的相鄰的兩個父Hash值進行Hash，生成更上層的Hash，最後會匯聚到樹的根節點，稱為Merkle Root。但是Merkle Tree最重要的好處是可以單獨取出Hash樹的一個分支對數據進行驗證，而不用計算整個Merkle Tree。
Second Preimage攻擊
Merkle Tree的根並不表示樹的深度，這將導致second-preimage攻擊，攻擊者可以創建出一個具有相同Merkle Root的的新Merkle Tree分支。一個簡單的解決方法在Certificate Transparency中定義：
計算葉節點Hash時，在數據前加0x00，在計算內部節點Hash時，在數據前加0x01，限制Hash樹的大小是一些正式安全驗證的先決條件。一些實現在Hash前使加樹深前綴來限制樹的深度，在獲取Hash鏈時，每一步都要減少前綴並且到達葉節點時仍為正才被認為有效。
Merkle Proof
Merkle Proof包括一個數據塊，Merkle Root，以及從數據塊到根路徑上的所有Hash組成的"分支"。閱讀證明者可以驗證給定數據塊的Hash(至少對於當前分支)以及到Root路徑上的所有節點的Hash的一致性，並最終驗證給定的數據塊是否真正在樹中的節點上。
Bitcoin中的Merkle證明
Merkle proofs最早由Satoshi Nakamoto在2009年提出並應用在Bitcoin中，Bitcoin區塊鏈使用Merkle proofs將交易存儲在每個塊中。
Picture From: https://blog.ethereum.org/wp-content/uploads/2015/11/mining.jpg
這樣做的好處正如中本聰描述的"simplified payment verification"：“light client(輕客戶端)”只下載鏈中區塊頭的80byte數據塊，而不是下載所有交易和所有區塊，每個塊僅包含以下五個元素：
- 前一區塊頭的Hash
- 時間戳
- 挖礦難度
- 隨機數工作量證明
- 包含當前區塊交易的Merkle tree的Root Hash
如果"輕客戶端"想要確認交易的狀態，只需簡單發起一個Merkle proof證明這個特定交易在Merkle tree上，並且樹的Merkle root在主鏈的區塊頭中。
雖然這樣做可以讓區塊鏈持續很久，但是Bitcoin "輕客戶端"也有其侷限性。其中一個限制是，雖然可以證明包含的交易狀態，但是無法證明當前的狀態(例如：持有的數字資產，名稱註冊，金融合約的狀態等)。用戶當前有多少Bitcoin？Bitcoin輕客戶端使用一個協議，該協議涉及查詢多個節點，並確信其中至少有一個節點會返回通知，包含你的地址支出的任何特定交易，雖然可以滿足Bitcoin應用，但對於更加複雜的應用還遠遠不夠。一筆交易影響的確切性取決於前幾筆交易，而前一筆交易又依賴更前面的交易，最終不得不驗證整條鏈上的每一筆交易。為了解決這個問題，Ethereum使用更先進的Merkle tree概念。
Ethereum中的Merkle證明
Ethereum區塊頭不是包含一棵Merkle tree，而是包含三顆樹代表三種不同類型：交易、收據和狀態。
Picture From: https://blog.ethereum.org/wp-content/uploads/2015/11/ethblockchain_full.png
這允許Ethereum使用更加先進的輕客戶端協議讓輕客戶端很容易地實現以下不同查詢類型的驗證：
- 當前交易是否包含在特定區塊中？
- 告訴我過去30天內該地址發出X類事件(例如：一個達到目標的眾籌合約)的所有情況。
- 我賬戶目前的餘額？
- 當前帳戶是否存在？
- 假設在合約中運行此交易將輸出什麼結果？
其中，第一條由事務樹處理；第三條和第四條由狀態樹處理，第二條由收據樹處理。前四條計算相對簡單；服務器只需簡單找到對象，獲取Merkle分支(從對象到Merkle root的Hash列表）並返回給輕客戶端。第五條也由狀態樹處理，但計算方式更加複雜。我們需要構造一個所謂的Merkle狀態轉換證明(Merkle state transition proof)。從本質上講，狀態轉換證明中聲明"如果你在具有根S的狀態樹上運行交易T，結果將是具有根S‘，日誌L和輸出為O的狀態"（由於每一筆交易都是一個函數調用，所以“輸出”只作為Ethereum中的一個概念存在，理論上它並不是必須的）。
為了計算Proof，服務器在本地創建一個假的區塊，將狀態設置為S，並在應用時充當輕客戶端。也就是說，如果應用交易的過程要求客戶端確定帳戶餘額，則輕客戶端會發起一個餘額查詢請求。如果輕客戶端需要檢查特定合約中存儲的特定條目，也同樣發起查詢請求。服務端正確地"responds"自己所有查詢，但跟蹤它發回的所有數據。然後，服務端將所有這些作為證明的請求的合併數據發送給客戶端。最後客戶端執行完全相同的過程，但使用服務端提供的證明做為數據庫，如果客戶端計算的結果與服務端聲明的結果一致，則客戶端接受此證明。
Particia Trees
最簡單的Merkle tree是一棵二叉樹。然而，Ethereum中使用的樹更復雜- 稱為"Merkle Patricia tree"，可以查詢Ethereum官方相關文檔。
對於事務樹，使用二叉Merkle樹來是非常好的數據結構，因為樹被一旦被創建一次會永久存在，所以編輯樹所花費的時間已經不重要了。
然而，對於狀態樹，情況會更復雜。Ethereum中狀態基本上是由鍵值對組成，其中鍵是地址，值是帳戶聲明，對於每個帳戶列出每個帳戶餘額，隨機數據，代碼和存儲(存儲本身也是一棵樹)。
同時，與事務歷史不同，狀態需要頻繁被更新。賬戶餘額和隨機數也經常變化，新帳戶頻繁創建，存儲的key也經常會增刪改操作。因此，在做增刪改操作後，我們期望一種快速計算新kerkle樹根的數據結構，而不是重新計算整棵樹。這種結構也要有兩個理想的次要屬性：
- 樹的深度是有限的，即使攻擊者故意製作交易以使樹儘可能深。否則，攻擊者可以通過操縱樹的深度來執行拒絕服務攻擊，使得每個更新變得非常緩慢。
- 樹的根只取決於數據，而不取決於更新的順序。以不同的順序進行更新甚至重新計算樹不應該更改根。
簡單來說，Patricia tree可能是我們實現所有這些屬性最接近的樹。它的工作原理最簡單的解釋是value存儲在key中，key被編碼到搜索樹的路徑中。每個節點有16個子節點，因此路徑由十六進制編碼決定：例如，key為dog的十六進制編碼是6 4 6 15 6 7，所以從根開始，下到第6個子節點，然後到第4個，再進行其餘四步，直到最後葉節點。在實踐中，當樹比較稀疏時，可以根據情況進行一些額外優化，但是要遵循這些基本原則。
總結
Merkle tree使用基於Hash的密碼學來確保數據傳輸的完整性，已經用在許多分佈式文件系統，P2P網絡，證書驗證，可信計算，NoSQL和區塊鏈等方面。Merkle tree中允許取出樹中一個分支來驗證數據，而避免計算整棵Hash樹，除了加帶檢索效率，也確保了使用Merkle tree的系統的可持續性。本文主要簡介了Merkle Tree基本原理和以及在區域鏈中的使用，對於Merkle tree更深層次的理解，可以閱讀一些開源代碼(如Ethereum和Hyperledger等)的實現。
References
https://en.wikipedia.org/wiki/Merkle_treehttps://blog.ethereum.org/2015/11/15/merkling-in-ethereum/閱讀更多 啟迪雲Tuscloud 的文章
