Merkle Trees And Bulk Transfers In Ethereum
Merkle Trees have become more popular than ever in the last decade for their heavy use in the crypto world. Merkle Trees or Hash Trees play a crucial role in verifying the integrity of transactions stored in the decentralized ledger, with fewer amounts of data.
It’s a data structure usually represented by a binary tree where each parent node contains a combination of hashes from their children. The top of the tree is called root hash or Merkle root, and it is obtained from the process of re-hashing the concatenation of the child nodes starting from the last layer up to the top.
Merkle roots are not used to verify individual transactions; instead, they are used to verify a set of transactions. If there is a change in any of the transactions, then there will be a change in the Merkle root. Merkle root gives the proof of which transactions are present in the block and in which order the transactions are present.
Bulk Transfer with Merkle Tree
We all know that executing an operation like a transfer in a Smart Contract cost money (or Ether in technical terms), which is paid as gas to the validation nodes in the network. Now imagine that you have to make thousands of transfers; that’s a lot of money given the high prices of the gas in the ETH mainnet.
This kind of scenario is fairly common for NFT airdrops, or in the betting industry. Merkle trees become handy for inverting roles in these particular scenarios. What if we make all the possible recipients claim their tokens instead of making a transfer to them? In that way, our solution would scale better as they will be responsible for paying the gas to claim the tokens.
Let’s now describe in detail how this solution works in practical terms. If we know all the addresses in advance, we can use a Merkle tree and compute a unique Merkle root. We can later distribute a proof representing one of the tree’s nodes to each of these addresses.
They can use the proof to claim the tokens. The Merkle root in our possession can validate the proof and make sure it belongs to the same tree. If the validation succeeds, we can assume the presented proof was ok, and we can issue the tokens.
Implementation Example
Use the hardhat suite to implement this.
Smart Contrat
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "hardhat/console.sol";
import "@openzeppelin/contracts/access/Ownable.sol";
import {MerkleProof} from "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";
contract Betting is Ownable {
event GainsClaimed(address indexed _address, uint256 _value);
using MerkleProof for bytes32[];
uint256 public totalBetOne;
uint256 public totalBetTwo;
uint256 public minimumBet;
address[] public playersBetOne;
address[] public playersBetTwo;
mapping(address => uint256) public players;
mapping(address => uint256) public claimed;
bytes32 merkleRoot;
uint8 winner;
constructor() Ownable() {
// minimum bet is 1 gwei
minimumBet = 1000000000;
}
function setMerkleRoot(bytes32 root, uint8 team) onlyOwner public
{
merkleRoot = root;
winner = team;
}
function checkPlayer(address player) public view returns(bool){
return !(players[player] == 0);
}
function getTotalBetOne() public view returns(uint256){
return totalBetOne;
}
function getTotalBetTwo() public view returns(uint256){
return totalBetTwo;
}
function getPlayersBetOne() public view returns(address[] memory) {
return playersBetOne;
}
function getPlayersBetTwo() public view returns(address[] memory) {
return playersBetTwo;
}
function bet(uint8 team) public payable {
require(team == 1 || team == 2, "Invalid team");
require(!checkPlayer(msg.sender), "You bet on a game already");
require(msg.value >= minimumBet, "Minimum bet is 1 gwei");
require(merkleRoot == 0, "Bets are closed");
if(team == 1) {
playersBetOne.push(msg.sender);
totalBetOne += msg.value;
} else {
playersBetTwo.push(msg.sender);
totalBetTwo += msg.value;
}
players[msg.sender] = msg.value;
}
function claim(bytes32[] memory proof) public {
require(merkleRoot != 0, "No winner yet for this bet");
require(proof.verify(merkleRoot, keccak256(abi.encodePacked(msg.sender))), "You are not in the list");
uint256 senderBet = players[msg.sender];
uint256 totalWinners = totalBetOne;
uint256 totalLosers = totalBetTwo;
if(winner == 2) {
totalWinners = totalBetTwo;
totalLosers = totalBetOne;
}
uint256 total = senderBet + ((senderBet / totalWinners) * totalLosers);
(bool success, ) = msg.sender.call{value:total}("");
require(success, "Transfer failed.");
emit GainsClaimed(msg.sender, total);
}
}Test the contract using merkletreejs and keccak256 from node.js.
const { expect } = require("chai");
const { MerkleTree } = require('merkletreejs');
const keccak256 = require('keccak256');describe("Betting", function () {
let owner, addr1, addr2, addr3, addr4, addr5;
let Betting, betting;
beforeEach(async function() {
[owner, addr1, addr2, addr3, addr4, addr5] = await ethers.getSigners();Betting = await ethers.getContractFactory("Betting");
betting = await Betting.deploy();
await betting.deployed();
});it("Should not allow bets for less than a gwei", async function () {
await expect(betting.bet(1, { value : 1e3 })).to.be.reverted;
});it("Should not allow bets for not existing teams", async function () {
await expect(betting.bet(3, { value : 1e9 })).to.be.reverted;
});it("Should not allow betting twice", async function () {
await betting.bet(1, { value : 1e9 });await expect(betting.bet(1, { value : 1e9 })).to.be.reverted;
});it("Should increase bets for team 1 after betting", async function () {
await betting.bet(1, { value : 1e9 });
await betting.connect(addr1).bet(1, { value : 1e9 })expect(await betting.getTotalBetOne()).to.be.equal(2e9);
});it("Should increase bets for team 2 after betting", async function () {
await betting.bet(2, { value : 1e9 });await betting.connect(addr1).bet(2, { value : 1e9 })expect(await betting.getTotalBetTwo()).to.be.equal(2e9);
});it("Should add players to a list after betting for team 1", async function () {
await betting.bet(1, { value : 1e9 });
await betting.connect(addr1).bet(1, { value : 1e9 })const list = await betting.getPlayersBetOne();expect(list[0]).to.be.equal(owner.address);
expect(list[1]).to.be.equal(addr1.address);
});it("Should add players to a list after betting for team 2", async function () {
await betting.bet(2, { value : 1e9 });
await betting.connect(addr1).bet(2, { value : 1e9 })const list = await betting.getPlayersBetTwo();expect(list[0]).to.be.equal(owner.address);
expect(list[1]).to.be.equal(addr1.address);
});it("Should not allow betting after team 1 won", async function () {
await betting.bet(1, { value : 1e9 });
const list = await betting.getPlayersBetOne();const merkletree = new MerkleTree(list, keccak256, { hashLeaves: true, sortPairs: true });const root = merkletree.getHexRoot();await betting.setMerkleRoot(root, 1);await expect(betting.connect(addr3).bet(1, { value : 1e9 })).to.be.reverted;
});it("Should allow claiming gains", async function () {
await betting.bet(1, { value : 1e9 });
await betting.connect(addr1).bet(1, { value : 1e9 })await betting.connect(addr2).bet(2, { value : 1e9 })const list = await betting.getPlayersBetTwo();const merkleTree = new MerkleTree(list, keccak256, { hashLeaves: true, sortPairs: true });const root = merkleTree.getHexRoot();await betting.setMerkleRoot(root, 2);const proof = merkleTree.getHexProof(keccak256(addr2.address));await expect(betting.connect(addr2).claim(proof))
.to.emit(betting, 'GainsClaimed')
.withArgs(addr2.address, 3e9);;
});it("Should not allow claiming gains for team 1 if team 2 won", async function () {
await betting.bet(1, { value : 1e9 });
await betting.connect(addr1).bet(1, { value : 1e9 })await betting.connect(addr2).bet(2, { value : 1e9 })const list = await betting.getPlayersBetTwo();const merkleTree = new MerkleTree(list, keccak256, { hashLeaves: true, sortPairs: true });const root = merkleTree.getHexRoot();await betting.setMerkleRoot(root, 2);const proof = merkleTree.getHexProof(keccak256(addr1.address));await expect(betting.connect(addr1).claim(proof)).to.be.reverted;
});it("Should not allow claiming gains for stolen proof", async function () {
await betting.bet(1, { value : 1e9 });
await betting.connect(addr1).bet(1, { value : 1e9 })await betting.connect(addr2).bet(2, { value : 1e9 })const list = await betting.getPlayersBetTwo();const merkleTree = new MerkleTree(list, keccak256, { hashLeaves: true, sortPairs: true });const root = merkleTree.getHexRoot();await betting.setMerkleRoot(root, 2);const proof = merkleTree.getHexProof(keccak256(addr2.address));await expect(betting.connect(addr1).claim(proof)).to.be.reverted;
});});
The test above calls the “bet” method from three different addresses, giving a total of 3 gwei as the total balance. We also compute a Merkle tree from the list of addresses for team two (that’s a single address, address 2). It also generates proof for address 2, and calls the “claim” method with that proof to claim the gains. Note that it’s crucial to impersonate the calls with the correct address using the connect method, as many of the methods in our contract use the msg.sender variable.
