[BitTorrent] BT2 & hash trees

Elliott Mitchell ehem at m5p.com
Fri Jul 23 16:38:55 EDT 2004

>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> 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.

I believe John was strictly refering to the difference between 1KB Merkle
tree, and 16KB Merkle tree; *not* the difference between plain SHA and
Merkle tree.

The delta there is 11 seconds. Most of that delta will be in computing
the internal nodes (as opposed to a completely bogus implementation that
simply adds a constant 5 seconds). Moving from 16KB blocks at the lowest
level to 1KB blocks at the lowest level results in sixteen times the
number of internal nodes. So in theory the numbers should look like:

	Pure SHA-1
Time computing hash:			180 seconds
	Total time:			180 seconds

	16KB blocks:
Time computing lowest level of blocks:	180 seconds
Time computing internal nodes:		 11 seconds
	Total time:			191 seconds

	1KB blocks:
Time computing lowest level of blocks:	180 seconds
Time computing internal nodes:		176 seconds  (11*16)
	Total time:			356 seconds

*That* is a big difference.

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

Hopefully this answers your question? (though I'm curious about an
empirical test, as opposed to just theory here)

>From: "}T{Reme [Q_G] applsapff" <xtremeq_g at hotmail.com>
> Don't really wish to butt in on a nice flame but... isn't the point of 
> bittorrent reducing load on servers? So what if it takes xx seconds longer 
> to calculate some hash? If it reduces the load on the servers, so be it. 
> (within limits of course, no point having a user's computer number-crunching 
> so much it becomes unresponsive)

The block size will be irrelevant to servers, it will have a massive
effect on clients though.

(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com 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 Sponsor --------------------~--> 
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!

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