8 ms·
How Merkle Trees Enable the Decentralized Web
- basemi 9y agoA similar concept (Merkle-DAG) is implemented by IPFS (ipfs.io) "A Merkle-DAG is similar to a Merkle tree in that they both are essentially a tree of hashes. A Merkle tree connects transactions by sequence, but a Merkle-DAG connects transactions by hashes. In a Merkle-DAG, addresses are represented by a Merkle hash. This spider web of Merkle hashes links data addresses together by a Merkle graph. The directed acyclic graph (DAG) is used to model information. In our case, modeling what address has stored specific data. " (https://www.cio.com/article/3174193/healthcare/from-medical-records-to-merkle-trees-with-ipfs.html https://www.cio.com/article/3174193/healthcare/from-medical-...)
- EGreg 9y agoWhy can't there be cycles in the Merkle graph That would be cool. You just have a partial order between children and parents, like in git.
- glic3rinu 9y agoYou would need to know the hash of a yet-to-exist node to create cycles on a Merkle graph :)
- deleted 9y ago[deleted]
- eternalban 9y agoIt is really not that different than the 'Grandfather Parsdox': Merkel graphs are inherently 'causal sequences' and when combined with nodes as 'spaces of things' they define the evolving manifold of a 'world of things'. This seems to inform a sort of deep structure in our reality manifesting in phenomena such as Golden Section, etc. [speculaing at the end there, of course.]
- deleted 9y ago[deleted]
- tolmasky 9y agoThis is a good paper that covers hashing graphs (including ones with cycles): "On Hashing Graphs" https://eprint.iacr.org/2012/352.pdf https://eprint.iacr.org/2012/352.pdf
- EGreg 9y agoWow, very interesting. Can you summarizd how the actual algorithm is supposed to work, ie its main ideas? I am surprised to find that using sha hashes in a tree or DAG will leak information to people who shouldn't have it. Is this a serious flaw and how do these guys ultimately solve the problem? I read the paper but the algorithm seems a bit hard to understand and follow.
- zardo 9y agoConsider the simplest cycle, a node that points to itself. To create it, you must include the content hash of the document in the document itself. To do that, you need to generate a collision. You enter a random content hash in the document, then keep modifying the document and hashing it untill it's hash matches the one you included. It's not impossible, but depending on the hash function, it may take you a very long while to find it.
- abrax3141 9y agoIt’s not so much the M-trees that make this work, as the idea of distributing the leaves around so that you can’t efficiently corrupt the tree by replacing it. If it was all in one machine you could just fake the tree. According to the original bitcoin paper, this idea came from Haber and Stornetta. (I have a personal theory that Stornetta is Satoshi ... who doesn’t reference their own papers multiple times?!)
- skate22 9y agoGood article, but there are a lot of claims of '100% certainty' that arn't necessarily true. The author even states that hash functions only guarentee no collisions to a high probability.
- DennisP 9y agoIt looks like there are about as many Earth-like planets in the universe as grains of sand on the Earth. Write your name on a grain of sand on one of those planets. Now have someone else randomly pick a single grain of sand from some planet in the universe. How certain are you that they won't pick yours? The chance of that happening is roughly equal to the chance of a collision randomly occurring somewhere in a few quadrillion SHA256 hashes. https://crypto.stackexchange.com/questions/52261/birthday-attack-against-sha256 https://crypto.stackexchange.com/questions/52261/birthday-at... http://www.npr.org/sections/krulwich/2012/09/17/161096233/which-is-greater-the-number-of-sand-grains-on-earth-or-stars-in-the-sky http://www.npr.org/sections/krulwich/2012/09/17/161096233/wh... https://www.cnet.com/news/the-milky-way-is-flush-with-habitable-planets-study-says/ https://www.cnet.com/news/the-milky-way-is-flush-with-habita...
- SimeVidas 9y agoMerkel tries to do what? Ah, Merkle trees, never mind.
- indigochill 9y agoFrom a dumb layman's perspective (mine), it seems as though the addressing issue has a very simple solution: to refer to some arbitrary file which is hosted by some known third-party (say, a video on YouTube), provide a link to it from your server and distribute the link to that link to others. When switching from YouTube to Vimeo, simply change the one link on your server and the link you distributed remains valid. This also avoids the danger of hash collisions, although it is vulnerable to third-party hosts taking down the content (although again, there's not much cost to that. Just move the content elsewhere and change your redirect link). With this method you do still have some server responsible for hosting the content rather than distributing that load, but that's actually a saving when looking at the storage load across the entire ecosystem. It's a cool article and I really like the idea of content addressing instead of host addressing. I just feel like it's too divergent from the web as most people use it today (and I'm mildly concerned about malicious hash shenanigans), whereas the above method can be used and understood right now by many web users.
- api 9y agoHash collisions are really a non-issue. A collision in SHA-256 or larger spaces is less likely than being, say, struck by a meteorite twice in one day. When you get up to 384 and 512 bit hashes you could content address the entire Internet for thousands of years and likely never have a collision.
- dracodoc 9y agoOr you can go one step further, use third party server to provide the link, because it's a burden to maintain your own server for many people. "Your server" is most likely somebody else's server anyway. That will be google voice for url. The OP's method is use people's name as phone number. Another problem with OP's method is that it's difficult to read for human, and very difficult to verify by eye. There is also no common parts for files organized in same hierarchy.
- ENGNR 9y agoCDN's have made hosting pretty easy to scale from a low powered controller, the hard problem is working out when to invalidate the cache. Which is easily solved by.... another layer of merkle trees actually! It's Angela Merkel's all the way down
- dracodoc 9y agoTo rephrase my comment: Some disadvantage of OP's method: - hash code is difficult to read for human. Urls under some hierarchy share some common patterns, it also bear some meanings. All hash code will look same and have nothing to hint on the content. - You have to copy it, almost impossible to type it, or compare two visually similar string. - You may end up with some link shortening service for hash code, but you can use link shortening to solve the portable file host problem already. The Merkle Trees can solve some problems, but I don't think portable urls are the right one.
- subless 9y agoI agree 100%. Also, Merkle Trees would only benefit static content uploaded to the Internet. Updating any dynamic content would constantly generate a new root hash meaning a new URL with each update to that specific content. It's just not a good option for anything other than static content in general. One place I could see it being valuable is with an online archiving type service like Archive.org where the content doesn't change except when a new snapshot of that content is recorded displaying any changes made to that content.
- um304 9y agoExactly! Editing content is the elephant in the room which author didn't even address
- tbv 9y agoIt was only a 10 minute talk, so I had to cut something out ;) Blahah’s comment above may interest you: https://news.ycombinator.com/item?id=15541392 https://news.ycombinator.com/item?id=15541392
- notheguyouthink 9y agoEditing is easy, fwiw - content hashes are immutable and are not to be used for mutable content (obviously). That's why IPFS has IPNS - so we can have mutable pointers to data.
- 9y ago
- yosito 9y agoCan someone ELI5 what happens when I want to change a piece of data in a tree? What if I have a document, and I notice a typo, and I want to fix it?
- tbv 9y agoNot quite ELI5, but Blahah explained how Dat handles changes below: https://news.ycombinator.com/item?id=15541392 https://news.ycombinator.com/item?id=15541392
- toomim 9y agoExactly. Then merkle trees don't help you. They only work for static documents.
- letlambda 9y agoThey certainly don't make that easier. But if the system supports a mutable link, you can have documents that always link to their own latest version. IPFS does this by storing (mutable link, contentID) pairs in the DHT, which can be updated if you know the private key for the mutable link.
- pfraze 9y agoletlambda's explanation for IPFS is right. In Dat, that method is used to produce an append only log out of a merkle tree. Each time you add an entry, a leaf is added to the tree, and the new head is signed. I wrote about it here [1] and have some gifs demonstrating the process. Merkle trees can work just fine for dynamic content. You just need to use a pubkey pointer. 1. https://beakerbrowser.com/2017/06/19/cryptographically-secure-change-feeds.html https://beakerbrowser.com/2017/06/19/cryptographically-secur...
- nattmat 9y agoBy using an append-only Merkle tree, you make 'edits' by adding a new piece of data with information on what was changed in the older data. You get the benefit of also keeping a version history. I think Git works like this.
- asadlionpk 9y agoVideo link of the talk if anyone wants: https://youtu.be/wGB5AYvFjxE?t=4h26m30s https://youtu.be/wGB5AYvFjxE?t=4h26m30s
- peterwwillis 9y ago> The Web is centralized, It isn't. > but why? "The web" is a collection of independent networks providing a means to traverse hyperlinked text documents across any network that is addressable. Not only are servers not a problem, host-based addressing is what makes the web work at all, as numerical addressing by itself would have killed the web's growth long ago, and users would have no reasonable way to address content.
- pfraze 9y agoYou're ignoring the data silo problem. Of course the Web is decentralized in terms of accessing web pages, but-- the majority of data is not composed of pages, and the majority of actions on the Web are not composed of hyperlink traversals. For the applications on the Web to be decentralized, the data and behaviors have to be decentralized as well, and they are not.
- peterwwillis 9y agoThe majority of data is composed of pages, but the biggest uses of the web today are not. The web isn't the web anymore. It's a shitty application platform. In this sense, the web works exactly how any application platform does. You can't get content out of old apps, or apps that no longer run, or on systems that no longer run. This isn't data siloing, this is just legacy applications. With web apps the data is siloed, but it doesn't have to be, and didn't used to be. The Internet Archive is proof. Getting the data out isn't that difficult, IF it 's not hiding behind a web app. The difficult part is to convince people to stop writing applications which are siloed and do prevent easy access to content that the web used to provide. Peer to peer networks are not a solution to incompatible legacy applications. It's like a vehicle which is immobile when it runs out of gas. Instead of building the vehicle so it can still be used when it lacks power, they're changing the way the roads work. It's ridiculous.
- pfraze 9y agoYou can't just wish that people would build apps a different way though, right? You have to change the system somehow. So, this is how we're doing it. No legacy support, but it does have interesting new use-cases that can disrupt the legacy.