[Cryptography] actual journalism, was LRB article, Satoshi's Trump Card

[James A. Donald]

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