[BitTorrent] BT2 & hash trees

Olaf van der Spek OvdSpek at LIACS.NL
Mon Jul 19 20:44:13 EDT 2004


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

Who's forcing who to transfer unneeded 'data for verification' (hashes?)?
>
> 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?

Other (future) hashing schemes.
>
> 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)?
>
> > 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).

Because if you only have the root hash and not the file size, you wouldn't
be able to tell whether a certain node was internal or leaf (whether it's
data or hashes).



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