[BitTorrent] BT2 & hash trees

Gregorio Roper gregorio at gmx.li
Tue Jul 20 03:23:10 EDT 2004


Elliott Mitchell wrote:

>>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:
> 
> 
> True to a point, but not entirely so. If they're distinct the least
> common multiple defines the smallest block that you can retrieve and
> verify efficiently. This is more a factor of the degree of branching of
> the internal nodes, than the leaves but it is still important. It is
> useful to be able to verify with 1KB granularity, but if the smallest
> protocol addressible block is 16KB why force someone to transfer unneeded
> data to do a verification?

You don't force anyone to force unneeded data because there is no need to 
transfer the whole tree, the additional work of creating a larger number of 
internal hash nodes before reaching the level in the hash tree that will be 
stored is really negligible and has not influence on the transfer.

> Transfering blocks of hashes in smaller chunks is useful, but the main
> data blocks are going to be a minimum of 16KB (possibly 32KB).
> 
> 
>>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)
> 
> 
> Interoperability with what?

Interoperability with p2p networks using THEX ( http://www.open-content.net/ ) 
that are using the block size and hash functions proposed in the THEX spec ( 
this would include Gnutella, OCN, G2 - virtually all networks using tree hashes 
already). This gives you one important advantage (which may not be interesting 
for you but which is very interesting for me): You can use these networks as a 
sort of distributed backup tracker for your torrents without breaking with the 
BT protocol and with only small extensions to the respective other networks.

> Last I checked BitTorrent was making clients interoperate, but there
> aren't any other protocols for which interoperability is anything but
> utterly ridiculous to talk about. So why bother with a block size that
> will harm BT (possibly greatly)?

My point was that the block size has not influence whatsoever on BitTorrent and 
could therefore be chosen to be easily compatible with existing protocols that 
are using the THEX (Tree-Hash-EXchange format).

>>LH(data) = H(0x00, data)
>>IH(A,B) = H(0x01, A,B)
> 
> 
> This actually puzzles me, why bother seeding the hash function with that
> extra value? Given that different inputs are being used, you're already
> almost guaranteed different outputs. I don't see any circumstances under
> which that is completely irrelevant. The rest of the Merkle tree idea is
> useful (though not too far from trivial).

You use different hash functions to calculate leaf nodes and internal nodes of 
the hash tree to avoid some possible collisions pointed out by the IRTF 
Cryptographic Forum Research Group.

>>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.
> 
> 
> Bram's plans are still unknown.  :-(  Specifying a fixed block size in
> the protocol seems a likely change (as no sizes other than 16KB and 32KB
> make any sense).

It will make perfect sense once you understand the way a hash tree works...

> 
> 
>>From: Gregorio Roper <gregorio at gmx.li>
>>Olaf van der Spek wrote:
>>
>>>>I didn't find any comment on how the pieces of a torrent will be addressed. If I 
>>>>understood correctly that BT2 is supposed to allow cross-trading, may I suggest that the 
>>>>pieces be addressed similar to: <file root hash><log2(pieceSize) or level in hash 
>>>>tree><pieceNum>.
>>>
>>>Eh, wouldn't it be easier to first exchange lists of files with integer 
>>>IDs and then just use the integer ID (8, 16, 24 or 32 bit) instead of 
>>>the 160 bit hash?
>>
>>Not necessarily easier but it would save a substantial amount of bandwidth.
> 
> 
> You've got to resolve the file hashes into integer IDs, making the
> protocol more complex. Depending on the design details the cost may be
> less than 16 bytes for REQUEST and PIECE messages. This is a cost of 32
> bytes on a payload of 16KB, a trivial cost. I've also mentioned a hash
> value can do double duty, identifying both the file and the piece number,
> under which the cost decreases significantly.

The cost is not trivial at all. You will have the cost of 16 additional bytes in 
every HAVE message (making its size more than double of its prior size) which, 
as was pointed out earlier, makes up for most of the overhead of BT.
Using the hash to identify the piece number, too still wastes 12 bytes.

Resolving file hashes into integer ids will (in the worst case) be just as 
expensive as using the hash to identify the piece, if you only consider REQUEST 
and PIECE messages and if you assume that you have to send exactly one 
REQUEST/PIECE message per piece (which is clearly not the case, btw). - It can 
be done dynamically using a WANT message and a reply to that WANT message so you 
don't waste too much bandwidth transferring torrents containing a large number 
of small files.

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

 
Yahoo! Groups Links

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



More information about the BitTorrent mailing list