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

什么是Merkle Tree

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

Merkle Tree有哪些用途

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

Bitcoin和Etheruem

Git和Mercurial版本控制

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

P2P網(wǎng)絡(luò)(BT)

Certificate Transparency framework

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

NoSQL：Apache Cassandra, Riak, and Dynamo

Trusted Platform(TPM)

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

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

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

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

Second Preimage攻擊

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

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

Merkle Proof

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

Bitcoin中的Merkle證明

Merkle proofs最早由Satoshi Nakamoto在2009年提出并應(yīng)用在Bitcoin中，Bitcoin區(qū)塊鏈?zhǔn)褂肕erkle proofs將交易存儲(chǔ)在每個(gè)塊中。

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

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

前一區(qū)塊頭的Hash

時(shí)間戳

挖礦難度

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

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

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

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

Ethereum中的Merkle證明

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

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

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

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

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

我賬戶目前的余額？

當(dāng)前帳戶是否存在？

假設(shè)在合約中運(yùn)行此交易將輸出什么結(jié)果？

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

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

Particia Trees

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

對于事務(wù)樹，使用二叉Merkle樹來是非常好的數(shù)據(jù)結(jié)構(gòu)，因?yàn)闃浔灰坏┍粍?chuàng)建一次會(huì)永久存在，所以編輯樹所花費(fèi)的時(shí)間已經(jīng)不重要了。

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

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

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

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

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

總結(jié)

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

References

互動(dòng)區(qū)

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

*「啟迪云技術(shù)?！姑恐苡蓡⒌显蒲邪l(fā)部提供技術(shù)干貨，敬請期待。如需轉(zhuǎn)載請聯(lián)系小編。