Merkle Tree 和 Merkle Root 介紹
目錄
什麼是 Merkle Tree?
Merkle Tree 如何運作?
為什麼在比特幣中使用 Merkle Root?
總結
Merkle Tree 和 Merkle Root 介紹
首頁文章
Merkle Tree 和 Merkle Root 介紹

Merkle Tree 和 Merkle Root 介紹

進階
發佈時間 Jul 6, 2020更新時間 Feb 3, 2022
7m

目錄


什麼是 Merkle Tree?

Merkle Tree 的概念由 Ralph Merkle 在 80 年代初提出,他是一位以公鑰加密學工作而聞名的電腦科學家。
Merkle Tree 是一種用於有效驗證集合中資料完整性的結構。這在點對點網路環境中尤其有趣,參與者需要在此共用並獨立驗證資訊。
雜湊函數是 Merkle Tree 結構的核心,因此,我們建議您查閱什麼是雜湊?後再繼續。


Merkle Tree 如何運作?

假設您要下載一個大型檔案。對於開源軟體,您通常需要檢查下載檔案的雜湊值是否與開發人員公開的雜湊值相符。如果是這樣,您就會知道您電腦上的檔案與其檔案完全相同。

如果雜湊不相符,則存在問題。您要么下載了偽裝成該軟體的惡意檔案,要么下載不正確,因此無法運作。如果是後者,而且必須等待一段時間才能下載,則可能會讓您失望。現在,您需要重新啟動該程序並希望它不會再次損毀。

您會想,如果有更簡單的方法來解決該問題該多好。幸運的是,這正是 Merkle Tree 的用武之地。使用其中之一,您可以將檔案分成多個區塊。如果是一個 50GB 的檔案,您可以將其分成 100 個區塊,每個區塊的大小為 0.5GB。然後逐個下載。這基本上就是您在下載檔案時所做的。
在這種情況下,您的來源將為您提供一個稱為 Merkle Root 的雜湊。這個單一雜湊即構成檔案的每個資料區塊。但 Merkle Root 使驗證資料變得更加容易。
為簡單起見,我們來舉例說明,假設我們使用 8GB 的檔案來分成八個區塊。叫用不同的片段 AH。每個片段隨後傳遞一個雜湊函數,得到八個不同的雜湊。


我們透過雜湊函數傳遞八個片段中的每一個,來獲取其雜湊。


我們得到了一些更有意義的東西。我們有了所有片段的雜湊,如果一個片段發生故障,我們會透過與源片段作比較來瞭解,對嗎?可以這樣做,但這非常低效。如果您的檔案有數千個片段,您確定要對所有片段進行雜湊處理並仔細比較結果嗎?

不。而是將獲取每一對雜湊,進行組合,然後將其雜湊在一起。得到雜湊 hA + hBhC + hDhE + hFhG + hH。最終得到四個雜湊值。我們隨後對這些進行另一輪雜湊處理,最終得到兩個。最後,我們對剩下的兩個進行雜湊處理以獲得主雜湊 – Merkle Root(或根雜湊)。


該結構看起來像一棵倒置的樹。底列有葉子,組合起來產生節點,最後是根。


現在得到代表下載檔案的 Merkle Root。我們可以將此根雜湊與來源提供的雜湊作比較。如果相符的話,很完美!但如果雜湊不同,則可以確定資料已經被修改。換句話說,一個或多個片段產生了不同的雜湊。因此,對資料的任何輕微修改都會給得到一個完全不同的 Merkle Root。

幸運的是,有一種方便的方法可以讓我們檢查哪個片段有問題。在本例中,假設是 hE。首先請求對等方提供產生 Merkle Root 的兩個雜湊值(hABCDhEFGH)。您的值 hABCD 應與其值相符,因為子樹中沒有錯誤。但 hEFGH 不會,所以您知道在那裡檢查。然後請求 hEFhGH ,並將其與您的作比較。hGH 看起來不錯,所以您知道 hEF 是罪魁禍首。最後,比較 hEhF 的雜湊值。您現在知道 hE 不正確,因此可以重新下載該區塊。

總而言之,Merkle Tree 透過將資料分成許多區塊來建立,然後重複雜湊處理以形成 Merkle Root。您隨後可以有效地驗證某個資料區塊是否出現問題。正如我們將在下一部分中看到的,還有其他有趣的應用程式。



想開始使用加密貨幣嗎?於幣安買入比特幣!



為什麼在比特幣中使用 Merkle Root?

Merkle Tree 有一些使用案例,但在這裡我們將重點關注其在區塊鏈中的重要性。Merkle Tree 在比特幣和許多其他加密貨幣中至關重要。它們是每個區塊的重要組成部分,可以在區塊頭中找到。為了獲取樹的葉子,我們使用區塊中所包含的每項交易的交易雜湊 (TXID) 。

在本例中,Merkle Root 有兩個用途。我們來看看其加密貨幣挖掘和交易驗證方面的應用。


挖礦

比特幣區塊由兩部分組成。第一部分是區塊頭,固定大小的區段,包含區塊的中繼資料。第二部分是大小可變的交易清單,但往往比區塊頭大得多。
礦工需要反復對資料進行雜湊處理,以產生符合特定條件的輸出,從而挖掘出一個有效的區塊。他們可能要進行數万億次嘗試才會找到一個區塊。每次嘗試時,他們都會變更區塊頭 (nonce) 中的隨機數,以產生不同的輸出。但區塊的大部分保持不變。可能有數以千計的交易,您仍然需要每次都對其進行雜湊處理。

Merkle Root 大大簡化了該程序。當您開始挖礦時,您將要包含的所有交易排列起來,並構建一個 Merkle Tree。您將產生的根雜湊(32 個位元組)放在區塊頭中。然後,在您挖礦時,只需對區塊頭進行雜湊處理,而非整個區塊。

由於可以防篡改,因此可以有效運作。您以緊湊的格式有效地總結所有區塊的交易。您無法找到有效的區塊頭並稍後變更交易清單,因為這會變更 Merkle Root。當區塊被傳送至其他節點時,它們會從交易清單中計算根。如果與區塊頭中的不相符,則會拒絕該區塊。


驗證

我們可以利用 Merkle Root 的另一個有趣特性。這涉及輕用戶端(不持有區塊鏈完整副本的節點)。如果您在資源有限的裝置上執行節點,您不會想要下載所有區塊的交易並進行雜湊處理。您可以做的只是請求 Merkle 證明 – 全節點提供的證據,證明您的交易在特定的區塊中。這通常被稱為簡化支付驗證 (SPV),中本聰在比特幣白皮書中對此進行了詳細說明。


若要檢查 hD ,只需要以紅色顯示的雜湊值。


假設在某場景中,我們想要知道 TXID 為 hD 的交易資訊。如果提供 hC,可以得出 hCD。然後,我們需要 hAB 來計算 hABCD。最後,使用 hEFGH ,我們可以檢查產生的 Merkle Root 是否與區塊頭中的根相符。如果相符,則證明交易已包含在區塊中,幾乎不可能用不同的資料來建立相同的雜湊。

在上面的範例中,我們只需要進行三次雜湊處理。如果沒有 Merkle 證明,則需要進行七次。由於如今的區塊包含數以千計的交易,使用 Merkle 證明為我們節省了大量時間和運算資源。


總結

Merkle Tree 已被證明在一系列電腦科學應用中非常有用,正如我們所見,其在區塊鏈中非常有價值。在分散式系統中,Merkle Tree 可輕鬆驗證資訊,而無需用不必要的資料淹沒網路。

若沒有 Merkle Tree(和 Merkle Root),比特幣和其他加密貨幣區塊不會像今天這樣簡單。雖然輕用戶端在隱私權和安全方面有所缺乏,但 Merkle 證明讓用戶能夠以最小的開銷檢查其交易是否包含在區塊中。