MerkleProofs.sol

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

// Distribute ether to a group of addresses using a merkle proofs.
contract MerkleDrop {
    // The root of the merkle tree, generated by constructTree().
    bytes32 public immutable ROOT;

    // Whether a member has claimed their drop.
    // Note this assumes each members is only eligible for a single drop, i.e.,
    // they occur in the merkle tree only once.
    mapping (address => bool) public hasClaimed;

    constructor(bytes32 root) payable {
        ROOT = root;
    }

    // Given a leaf hash in a merkle tree and a list of sibling hashes/nodes,
    // attempt to arrive at the root hash, returning true if we got there.
    function prove(bytes32 leaf, bytes32[] memory siblings) public view returns (bool) {
        // In a sparse tree, empty leaves have a value of 0, so don't allow 0 as input.
        require(leaf != 0, 'invalid leaf value');
        bytes32 node = leaf;
        for (uint256 i = 0; i < siblings.length; ++i) {
            bytes32 sibling = siblings[i];
            node = keccak256(
                // Siblings are always hashed in sorted order.
                node > sibling ? abi.encode(sibling, node) : abi.encode(node, sibling)
            );
        }
        return node == ROOT;
    }

    // Claim a drop on behalf of a member, given a proof that their claim belongs
    // to the merkle tree.
    function claim(
        address payable member,
        uint256 claimAmount,
        bytes32[] memory proof
    )
        external
    {
        require(!hasClaimed[member], 'already claimed');
        // Security note: Leaf hashes are inverted to prevent second preimage attacks,
        // i.e., passing in intermediate node values (subtree hashes) for member and
        // claimAmount.
        require(prove(~keccak256(abi.encode(member, claimAmount)), proof), 'bad proof');
        hasClaimed[member] = true;
        member.transfer(claimAmount);
    }
}

// Utils for generating merkle trees and proofs. Normally this would be implemented
// off-chain.
contract MerkleDropHelper {
    // Construct a sparse merkle tree from a list of members and respective claim
    // amounts. This tree will be sparse in the sense that rather than padding
    // tree levels to the next power of 2, missing nodes will default to a value of
    // 0.
    function constructTree(
        address[] memory members,
        uint256[] memory claimAmounts
    )
        external
        pure
        returns (bytes32 root, bytes32[][] memory tree)
    {
        require(members.length != 0 && members.length == claimAmounts.length);
        // Determine tree height.
        uint256 height = 0;
        {
            uint256 n = members.length;
            while (n != 0) {
                n = n == 1 ? 0 : (n + 1) / 2;
                ++height;
            }
        }
        tree = new bytes32[][](height);
        // The first layer of the tree contains the leaf nodes, which are
        // hashes of each member and claim amount.
        bytes32[] memory nodes = tree[0] = new bytes32[](members.length);
        for (uint256 i = 0; i < members.length; ++i) {
            // Leaf hashes are inverted to prevent second preimage attacks.
            nodes[i] = ~keccak256(abi.encode(members[i], claimAmounts[i]));
        }
        // Build up subsequent layers until we arrive at the root hash.
        // Each parent node is the hash of the two children below it.
        // E.g.,
        //              H0         <-- root (layer 2)
        //           /     \
        //        H1        H2
        //      /   \      /  \
        //    L1     L2  L3    L4  <--- leaves (layer 0)
        for (uint256 h = 1; h < height; ++h) {
            uint256 nHashes = (nodes.length + 1) / 2;
            bytes32[] memory hashes = new bytes32[](nHashes);
            for (uint256 i = 0; i < nodes.length; i += 2) {
                bytes32 a = nodes[i];
                // Tree is sparse. Missing nodes will have a value of 0.
                bytes32 b = i + 1 < nodes.length ? nodes[i + 1] : bytes32(0);
                // Siblings are always hashed in sorted order.
                hashes[i / 2] = keccak256(a > b ? abi.encode(b, a) : abi.encode(a, b));
            }
            tree[h] = nodes = hashes;
        }
        // Note the tree root is at the bottom.
        root = tree[height - 1][0];
    }

    // Given a merkle tree and a member index (leaf node index), generate a proof.
    // The proof is simply the list of sibling nodes/hashes leading up to the root.
    function createProof(uint256 memberIndex, bytes32[][] memory tree)
        external
        pure
        returns (bytes32[] memory proof)
    {
        uint256 leafIndex = memberIndex;
        uint256 height = tree.length;
        proof = new bytes32[](height - 1);
        for (uint256 h = 0; h < proof.length; ++h) {
            uint256 siblingIndex = leafIndex % 2 == 0 ? leafIndex + 1 : leafIndex - 1;
            if (siblingIndex < tree[h].length) {
                proof[h] = tree[h][siblingIndex];
            }
            leafIndex /= 2;
        }
    }
}