DAY 25 - Merkle Tree

16th鐵人賽

anzhe

2024-10-09 23:59:14

36 瀏覽

分享至

Merkle Tree

Merkle Tree，也稱為梅克爾樹或哈希樹，是區塊鏈的底層加密技術，被比特幣和以太坊區塊鏈廣泛採用。Merkle Tree 是一種由下而上建構的加密樹，每個葉子是對應資料的 Hash，而每個非葉子為它的 2 個子節點的 Hash。

Merkle Tree 允許對大型資料結構的內容進行有效且安全的驗證（Merkle Proof），對於有 N 個葉子結點的 Merkle Tree，在已知 root 根值的情況下，驗證某個資料是否有效（屬於 Merkle Tree 葉子結點）只需要 ceil (log₂N) 個資料（也叫 proof），非常有效率，如果資料有誤，或給的 proof 錯誤，則無法還原出 root 根植。

在下面的例子中，葉子 L1 的 Merkle proof 為Hash 0-1 和 Hash 1：知道這兩個值，就能驗證 L1 的值是不是在 Merkle Tree 的葉子中。為什麼呢？因為透過葉子 L1 我們就可以算出 Hash 0-0，我們又知道了 Hash 0-1，那麼 Hash 0-0 和 Hash 0-1 就可以聯合算出 Hash 0，然後我們又知道 Hash 1，Hash 0 和 Hash 1 就可以聯合算出 Top Hash，也就是 root 節點的 hash。

生成 Merkle Tree

我們可以利用網頁或 Javascript 函式庫 merkletreejs 來產生 Merkle Tree。
這裡我們用網頁來產生4個位址當葉子結點的Merkle Tree。葉子結點輸入：

    [
    "0x5B38Da6a701c568545dCfcB03FcB875f56beddC4", 
    "0xAb8483F64d9C6d1EcF9b849Ae677dD3315835cb2",
    "0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db",
    "0x78731D3Ca6b7E34aC0F824c42a7cC18A495cabaB"
    ]

在選單裡選 Keccak-256、hashLeaves 和 sortPairs 選項，然後點選 Compute，Merkle Tree 就生成好了。

Merkle Tree 展開為：

Merkle Proof 驗證

透過網站，我們可以得到地址 0 的 proof 如下：

利用 MerkleProof 函式庫來驗證：

library MerkleProof {
    /**
     * @dev 當透過`proof`和`leaf`重建的`root`與給定的`root`相等時，傳回`true`，資料有效。
     * 重建時，葉子節點對和元素對都是排序過的。
     */
    function verify(
        bytes32[] memory proof,
        bytes32 root,
        bytes32 leaf
    ) internal pure returns (bool) {
        return processProof(proof, leaf) == root;
    }

    /**
     * @dev Returns 透過Merkle樹用`leaf`和`proof`計算出`root`. 當重建出的`root`和給定的`root`相同時，`proof`才是有效的。
     * 在重建時，葉子節點對和元素對都是排序過的。
     */
    function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
        bytes32 computedHash = leaf;
        for (uint256 i = 0; i < proof.length; i++) {
            computedHash = _hashPair(computedHash, proof[i]);
        }
        return computedHash;
    }

    // Sorted Pair Hash
    function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
        return a < b ? keccak256(abi.encodePacked(a, b)) : keccak256(abi.encodePacked(b, a));
    }
}

MerkleProof 函式庫有三個函數：

verify()函數：利用proof數來驗證leaf是否屬於根為root的Merkle Tree中，如果是，則傳回true。它呼叫了processProof()函數。
processProof()函數：利用proof和leaf依序計算出Merkle Tree的root。它呼叫了_hashPair()函數。
_hashPair()函數：用keccak256()函數計算兩個非根節點對應的子節點的雜湊（排序後）。

利用 Merkle Tree 發放 NFT 白名單

一份擁有 800 個地址的白名單，更新一次所需的 gas fee 很容易超過 1 個 ETH。而由於 Merkle Tree 驗證時，leaf 和 proof 可以存在後端，鏈上只需儲存一個 root 的值，非常節省g as，專案方常用它來發放白名單。許多 ERC721 標準的 NFT 和 ERC20 標準代幣的白名單/空投都是利用 Merkle Tree 發出的，例如 optimism 的空投。

contract MerkleTree is ERC721 {
    bytes32 immutable public root; // Merkle樹的根
    mapping(address => bool) public mintedAddress;   // 記錄已經mint的位址

    // 建構子，初始化NFT合集的名稱、代號、Merkle樹的根
    constructor(string memory name, string memory symbol, bytes32 merkleroot)
    ERC721(name, symbol)
    {
        root = merkleroot;
    }

    // 利用Merkle樹驗證地址並完成mint
    function mint(address account, uint256 tokenId, bytes32[] calldata proof)
    external
    {
        require(_verify(_leaf(account), proof), "Invalid merkle proof"); // Merkle檢驗通過
        require(!mintedAddress[account], "Already minted!"); // 地址沒有mint過
        _mint(account, tokenId); // mint
        mintedAddress[account] = true; // 記錄mint過的地址
    }

    // 計算Merkle樹葉子的 hash
    function _leaf(address account)
    internal pure returns (bytes32)
    {
        return keccak256(abi.encodePacked(account));
    }

    // Merkle樹驗證，呼叫MerkleProof函式庫的verify()函數
    function _verify(bytes32 leaf, bytes32[] memory proof)
    internal view returns (bool)
    {
        return MerkleProof.verify(proof, root, leaf);
    }
}

MerkleTree 合約繼承了 ERC721 標準，並利用了 MerkleProof 函式庫。

狀態變數

root儲存了Merkle Tree的根，部署合約的時候賦值。
mintedAddress是一個mapping，記錄了已經mint過的地址，某地址mint成功後進行賦值。

函數

建構子：初始化NFT的名稱和代號，還有Merkle Tree的root。
mint()函數：利用白名單鑄造NFT。參數為白名單地址account，鑄造的tokenId，和proof。首先驗證address是否在白名單中，驗證通過則把序號為tokenId的NFT鑄造給該地址，並將它記錄到mintedAddress。此過程中呼叫了_leaf()和_verify()函數。
_leaf()函數：計算了Merkle Tree的葉子地址的雜湊。
_verify()函數：呼叫了MerkleProof函式庫的verify()函數，進行Merkle Tree驗證。