# Using merkle trees for airdrop whitelists

By [PLUΞM](https://paragraph.com/@pluem) · 2022-05-07

---

ก่อนจะนำ [Merkle tree](https://en.wikipedia.org/wiki/Merkle_tree) มาใช้เนี่ยเราลองหาเหตุผลที่ต้องใช้กันก่อนดีกว่า เริ่มที่โจทย์ว่าเราอยากจะทำ Airdrop โดยจะแจกโทเคน [ERC20](https://ethereum.org/en/developers/docs/standards/tokens/erc-20/) ให้กับผู้ใช้บางกลุ่มที่ผ่านการทำกิจกรรมบางอย่างกับ Platfrom ของเรา เช่น ตอบคำถามถูก 10 คนแรก ซึ่งเราจะให้สิทธิ์ผู้ใช้กลุ่มนี้ในการรับ Airdrop

![User claim flow diagram.](https://storage.googleapis.com/papyrus_images/a0c4b6f5e1ba823a4fa325bc3c9a6d06426847ecb32efc19ee40537cee672f69.png)

User claim flow diagram.

ที้นี้ ถ้าเรามาลองลงมือเขียน Solidity แบบง่ายๆ โดยรับเป็น Array address ของกลุ่มที่มีสิทธิ์รับ Airdrop มาเก็บไว้แล้วก็ทำ Map ตัวนึงสำหรับเช็คว่าผู้ใช้รับไปเรียบร้อยแล้ว

![Normal whitelist airdrop contract.](https://storage.googleapis.com/papyrus_images/6688ac5102072ef4ae1c03c6e7f400eec1146be8524f33887800ec4d658edbb0.png)

Normal whitelist airdrop contract.

ในการ deploy contract นี้เราต้องใช้ค่าแก๊สทั้งหมด `693054 gas` สำหรับการใส่ address list จำนวน 1 คน แล้วถ้าเราต้องการใส่ 10 คนตามโจทย์ละ เราต้องใช้ค่าแก๊สทั้งหมด `929965 gas` จะเห็นได้ว่าค่าแก๊สจะโตตามจำนวน address ที่เราใส่เข้าไป นี่ก็คือเหตุผลที่เราจะนำ Merkle tree มาใช้เพื่อช่วยลดค่าแก๊สนั่นเอง

Merkle tree
-----------

Merkel tree หรือเรียกว่า Hash tree จะประกอบไปด้วย Leaf node จะเกิดจากการ Hash data และแต่ละ Branch node จะมาจาก Hash ของ Children node

![Structure of merkle tree.](https://storage.googleapis.com/papyrus_images/e03e3325cac64741e9e34427f19116ab603a355a93cf5f8bc12531d42e69b466.png)

Structure of merkle tree.

เราสามารถนำ Merkle tree มาใช้ในการเช็คได้ว่ามี Data อยู่บน Tree จริงๆ โดยไม่ต้องเก็บ Data ทั้งก้อนไว้ จะเรียกวิธีนี้ว่า **Merkle proof**

ยกตัวอย่างเช่น หากเราต้องการเช็คว่ามี xD2 อยู่บนต้นไม้ไหม ลำดับแรกเราต้องสร้าง Merkle tree ตามภาพด้านบนให้เสร็จเรียบร้อยแล้วเก็บ Root hash ไว้หรือก็คือ **H5**

![Merkle proof node.](https://storage.googleapis.com/papyrus_images/471abc9552223a35060292cabb0cf9e6aeeddc3ee8facab3a7caf85602d8b594.png)

Merkle proof node.

จากนั้นเราจะ Proof ได้โดยการนำ xD2 ไป `hash(xD2)` ให้ได้ xH2 แล้วหยิบ H1 มา `hash(H1+xH2)` ให้ได้ xH4 แล้วสุดท้ายไปหยิบ H3 มา `hash(xH4+xH3)` เราก็จะได้ Root hash **xH7** เมื่อนำไปเทียบกับ **H7** แล้วตรงกันก็ถือว่า data xD2 อยู่บนต้นต้นไม้นี้จริง

Merkle airdrop
--------------

หลังจากเข้าใจ Merkle tree แล้วเราก็จะนำมาลองใช้งานจริงกับการทำ Airdrop ผมขออธิบายขั้นตอนคร่าวๆ ก่อน เราจะนำ address ของผู้ที่มีสิทธิ์รับเนี่ยมาประกอบ Merkle tree แล้วนำไป `hash(address)` ใส่ Leaf node ทั้งหมด จากนั้นเก็บแค่ Root hash ที่ได้ไว้ใน Airdrop contract แทน address ทั้งหมดของผู้รับ จากนั้นตอนที่ผู้ใช้กด Claim ก็จะส่งแค่ Proof hash กับ address ของคนรับ เข้ามา Verify ว่าได้ Root hash ตรงกันไหม ถึงจะโอน Token ให้ผู้ใช้

ข้างล่างนี่เป็น Libraries ทั้งหมดที่จะนำมาใช้ในการช่วยทำ Merkle airdrop

*   [merkletreejs](https://github.com/miguelmota/merkletreejs) ใช้ในประกอบ Merkle tree
    
*   [keccak256](https://github.com/miguelmota/keccak256) ใช้เป็น hash function ใน Merkle tree
    
*   [MerkleProof.sol](https://docs.openzeppelin.com/contracts/4.x/api/utils#MerkleProof) ใช้ในการช่วย Verify root hash ใน Smart contract
    

### Build a merkle tree root hash

เริ่มต้นที่การสร้าง Merkle tree โดยการสร้าง Node.JS Project กันก่อนเลยและเพิ่ม dependency ที่ต้องใช้ให้ครบ

    pnpm[npm, yarn] init -y
    pnpm[npm, yarn] add keccak256 merkletreejs
    

จากนั้นก็สร้าง `index.js` ขึ้นมาเริ่มเขียนโค้ดเพื่อหา Root hash

![content of index.js file](https://storage.googleapis.com/papyrus_images/d36059f77c9d026ce38c00d1d55b03521935e97c9190308315de3f0034e4a9db.png)

content of index.js file

### Using Merkle proof to verify in airdrop contract

หลังจากได้ Root hash แล้วเราก็จะนำมาใส่ Airdrop contract โดยรับมาทาง constructor แทนการรับ Address list

![content of MerkleWhitelistAirdrop.sol file](https://storage.googleapis.com/papyrus_images/f60608f009fb3ec730ce08ca087b1d43a631c9299270287bc0cf2bc2ba1f88c5.png)

content of MerkleWhitelistAirdrop.sol file

### How user can claim airdrop?

ทีนี้ในตอนที่ผู้ใช้จะ claim airdrop เราจะต้องรู้ address ของผู้ใช้ที่ต้องการจะรับ โดยจะยกตัวอย่างเป็น `0x4B20993Bc481177ec7E8f571ceCaE8A9e22C02db` หรือนี่ก็คือ xD2 ในตัวอย่าง Merkle proof นั่นเอง เราจะนำมา hash keccak256 แล้วโยนให้ merkletreejs ช่วยหา Proof node

![content of index.js file](https://storage.googleapis.com/papyrus_images/d3a49a025bad7ec11d5301a5f86ff7a949092121d661e86090a981033eed3d2d.png)

content of index.js file

ทีนี้เราก็ส่ง proof ให้ผู้ใช้ไปเรียก `claim(proof);` เพียงเท่านี้ Token จาก Airdrop ก็จะโอนไปหาผู้ใช้ที่มีสิทธิ์รับแล้ว

ซึ่งในขั้นตอนในการหา proof เนี่ยเราสามารถนำไปเขียนต่อเป็น Front-end ได้โดยดึง address จาก Metamask ของผู้ใช้เพื่อไปสร้าง proof แล้วค่อยสั่งเรียก `claim(proof);` ให้ผู้ใช้

![User claim flow with merkle proof diagram. ](https://storage.googleapis.com/papyrus_images/6a65a6e1de111747157c6371fe9c9b3060f939d9785e865b291ae7ef15c68e08.png)

User claim flow with merkle proof diagram.

Conclusion
==========

ทีนี้เราไปลองส่องค่าแก๊สจากการ Deploy MerkleWhitelistAirdrop contract กันหน่อย

![Deploy contract transaction detail.](https://storage.googleapis.com/papyrus_images/eee41c47cd38b80c3b385e0deb09a926db9aa8680c6f83bc206c02f2ebd2eb44.png)

Deploy contract transaction detail.

จะเห็นได้ว่าเราใช้ไปเพียง `696206 gas` สำหรับ address ผู้รับ 10 คน ซึ่งหากเราเพิ่มจำนวนผู้รับมากกว่านี้ค่าแก๊สก็จะไม่ได้โตไปมากกว่านี้มาก เพราะเราเก็บเพียงแค่ bytes32 ของ Merkle root ไว้ใน Contract นั่นเอง

---

*Originally published on [PLUΞM](https://paragraph.com/@pluem/using-merkle-trees-for-airdrop-whitelists)*