# [BitTorrent] BT2 & hash trees

Gregorio Roper gregorio at gmx.li
Thu Jul 22 12:23:15 EDT 2004

```
Olaf van der Spek wrote:
> 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:
>
>     7
>   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.

I was thinking along these lines:
To verify 3 I need the hashes of 3,4 & 6
To verify 1 I need the hashes of 1,2 & 5
Verifying 2 & 4 can be done without requesting any further hashes.

All in all I requested 6 = 2^(2+1) - 2. Beginning with the root hash as level 0,
n is 2 for this tree. When I say level-n node X, I mean that the distance
between X and the root is n. I did not want to say that your tree had n nodes.

mfg
gregorio

------------------------ Yahoo! Groups Sponsor --------------------~-->
Make a clean sweep of pop-up ads. Yahoo! Companion Toolbar.
Now with Pop-Up Blocker. Get it for free!
http://us.click.yahoo.com/L5YrjA/eSIIAA/yQLSAA/dkFolB/TM
--------------------------------------------------------------------~->

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

```