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

[Ben Laurie]

On 3 July 2017 at 11:08, James A. Donald <jamesd at echeque.com> wrote:

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

Yeah, exactly. See the design of Trillian:
https://github.com/google/trillian/blob/master/docs/VerifiableDataStructures.pdf
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20170703/0d332313/attachment.html>