News for hackers. Stuff that matters.
Re:Implementing a Merkle Tree for an Immutable Verifiable Log by TedDoesntTalk on Friday May 06, 2022 @02:57PM (#31288594)
How is this different from a blockchain (serious question)?
Re:Implementing a Merkle Tree for an Immutable Verifiable Log by greiskul on Friday May 06, 2022 @02:59PM (#31288612)
A blockchain is a merkle tree with a distributed consensus algorithm.
Re:Implementing a Merkle Tree for an Immutable Verifiable Log by charcircuit on Friday May 06, 2022 @05:18PM (#31289704)
A blockchain is just a data structure. A consensus algorithm can agree what the current state / last block of a block chain is, but they are separate.

Similarly if one says B tree or LSM tree that doesn't mean they are also talking about a consensus algorithm.

Re:Implementing a Merkle Tree for an Immutable Verifiable Log by WorldMaker on Friday May 06, 2022 @06:15PM (#31290129)
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.

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.
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

Re:Implementing a Merkle Tree for an Immutable Verifiable Log by Groxx on Saturday May 07, 2022 @01:00AM (#31292278)
As others have pointed out: very little is different. Depending on if you include consensus in your use of "blockchain", there may be no difference whatsoever.

Currently it's a massively popular buzzword that frequently means very little in reality. It's just being tacked onto everything whether or not it makes sense because e.g. the Long Island Iced Tea company switched their name to "Long Blockchain" and immediately had massive stock gains: https://arstechnica.com/tech-policy/2017/12/iced-tea-company... . Even in the cases where it is technically accurate, it's rarely a good or useful idea... but it helps get funding.

So in practice, "blockchain" currently means "you will magically get rich". Technically it's almost always a Merkle tree, or a less efficient structure (e.g. Bitcoin's core "chain" is basically a linear version, which is dramatically less efficient to verify to the root for any given block... because it doesn't need that quality. Though it also uses Merkle trees within each block).

Re:Implementing a Merkle Tree for an Immutable Verifiable Log by a1369209993 on Friday May 06, 2022 @03:48PM (#31289009)
A blockchain provides a guarantee of (statisical eventual) write availability, since anyone can mine new blocks (eventually). A verifiable log only accepts new entries from a limited, generally closed set of writers (usually just one), and you can only add new entries by going through one of those writers. (Blockchains also tend to have better read availability due to being more widely distributed, but there's no reason why you couldn't destribute a verifiable log that widely, it just tends not to happen in practice.)

This makes a verifiable log unsuitable for financial purposes since a adversary with lead pipe capabilities (or corrupt judge capabilities as the case may be) can block undesirable transactions at a single (or few) point of failure, whereas against a blockchain they'd have to target anyone with significant compute capacity.

On the other hand, verifiable logs don't need proof of work/stake/etc to limit hostile forking, so if the log is describing things rather than acting a ground source of truth (so you can just ignore it if it starts refusing writes), it's much more efficient than a blockchain.

Re:Implementing a Merkle Tree for an Immutable Verifiable Log by MrStonedOne on Friday May 06, 2022 @11:46PM (#31291995)
None of those things are features of blockchains, they are all features of cryptocurrencies.

Blockchains refer to any time you use a chain of hashes to prove a block of data and any data that came before it, has not been mutated.

The time keeper service that takes out classified ads in the new york times with hash blocks for the documents they timestamped to prove they were timestamped before a certain date, is a blockchain, because they include the previous day's hash.

Git, is a blockchain.

It's just hashes all the way down.

The random entropy driver in linux, is technically a blockchain, with how it works.

Re:Implementing a Merkle Tree for an Immutable Verifiable Log by est31 on Friday May 06, 2022 @03:14PM (#31288729)
There is no token/currency associated to it, and it's made for a single specific purpose only, compared to most blockchains which try to run programs, manage wallets, etc. It also doesn't have a decentralized consensus algorithm, nor is there a gossip network to inform about new transactions that are to be added to the log. It's centralized per design.

Which of these differences you see as important to the blockchain / non-blockchain distinction, depends on the precise definition for blockchain that you want to use.

That being said, even the CT website uses the term "ledger" to explain what the logs are: https://certificate.transparency.dev/howctworks/

Re:Implementing a Merkle Tree for an Immutable Verifiable Log by radicalbyte on Friday May 06, 2022 @04:03PM (#31289134)
The term "ledger" pre-dates crypto. An append-only log is a ledger if the writers are trusted.