[BitTorrent] BT2 & hash trees

Gregorio Roper gregorio at gmx.li
Thu Jul 22 11:35:41 EDT 2004

Olaf van der Spek wrote:

> You don't need to transfer the entire path to the root each time.
> After some time, you already have part of the tree and you only need the
> first part of the path (looking from the bottom).
> That way, you'll transfer n, not 2n.

I only need 2n hashes for the first level-n node of a tree. If you build the 
average over the whole transfer, you would request 2 hashes per node.

Consider a simple balanced tree of n levels. The nth level has 2^n nodes. If I 
request this level as a whole, I will only transfer 2^n nodes and verify them 
against the root hash. If I always request just enough nodes to verify the next 
level-n node, I effectively request the complete levels 1 to n of the hash tree 
during the transfer. I would have to transfer 2^(n+1)-2 nodes versus 2^n nodes.

In the end it's just a factor 2 difference but getting the hashes in one piece 
makes implementing the protocol considerably easier.


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