Merkle 樹

什麼是 Merkle 樹？

Merkle 樹是一種密碼學資料結構，可將多筆資料整理成由雜湊值構成的樹狀結構。

在加密貨幣領域，Merkle 樹可協助區塊鏈有效率地驗證交易、餘額、帳戶、儲存值、空投領取資格、NFT 允許名單和其他大型資料集。

Merkle 樹也稱為雜湊樹，因為樹中的每一層都是由密碼學雜湊值建立而成。

最底層包含稱為葉節點的個別資料項目。

每個葉節點都會進行雜湊，再與另一個雜湊值配對並再次雜湊，以建立下一層。

這個程序會持續進行，直到頂端只剩下一個最終雜湊值。

這個最終雜湊值稱為 Merkle 根。

Bitcoin 開發者指南說明，交易雜湊值會兩兩配對並反覆進行雜湊，直到區塊標頭中只剩下一個 Merkle 根。

核心概念很簡單：一個精簡的根值就能代表大型資料集。

如果資料集中的任何項目發生變化，其上層雜湊值也會隨之改變，進而改變 Merkle 根。

Merkle 樹的運作方式

Merkle 樹從交易、錢包地址、帳戶紀錄或領取項目等原始資料開始。

每個項目都會經過密碼學雜湊函數處理，產生葉節點雜湊值。

兩個葉節點雜湊值會合併並一起進行雜湊，產生父雜湊值。

接著，父雜湊值會兩兩配對並再次雜湊，產生更高層的雜湊值。

這個程序會持續進行，直到只剩下一個雜湊值。

這個最終雜湊值就是 Merkle 根。

Merkle 根就像整份資料集的精簡指紋。

如果資料沒有變動，使用相同的建樹方法應該會產生相同的根值。

如果某筆交易、地址、餘額或領取數量發生變化，最終根值也應隨之改變。

Merkle 樹為何對加密貨幣很重要

Merkle 樹很重要，因為區塊鏈必須在不要求每位使用者時時處理所有資料的情況下，驗證大量資訊。

一個區塊可能包含許多交易。

一次代幣空投可能涵蓋數千或數百萬個符合資格的錢包。

區塊鏈狀態資料庫可能包含帳戶、餘額、合約儲存資料和程式碼。

Merkle 樹讓系統能以一個根值承諾大型資料集，同時仍允許日後驗證個別項目。

這有助於提升效率、可擴展性和資料完整性。

它也能降低許多加密貨幣應用程式所需的儲存空間和頻寬。

若沒有 Merkle 樹或類似的認證資料結構，許多區塊鏈驗證工作都會更慢、更繁重且成本更高。

Merkle 根

Merkle 根是 Merkle 樹頂端的最終雜湊值。

它代表下方的所有資料。

在區塊鏈區塊中，Merkle 根可摘要表示該區塊中的所有交易。

在空投合約中，Merkle 根可摘要表示所有符合資格的錢包地址和領取數量。

在狀態樹中，根值可摘要表示許多帳戶或儲存值。

根值本身不會揭露完整資料集。

它只會作為該資料集的密碼學承諾。

使用者仍需要正確的證明和驗證規則，才能確認某個項目是否屬於該樹。

Merkle 葉節點與分支

葉節點是 Merkle 樹最底層的雜湊值。

每個葉節點通常代表一筆資料。

例如，葉節點可能代表交易雜湊值、錢包地址、領取紀錄、NFT 鑄造權限或帳戶值。

分支則是葉節點和根節點之間的中間雜湊值。

分支會將個別葉節點連接至最終 Merkle 根。

Merkle 證明會使用這些分支雜湊值，證明某個葉節點屬於該樹。

這種設計讓使用者不必顯示或下載其他所有葉節點，也能完成驗證。

Merkle 樹證明

Merkle 樹證明是一組同層雜湊值，用於證明某個葉節點屬於具有已知根值的樹。

驗證者會從目標葉節點開始，依正確順序將它與證明中的雜湊值合併。

如果最後計算出的雜湊值與可信任的根相符，證明即有效。

如果最後計算出的雜湊值與可信任的根不相符，證明即無效。

OpenZeppelin MerkleProof 文件說明了智能合約工具如何驗證葉節點是否能被證明屬於由根值定義的 Merkle 樹。

因此，Merkle 樹適用於鏈上允許名單、領取、獎勵和存取權限檢查。

Bitcoin 中的 Merkle 樹

Bitcoin 使用 Merkle 樹整理區塊中的交易。

每筆交易都會先進行雜湊，接著將交易雜湊值兩兩配對並向上進行雜湊，直到產生一個 Merkle 根。

Merkle 根會儲存在區塊標頭中。

這有助於 Bitcoin 節點偵測交易資料是否遭到修改。

它也支援輕量交易驗證。

輕量客戶端可使用 Merkle 證明，檢查某筆交易是否包含在區塊中，而不必下載該區塊中的每筆交易。

這項機制支援簡化支付驗證（Simplified Payment Verification），通常稱為 SPV。

SPV 的完整性不如完整節點驗證，但對資源有限的裝置和錢包而言，效率更高。

Ethereum 中的 Merkle 樹

Ethereum 使用一種相關的認證資料結構，稱為 Merkle Patricia Trie。

Ethereum Merkle Patricia Trie 文件說明，Ethereum 的結構具確定性，並可透過密碼學驗證。

這種結構有助於 Ethereum 表示帳戶狀態、儲存資料及其他鍵值資料。

如果狀態發生變化，狀態根也會改變。

如此一來，Ethereum 客戶端和應用程式就能依據已知根值驗證狀態資料。

EIP-1186 eth_getProof 標準描述一種取得 Ethereum 帳戶和儲存值 Merkle 證明的 RPC 方法。

Ethereum 的結構與簡單的二元 Merkle 樹不同，但使用了雜湊連結驗證的相同核心概念。

空投中的 Merkle 樹

加密貨幣空投常使用 Merkle 樹管理大量領取名單。

專案可能會建立符合資格的錢包地址和代幣數量清單。

每組地址和數量都會成為 Merkle 樹中的一個葉節點。

專案只會在智能合約中儲存 Merkle 根。

使用者領取空投時，會提交 Merkle 證明。

合約會驗證錢包和數量是否屬於已儲存根值所代表的樹。

由於合約不必在鏈上直接儲存每個符合資格的錢包，因此能節省 Gas 費。

這也讓大型領取活動更容易執行。

NFT 允許名單中的 Merkle 樹

NFT 專案常使用 Merkle 樹管理允許名單、預售和提前鑄造資格。

專案不必在合約中儲存每個核准的錢包地址，只需儲存一個 Merkle 根。

每個核准錢包都會取得一份證明，證明其屬於允許名單。

鑄造時，智能合約會依據已儲存的根檢查該證明。

如果證明有效，該錢包即可依允許名單規則鑄造。

這可降低鏈上儲存成本，並提高允許名單驗證效率。

使用者仍應確認鑄造頁面、合約地址和 Merkle 根皆來自官方來源。

輕量客戶端中的 Merkle 樹

輕量客戶端使用精簡的驗證方法，減少必須下載的區塊鏈資料量。

Merkle 樹可協助輕量客戶端依據可信任的區塊標頭或根值，驗證特定交易或狀態資料。

這對行動錢包、瀏覽器，以及儲存空間或頻寬有限的裝置都很有用。

輕量客戶端提供的安全模型與完整驗證節點不同。

不過，基於 Merkle 的驗證比盲目信任單一資料提供者更可靠。

因此，Merkle 樹是打造更容易使用的加密貨幣基礎架構的重要組成部分。

區塊鏈遊戲和元宇宙應用程式中的 Merkle 樹

區塊鏈遊戲和元宇宙應用程式可使用 Merkle 樹驗證大量資產、獎勵、玩家或權限清單。

遊戲可使用 Merkle 根承諾某個賽季的獎勵資格。

元宇宙應用程式可使用 Merkle 根驗證活動徽章領取資格或虛擬土地權限。

NFT 專案可使用 Merkle 樹管理特徵揭露或白名單存取權。

這讓應用程式能將大型資料集保留在鏈下，同時仍可在鏈上驗證個別項目。

因此，成本可能更低，可擴展性也更高。

但代價是鏈下建樹程序必須透明且正確。

Merkle 樹與資料完整性

Merkle 樹可藉由讓資料變更容易被偵測，保障資料完整性。

如果某個葉節點發生變化，其雜湊值也會改變。

這項變化會影響父雜湊值，再影響上一層父雜湊值，最終改變 Merkle 根。

因此，驗證者可比較根值，判斷資料集是否相同。

Merkle 樹無法阻止任何人建立虛假的資料集。

它有助於證明資料是否符合特定的已承諾根值。

因此，根值必須來自可信任或經共識驗證的來源。

Merkle 樹與雜湊清單

雜湊清單是由雜湊值構成的簡單清單。

Merkle 樹則是結構化的雜湊樹，可支援精簡證明。

使用雜湊清單時，驗證單一項目可能需要取得完整清單中的更多資料。

使用 Merkle 樹時，驗證者通常只需要目標葉節點和少量同層雜湊值。

因此，Merkle 樹更適合大型資料集。

資料集越大，Merkle 樹的效率優勢就越明顯。

Merkle 樹與 Merkle Patricia Trie 的差異

Merkle 樹是一般性的雜湊樹資料結構。

Merkle Patricia Trie 則是專門用於鍵值資料的結構。

Ethereum 使用經修改的 Merkle Patricia Trie，有效率地儲存並驗證狀態。

簡單的 Merkle 樹常用於交易包含驗證、NFT 允許名單和空投領取。

當資料需要依鍵值查詢時，例如帳戶地址或儲存欄位，Trie 更適合使用。

這兩種結構都使用密碼學雜湊值，讓資料竄改容易被偵測。

Merkle 樹與 Verkle 樹的差異

Verkle 樹是一種較新的認證資料結構，使用向量承諾，而非只使用雜湊值配對。

Verkle 樹常被視為區塊鏈狀態系統未來的改進方向，因為它可讓某些證明更精簡。

Ethereum 文件指出，Ethereum 計畫未來從目前的 Merkle Patricia Trie 結構遷移至 Verkle 樹結構。

這不代表 Merkle 樹已經過時。

Merkle 樹仍廣泛使用，因為它簡單、可靠且廣為人知。

在空投和允許名單等許多應用情境中，Merkle 樹仍然實用且有效率。

Merkle 樹的優點

第一項優點是驗證效率高。

使用者不必下載整份資料集，就能驗證單一項目。

第二項優點是資料完整性。

底層資料的任何變化都會改變其上層雜湊值。

第三項優點是降低鏈上儲存成本。

智能合約可儲存一個根，而不必儲存許多個別紀錄。

第四項優點是可擴展性。

大型資料集可透過一個精簡根值來表示。

第五項優點是部分隱私。

使用者可以證明某項資料包含在資料集中，而不必揭露其他所有項目。

Merkle 樹的風險與限制

第一項風險是根值錯誤。

Merkle 證明只能證明資料包含在該根值所代表的資料集中，因此根值必須可信或經過驗證。

第二項風險是樹的建構方式錯誤。

如果專案使用錯誤的雜湊方法、編碼、排序方式或葉節點格式，證明可能無法通過驗證或變得不安全。

第三項風險是重放或重複領取錯誤。

如果領取只能進行一次，領取合約就必須追蹤錢包是否已使用其證明。

第四項風險是網路釣魚。

詐騙者可能建立假的領取網站，假冒使用 Merkle 證明，實際上卻要求使用者簽署有害交易。

第五項風險是誤解。

Merkle 樹可證明資料包含在其中，但無法證明專案誠實、有價值或安全。

如何評估 Merkle 樹系統

先確認 Merkle 根是否來自官方或經共識驗證的來源。

檢查葉節點的編碼方式。

確認使用的雜湊函數。

確認該樹使用排序配對，還是固定的左右順序。

檢查證明是否由官方工具或開源程式碼產生。

若涉及智能合約，請檢視證明驗證函數和領取紀錄追蹤邏輯。

對於空投和 NFT 允許名單，提交證明或簽署交易前，請先確認官方合約地址。

設計完善的 Merkle 樹系統應清楚說明根值、規則和驗證程序。

對 Merkle 樹的常見誤解

一種常見誤解是，Merkle 樹會將所有資料都儲存在鏈上。

許多加密貨幣應用程式只會將 Merkle 根儲存在鏈上，而完整資料集則在鏈下建立和儲存。

另一種誤解是，Merkle 根會揭露完整資料集。

根值只是一種雜湊承諾，本身不會顯示所有葉節點。

第三種誤解是，有效的 Merkle 證明能從道德或法律角度證明使用者應獲得獎勵。

它只能證明提交的資料包含在該根值所代表的資料集中。

第四種誤解是，所有 Merkle 樹的建構方式都相同。

不同系統可能使用不同的雜湊函數、編碼方式、排序規則和樹狀結構。

常見問題

簡單來說，什麼是 Merkle 樹？

Merkle 樹是一種雜湊值樹狀結構，讓使用者可透過簡短證明，驗證大型資料集中的單筆資料。

什麼是 Merkle 根？

Merkle 根是 Merkle 樹頂端的最終雜湊值，可作為整份資料集的精簡指紋。

區塊鏈為何使用 Merkle 樹？

區塊鏈使用 Merkle 樹，有效率地驗證大型資料集、降低資料需求，並偵測交易或狀態資料的變化。

Bitcoin 如何使用 Merkle 樹？

Bitcoin 使用 Merkle 樹摘要表示區塊中的交易，並將 Merkle 根儲存在區塊標頭中。

Ethereum 如何使用 Merkle 結構？

Ethereum 使用經修改的 Merkle Patricia Trie 儲存並驗證帳戶狀態和合約儲存資料。

什麼是 Merkle 樹證明？

Merkle 樹證明是一組同層雜湊值，用於證明特定葉節點屬於具有已知 Merkle 根的樹。

Merkle 樹如何用於空投？

空投合約可儲存一個 Merkle 根，再透過 Merkle 證明驗證使用者的領取資格，而不必在鏈上儲存每個符合資格的錢包。

Merkle 樹如何用於 NFT 允許名單？

NFT 專案可使用 Merkle 根代表核准錢包，並在鑄造時透過證明驗證每個錢包。

Merkle 樹具有隱私性嗎？

Merkle 樹可提供部分隱私，因為使用者可以證明資料包含在其中，而不必揭露整份資料集。

Merkle 樹和零知識證明相同嗎？

不相同。Merkle 樹可證明資料包含在已承諾的資料集中；零知識證明則可在不揭露私密輸入的情況下，證明更廣泛的陳述。

結論

Merkle 樹是加密貨幣領域的核心資料結構，可讓大型資料集更容易驗證。

它會將多筆資料轉換成雜湊樹，並產生一個最終 Merkle 根。

該根值可代表交易、餘額、地址、領取紀錄、儲存值或其他區塊鏈資料。

Merkle 樹之所以重要，是因為它支援有效率的驗證、降低儲存成本、維護資料完整性，也適用於輕量客戶端、空投、NFT 允許名單和區塊鏈狀態證明。

Bitcoin 使用 Merkle 樹摘要表示區塊中的交易。

Ethereum 則使用相關的 Merkle Patricia Trie 結構處理帳戶和儲存狀態。

只要加密貨幣應用程式需要證明某個項目屬於大型資料集，又不想將整份資料集放在鏈上，就可能使用 Merkle 樹。

Merkle 樹功能強大，但其可靠性取決於正確的雜湊、安全的編碼、可信任的根值，以及安全的證明驗證方式。

妥善使用 Merkle 樹可讓加密貨幣系統更輕量、成本更低，也更容易驗證。