MerkleTree typescript library

[kerzhner]

From a brief investigation, it seems that off-the-shelf merkle tree libraries might not work for us. Libraries investigated are https://www.npmjs.com/package/merkletreejs and https://www.npmjs.com/package/merkle-tools.

The rough interface that we need is:

// These are placeholders to be defined
type MerkleProof = string;
type MerkleRoot = string

abstract class MekleTree {
  constructor(leaves: string) {}
  abstract get root(): MerkleRoot;
}

type VerifyProof = (root: MerkleRoot, proof: MerkleProof, height: number) => boolean;
type IndexForProof = (proof: MerkleProof) => number;

Our interface requirements are:

• We need to verify a proof given just a root and tree height. merkletreejs library interface is tree.verify(proof, leaf, root). This requires an instance of the tree and a leaf in addition to the proof and the root.
• We need to have the ability to convert proofs to leaf index numbers.

[lalexgap]

I think it makes sense to split this into two parts:

• Merkle related functionality required in the on-chain contract
• Merkle related functionality required in the off-chain client

Off chain client

All the client needs to do is generate proofs. This means we can use any existing merkle tree library that generates us a proof.

@NiloCK has pointed out the merkle proof spec that's part of the ssz spec, which may make sense to implement when we're actually sending the proof to the chain.

In the meantime it's probably fine to use the proof format of whatever library we use, as long as the proof is sparse and easy to parse. The format of the merkle-tools proof seems reasonable.

On Chain Contract

The contract needs to:

• verify a proof with just a root and tree height
• Convert the proof to a leaf index number

For verifying we'll have to write bespoke solidity code to do this eventually. For now it looks like merkle-tools has a validateProof function that just requires the rootHash and the proof and the elementToVerify. Although the validateProof method is a member of the MerkleTree class it can be used to validate a proof from any tree as seen below:

import MerkleTree from 'merkle-tools';
const tree = new MerkleTree({hashType: 'SHA3-256'});

const elements = ['0', '1', '2', '3', '4', '5', '6', '7'];

tree.addLeaves(elements, true);
tree.makeTree();
const proofNode = tree.getLeaf(2)?.toString('hex');
const proof = tree.getProof(2);
const root = tree.getMerkleRoot()?.toString('hex');

const tree2 = new MerkleTree({hashType: 'SHA3-256'});
// I think the typing might be incorrect here.
const isValid = tree2.validateProof(proof as any, proofNode!, root!);
// Will print isValid true
console.log(`isValid: ${isValid}`);

For converting the proof to a leaf index number I think we could write this ourselves. It's relatively easy to calculate the leaf index from the proof.

Selecting a library

Merkle-tools seems to have enough functionality to get us up and running quickly while mostly satisfying the desired interface.

merkletreejs doesn't seem to have a getLeaf function to get a leaf at a given index which is kind of annoying.

I think it makes sense to go with merkle-tools for now and we can re-evaluate when we rewrite the contract code in solidity.

[kerzhner]

Thanks for the great breakdown!