[BitTorrent] Back to Merkle Hash Trees...

Elliott Mitchell ehem at m5p.com
Mon Feb 7 21:54:02 EST 2005


>From: "Joseph Ashwood" <ashwood at msn.com>
> ----- Original Message ----- 
> From: "sh4dowmatter" <mgp at ucla.edu>
> 
> > 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).

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

Is there a real case that is worse than a fixed branching rate of two? I
doubt anyone is planning to use a tree with large linear pieces if they
can avoid it, so I don't see a worse case.

There is the tail end of the file, but that will need no more than log(n)
nodes (worst case being 2^n+1 nodes, the extra chunk would need one node
for each level). Though the notation isn't right, this gives O(n+log(n))
nodes. The linear factor completely overwhelms the logarithmic portion,
so the tree size is essentially linearly related to the size of the
payload.

> > 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).
> 
> Your proof if valid, except for one, not so minor, problem. Your n-space 
> equation is incorrect, the Merkle tree requires nlogn space, leading to 
> O(nlogn) time to verify. Beyond this reconstruction will also require 

Just one problem, the tree requires n+log(n) space; this is *very*
different from nlog(n) (n*log(n)). You're corrent that O(n*log(n)) is
quite a big larger than O(n); however, O(n+log(n)) is identical to O(n).

> O(nlogn) because the insertion requires that the tree be stepped through 
> downwards n times. Since the depth of the tree is logn, the time to insert 
> one node will be O(logn), multiply by the n times necessary, and we reach 
> O(nlogn) reconstruction time.

Creating a tree by iterative insertion is an O(nlog(n)) operation. This
is not the only way to (re)construct a tree though. In the case of Merkle
trees and BT2, breadth-first seems the obvious one. This doesn't require
the search and so is linear with the size of the payload.
 

>From: Joseph Ashwood <ashwood at msn.com>
> ----- Original Message ----- 
> From: "Elliott Mitchell" <ehem at m5p.com>
> 
> >>From: Joseph Ashwood <ashwood at msn.com>
> > If there is only one way to construct the tree, the above is implicit in
> > the structure of the tree. If it is tampered with the hashes won't
> > verify.
> 
> Not quite, there are cryptographic attacks that you're not considering. In 
> particular the preimage reorder attack, where carefully chosen input blocks 
> are reordered without changing the upper hash, see the latest SHA/MD5 attack 
> for examples of doing this as well as the reordered preimage attacks 
> proposed as a result that apply to all hashes, and can be addressed at the 
> protocol level.

Luckily we aren't dealing with input blocks that have been carefully
chosen by an attacker.

> > This is not the only possible handling of Merkle though. If blocks of
> > tree nodes are handled similarly to any other data blocks, you only
> > transfer the tree nodes once and only verify them once. At which point
> > the work and data overhead becomes O(n), where n is the size of the file.
> > The overhead will be slightly higher if you only do a partial transfer.
> 
> Most of this is good, but you're forgetting that there are nlogn hashes to 
> be verified, and that the hashes have significant overhead at termination, 

As I said above, n+log(n), bringing the O(n) back.

> has a major impact on the overall hash speed for a few kilobytes. 16K chunks 
> should be enough to dominate this as long as there is a reasonable branching 
> order to the Merkle tree (part of the reason I prefer my proposal is that by 
> setting the #children to a 32-bit number the branching order can be 4 
> billion enough to quickly dominate the fixed cost).

2^32nd children is ridiculous, even 2^16th children is ridiculous. I
think the size of the smallest transferable data block (likely 16K or
32K) divided by the size of the hash. This leads to blocks of hashes
being handled similarly to payload blocks (reducing the complexity of the
over the wire protocol).

> > To verify a block, you appear to need the block, then you need the hashes
> > of all sibling blocks and the parent block for the next level up. You
> > then appear to need the same for all higher levels. You're likely to
> > transfer those and they appear much larger than Merkle's.
> 
> The cost of initial verification of a block (should be good enough to send 
> on) is reduced to O(blockSize), because the lookup takes O(1) and the 
> verification O(blocksize). Once the a sufficient number of blocks have been 
> received to verify a hash in the next level it can be moved up. Eventually 

But how do you verify a block knowing only the block, root hash, and some
portion of the tree? How much of the tree do you need to transfer to
start verifying blocks?


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/




 
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:
    BitTorrent-unsubscribe at yahoogroups.com

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





More information about the BitTorrent mailing list