13 ms·

People keep saying Merkle DAGs when someone calls a linear chain of recursively hashed data blocks a blockchain. I don’t understand. My understanding of the M

People keep saying Merkle DAGs when someone calls a linear chain of recursively hashed data blocks a blockchain. I don’t understand. My understanding of the Merkle Tree is that it’s a recursive hash, but the leaf nodes are the data, each layer up the tree is the hash of the child nodes. In a merkle tree, only the leaf nodes store (or reference) data, everything else is just a hash. Is there another merkle structure I don’t know about? https://en.wikipedia.org/wiki/Merkle_tree https://en.wikipedia.org/wiki/Merkle_tree If the nodes with hashes contain data, it’s not a merkle tree.

tedunangst 3y ago
I think this is isomorphic to an unbalanced tree where every node has one non leaf child and one leaf child.
- r3trohack3r 3y ago
  Seems like claiming that a linked list isn't actually a linked list it’s an unbalanced tree where every node has one child node. I mean, you’re not wrong but it’s still a linked list. I’d be careful muddying up your mental models this way though - they’re distinct data structures for distinct purposes. You would likely not want to use a merkle tree for an append only log, and likely would not want to use a blockchain for verifying file integrity. For example, BitTorrent, IPFS, and Storj use merkle trees to verify and discover blocks on the DHT, you would not want to use a blockchain for this. And Scuttlebutt uses a blockchain as an append only log that is gossip friendly, you would not want to use a merkle tree for this.
r3trohack3r 3y ago
Since posting this, I've discovered that IPFS has something it calls Merkle-DAGs. A Block-Chain is a chain of blocks where there is one valid previous block and one valid next block. A Block-Tree is a chain of blocks where there is one single valid previous block, and multiple valid next blocks. A Block-DAG is a chain of blocks where there are multiple valid next blocks and multiple valid previous blocks, with the constraint that you can not form cycles. They are analogues to linked-lists, trees, and directed-acyclic-graphs but with chained hashes. From the Merkle-DAG article on the IPFS page: > Merkle DAGs are similar to Merkle trees, but there are no balance requirements, and every node can carry a payload. In DAGs, several branches can re-converge or, in other words, a node can have several parents. What's interesting here is that a Merkle Tree is a valid Merkle DAG, since a node can _optionally_ include a data payload. So a blockchain, a blocktree, and a blockdag are all also Merkle-DAGs. Merkle-DAG is a kind of unifying structure that can be used to model all of them. It's really quite clever. https://docs.ipfs.tech/concepts/merkle-dag/ https://docs.ipfs.tech/concepts/merkle-dag/ This appears to have been coined in 2014: https://github.com/jbenet/random-ideas/issues/20 https://github.com/jbenet/random-ideas/issues/20 However the term blockchain dates back to at least 2008. A blockchain might be a Merkle-DAG but a Merkle-DAG is not a blockchain.
- deleted 3y ago
  [deleted]

tedunangst 3y ago

I think this is isomorphic to an unbalanced tree where every node has one non leaf child and one leaf child.

r3trohack3r 3y ago
Seems like claiming that a linked list isn't actually a linked list it’s an unbalanced tree where every node has one child node. I mean, you’re not wrong but it’s still a linked list. I’d be careful muddying up your mental models this way though - they’re distinct data structures for distinct purposes. You would likely not want to use a merkle tree for an append only log, and likely would not want to use a blockchain for verifying file integrity. For example, BitTorrent, IPFS, and Storj use merkle trees to verify and discover blocks on the DHT, you would not want to use a blockchain for this. And Scuttlebutt uses a blockchain as an append only log that is gossip friendly, you would not want to use a merkle tree for this.

r3trohack3r 3y ago

Since posting this, I've discovered that IPFS has something it calls Merkle-DAGs. A Block-Chain is a chain of blocks where there is one valid previous block and one valid next block. A Block-Tree is a chain of blocks where there is one single valid previous block, and multiple valid next blocks. A Block-DAG is a chain of blocks where there are multiple valid next blocks and multiple valid previous blocks, with the constraint that you can not form cycles. They are analogues to linked-lists, trees, and directed-acyclic-graphs but with chained hashes. From the Merkle-DAG article on the IPFS page: > Merkle DAGs are similar to Merkle trees, but there are no balance requirements, and every node can carry a payload. In DAGs, several branches can re-converge or, in other words, a node can have several parents. What's interesting here is that a Merkle Tree is a valid Merkle DAG, since a node can _optionally_ include a data payload. So a blockchain, a blocktree, and a blockdag are all also Merkle-DAGs. Merkle-DAG is a kind of unifying structure that can be used to model all of them. It's really quite clever. https://docs.ipfs.tech/concepts/merkle-dag/ https://docs.ipfs.tech/concepts/merkle-dag/ This appears to have been coined in 2014: https://github.com/jbenet/random-ideas/issues/20 https://github.com/jbenet/random-ideas/issues/20 However the term blockchain dates back to at least 2008. A blockchain might be a Merkle-DAG but a Merkle-DAG is not a blockchain.

deleted 3y ago
[deleted]