[BitTorrent] Performance (was Merkle, URLs, etc)

Justin Cormack justin at street-vision.com
Fri Mar 4 07:18:07 EST 2005


> 
> 
> I apologize for my aparent falling off the earth act being an entrepreneur I
> work when I have to, and I can only dedicate some free time to this.
 
Thats ok, many of us are in this situation.

Going to reply in bits, as its a long mail.
 
> Speed ratings for hashes. Wei Dai maintains benchmarks for all the
> operations that Crypto++ supports available via
> http://www.eskimo.com/~weidai/benchmarks.html . These benchmarks are:
> 32-bit machine
> SHA-1 68 MB/sec
> SHA-256 44 MB/sec
> SHA-512 11 MB/sec
> 
> 64-bit machine
> SHA-1 100 MB/sec
> SHA-256 58 MB/sec
> SHA-512 93 MB/sec
> 
> While this clearly demonstrates the linear effect of moving to the larger 
> hashes, but in the current situation there is actually a second linear 
> problem, as the hash size grows the size of the data to be hashed at the 
> next level grows, leading to slow but exponential growth. The security 
> benefits though are more substantial and with SHA-1 broken there is plenty 
> of reason to move up.

I did some tests on Crypto++ and openssl in 32 and 64 bit mode on the same
machine (1.4GHz Opteron) and get

                       SHA1     SHA256     SHA512
Crypto++ 64 bit      84MB/s     49MB/s     77MB/s
Crypto++ 32 bit      99MB/s     48MB/s     18MB/s
openssl 64 bit      109MB/s

(openssl is just there as it is the fastest implementation I know, gives
you an idea of the margin for improvement if you have a perl script to write
assembly for you). I thought that SHA384 might be an improvement but it
seems to run at the same speed as SHA512 from the benchmarks I can find
(though it saves some space). Overall I would say that SHA256 is really not
a good choice and it is best to stick with SHA1 until 64 bit machines are
more common (rather soon it seems) and then move to SHA512.

In terms of hashing the internal nodes, I think the main problem is not
the growing size, but that hashing speeds are much lower for small blocks,
so nodes need lots of children: with openssl sha1, 3 children hash at
half the rate of 12 children.

> Merkle Trees: For verification of my suggestion I took some time and
> implemented my proposed format (although I am not ready to call it finished
> it does work). In the current implementation it will scale to 2^128 bytes of
> original file size, but that should probably be shrunk some to save
> overhead. I should say that it takes a huge amount of time build the tree
> from a file, as I type I'm 29 minutes into processing a 180 MB file at 4kb
> pieces ~ 95% done, and it occupies huge amounts of RAM, the test will occupy
> about 4 times the storage space, but has 2 copies of the original file along
> with the tree in memory at one point.

Thats really slow. Is it swapping thats causing slowdown or other things?
Sounds like getting the data structures right is going to be really important
with this.  Clearly you dont need 2 (or any) copies of the file though and
thats really going to hurt you. What language are you programming in?

Justin


 
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