Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

The only thing that keeps a blockchain appearing to be a rebase-only straight line and not an otherwise ordinary merkle tree is the consensus algorithm on what the "current state / last block of the chain" is.

The difference between a blockchain and a merkle tree in no way resembles that between a B tree or LSM tree. It's closer to the difference between a Binary Search Tree and a Red/Black Tree. They are both Binary Search trees and most operations are the exact same, but Red/Black Trees have an extra "color" attribute and rely on that for a better balancing algorithm than the "default" BST algorithm.



I think you are over complicating things. A blockchain is just a linked list with content addressed next pointers. You don't need a distributed system to use it. When on a single machine you don't need a consensus algorithm to agree on what the head of the list is. Even if you have multiple different heads none of them will be a tree. A node can only ever point to 1 other node.


Most Git commits (almost all non-merge commits) only point to one other commit (node, whatever) and that still forms a tree of branches naturally. Rebase is a "consensus algorithm" that some need in git to keep their commits a straight line. On a single machine a blockchain consensus algorithm is nearly indistinguishable from "rebase" and yeah doesn't "feel like you need a consensus algorithm". That doesn't mean there isn't a consensus algorithm.

Multiple different heads is a tree. Multiple forks is very much a tree. I think it is Blockchain proponents that are overcomplicating things and bending over backwards to describe their Merkle trees as non-tree as possible.


Think the main confusion going on here is that people do not think of tree as lists, even if they could be 100% represented as such.


It's early so could you help me out by showing how to represent say this[1] tree as a list?

Or did you just mean you can store the nodes in an array and index them by level? In that case I wouldn't call it a list.

[1]: https://en.wikipedia.org/wiki/B-tree#/media/File:B-tree.svg




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: