[BitTorrent] Back to Merkle Hash Trees...

John Hoffman theshadow at shambala.net
Sat Feb 5 01:22:41 EST 2005

>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
>Higher overhead...: Computing root hash using current method O(n) time.
>Computing root hash for Merkle O(nlogn) time.

Well...  the O(n) overhead is a lot heavier than the O(n log n) 
overhead, so except on extremely large torrents (read >100G) you aren't 
going to see a significant increase.

>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 idea is to both send opposing tree data, as requested, with chunks, 
and to cache the data.  It does not require redownloading the entire 
tree in the case of an error, but merely the hashes received with a bad 
chunk, which would not be a large number (30 or less, max 600 bytes, 
probably much less).

>There are additional problems in balancing the signed library tree in order
>to achieve maximum speed and in not propogating the bad segments.
>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.

It's not really necessary to balance the tree so perfectly.  A 
breadth-first parse is quite adequate.

>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.

No, downloaded chunks will be verified as they come in.

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