[BitTorrent] BT2 & hash trees

Olaf van der Spek OvdSpek at LIACS.NL
Fri Jul 23 07:33:05 EDT 2004


John Hoffman wrote:
> *FLAME ON*
> Damn it, Olaf, don't pontificate on shit if you aren't going to do the 
> research!  I'm telling you, I ran tests, I looked at what other systems 

Well, my research shows that calculating the merkle tree root (1 kbyte 
leafs) of a  4.707.319.808 byte file takes 191 seconds CPU usage.
Generating a normal .torrent of the same file takes 180 seconds CPU usage.
So the total additional overhead is just 6 %. That's not just the 1 kb 
-> 16 kb step, but the generation of the entire merkle tree.

So I'm afraid I can't reproduce your test results.

> use.  I went looking for source code for Tiger tree handling, looking to 
> convert it to Python, and that's how I found out what I know.  I ran 
> tests on hash generation.  If you disbelieve me, then go look for your 
> god damned self.  Don't imply I'm a liar while talking out of your ass.

I'm not implying anything, I'm just trying to find out what causes that 
much CPU usage.

>>>>>I considered recommending using THEX as the algorithm for BT2, but THEX 
>>>>>is based on the Tiger hash, and on a low-iteration version of the hash 
>>>>>       
>>>>>
>>>>
>>>>Where does it say that?
>>>>
>>>>     
>>>>
>>>
>>>Read the spec, look at the implementation.
>>>   
>>>
>>
>>This part?
>>For instance, the SHA-1 algorithm is identified by ...
>>The Tiger algorithm is also supported and is identified by ...
>>
>> 
>>
>>
>>>>>I did some tests and calculating hashes on such a fine-grained level 
>>>>>does impose a significant amount of additional overhead, and since BT 
>>>>> 
>>>>>
>>>>>       
>>>>>
>>>>
>>>>What kind of overhead?
>>>>More (complex) code?
>>>>More CPU?
>>>>More RAM?
>>>>More network?
>>>>
>>>>     
>>>>
>>
>> > Significantly more CPU.
>>
>>During what operation?
>>There's almost no difference in complexity between computing the hash of 
>>a 16 kbyte block directly or via 1 kbyte base blocks.


------------------------ Yahoo! Groups Sponsor --------------------~--> 
Yahoo! Domains - Claim yours for only $14.70
http://us.click.yahoo.com/Z1wmxD/DREIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~-> 

 
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