[BitTorrent] BT2 & hash trees

Gregorio Roper gregorio at gmx.li
Mon Jul 19 04:03:14 EDT 2004

Elliott Mitchell wrote:
>>From: Gregorio Roper <gregorio at gmx.li>
>>Is there any chance of using a block size of 1024 bytes for the hash tree, since it 
>>completely removes any limitations imposed by the block size, even for small files and 
>>it's also the block size recommended by THEX[1] which is used by several p2p networks that 
>>could then be used as a backup in case the tracker fails.
> 1024 would make sense if the protocol could address blocks that small.
> As only a few discrete block sizes make sense (somewhere in the 16KB or
> 32KB range), trying to limit the block# to be a byte makes sense. If a
> bit is allocated to indicate block size, you can address 128 blocks,
> which means a minimum of 2K blocks for 256KB pieces (and then the issue
> of whether to allow selectible larger block sizes comes up).

The block size that you use to create the leaf hashes is totally independent of the piece 
size used in the BT transfer. Your hashtree will look like this:

0			ROOT=IH(A,B)
        			   /   \
1                  A=IH(C,D)  B=IH(E,F)
                      /     \      /   \
            /     \
n       LH(....) LH(...) ....

IH is your internal hash function creating the level i hash from two level i+1 hashes, LH 
is the leaf hash function creating the level n hash from (block size) bytes. These level n 
hashes are not necessarily stored, - for a hash tree to be usable, you only have to know 
any level 0 <= i <= n that defines the size of the smallest chunk that you are able to 

So, you don't loose anything if, for the sake of interoperability, you use a block size of 
1024 bytes for your hash tree (even if 1KB pieces are too small to make sense) and the 
following internal / leaf hash function (where H is your hash function - probably SHA1)
LH(data) = H(0x00, data)
IH(A,B) = H(0x01, A,B)

Of course you don't have to define the block size of the hash tree or the hash functions 
in your protocol, you can also specify them during the handshake of each transfer.


------------------------ Yahoo! Groups Sponsor --------------------~--> 
Yahoo! Domains - Claim yours for only $14.70

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