將 Merkle Trees用於 NFT 白名單

胡家維 Hu Kenneth
My blockchain development Journey
8 min readJan 16, 2022

source : https://medium.com/@ItsCuzzo/using-merkle-trees-for-nft-whitelists-523b58ada3f9 by Alan

介紹

早在我們今天所知道和喜愛的區塊鏈出現之前,默克爾樹就一直是密碼學和計算機科學領域的一個方面。如今,我們慢慢開始看到它們在鏈上更頻繁地用於數據驗證。在本文中,我將解釋如何在 NFT (ERC-721) 上下文中實現默克爾樹以實現代幣白名單,以及它們如何確保代幣只能由預期的參與者認領。

但是,什麼是默克爾樹!?

Merkle 樹是一種樹狀結構,其中樹上的每個節點都由一個值表示,該值是某個加密哈希函數的結果。散列函數是單向的,這意味著很容易從輸入中產生輸出,但在計算上從輸出中確定輸入是不可行的。 Merkle 樹具有 3 種類型的節點,如下所示:

  1. 葉節點(Leaf Nodes) — — 這些節點位於樹的最底部,它們的值是根據指定的散列函數對原始數據進行散列的結果。對於需要散列的多條原始數據,樹中有盡可能多的葉節點。例如。如果需要對 7 條數據進行哈希處理,則將有 7 個葉子節點。
  2. 父節點(Parent Nodes) — — 父節點可以位於樹的不同級別,具體取決於樹的整體大小,但始終位於葉節點之上。父節點只會培育最少一個節點,最多兩個節點。父節點的值由其下方節點的連接哈希值確定,通常從左到右開始。由於不同的輸入總是會產生不同的哈希,因此連接培育節點哈希的順序很重要。值得一提的是,父節點可以根據樹的大小培育出其他父節點。
  3. 根節點(Root Node) — 根節點位於樹的頂部,從位於其下方的兩個父節點的連接哈希的哈希派生而來,同樣從左到右開始。任何默克爾樹上都只有一個根節點,並且根節點擁有根哈希。

我知道有很多信息需要消化,因此請參閱下圖(圖 1)以更好地可視化這些樹的結構。

Figure 1. Merkle Tree Structure

語境

如前所述,在 NFT (ERC-721) 上下文中使用默克爾樹在為選定的參與者組(本身就是白名單)保留一定數量的代幣的情況下會很有用。默克爾樹必須預先計算,因此使用某種形式的數據,每個成員都是不同的。在這種情況下,假設一個葉子節點代表我們白名單中的一個錢包地址。

假設您的項目已經實施了白名單策略,其中為選定的錢包地址保留了任意數量的代幣,這些錢包地址可能是通過競爭、抽獎或其他系統選擇的。由於各種原因,這些列入白名單的地址已被授予在公共鑄幣廠之前的某個時間點認領其保留代幣的能力。這些可能與避免高昂的汽油費、獎勵創造力、早期參與、社區參與等有關。

由於這些地址是已知的並且是恆定的,我們可以使用這些信息來創建 Merkle 樹。為了證明這一點,讓我們使用 merkletreejs 和 keccak256 JavaScript 庫。注意:為簡單起見,我將只使用 7 個錢包地址來保持樹大小的簡潔。

JavaScript 實現

我們要做的第一件事是派生葉節點。如果您還記得,位於樹上葉節點正上方的每個父節點最多只能培養兩個葉節點。如果存在奇數個葉節點,則父節點將培育一個葉節點。每個葉節點應該是某種形式的散列數據,因此對於本示例,讓我們使用 keccak256 庫對白名單上的所有地址進行散列(圖 2)。我們正在使用這種特定的哈希算法,因為稍後將在我們的 Solidity 智能合約中使用它。

Figure 2. Deriving Leaf Nodes and Merkle Tree object.

一旦我們對白名單上的所有地址進行了哈希處理,從而獲得了葉節點,我們現在就可以創建 Merkle Tree 對象了。 我們使用 merkletreejs 庫並通過調用新的 MerkleTree() 函數來執行此操作,將葉節點作為第一個參數傳遞,我們的散列算法作為第二個參數,並將 { sortPairs: true } 選項作為最後一個參數。 最後一個參數是可選的,但我在不使用它的情況下試圖讓這個例子工作時遇到了很大的困難。

Figure 3. Merkle Tree Visualisation and Root Hash.

現在我們已經導出了一個完整的 Merkle Tree,我們可以通過調用 Merkle Tree 對象的 getRoot() 方法(圖 3)來獲取根哈希。請記住,默克爾樹的根哈希是樹上根節點正下方的兩個父節點的哈希。在這種情況下,0xf352… 和 0x3cc0…。使用 toString() 方法記錄我們的 Merkle 樹的控制台為我們提供了一個很好的可視化樹的結構。

Merkle 樹的獨創性源於它不需要任何原始數據塊的知識來驗證節點是否屬於我們的樹。如果我們試圖驗證一個葉子節點是否屬於我們的樹,則只需要知道直接相鄰的葉子節點哈希(如果有的話),並且直接在葉子節點上方的相鄰父節點哈希是必需的。對於它是如何工作的簡短而甜蜜的解釋,我建議查看 Tara Vancil 的這個視頻。此信息也稱為證明,將在我們的 Solidity 智能合約中使用,以驗證調用者是否在我們的白名單中。

網站實施

現在我們已經有了 Merkle Tree 對象和它的根哈希,我們已經準備好開始考慮如何在白名單用戶試圖索取他們的代幣時為我們的智能合約提供 Merkle 證明。真正需要做的就是在我們的項目網站上實現一些類似於上面的 JavaScript,在 mint 頁面上向外部 API 發出獲取請求。該 API 將接收連接的錢包地址,因為這是我們最初用來生成葉子節點的地址,並返回指定的證明。

在服務器端,您將收到地址,使用 keccak256 對其進行哈希處理,並使用我們的 Merkle Tree 對像上的 getHexProof() 方法檢索證明。下圖(圖 4)顯示了您可能從此 API 調用返回的內容的示例。

在收到此證明並將其作為參與者交易的參數發送後,我們現在可以開始研究如何在智能合約中驗證它。

智能合約實施

注意:所示的智能合約示例是使用顯示概念證明所需的最少代碼量構建的。 這絕不是您應該如何編寫鑄幣函數的示例。

為了驗證提供的證明,我們必須做的第一件事是導入 OpenZeppelin MerkleProof.sol 合約(第 6 行,圖 5),這將使我們能夠在智能合約代碼中使用 MerkleProof.verify() 函數。 接下來需要做的是定義根 Merkle 哈希。 如果智能合約在白名單最終確定之前已部署到以太坊主網,則假設有一些設置函數可用於在稍後的時間點更新此值。 在本例中,我對根 Merkle 哈希值進行了硬編碼,以便在部署時設置它(第 12 行,圖 5)。

Figure 5. Smart Contract code.

接下來,我們需要驗證證明。回想一下,證明是與交易一起發送的,並且是一個 bytes32 類型值的數組。從技術上講,它們屬於字符串類型,但 Solidity 無論如何都會正確解釋它們。我們生成目標葉節點(第 25 行,圖 5),如果您還記得,它是白名單地址的 keccak256 哈希。在這個例子中,我們通過散列 msg.sender 的值來生成我們的目標葉節點。請記住,此值是不可變的,不能被惡意更改。

由於僅使用白名單地址來生成我們的葉節點,因此可以假設如果非白名單地址嘗試使用有效或無效證明調用此函數,則生成的目標葉節點根本不會存在於我們的Merkle Tree 和驗證將失敗。此實現的最後一步只是調用 MerkleProof.verify() 函數,將提供的證明作為第一個參數,將根 Merkle 哈希作為第二個參數,將目標葉節點作為最後一個參數。如果此函數返回 false,則 require 語句將失敗,交易將被簡單地恢復,否則,該函數將繼續執行並鑄造代幣。

離別詞

你有它!一種相對簡單直接的方法來展示如何在 NFT 項目中使用 Merkle Trees 進行白名單聲明可以讓您高枕無憂,這樣只有白名單的指定地址才能聲明。我知道還有其他可用的解決方案,但在我研究過的解決方案中,這是迄​​今為止最有趣的。我希望你喜歡閱讀這篇文章,就像我做研究一樣,請隨時為我鼓掌,並在 Twitter 上關注我,了解我正在做的工作以及我的下一篇文章何時發布。 ✌️

--

--

胡家維 Hu Kenneth
My blockchain development Journey

撰寫任何事情,O型水瓶混魔羯,咖啡愛好者,Full stack/blockchain Web3 developer,Founder of Blockchain&Dapps meetup ,Udemy teacher。 My Linktree: https://linktr.ee/kennethhutw