<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On 3 July 2017 at 11:08, James A. Donald <span dir="ltr"><<a href="mailto:jamesd@echeque.com" target="_blank">jamesd@echeque.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Confused by this - Merkle trees inherently don't grow to enormous depth.<br>
</blockquote></blockquote>
<br></span>
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.<br>
<br>
So let me define instead a donald tree.   :-)  (just kidding)<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br>
<br>
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.<br></blockquote><div><br></div><div>Yeah, exactly. See the design of Trillian: <a href="https://github.com/google/trillian/blob/master/docs/VerifiableDataStructures.pdf">https://github.com/google/trillian/blob/master/docs/VerifiableDataStructures.pdf</a> </div></div><br></div></div>