Hacker News Reader

Comment by xpe | Hacker News Reader

For those in the know... Do you have any recommended reading for Merkle-curious people that may have some scars from blockchain-related hype? It would be nice to find a nice introductory resource that covers some interesting use-cases that may not be well-known. Perhaps with nice graphics, interactivity, etc.?

For example, here is a slick web site that shows how certificate transparency uses Merkle trees: https://certificate.transparency.dev/howctworks/

View on HN

The joke is there are two kinds of distributed systems: Spanner and Bitcoin.

I'm currently exploring how different APIs compute ETags [1]. I'm inclined to think the overhead of Merkle-trees make them relatively less useful for ETags for paginated APIs where responses are small and flat hashing is fast. One rule of thumb would be: the overhead isn't justified unless you need either (a) efficient updates on very large collections, or (b) collection-level state tracking across pagination boundaries. Sound about right?

[1]: https://developer.mozilla.org/en-US/docs/Web/HTTP/Reference/...

Also, ETags can use weak validators:

> W/ (case-sensitive) indicates that a weak validator is used. Weak ETags are easy to generate, but are far less useful for comparisons. Strong validators are ideal for comparisons but can be very difficult to generate efficiently. Weak ETag values of two representations of the same resources might be semantically equivalent, but not byte-for-byte identical. This means weak ETags prevent caching when byte range requests are used, but strong ETags mean range requests can still be cached.

I'm working on a project where I need to prove that a file in a git repo is append only, ie all changes to the file only added lines. The only way I can think of is looking at the git history of the file, but would there be a faster way using Merkel trees somehow?

Is this trying to deal with that git history can be replaced?

We handle the case to prevent git history rewrites, but an alternative solution could be adopted if less cumbersome.

There are use-cases outside of "crypto" for blockchain - notably for security related use-cases such as historization ; tough I concede that use-case can be handled with more standard technologies it is very fun to get into it and study such use as it may have properties that could be interesting. One has to have some time for this but to be frank it's not really something super hard to pull-off (Bc itself conceptually)

I think the question, certainly the question I have - is, what are some use cases outside of "crypto" and the CT log ?

Git and other vcs are generally built on merkle-trees for consistent hashing.

There's a list of other common hashing cases on the Wikipedia entry: https://en.wikipedia.org/wiki/Merkle_tree#Uses

You can make use of merkle-trees when ever you want to proof the data integrity of large amounts of individually independent data (distributed FS etc). After playing arround with SMTs for a bit, possible use-cases came to mind quite frequently.

The challenge to me is that the ability to prove the data integrity is quite hard once you store the data elsewhere, particularly on a single disk - I don’t know that people are regularly reading and reevalidating the stored data and likely not on every I/o operation.

Reply on news.ycombinator.com