Preface

昨日介紹了如何使用 mapping 來作出一個簡單的白名單，而今天會專注在另一種白名單方式 -- Merkle Tree NFT Whitelists

Merkle Tree

Basic Structure

Merkle Tree 的中文稱「砸湊樹」，是一種二元樹的資料結構。

其有重要的三個結構：

1. Leaf: 中文稱為葉子，是在最樹的階層中最底部的節點，會儲存初始資料的 hash 值（oringinal data）。
2. Parent: 父或母節點，是由兩個 leaf 或是兩個節點（可能是 leaf 的 parents） hash 而得到。
3. Merkle Root: 是樹的最高階的節點，首先 leaf 會先 hash 成其 parents，parents 會再 hash 成 grandparents... 不斷的 hash 到後會得到唯一一個 root，這個 root 通常可以拿來作為驗證來使用。

下方就是一個由四個 leaf 構成的 Merkle Tree：

sited from wikipedia

而比特幣與以太坊（以太坊準確地來說是 Sparse Merkle Tree）的架構中 Merkle Tree 都扮演了非常重要的角色。

Merkle Proof

那 Merkle Tree 要如何拿來當作白名單來使用呢？

其實仔細想想白名單的運作流程就像是一個驗證系統，這時可以退一步來討論，我們該如何使用它來達到驗證的功能？

舉一個 Leaf 為 A、B、C、D 四個元素的 Merkle Tree，如下:

由於 hash function 是非對稱加密的特色，一個 element 經過 hash() 雜湊後會使得很難透過得到的資訊回推原本的 element 是什麼。

因此我們多只能透過將正確的資訊填回去後獲得同樣的結果來驗證。

例如我們今天只擁有 C element 的資訊，這時我們只要提供 hash(D)、hash(AB)，並經由正確的 hash() 流程便可以得到一個與原本相同的 Root。

Implement with merkletreejs

雖然要手刻一個 Merkle Tree 好像不是不行（好啦其實對我來說有點難），但是還是稍嫌麻煩了億點。

因此這邊推薦使用 merkletreejs 這個套件，讓我們可以在鏈下建構屬於我們自己的 merkle tree whitelist。

首先先安裝需要的套件：

npm i merkletreejs
npm i keccak256

注意！如果出現Buffer is not defined 的 error 時需要使用：

npm install buffer

並在 home.js 或是 main.js 中引用：

import { Buffer } from "buffer/";
window.Buffer = window.Buffer || Buffer;

接著引用需要使用的物件

import { MerkleTree } from 'merkletreejs';
import keccak256 from 'keccak256';

Build Merkle Tree

首先建立 whitelist merkle tree，其實就是把每一個 whitelist address 當成一個 leaf，並將 leaf 再作成一顆樹。

我們假設 A ~ G 是我們的白名單地址。

const whitelistAddresses = [
    "A",
    "B",
    "C",
    "D",
    "E",
    "F",
    "G"
]

const leafNodes = whitelistAddresses.map(addr => keccak256(addr));
const merkleTree = new MerkleTree(leafNodes, keccak256, { sortPairs: true });
// 檢查 merkle tree 的樣子
console.log('Whitelist Merkle Tree:\n', merkleTree.toString());

在 MerkleTree() 中需要傳入三個 parameter:

• leaves: 就是 leaf 們（在我們的例子中就是 address）。
• hash function: 用來雜湊的函式。
• options: 可以選擇要用什麼條件來進行，有 isBitcoinTree、hashLeaves、sortLeaves與 sortPairs，這邊使用 sortPairs 是會在 hash 時將兩次的 hash 值再作排列，詳細可看程式碼或下方的 Buffer & Hash 部分。

成功的得到了一個 merkle tree ><

Generate Proof

一個完整的 verify 需要滿足三個東西：

1. leaf: 使用者（白名單）的地址。
2. proof: 像上方例子中的 hash(D) 與 hash(AB)。
3. root: Merkle Tree 最終 hash 出來的結果。

這邊我們已經有了 leaf，因此還需要 proof 與 root。

const buf2hex = x => '0x' + x.toString('hex');
const leaf = leafNodes[0];
const proof = merkleTree.getHexProof(address);
const root = buf2hex(merkleTree.getRoot());

console.log(merkleTree.verify(hexProof, leaf, root));

首先需要定義一個 buf2hex() 將 Buffer（二進位制） 轉換成 Hex（十六進位制）。

這邊取得 proof 的方式是使用 .getHexProof(leaf) 這個 method 而不是 .getProof(leaf)，原因也是因為不同進位制。

最後可以用 merkleTree.verify(proof, leaf, root) 來檢查是否這個 leaf 存在於 Merkle Tree 中。

若今天使用者的地址不在這個 whitelist 中，merkleTree.verify() 則會回傳 false

Buffer & Hash

在整個過程中有一件令我好奇的事：在我們宣告一個 new MerkleTree() 時傳入的第三個 parameter 到底代表什麼。

（以下會依照我們使用的 sortPairs 來解析）

在仔細的端詳了 merkletreejs 中刻出的程式中，我發現其實在 hash 前，左與右 leaf 會先被丟到一個 宣告為 conbine 的 array 中，並透過 array.sort(comparison function) 來改動他們的順序，而其中使用的 comparison function 是 Buffer.compare。

Buffer 是在 Node.js 中用來將資料轉換成二進位的函式，在 Merkle Tree 的實作中會很常遇到，詳細可見此。

而 Buffer.compare(a, b) 則會比較兩者的二進位值何者較大：

• 一樣: 回傳 0。
• a > b: 回傳 1。
• a < b: 回傳 -1。

透過這個方式可以將 combine 中的左與右 leaf 依照大小排序。

接下來會 Buffer.concat() 將 combine 中的資料結合，最後用一開始設定好的 hash function 完成 hash，當然最後會再將結果紀錄在一個 array 中。

Closing

今天學會了如何使用 merkletreejs 來建造一個 whitelist Merkle Tree，並學會如何使用其中的 method 來取得 proof 與 root。而明天會使用 Openzepplin 的 MerkleProof.sol 來達到在鏈上驗證的效果。

另外今天我還差點把我全部的 node modules 全部刪掉重載...，因為 google 跑出來的 error 後竟然有人說全部刪除，再 npm i 就可以了，我差一點也跟著做下去了，還好理性告訴我不准這麼做。

Reference

• Smart Contract Whitelist Mechanism
• Day13|密碼學初探(6)：Merkle Tree
• MerkleProof.sol
• Build a Whitelisted Mint in React using MerkleTreeJS
• Using Merkle Trees for NFT Whitelists
• MerkleTree.ts
• Javascript ArrayBuffer to Hex
• keccak.js Uncaught ReferenceError: Buffer is not defined

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

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