Pablo Cibraro

My notes about software development, security and other stuff.

Using Merkle Trees for Bulk transfers in Ethereum

Merkle Trees have become more popular than ever in the last decade for their heavy use in the crypto world. Most Blockchain implementations rely on this data structure for validating transactions as part of the consensus protocols.

What is a Merkle tree exactly? 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.

alt

If the hash in one of the nodes is changed, the resulting tree and Merkle Root are also changed. This is an essential factor for one of the scenarios we will discuss in this article, bulk transfers.

The use of Merkle Trees for Bulk Transfers

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 giving 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.

This article will show you how to implement this with Solidity for a Betting scenario.

Anatomy of the Betting Smart Contract

The implementation of our Smart Contract uses the OpenZeppelin Contract Library and MerkleProof utility. It's a contract for betting on a match with two teams, team one and team two.

This is how the contract looks like

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

Let's discuss different sections of it in detail.

import "@openzeppelin/contracts/access/Ownable.sol";
import {MerkleProof} from "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

This imports the OpenZeppelin Ownable contract and the MerkleProof utility. You must previously install those dependencies by running NPM install "@openzeppelin/contracts" --save-dev. Our contract references the Ownable contract as we will use the onlyOwner condition in some methods. 

contract Betting is Ownable {
  event GainsClaimed(address indexed _address, uint256 _value);

The contract will emit an event GainsClaimed when someone with valid proof claims the gains. 

function setMerkleRoot(bytes32 root, uint8 team) onlyOwner public 
  {
    merkleRoot = root;
    winner = team;
  }

This is the method that we will call when the match finishes. We will pass the Merkle root computed from a tree with all the addresses that bet on the winner. We also pass the winner team. Also, note that this method is marked with the onlyOwner condition, so only the contract owner can set the root.

function getPlayersBetOne() public view returns(address[] memory) {
    return playersBetOne;
  }

  function getPlayersBetTwo() public view returns(address[] memory) {
    return playersBetTwo;
  }

These two methods return a list of the addresses that bet on each team. We will use these lists to compute the Merkle Tree. As these are views, they don't cost anything; they are simply resolved in our local ETH node. 

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

The method for betting on a team accepts the team as an argument and does two things,

  1. Push the address on the correct list (Team A or Team B)
  2. Increases the total amount for the bet associated with the contract
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);
  }
}

Finally, the method for claiming the gains on the game. This method requires proof, which was previously computed from a Merkle tree containing all the addresses in the winner's list. If someone passes an invalid proof, or a proof calculated from some other tree, the method will validate that and reject the call.

require(proof.verify(merkleRoot, keccak256(abi.encodePacked(msg.sender))), "You are not in the list");

This method uses the following formula to distribute the gains.

uint256 total = senderBet + ((senderBet / totalWinners) * totalLosers);

Generating the Merkle Tree

We will be using the merkletreejs and keccak256 from node.js with a Hardhat test suite to test our contract.

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

The code above deploys the contract and stores a few addresses provided by Hardhat in local variables so we can reference them later on in the tests.

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

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, the 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.

The complete code is available in my github repository "merkletrees-smartcontracts"