Follow

Okay pinned it to read it later, seems to be a tiny goldmine team.inria.fr/wide/publication

· · Web · 1 · 0 · 1

Ahhh, I can't just not read it, it's funny how it's close to a toy implementation I did to also replicate efficiently a large kv database

Yet I didn't knew what was merkle tree then :blobcatExtremeJoy: I guess I miss a lot of studying in the field lmao

Honestly friends interested in replicated kv/databases might be interested in this hal.inria.fr/hal-02303490

New paper to have fun with 😵

"Merkle Hash Grids Instead of Merkle Trees"
www2.cs.uh.edu/~paris/MYPAPERS

On a sidenote, about the "Merkle Search Tree", some IPFS person took the idea in the paper and is trying a kinda crazy project

github.com/mikeal/IPSQL

@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. :blobshrug:

Sign in to participate in the conversation
RaRuRe

It's pronounced ʁaʁyʁe. And written RaRuRe, or R3 for short.
You can find more infos on this place by clicking there.