Okay pinned it to read it later, seems to be a tiny goldmine https://team.inria.fr/wide/publications/
New paper to have fun with 😵
"Merkle Hash Grids Instead of Merkle Trees"
On a sidenote, about the "Merkle Search Tree", some IPFS person took the idea in the paper and is trying a kinda crazy project
@Miaourt Ignoring any of the performance benefits that the paper claims (because I've yet to see a system where Merkle tree construction or verification is anywhere close to a bottleneck), and from a quick glance, the primary claimed benefit of Merkle Grids is that they require less space.
But that assumes that you store and transfer all intermediate nodes of the Merkle tree... does anyone even do that, when all you need to construct the full tree is just the leaf nodes? (outside of incremental tree construction schemes, which Grids don't seem to support at all?)
@ayo well, half the space is kinda a good claim imho, and calculation of hashes can be expensive too I guess (so half less is better ?)
In the context of "diffing trees" to efficiently compare two dataset and merge differences, I hope it can be used :3
@Miaourt I mean, calculating intermediate hash nodes is incredibly cheap, as you just hash two hashes for each node (=64 bytes)?
The half the space claim *only* applies if you store the full tree, but as I mentioned, you rarely have to do that because it's so cheap to construct on demand. In fact, hashing might even be cheaper than accessing the tree from memory.
It's pronounced ʁaʁyʁe.
And written RaRuRe, or R3 for short.
You can find more infos on this place by clicking there.