How to verify tries in Solidity?

[alvin854]

I'm looking to generate a Merkle tree in JS and verify proofs on-chain in Solidity. There are Solidity libraries like OpenZeppelin's MerkleProof.sol that let me do so, but I can't find a reliable Merkle library in JS. merkle-patricia-trees seems to be the most reliable, but I can't find any examples on how I would verify tries in Solidity.

With a Merkle tree, each of my objects would look something like this:

{
    address: "0x123",
    token: "0x456",
    amount: "15000000000000000000"
}

...which I would ideally hash with something like web3.utils.soliditySha3(address, token, amount), and pass an array of those leaves to the tree.

Am I correct in thinking that in a trie, the key would be Buffer.from(address) and the value would be Buffer.from('${token}${amount}')? And then how would I verify that in Solidity? Would really appreciate a hand or any resources that I may have overlooked. Thanks.

[ryanio]

Hey there. After setting up your trie, you would use Trie.createProof, and then pass the proof along with the root (Trie.root) and leaf (Buffer.from(address)) to MerkleProof.sol's verify method.

For some examples on how this is done within merkle-patricia-tree, check out test/proof.spec.ts

[alvin854]

Thanks @ryanio. I need to reconstruct the leaf in Solidity to verify that the other arguments passed to the contract function (like amount) are correct before the sender can claim that amount in tokens. With a tree, I'd probably pass address, token, and amount to a contract function that reconstructs the leaf via keccak256(abi.encodePacked(address, token, amount)), and then pass that leaf to MerkleProof.sol's verify with the proof and root.

1. How might you recommend putting an object with multiple values? Would it make sense to trie.put(Buffer.from('${address}${token}'), Buffer.from(amount))?

2. How would I reconstruct a leaf of that key/value in Solidity to align with the root and proof generated by merkle-patricia-tree?

[ryanio]

I found the openzeppelin PR that introduces the MerkleTree.sol contract, that has tests, docs and helpers along with it: OpenZeppelin/openzeppelin-contracts#260

Following this example with their JS MerkleTree helper class, you should be able to modify for your own uses:

  describe("verifyProof", function() {
    it("should return true for a valid Merkle proof", async function() {
      const elements = ["a", "b", "c", "d"];
      const merkleTree = new MerkleTree(elements);

      const root = merkleTree.getHexRoot();

      const proof = merkleTree.getHexProof(elements[0]);

      const leaf = bufferToHex(sha3(elements[0]));

      const result = await merkleProof.verifyProof(proof, root, leaf);
      assert.isOk(result, "verifyProof did not return true for a valid proof");
    });

(link)

So your elements array could be [`${address}${token}${amount}`, ...]

[holgerd77]

@ryanio is this something where we could extract some useful example from for our proof section in the Trie library README? 🤔

[ryanio]

The OP was asking how to verify a merkle tree in solidity and I pointed to OpenZeppelin's MerkleTree.sol contract and their respective JS code.

From OpenZeppelin/openzeppelin-contracts#260:

merkleTree.js contains a helper Merkle tree class that is used to generate Merkle trees, roots and proofs in the JS tests. When generating the Merkle tree, leaves are sorted and pre-images are also pair-wise sorted before being concatenated/hashed to create the parent of a pair of pre-images.

verifyProof in MerkleProof.sol assumes that the Merkle root provided is from a Merkle tree with sorted leaves and pair-wise sorted pre-images.

I am not sure if we do this same sorting in merkle-patricia-tree so our lib might return a different proof? I haven't investigated further.

[holgerd77]

Long period of inactivity and very special topic, somewhat solved with some hints as well, will close.