Tally Merkle Tree generator

The diff from this to the OZ standard is leafHashing method.

we at tally had to make this small change to use in our product the DAO Launcher

A JavaScript library to generate merkle trees and merkle proofs.

Well suited for airdrops and similar mechanisms in combination with OpenZeppelin Contracts MerkleProof utilities.

Quick Start

npm install @tallyxyz/merkle-tree

Building a Tree

import { StandardMerkleTree } from "@tallyxyz/merkle-tree";
import fs from "fs";

// (1)
const values = [
  ["0x1111111111111111111111111111111111111111", "5000000000000000000"],
  ["0x2222222222222222222222222222222222222222", "2500000000000000000"]
];

// (2)
const tree = StandardMerkleTree.of(values, ["address", "uint256"]);

// (3)
console.log('Merkle Root:', tree.root);

// (4)
fs.writeFileSync("tree.json", JSON.stringify(tree.dump()));

1. Get the values to include in the tree. (Note: Consider reading them from a file.)
2. Build the merkle tree. Set the encoding to match the values.
3. Print the merkle root. You will probably publish this value on chain in a smart contract.
4. Write a file that describes the tree. You will distribute this to users so they can generate proofs for values in the tree.

Obtaining a Proof

Assume we're looking to generate a proof for the entry that corresponds to address 0x11...11.

import { StandardMerkleTree } from "@tallyxyz/merkle-tree";
import fs from "fs";

// (1)
const tree = StandardMerkleTree.load(JSON.parse(fs.readFileSync("tree.json", "utf8")));

// (2)
for (const [i, v] of tree.entries()) {
  if (v[0] === '0x1111111111111111111111111111111111111111') {
    // (3)
    const proof = tree.getProof(i);
    console.log('Value:', v);
    console.log('Proof:', proof);
  }
}

1. Load the tree from the description that was generated previously.
2. Loop through the entries to find the one you're interested in.
3. Generate the proof using the index of the entry.

In practice this might be done in a frontend application prior to submitting the proof on-chain, with the address looked up being that of the connected wallet.

Validating a Proof in Solidity

Once the proof has been generated, it can be validated in Solidity using MerkleProof as in the following example:

pragma solidity ^0.8.4;

import "@openzeppelin/contracts/utils/cryptography/MerkleProof.sol";

contract Verifier {
    bytes32 private root;

    constructor(bytes32 _root) {
        // (1)
        root = _root;
    }

    function verify(
        bytes32[] memory proof,
        address addr,
        uint256 amount
    ) public {
        // (2)
        bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(addr, amount))));
        // (3)
        require(MerkleProof.verify(proof, root, leaf), "Invalid proof");
        // (4)
        // ...
    }
}

1. Store the tree root in your contract.
2. Compute the leaf hash for the provided addr and amount ABI encoded values.
3. Verify it using MerkleProof's verify function.
4. Use the verification to make further operations on the contract. (Consider you may want to add a mechanism to prevent reuse of a leaf).

Standard Merkle Trees

This library works on "standard" merkle trees designed for Ethereum smart contracts. We have defined them with a few characteristics that make them secure and good for on-chain verification.

• The tree is shaped as a complete binary tree.
• The leaves are sorted.
• The leaves are the result of ABI encoding a series of values.
• The hash used is Keccak256.
• The leaves are double-hashed[^1] to prevent second preimage attacks.

Leaf Hash

From the last three points we get that the hash of a leaf in the tree with value [addr, amount] can be computed in Solidity as follows:

// bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(addr, amount))));
bytes32 leaf = keccak256(abi.encodePacked(_user, _amount));

This is an opinionated design that we believe will offer the best out of the box experience for most users. We may introduce options for customization in the future based on user requests.

API & Examples

StandardMerkleTree

import { StandardMerkleTree } from "@tallyxyz/merkle-tree";

StandardMerkleTree.of

const tree = StandardMerkleTree.of([[alice, '100'], [bob, '200']], ['address', 'uint']);

Creates a standard merkle tree out of an array of the elements in the tree, along with their types for ABI encoding. For documentation on the syntax of the types, including how to encode structs, refer to the documentation for Ethers.js's AbiCoder.

Note Consider reading the array of elements from a CSV file for easy interoperability with spreadsheets or other data processing pipelines.

StandardMerkleTree.verify

const verified = StandardMerkleTree.verify(root, ['address', 'uint'], [alice, '100'], proof);

Returns a boolean that is true when the proof verifies that the value is contained in the tree given only the proof, merkle root, and encoding.

StandardMerkleTree.verifyMultiProof

const isValid = StandardMerkleTree.verifyMultiProof(root, leafEncoding, multiproof);

Returns a boolean that is true when the multiproof verifies that all the values are contained in the tree given only the multiproof, merkle root, and leaf encoding.

StandardMerkleTree.load

StandardMerkleTree.load(JSON.parse(fs.readFileSync('tree.json', 'utf8')));

Loads the tree from a description previously returned by tree.dump.

tree.root

console.log(tree.root);

The root of the tree is a commitment on the values of the tree. It can be published (e.g., in a smart contract) to later prove that its values are part of the tree.

tree.dump

fs.writeFileSync('tree.json', JSON.stringify(tree.dump()));

Returns a description of the merkle tree for distribution. It contains all the necessary information to reproduce the tree, find the relevant leaves, and generate proofs. You should distribute this to users in a web application or command line interface so they can generate proofs for their leaves of interest.

tree.getProof

const proof = tree.getProof(i);

Returns a proof for the ith value in the tree. Indices refer to the position of the values in the array from which the tree was constructed.

Also accepts a value instead of an index, but this will be less efficient. It will fail if the value is not found in the tree.

const proof = tree.getProof([alice, '100']);

tree.getMultiProof

const { proof, proofFlags, leaves } = tree.getMultiProof([i0, i1, ...]);

Returns a multiproof for the values at indices i0, i1, .... Indices refer to the position of the values in the array from which the tree was constructed.

The multiproof returned contains an array with the leaves that are being proven. This array may be in a different order than that given by i0, i1, ...! The order returned is significant, as it is that in which the leaves must be submitted for verification (e.g., in a smart contract).

Also accepts values instead of indices, but this will be less efficient. It will fail if any of the values is not found in the tree.

const proof = tree.getProof([[alice, '100'], [bob, '200']]);

tree.verify

tree.verify(i, proof);
tree.verify([alice, '100'], proof);

Returns a boolean that is true when the proof verifies that the value is contained in the tree.

tree.verifyMultiProof

tree.verifyMultiProof({ proof, proofFlags, leaves });

Returns a boolean that is true when the multi-proof verifies that the values are contained in the tree.

tree.entries

for (const [i, v] of tree.entries()) {
  console.log('value:', v);
  console.log('proof:', tree.getProof(i));
}

Lists the values in the tree along with their indices, which can be used to obtain proofs.

tree.render

console.log(tree.render());

Returns a visual representation of the tree that can be useful for debugging.

tree.leafHash

const leaf = tree.leafHash([alice, '100']);

Returns the leaf hash of the value, as defined in Standard Merkle Trees.

Corresponds to the following expression in Solidity:

// bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(alice, 100))));
bytes32 leaf = keccak256(abi.encodePacked(_user, _amount));

[^1]: The underlying reason for hashing the leaves twice is to prevent the leaf values from being 64 bytes long prior to hashing. Otherwise, the concatenation of a sorted pair of internal nodes in the Merkle tree could be reinterpreted as a leaf value. See here for more details.