Merkle Tree是區(qū)塊鏈中一個基本組成部分。雖然理論上也可以沒有Merkle Tree來構建區(qū)域鏈， 但是需要直接創(chuàng)建包含每筆交易的巨型數(shù)據(jù)塊頭，從長遠考慮，這樣做會帶來巨大的擴展性挑戰(zhàn)，除了超級計算機，最后所有其它人都無法使用區(qū)塊鏈。有了Merkle Tree，區(qū)塊鏈才可以在所有PC和筆記本，智能手機甚至物聯(lián)網(wǎng)設備上運行。本文主要針對區(qū)塊鏈中數(shù)據(jù)完整性和交易真實性驗證方式進行簡要介紹和記錄，以幫助自己和區(qū)塊鏈入門者快速了解區(qū)塊鏈中這些核心概念和原理。

什么是Merkle Tree

Merkle Tree也稱為Hash Tree，由Ralph Merkle于1979年提出并命名，是基于Hash的數(shù)據(jù)結構，它是一種樹結構，每個葉節(jié)點是數(shù)據(jù)塊的Hash，每個非葉節(jié)點是其子節(jié)點的Hash。Merkle Tree可以高效和安全地實現(xiàn)較大的數(shù)據(jù)內(nèi)容驗證，它是Hash List和Hash Chain的泛化。Merkle Tree通常實現(xiàn)為二叉樹，如下圖所示。但Merkle Tree也可以實現(xiàn)節(jié)點包含多個子節(jié)點的。

Merkle Tree有哪些用途

Mekle Tree被用于分布式系統(tǒng)中，可用于驗證計算機之間存儲，處理和傳輸?shù)娜魏晤愋蛿?shù)據(jù)，確保在P2P網(wǎng)絡中收到的數(shù)據(jù)塊沒有被破壞或者篡改，甚至有沒有發(fā)送假數(shù)據(jù)塊。Merkle tree已經(jīng)被用于以下場景：

Bitcoin和Etheruem

Git和Mercurial版本控制

IPFS，Btrfs，ZFS文件系統(tǒng)

P2P網(wǎng)絡(BT)

Certificate Transparency framework

數(shù)字簽名：Merkle Signature Scheme

NoSQL：Apache Cassandra, Riak, and Dynamo

Trusted Platform(TPM)

為什么不直接將數(shù)據(jù)塊拼成一個大塊在計算Hash

Hash Function：實現(xiàn)數(shù)據(jù)完整性驗證最簡單的方法是對整個數(shù)據(jù)進行Hash，通常對于提供下載的文件，發(fā)布者會同時分發(fā)一個checksum值，用戶下載完成后對文件用同樣的Hash算法計算checksum，如果用戶計處的值與發(fā)布者值不同，表明文件已經(jīng)損壞或者被篡改過，Hash算法保證了數(shù)據(jù)中任意bit被修改都會造成整個Hash值的改變。這里不會詳細講解Hash算法，常用的Hash算法有md5，sha1，sha2，通常使用sha2進行Hash運算，如果權驗證數(shù)據(jù)是否損壞，可以使用安全性較低的校驗和算法(CRC)。

Hash List：p2p被設計成一個分布式網(wǎng)絡傳輸系統(tǒng)，在使用p2p網(wǎng)絡傳輸文件時，文件被分割成大量小數(shù)據(jù)塊，客戶端會同時從其它p2p客戶機下載數(shù)據(jù)塊，由于網(wǎng)絡中不穩(wěn)定性和不可信的存在，需要對每個數(shù)據(jù)塊進行完整性驗證，當其中某塊數(shù)據(jù)損壞時，只重傳某塊數(shù)據(jù)而不用重新下載整個文件。為了完成數(shù)據(jù)塊的驗證，在文件下載前先獲取所有數(shù)據(jù)塊的Hash列表，再將所有Hash列表進行Hash得到一個根Hash，將客戶端計算的根Hash與可信根Hash比較來驗證Hash列表的完整性。

Merkle Tree：Hash List可認為是一種樹高為2的N叉Merkle Tree，實現(xiàn)原理與Hash List類似，將數(shù)據(jù)分割成小的Block，并計算數(shù)據(jù)塊的Hash，將相鄰兩個Hash合并后再計算出父Hash，Hash(Hash(DataBlock1) | Hash(DataBlock2))，再將新的相鄰的兩個父Hash值進行Hash，生成更上層的Hash，最后會匯聚到樹的根節(jié)點，稱為Merkle Root。但是Merkle Tree最重要的好處是可以單獨取出Hash樹的一個分支對數(shù)據(jù)進行驗證，而不用計算整個Merkle Tree。

Second Preimage攻擊

Merkle Tree的根并不表示樹的深度，這將導致second-preimage攻擊，攻擊者可以創(chuàng)建出一個具有相同Merkle Root的的新Merkle Tree分支。一個簡單的解決方法在Certificate Transparency中定義：

計算葉節(jié)點Hash時，在數(shù)據(jù)前加0x00，在計算內(nèi)部節(jié)點Hash時，在數(shù)據(jù)前加0x01，限制Hash樹的大小是一些正式安全驗證的先決條件。一些實現(xiàn)在Hash前使加樹深前綴來限制樹的深度，在獲取Hash鏈時，每一步都要減少前綴并且到達葉節(jié)點時仍為正才被認為有效。

Merkle Proof

Merkle Proof包括一個數(shù)據(jù)塊，Merkle Root，以及從數(shù)據(jù)塊到根路徑上的所有Hash組成的'分支'。閱讀證明者可以驗證給定數(shù)據(jù)塊的Hash(至少對于當前分支)以及到Root路徑上的所有節(jié)點的Hash的一致性，并最終驗證給定的數(shù)據(jù)塊是否真正在樹中的節(jié)點上。

Bitcoin中的Merkle證明

Merkle proofs最早由Satoshi Nakamoto在2009年提出并應用在Bitcoin中，Bitcoin區(qū)塊鏈使用Merkle proofs將交易存儲在每個塊中。

Picture From: https://blog./wp-content/uploads/2015/11/mining.jpg

這樣做的好處正如中本聰描述的'simplified payment verification'：“l(fā)ight client(輕客戶端)”只下載鏈中區(qū)塊頭的80byte數(shù)據(jù)塊，而不是下載所有交易和所有區(qū)塊，每個塊僅包含以下五個元素：

前一區(qū)塊頭的Hash

時間戳

挖礦難度

隨機數(shù)工作量證明

包含當前區(qū)塊交易的Merkle tree的Root Hash

如果'輕客戶端'想要確認交易的狀態(tài)，只需簡單發(fā)起一個Merkle proof證明這個特定交易在Merkle tree上，并且樹的Merkle root在主鏈的區(qū)塊頭中。

雖然這樣做可以讓區(qū)塊鏈持續(xù)很久，但是Bitcoin '輕客戶端'也有其局限性。其中一個限制是，雖然可以證明包含的交易狀態(tài)，但是無法證明當前的狀態(tài)(例如：持有的數(shù)字資產(chǎn)，名稱注冊，金融合約的狀態(tài)等)。用戶當前有多少Bitcoin？Bitcoin輕客戶端使用一個協(xié)議，該協(xié)議涉及查詢多個節(jié)點，并確信其中至少有一個節(jié)點會返回通知，包含你的地址支出的任何特定交易，雖然可以滿足Bitcoin應用，但對于更加復雜的應用還遠遠不夠。一筆交易影響的確切性取決于前幾筆交易，而前一筆交易又依賴更前面的交易，最終不得不驗證整條鏈上的每一筆交易。為了解決這個問題，Ethereum使用更先進的Merkle tree概念。

Ethereum中的Merkle證明

Ethereum區(qū)塊頭不是包含一棵Merkle tree，而是包含三顆樹代表三種不同類型：交易、收據(jù)和狀態(tài)。

Picture From: https://blog./wp-content/uploads/2015/11/ethblockchain_full.png

這允許Ethereum使用更加先進的輕客戶端協(xié)議讓輕客戶端很容易地實現(xiàn)以下不同查詢類型的驗證：

當前交易是否包含在特定區(qū)塊中？

告訴我過去30天內(nèi)該地址發(fā)出X類事件(例如：一個達到目標的眾籌合約)的所有情況。

我賬戶目前的余額？

當前帳戶是否存在？

假設在合約中運行此交易將輸出什么結果？

其中，第一條由事務樹處理；第三條和第四條由狀態(tài)樹處理，第二條由收據(jù)樹處理。前四條計算相對簡單；服務器只需簡單找到對象，獲取Merkle分支(從對象到Merkle root的Hash列表）并返回給輕客戶端。第五條也由狀態(tài)樹處理，但計算方式更加復雜。我們需要構造一個所謂的Merkle狀態(tài)轉換證明(Merkle state transition proof)。從本質(zhì)上講，狀態(tài)轉換證明中聲明'如果你在具有根S的狀態(tài)樹上運行交易T，結果將是具有根S‘，日志L和輸出為O的狀態(tài)'（由于每一筆交易都是一個函數(shù)調(diào)用，所以“輸出”只作為Ethereum中的一個概念存在，理論上它并不是必須的）。

為了計算Proof，服務器在本地創(chuàng)建一個假的區(qū)塊，將狀態(tài)設置為S，并在應用時充當輕客戶端。也就是說，如果應用交易的過程要求客戶端確定帳戶余額，則輕客戶端會發(fā)起一個余額查詢請求。如果輕客戶端需要檢查特定合約中存儲的特定條目，也同樣發(fā)起查詢請求。服務端正確地'responds'自己所有查詢，但跟蹤它發(fā)回的所有數(shù)據(jù)。然后，服務端將所有這些作為證明的請求的合并數(shù)據(jù)發(fā)送給客戶端。最后客戶端執(zhí)行完全相同的過程，但使用服務端提供的證明做為數(shù)據(jù)庫，如果客戶端計算的結果與服務端聲明的結果一致，則客戶端接受此證明。

Particia Trees

最簡單的Merkle tree是一棵二叉樹。然而，Ethereum中使用的樹更復雜- 稱為'Merkle Patricia tree'，可以查詢Ethereum官方相關文檔。

對于事務樹，使用二叉Merkle樹來是非常好的數(shù)據(jù)結構，因為樹被一旦被創(chuàng)建一次會永久存在，所以編輯樹所花費的時間已經(jīng)不重要了。

然而，對于狀態(tài)樹，情況會更復雜。Ethereum中狀態(tài)基本上是由鍵值對組成，其中鍵是地址，值是帳戶聲明，對于每個帳戶列出每個帳戶余額，隨機數(shù)據(jù)，代碼和存儲(存儲本身也是一棵樹)。

同時，與事務歷史不同，狀態(tài)需要頻繁被更新。賬戶余額和隨機數(shù)也經(jīng)常變化，新帳戶頻繁創(chuàng)建，存儲的key也經(jīng)常會增刪改操作。因此，在做增刪改操作后，我們期望一種快速計算新kerkle樹根的數(shù)據(jù)結構，而不是重新計算整棵樹。這種結構也要有兩個理想的次要屬性：

樹的深度是有限的，即使攻擊者故意制作交易以使樹盡可能深。否則，攻擊者可以通過操縱樹的深度來執(zhí)行拒絕服務攻擊，使得每個更新變得非常緩慢。

樹的根只取決于數(shù)據(jù)，而不取決于更新的順序。以不同的順序進行更新甚至重新計算樹不應該更改根。

簡單來說，Patricia tree可能是我們實現(xiàn)所有這些屬性最接近的樹。它的工作原理最簡單的解釋是value存儲在key中，key被編碼到搜索樹的路徑中。每個節(jié)點有16個子節(jié)點，因此路徑由十六進制編碼決定：例如，key為dog的十六進制編碼是6 4 6 15 6 7，所以從根開始，下到第6個子節(jié)點，然后到第4個，再進行其余四步，直到最后葉節(jié)點。在實踐中，當樹比較稀疏時，可以根據(jù)情況進行一些額外優(yōu)化，但是要遵循這些基本原則。

總結

Merkle tree使用基于Hash的密碼學來確保數(shù)據(jù)傳輸?shù)耐暾?，已?jīng)用在許多分布式文件系統(tǒng)，P2P網(wǎng)絡，證書驗證，可信計算，NoSQL和區(qū)塊鏈等方面。Merkle tree中允許取出樹中一個分支來驗證數(shù)據(jù)，而避免計算整棵Hash樹，除了加帶檢索效率，也確保了使用Merkle tree的系統(tǒng)的可持續(xù)性。本文主要簡介了Merkle Tree基本原理和以及在區(qū)域鏈中的使用，對于Merkle tree更深層次的理解，可以閱讀一些開源代碼(如Ethereum和Hyperledger等)的實現(xiàn)。

References

互動區(qū)

* 你對以上內(nèi)容有什么看法？你最關注云計算哪個趨勢？如果你還有想了解的技術話題，歡迎留言分享。

*「啟迪云技術棧」每周由啟迪云研發(fā)部提供技術干貨，敬請期待。如需轉載請聯(lián)系小編。