Re: Back to Merkle Hash Trees...

I don't know where you people learned your maths and fancy proofs...
But the last time I checked, a tree with k leaves requires k-1
"interior" nodes, regardless of how the tree was constructed --
whether it's maximally unbalanced, full, etc. The size of the tree is
thus k + k-1 = 2k - 1. And then, "trivially," 2k - 1 < 2k, or O(k).
But k is some fraction of n, so k = cn for some constant c <= 1. Hence
the size of the tree is O(n).

Which leads me to... Constructing the root of a Merkle tree, and
reconstructing the entire tree just given the root, takes O(n) time.

To prove that reconstructing the tree takes O(n) time (assuming
top-down reconstruction), realize that you have to "verify" 2n-2 nodes
-- that is, every node in the tree except the root. To verify a node,
you just need to 1) hash it with its sibling and 2) check that it
equals the parent. (Actually, note that since this also verifies the
sibling simultaneously, this only happens for (2n-2)/2 = n-1 nodes.)
The hashes are a constant size, and there is only one sibling for each
verification. So verifying a node takes constant time. Once every node
is the tree is verified, it is constructed. There are 2n-2 (or n-1)
verifications, which is O(n). Which means constructing the tree is O(n).

To prove that constructing the tree takes O(n) time, apply a similar
argument.

- shadowmatter


--- In [email protected], "Joseph Ashwood" <ashwood@m...> wrote:

> Higher overhead...: Computing root hash using current method O(n) time.
> Computing root hash for Merkle O(nlogn) time.






 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/BitTorrent/

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/