Re: Back to Merkle Hash Trees...

----- Original Message ----- 
From: "Olaf van der Spek" <[email protected]>
Subject: Re: [BitTorrent] Back to Merkle Hash Trees...


> Joseph Ashwood wrote:
>> And the associated disadvantages of not having those hashes immediately
>> available. Harder to determine the bad parts of the file, higher overhead 
>> in
>
> Who said anything about not having the hashes available when needed?

Unfortunately the lack of hashes available is a requirement for random 
access downloading. If everyone downloads the hash tree first, the hash tree 
becomes universally available, but the data may not be. In order to rectify 
this the tree must be randomly accessed as well during the download. This 
leads directly to a situation where subtrees may not be linked into the full 
tree, and hence the hashes for verification are not available.

>> 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)).
>
> Isn't that limited by network transfer rate instead of CPU time?

As with any bottleneck it moves around as assumptions change. Assuming 
SHA-512, 2.1 GHz pentium 4, Windows XP, Crypto++ used for implementation, 
and assuming a 100baseT connection the situation changes substantially. The 
system can receive at 12.5Mbytes/second, but can only hash at 11.4 MB/s even 
the flat file would be unable to keep up. Admittedly this situation is not 
in the near future for most uses, but my systems spends most of their time 
at 100% computation load, the extra overhead required for a non-flat 
traversal would have an impact even if I was running on an 800 baud modem.

>
>> Higher overhead...: Computing root hash using current method O(n) time.
>> Computing root hash for Merkle O(nlogn) time.
>
> Isn't that limited by disk transfer rate instead of CPU time?

Most of the time, yes, but as with above the bottlenecks move. Already 
though we're seeing some change in this. As SATA becomes more available and 
pushes more towards the 200MBytes/second even SHA-1 is having trouble 
keeping up in a flat file.

It may seem trivial to try to optimize these other bottleneck points when 
the other bottlenecks are dominant, but as those bottlenecks are eliminated 
the other known bottlenecks will become evident.
                Joe 



 
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/