Preface

昨日使用 merkletreejs 來建構我們的 Merkle Tree Whitelist，並了解怎麼利用 merkletreejs 來生成 proof 與 root。當我們在鏈下生成 proof 之後，可以將其結果傳送給 merkleProof 這個合約定義的 verify function 中進行驗證，達成在鏈上驗證的效果！

Merkle Proof library from OZ

在 Openzeppelin 的合約庫中的 Cryptography 中有一個稱為 MerkleProof.sol 的 library。

How to use it?

首先需要 import 這個合約，並在我們自己的合約中實作一個 isWhitelisted() 如下：

首先要在 constructor() 中儲存鏈下產生的 root，將其永久被儲存在鏈上。

bytes32 root;
constructor(bytes32 memory _root) {
    root = _root;
}

function isWhitelisted(bytes32[] memory proof) public view returns(bool) {
    bytes32 leaf = keccak256(abi.encodePacked(msg.sender));
    return MerkleProof.verify(proof, root, leaf);
}

又或是可將其改寫成 modifier：

modifier isWhitelisted(bytes32[] memory proof) {
    require(MerkleProof(
        proof,
        root,
        keccak256(abi.encodePacked(msg.sender))
    ));
    _;
}

接下來你可以用這個 function 並依照你想要的身分做驗證，例如 preSaleMint()（在公開 mint 前讓有白名單的人可以 mint）。

function preSaleMint(bytes32[] proof) public  {
    require(isWhitelisted(proof), "Not a whitelisted address");
    //...
}

或者說白名單可以設定成一次 mint 多少個 NFT，可以依照自己想要的方式來做更動。

MerkleProof.sol analysis

How do they proof?

我其實也好奇這個 library 是如何運作的，因此研究了一下 OZ 的合約。

verify()

我們使用的 verify() 中會呼叫 processProof() 這個 function

function verify(
    bytes32[] memory proof,
    bytes32 root,
    bytes32 leaf
) internal pure returns (bool) {
    return processProof(proof, leaf) == root;
}

processProof()

再往下看可以看到 processProof()，其中會用到 _hashPair() 這個 function。

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;
}

在 OZ 的中可以看到一些 Merkle Tree 的基本運行 function。

hash functions

function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
        return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
}

function _efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32 value) {
    assembly {
        mstore(0x00, a)
        mstore(0x20, b)
        value := keccak256(0x00, 0x40)
    }
}

第一個 _hairPair() 是會比較兩個 leaves/ parents 的大小並依照其規則來進行 hash()。

第二個 _efficientHash() 則是透過 assembly 的語法直接使用 memory allocation 並使用 keccak256() 來達成將兩個元素 hash() 的效果。

因此我整理了這幾個 function 的流程：

首先可以看這張圖，我先產生一個 leaf 為 0x6ee8063bddba9a0e8451e526287f94fba4f2cae8701c199a48507b80d363e859 （打綠勾勾的地方）的 proof，結果如圖的右邊所示。

根據昨日敘述的 Merkle Proof 的方法，我們需要依序 hash() 的就是透過 merkletreejs 產生的 proof，也就是：

proof: [
    0 : "0x1f675bff07515f5df96737194ea945c36c41e7b4fcef307b7cd4d0e602a69111"
    1 : "0xe62e1dfc08d58fd144947903447473a090c958fe34e2425d578237fcdf1ab5a4"
    2 : "0x43bc62416b58094e4177b6216c5fa32f18b84c5bced4b544c5499ab291d27071"
]

hash 的流程就是 hash(hash(hash(leaf, proof[0]), proof[1]), proof[2])

流程:

1. 我們將這串 proof 傳到 processProof() 後會依照這個順序，與我們設定好的 leaf 先進行比較，就如同昨日的 Buffer.compare()，不過 solidity 中可以直接比較。
2. 比較後依照與 merkletreejs 相同的順序將其 abi.encodePacked()（見此，功能與 Buffer.concat() 的作用相同，否則就不能 hash 出同樣的值了!）。
3. 最後再使用 assembly{...} 的方式將二者 hash()。
4. 按照順序的 hash() 後如果得到與我們鏈下做出的 root 相同的話，便可以代表這個 address 是存在 merkle tree 中的！

Closing

今日使用 Openzeppelin 的 library 讓我們做出可以在鏈上驗證 merkleProof 的合約，並理解這個 library 的驗證運作邏輯為何。

但是這個 merkleProof 要如何真正運用在合約中還是需要多看例子，仍然要學習的部分還有很多很多，加油！

References

• How to use MerkleProof library?
• OZ - Cryptography
• MerkleProof.sol
• modifier function

若有文章內有任何錯誤的地方歡迎指點與討論！非常感謝！

歡迎贊助窮困潦倒大學生
0xd8538ea74825080c0c80B9B175f57e91Ff885Cb4