Re:Implementing a Merkle Tree for an Immutable Verifiable Log
by charcircuit on Friday May 06, 2022 @06:44PM
(#31290321)
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.
[ Parent
| on HN ]
Re:Implementing a Merkle Tree for an Immutable Verifiable Log
by WorldMaker on Friday May 06, 2022 @09:07PM
(#31291253)
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.
Re:Implementing a Merkle Tree for an Immutable Verifiable Log
by cfcosta on Saturday May 07, 2022 @12:52AM
(#31292248)
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.
Re:Implementing a Merkle Tree for an Immutable Verifiable Log
by magicalhippo on Saturday May 07, 2022 @08:30AM
(#31293992)
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