2 ms·

I know Git and Blockchains are said to be examples for (usage of) Merkle trees, but I fail to see how they're actually (using) a merkle tree. Using the hash of

by ascar 7y ago

I know Git and Blockchains are said to be examples for (usage of) Merkle trees, but I fail to see how they're actually (using) a merkle tree. Using the hash of a parent node as input to a nodes hash alongside the nodes data creates a link, but it doesn't create a merkle tree. In a Merkle tree the parent node is the hash of the hashes of its child nodes and only leafes have data. These are entirely different definitions and also serve completely different purposes (linking to a parent node vs efficient lookup of membership of some data in a larger dataset). Could someone clear up my confusion and explain to me where Git/Blockchain use a Merkle tree in their fundamental functionality? Or is the term Merkle tree simply misreferenced a lot?

nebulous1 7y ago
in bitcoin the transactions are the leaves
- ascar 7y ago
  Could you please elaborate how that ends up as a Merkle tree? In a merkle tree the leaves are not linked and they have a tree structure of parent hashes on top. Git and Blockchain nodes are linked and the fundamental architecture doesn't need a tree structure of hashes on top. While this tree structure on top might be useful, it would be an optimization, but not part of the fundamental architecture. Again, what am I missing?
  - nebulous1 7y ago
    This might be complicated by the fact that "merkle trees" and git/blockchain invert the parent/child relationship. The root of the git/blockchain trees changes every time a commit/block is added, and the child nodes are called "parent commits" in git. Also the shape isn't going to have a wide base or be balanced like a binary search tree or similar. When you say that "git and blockchain nodes are linked", I think you might be not abstracting the concepts from the form the data usually takes. For instance in git you might be thinking of a commit as a single package with all its source changes, headers, parent details and hash, but it terms of it being a merkle tree the leaf node would be non-hash parts (source code, non-hash headers etc) and the "tree on top" would be the hashes. This tree structure of hashes are absolutely part of the fundamental architecture of git/blockchain.
CiPHPerCoder 7y ago
See https://news.ycombinator.com/item?id=9437021 https://news.ycombinator.com/item?id=9437021

by ascar 7y ago

nebulous1 7y ago

in bitcoin the transactions are the leaves

ascar 7y ago
Could you please elaborate how that ends up as a Merkle tree? In a merkle tree the leaves are not linked and they have a tree structure of parent hashes on top. Git and Blockchain nodes are linked and the fundamental architecture doesn't need a tree structure of hashes on top. While this tree structure on top might be useful, it would be an optimization, but not part of the fundamental architecture. Again, what am I missing?
- nebulous1 7y ago
  This might be complicated by the fact that "merkle trees" and git/blockchain invert the parent/child relationship. The root of the git/blockchain trees changes every time a commit/block is added, and the child nodes are called "parent commits" in git. Also the shape isn't going to have a wide base or be balanced like a binary search tree or similar. When you say that "git and blockchain nodes are linked", I think you might be not abstracting the concepts from the form the data usually takes. For instance in git you might be thinking of a commit as a single package with all its source changes, headers, parent details and hash, but it terms of it being a merkle tree the leaf node would be non-hash parts (source code, non-hash headers etc) and the "tree on top" would be the hashes. This tree structure of hashes are absolutely part of the fundamental architecture of git/blockchain.

CiPHPerCoder 7y ago

See https://news.ycombinator.com/item?id=9437021 https://news.ycombinator.com/item?id=9437021