默克爾樹(Merkle Tree)解釋

要了解區塊鏈,您需要了解它所基於的基本原理。它的主要特征可能是默克爾樹,有時也稱為哈希樹。多虧了它,區塊鏈可以同時有效和透明的運作。該概念在1979年由拉爾夫·默克爾(Ralph Merkle)教授申請了專利。現在,它有助於解決大型分散式網絡中的問題。

什麼是默克爾樹,它與加密貨幣有什麼關系?讓我們在Changelly的這篇文章中一起探尋吧!

默克爾樹基礎知識

默克爾樹是樹狀的完整數據結構,在其葉頂點中有來自數據塊的哈希值,而內部頂點包含通過在子頂點中添加值而得到的哈希值。這將所有元素之間相互聯系起來。最后,它看起來像這樣。

Merkle-Tree

哈值希是轉換哈希函數的結果。它是根據特定算法將任意長度的輸入數據數組轉換為指定長度的輸出字符串的功能。

默克爾樹有什麼用?

在集中式系統中,信息的准確性不是問題,因為其所有組件都依賴一個集中式節點。當您收到轉入您的銀行帳戶的資金時,您無需擔心資金的真實性。

但是,在分散的網絡中,一切都不是那麼簡單。每個節點都負責所傳輸信息的准確性,因此,由於網絡上的交易數量眾多,驗証完整卷的真實性並非易事。至少在沒有默克爾樹的情況下是如此。它使您可以優化使用哈希顯示數據的過程。文件系統使用默克爾樹檢查信息中的錯誤,並使用分布式數據庫來同步記錄。

在區塊鏈上,哈希樹可簡化付款驗証(SPV)。SPV客戶端稱為輕量級客戶端(因為它們僅存儲區塊標題,而不存儲其內容),以驗証交易信息,不重新計算所有哈希值,而是要求默克爾樹提供証明。它由一個根和一個分支組成,該分支包括從請求的事務到根的哈希值,因為客戶端不需要有關其他操作的信息。當添加所請求的哈希並將它們與根進行比較時,客戶端將確保事務已在其位置。這種方法允許您處理任意數量的數據,因為僅下載了必要的哈希,它可以大大減少網絡上的負載。例如,具有五個最大大小的事務的區塊的大小超過500 KB。在相同情況下,默克爾証明的大小不會超過140個字節。

默克爾樹如何在比特幣中運作

哈希函數是將輸入數據轉換為指定長度的位字符串的過程。接收到的字符串(哈希)在很大程度上取決於傳入數據的數組。即時整個數組中一個字符發生了變更,則生成的哈希將採用完全不同的值。

比特幣區塊中的所有交易都是十六進制格式的字符串。它們被哈希運算並顯示為事務標識符(txid)。直到收到該區塊的單個哈希值為止,該區塊中的所有txid進行均會被哈希運算。在此過程中,將構建默克爾樹:

  1. 首先,計算txid(交易ID)本身,即交易哈希值﹔
  2. 然后,根據交易哈希值的總和計算哈希值。 默克爾樹是二進制的-也就是說,在每個新的哈希步驟中,樹元素的數量必須為偶數。如果該區塊的事務數為奇數,則將復制最后一個的哈希並將其添加到自身﹔
  3. 根據交易哈希值總和來計算新的哈希值。該過程一直持續到獲得單個哈希(根節點)為止。並在區塊標題中指示。
merkle-tree in depth

在比特幣區塊鏈中,默克爾樹是使用SHA-256雙哈希構建的。這是哈希運算“Hello”字符串的示例:

第一輪SHA-256:

2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824

第二輪SHA-256:

9595c9df90075148eb06860365df33584b75bff782a510c6cd4883a419833d50

默克爾樹原理

編譯默克爾樹的過程類似於數據折疊。 多虧了它,交易或任何其他信息陣列的龐大列表可以在一行中表示。 令人驚奇的是,如果在這些相同事務的列表中的某處,我們僅更改一個符號,則樹的下一層和最終的哈希將完全不同。 這意味著樹的頂部也會改變。

換句話說,您不能將一個事務替換為該區塊中的另一個事務,也不能更改現有事務的數據。 這就是為什麼默克爾樹被認為是在區塊鏈中記錄交易的有效方法。 還有默克爾証明(Merkle Proof)的概念。 這是使用哈希值驗証信息有效性的原理。 無需檢查整個數據數組,隻需檢查樹中的各個哈希就足夠了,這大大減少了整個過程的計算能力開銷。

默克爾樹的其它版本

本文討論了拉爾夫·默克爾發明的概念的最簡單的二進制版本。 在其中,每個“父”哈希都有兩個“繼承人”。 在比特幣中,使用SHA-256雙重哈希構建哈希樹。

ethereum merkle tree

對這個概念有更復雜的解釋。 例如,以太坊使用前綴默克爾樹。 每個以太坊區塊報頭一次包含三個這樣的樹:關於事務,有關其執行和狀態的信息。 與二叉樹不同,前綴節點的值還取決於與其他節點的連接。 該值是動態的而非固定的。 可以更改它而不必重新計算樹的所有哈希值。