Tree hashing mode

Development and Technical Discussion
1

Saw this -
https://news.ycombinator.com/item?id=16572793

Linked to a paper talking about “tree hashing” -

The blake2 docs also talk about “tree hashing” here -
https://blake2.net/

BLAKE2 offers these algorithms tuned to your specific requirements, such as keyed hashing (that is, MAC or PRF), hashing with a salt, updatable or incremental tree-hashing, or any combination thereof.

Currently in the Grin MMR implementation we simply concatenate two nodes together and hash the result. We also include the position of the leaf element in the MMR as part of the value being hashed.
The links above suggest there may be a better way of doing this (or at least a standard way?) in a tree like structure?

Seems like something that may be worth exploring and investigating some more.

1 Like
2

Yes, definitely worth a read, adding it to my list.

3

The more I think about this the less convinced I am that we are doing anything “wrong” here.
This “tree hashing mode” seems to be more around how the hash the “full message” which in our case is the entire set of outputs (in the output MMR for example).
And less around exactly how to hash the individual nodes (the parts of the broken up message, or the individual outputs in this example).

Either way - I need to read through this again, fee like I’m not fully understanding it just yet.

4

My guts tell me the positions in the MMR make it pretty strong because they represent a unique MMR configuration, with leaves having positions that parents can’t have and vice versa.