[BitTorrent] BT2 & hash trees

Olaf van der Spek OvdSpek at LIACS.NL
Thu Jul 22 12:11:20 EDT 2004

Gregorio Roper wrote:
> 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.

Then you're doing something wrong.
Assume a 4 leaf, 7 node tree:

  5   6
1 2 3 4

Transfer order: 3, 1, 2, 4.
To verify 3, I need 4 and 5, so I request 2 hashes.
To verify 1, I need 2, so I request 1 hash. (You already have 5 from the 
previous step).
To verify 2, I need 2, which I already have, so I request 0 hashes.
To verify 4, I need 4, ".
To I transfered just 2 + 1 = 3 hashes, which is n, not 2n.
So it doesn't cost more hashes then transfering 1, 2, 3 and 4 up front.

> 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