Re: [Cryptography] actual journalism, was LRB article, Satoshi's Trump Card
On 03/07/2017 4:31 PM, Ben Laurie wrote:
Confused by this - Merkle trees inherently don't grow to enormous depth.
The bitcoin hash chain grows to enormous depth, and arguably it is a Merkle tree that testifies to all transactions everywhere that ever taken place in bitcoin. If you say it is not a Merkle tree, then fine. A scalable crypto currency has to employ a Merkle trees instead of whatever we call the thing that Bitcoin uses.
Confused by this - Merkle trees inherently don't grow to enormous depth.
I am pretty sure that if I give a definition and say "A Merkle tree is such and such", a bikeshed war will ensue over my definition of Merkle tree, which war will probably result in Perry blocking my posts. So let me define instead a donald tree. :-) (just kidding) A donald tree is a tree where every node contains the hash of its immediate children. Thus the hash of the root of any subtree guarantees the contents of all its descendants, just as the hash of a file guarantees the contents of the entire file. This means that we can keep on adding to the tree, while keeping the past immutable, which is a useful feature for tracking who owns what, and who owes what. If many people see the current hash at time X, you cannot change details about the past of time X without revealing what you have been up to. Any tree can be severely unbalanced, for example a binary tree where every node has a right hand child, and very few nodes have a left hand child, in which case the depth of the tree is approximately proportional to the total number of nodes in the tree - and the tree grows to enormous depth when the total number of node is enormous. Or it can be approximately balanced, in which case the depth of the tree is approximately proportional to the log of the number of nodes, which is always a reasonably small number even if the number of nodes is enormous. And a hash that testifies to every transaction that anyone ever did is going to be the hash of an enormous number of nodes. But if it is at the root of a tree of moderate depth, then we can validate any part of the tree for conformity with the rules without validating the entire tree for conformity to the rules.
participants (1)
-
James A. Donald