Customize leaf hash function

[artemstrpcv]

merkle-tree/src/standard.ts

Line 9 in b3d9889

function standardLeafHash<T extends any[]>(value: T, types: string[]): Bytes {

In the provided example, the desired algorithm for getting leaves is:

bytes32 leaf = keccak256(bytes.concat(keccak256(abi.encode(addr, amount))));

And this works perfectly fine when there is more than 1 value inside the leaf.

However, when the value inside the leaf is singular, then there is no need for extra concat and keccak256, it only makes gas overhead. And the preferred algorithm is:

bytes32 leaf = keccak256(abi.encodePacked(addr));

This makes make a big difference because there is no possibility to change the leaf algorithm that this library uses, hence all trees and proofs for them can't be synced with the contract's behavior.

[frangio]

However, when the value inside the leaf is singular, then there is no need for extra concat and keccak256

This is not necessarily true. The reason the leaf is double-hashed is to mitigate second preimage attacks. If the leaf is a single bytes32 value the tree is likely vulnerable to those attacks, so I would say those are in fact the cases when it is particularly necessary to do double hashing.

If the singular value is an address and you use encodePacked then the tree is not vulnerable and you could omit the double hash.

The issue is not that standardLeafHash works incorrectly, it's that you want a different leaf hashing algorithm.

[Amxx]

Want to bring that up.

I think we should support cases where:

• leaves are Bytes (instead of any[])
• types is undefined

In that case, we check that the leaves are all 32 bytes, and we use them directly, without any hashing.

This will add support for leaves that are produced using a "non standard hash"

[frangio]

I think customizing the leaf hash (including unhashed leaves) conflicts with the concept of "Standard" Merkle Tree that this class intends to implement. It makes me think that it should remain standard, and at most give a few preset options for hashing. However, using the core API directly is a lot more cumbersome so I see the point in a nicer wrapper with an interface like StandardMerkleTree. There could be a base MerkleTree class with the nice API for that.

Something like this?

type Hasher = <T>(leaf: T, encoding: E) => Bytes;

export class MerkleTree<T, E> {
  static of<T, E>(values: T[], leafEncoding: E, hasher: Hasher<T, E>) {
    ...
  }

  ...
}

leafEncoding and hasher could be optional arguments to support passing pre-hashed leaves but I wouldn't do that. It can always be done by just passing in the identity function as the "hasher".

[Amxx]

I did make a local branch with

type LeafLike = any[] | BytesLike;
type Encoding<T extends LeafLike> = T extends any[] ? string[] : undefined;

export class MerkleTree<T extends LeafLike> {
    static of<T, E>(values: T[], leafEncoding: Encoding<T>) {
        ...
    }
}

And a hashing function that does:

• double hashing (like today) if T extends any[]
• check that the value is 32 bytes long, and pass it through with no modification if T is BytesLike

[Amxx]

My issue with the hasher, is that I'm not sure there is a way to dump it / load it.

We would rely on the loading part getting the correct hasher as an argument (we could rehash all the leafs to check its correct ... or disable the hashLeaf function after construction)

[frangio]

My issue with the hasher, is that I'm not sure there is a way to dump it / load it.

Ah, that's true. This would be a point in favor of supporting a predefined set of options. 'double' | 'single' | 'passthrough'

[Amxx]

#36 provides a SimpleMerkleTree that support can be used for that. Users of the SimpleMerkleTree are responsible of doing the hasing themselves.