Re: Back to Merkle Hash Trees...

>From: Joseph Ashwood <[email protected]>
> Harder .... bad parts. Current process: lookup segment hash in O(1) time,
> compare hash O(m) time, total time O(n). Merkle process: step through tree
> to leaf O(log(n)) time, then compare hashes O(n) time, total time
> O(nlog(m)).
> 
> Higher overhead...: Computing root hash using current method O(n) time.
> Computing root hash for Merkle O(nlogn) time.

A legitimate concern. Two counterpoints though. The smallest size chunk
that anyone has suggested making verifiable is 4K at the high end you
might only make 256K chunks verifiable. There is also a question of how
branchy the tree should be. Given that the smallest requestable chunk is
likely to be 16K or 32K, it seems to me that the second layer might
consist of 512 hashes as that many can be packed into a 16K chunk.

Consider, for a 4GB file with the smallest chunk size suggested of 4K and
the bottom end branching factor of 2. The complete tree will consist of
2^21 hashes. If SHA256 is used, we'll have 64MB of hashes. An overhead of
less than 2%.

> Longer download: Currently the overhead is known. In the case of detecting
> bad segments, Merkle overhead will necesarily include downloading the entire
> Merkle tree, in addition to the current overhead. Where detecting bad
> segment is unnecessary the overhead remains the same.

The V1 protocol already requires you to download hashes for the entire
file from a resource constrained server (the torrent file). The V2
protocol will almost certainly require you to download hashes at a
minimum for every piece to prevent the spread of corrupt pieces. There is
then the problem of verifying the blocks of hashes which is where the
extra overhead comes in.

As noted above I don't see it being worth transfering blocks of less than
512 hashes, as this number neatly fits in the smallest verifiable block.
At this point the tree internal nodes are going to be less than 1% of the
size of the leaf nodes. Given that V1 already requires you to transfer
leaf node hashes, this additional overhead is minimal.

> For maximum processing speed the tree needs to be properly balanced doing
> this requires properly balancing across the hash. In the case os SHA-1 this
> requires tuning in such a way that numHashes*512/160 is as close as possible
> to an integer, while this is not immediately apparent as computationally
> intensive you have to understand that it is actually an O(nlogn) problem,
> and while not overly costly is not cheap.

The smallest verifiable unit will likely be fixed (Bram's writings
suggest this, but we haven't seen code yet). At this point the above
becomes futile. You can trade internal nodes in one location for internal
nodes in another location, but you're merely spreading the inefficiency
across the tree, not actually gaining anything (and spending the above
cost). Leaving it an unbalanced tree is simplest, and in fact
advantageous if you which to be able to expand torrents.

More detail?

> Bed segment propogation is already a small problem as parts may be
> downloaded and uploaded before verification. By using a Merkle tree you are
> raising the computational overhead to perform verification, and in some
> cases may be delaying the verification until the complete file is downloaded
> (to compute the non-downloaded complete tree), creating a situation where
> there is a high likelihood of large scale propogation of any bad data.

Wrong. V1 places hashes in the torrent file so at the piece-level (256K
by default) things get verified. Due to this very concern I doubt Bram
would be so stupid as to not require the transfer and verification of
this granularity of hashes. By placing the transfer of hashes onto the
peers, you're removing a lot of strain from the centralized server
holding the torrent file.

> For those that are truly security conscious of security there are a great 
> deal many other things that must be addressed to maintain the security that 
> I have not even touched on, but suffice it to say that the original Merkle 
> tree should not be considered secure.

Yes. Hopefully I've shot down these concerns?

One you might think about helping me murder is the "THEX" design various
folks have been advocating. THEX distinguishes leaves from internal nodes
by appending a byte depending on whether it is leaf or payload; *that*
is bogus!  (kills alignment, makes testing expensive)

http://www.open-content.net/specs/draft-jchapweske-thex-02.html


-- 
(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         [email protected] 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:
    [email protected]

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