Add method to generate Merkle root from leaves

[cwhinfrey]

🧐 Motivation

Generate Merkle roots from leaves on-chain

📝 Details It would be nice to have a method for generating a Merkle root from leaves like this one.

Has this been discussed before?

[Amxx]

Hello @cwhinfrey

That is an interesting idea. We've never seen the usecase for it, but that doesn't mean it doesn't exist.

[frangio]

This sounds useful. Can you share some of the use cases you have in mind? Is the linked function exactly what you're looking for or is there something you would change?

@Amxx You shared some concerns about when the list length is not a power of 2. According to the docs of the linked code the list is extended to a power of 2 with "zero hashes" (not clear what this means), and there is also a security caveat that I don't understand. Is this related to the concerns you have?

[Amxx]

Yes.

If the list is padded with 0 values, then everything becomes easy, but then you can also prove that 0 is in the tree, even if it's not one of the leaves.

In some cases it might be fine, but in others it might create an attack vector.

[frangio]

@Amxx Is this the same as https://github.com/OpenZeppelin/openzeppelin-contracts/pull/3617? Or is that necessarily for storage, whereas this issue could refer to building a root in memory?

[Amxx]

The two are différent things.

[Amxx]

This is:

Given a set of leaves, build the merkle root in memory. Its easy if the number of leaves is a power of 2.

#3617 is:

Given a stream of leaves that fill a tree of given depth D from left to right, we maintain a history of the last N merkle roots in storage.