[BitTorrent] Re: Back to Merkle Hash Trees...

sh4dowmatter mgp at ucla.edu
Mon Feb 7 19:28:49 EST 2005

--- In BitTorrent at yahoogroups.com, "Joseph Ashwood" <ashwood at m...> wrote:
> Completely incorrect. First and foremost O() cannot be applied to
> constraints, there is an entirely seperate notation reserved for that. 

So I can't say that a declaring an array of size N takes O(N) bytes?

> I 
> apologize if I made the mistake first. Second your assumptions are
> fallacious as well. Your assumptions require that the the branch
rate be 
> fixed, and beyond that it requires that it be fixed at 2. 

When I started this thread, I built/expanded upon the example found in
the THEX specification; it was a binary tree, and I proposed extending
it to a full binary tree. I apologize if my assumptions were not explicit.

> Second, your 
> method of computation is invlid for O() notation, O() notation
requires the 
> use of calculus in the summing, otherwise the variables become
unusable. To 
> give a firm example the following is perfectly valid for a Merkle tree:
> Root = hash(A,B,C)
> A - leaf node
> B - leaf node
> C - leaf node
> This has 4 nodes instead of the required 5 under your constructions.  

I understand that this is valid...

> Next 
> O() requires that you keep those reals that are critical to the 
> understanding, or at the very least disclose them, in this case your 
> dropping of the 2 shows a situation where dropping the real eliminates 
> information that is necessary for proper understanding. So to be
> blunt, you used the wrong notation, you calculated wrong, and your 
> calculations were inaccurate anyway.

I don't see where you prove these assertions.

> Your proof if valid, except for one, not so minor, problem. Your
> equation is incorrect, the Merkle tree requires nlogn space, leading to 
> O(nlogn) time to verify. Beyond this reconstruction will also require 
> O(nlogn) because the insertion requires that the tree be stepped
> downwards n times. Since the depth of the tree is logn, the time to
> one node will be O(logn), multiply by the n times necessary, and we
> O(nlogn) reconstruction time.

I still fail to understand how a Merkle hash tree takes O(n logn)
space, assuming that the number of leaves (which we start with) is
proportional to the size of the file. 

In any tree -- a binary tree, a ternary tree, any tree where any
interior node has more than one sibling (indeed, if this weren't the
case, it would be one lame tree, and you could construct it better) --
the number of internal nodes is always less than the number of leaves.
But the number of leaves is O(n), because they are all of a constant
size (say k) and n is the size of our file. So if the number of leaves
is O(n), and the number of internal nodes is bounded above by the
number of leaves, it must be O(n) too! So our total memory requirement
is O(n).

So if we agree (again, if...) that the size of a Merkle hash tree
(like all trees) is O(n), I provide a new argument that the
construction of such a tree takes O(n) time, based on the observations
that constructing such a tree (from scratch, given the file of length
n) takes two steps: computing the leaf hashes, and then computing the
internal nodes (and finally the root).

1) Computing the leaf hashes takes O(n) time: I think we agree on this
part. The file has size n, and leaves are hashes are of size k; thus
the number of leaf hashes is ceil(n/k), which is O(n).

2) Computing the internal hashes takes O(n) time: Okay, I lied before.
This doesn't really take O(n) time -- you caught me. I assumed that
the number of children per internal node was 2. It can be fixed at any
constant greater than 1 -- 3, 4, 5, whatever. (If you insist it is a
value less than or equal to 1, each internal node doesn't have two
children when it could, and you don't have a very efficient tree...)
Say each internal node has up to m children, where each child is a
hash of constant size. The hash of an internal node is simply computed
by hashing the concatenation of all its m children. It thus takes O(m)
time. Since there are O(n) internal nodes, the total time to compute
all internal nodes is O(nm). You could argue that m is large enough so
that O(nm) > O(n logn), but then you're totally abusing what
O-notation is: I can always find some n0 such that for n >= n0, O(nm)
< O(n logn). And the finale: m is a fixed constant -- so really this
is O(n) time.

The height of the tree is, quite simply, irrelevant. You could have a
full binary tree, of minimum height, or a completely unbalanced tree
of maximum height, but the time to compute the internal hashes in the
tree is the same. This is because the number of internal hashes does
not vary, and the number of children per internal node is fixed, and
that is all the computation depends on. So I don't think log n belongs
into the equation...

> Your math is not as bad as I first assumed, and O() notation is
> confusing for a wide range of people. I have even seen professional 
> mathematicians mess up on it for the same reasons you have. The
reason is 
> that they have been taught the non-calculus method that usually
> good answers, and they have been taught to drop all integers.

If you're comparing my math to professional mathematicians, I'm in
better company than I had thought. Thank you for the compliment ;)

> If you would like to further your education in this regards, I would
> reading most anything published by Knuth, he is well respected and
> nearly perfectly strict notation.

Knuth is God, I admit. I keep meaning to read "Concrete Mathematics"
but can't find the time...

Finally, I'm sorry if my last response sounded demeaning or full of
vitriol. I'm just looking to find an answer we can both agree upon,
regardless of who (if either!) of us is right.


Yahoo! Groups Links

<*> To visit your group on the web, go to:

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list