[BitTorrent] BT2 & hash trees

Gregorio Roper gregorio at gmx.li
Tue Jul 20 04:51:55 EDT 2004

Elliott Mitchell wrote:

>>Who's forcing who to transfer unneeded 'data for verification' (hashes?)?
> With this scheme you'll transfer 1024 hashes in a block (reasonable),
> you'll then need to use 256 of them to verify a 256KB piece. If the worst
> case happens and you need to transfer every hash (massive attack?) you'll
> be transfering one block of hashes for every four pieces (not including
> secondary levels). If you only hashed 16KB pieces you'd only have to
> transfer one block of hashes for every thirty-two pieces.
> A 2% (20 byte hash for 1024 bytes of payload) cost in bandwidth isn't
> /that/ large, but it is bigger than the total of all other overhead in
> the BitTorrent protocol. Larger hashes will increase this proportionally
> (over 5% for SHA512, without higher levels of hashes). This factor of 16
> savings is enough to push SHA512 back below 0.5% (reasonable).

Transferring the hash tree during the transfer as part of the peer protocol may 
not be such a swell idea, - especially if you still plan on addressing single 
pieces using the hash. For security, you would have to transfer the hash tree as 
a whole (that would be more than 600KB of data only for the first 15 levels) 
anyway. So you would probably be better of putting the nth level of your hash 
trees along with your root hashes into your torrent file.
If every node in the network starts of with the equivalent of the root hash and 
tries to request further parts of the hash tree on the fly, you add a lot of 
unneeded and unwanted complexity.
One possible scenario for requesting a part of a hash tree that could make sense 
  as an optimization (that should not be a requirement by the protocol) is when 
you notice one of your 1024KB pieces is corrupted and you are to lazy to 
download the whole 1024KB again, so you request the k'th level of the hash tree 
of this piece.

This is one scenario btw, where you can actually make use of 1KB block size btw: 
Suppose one byte of your 1MB piece is corrupted, that's 10 levels above the 1KB 
block. You can work your way down the hash tree in 10 requests (that's certainly 
less than 200 bytes outgoing traffic) exactly identifying the corrupted block. 
The remote host would return you 20 hashes (2 per request) which shouldn't cost 
more than 600 bytes (400 bytes for the hashes and less than 200 bytes overhead). 
   As a result you would have cleared the corruption using ~1,8KB after 
re-downloading the 1KB block. You can repeat that for any piece size, and any 
block size > 1KB, 1KB blocks will always save you some traffic;-).

And thus it is proven that 1KB blocks in your hash tree may save a lot of 
bandwidth compared to your pathetic 16KB blocks. Behold the size of my endian!

> Let us compare some fairly well known hashes and see what is similar and
> what is different about them. How about CRC32, MD4, MD5, SHA1, SHA256,
> SHA384, and SHA512. What do they all have in common? They are defined for
> operation on arbitrary lengths of strings, 1 byte is fine, 1024 bytes are
> fine, 1023 or 1025 work fine as well. All but CRC32 have pretty similar
> internals. How are they different? Different code, an implementation of
> one *cannot* compute any of the others (SHA384 and SHA512 have 99% of the
> code in common, but you do have to handle them differently at the end).
> Except for MD4 and MD5 they all produce output of different sizes. They
> all produce different values for different input.
> Given that handling a new one *will* require new code (what is the use of
> using a hash you can't verify?), and they all operate on an arbitrary
> number of bytes of input (future hashes are *certain* to follow this);
> how does using a branching factor of 1024 help the future?

Since I am certainly not going to implement any of the message digests you 
mention but rather use a library that is capable of creating any of them, I 
don't require any new code.
Here is where I gain something if the block size used in BT is the one I already 
use: If I create a torrent for any file with my software, I will not even 
recompute the hashes to create the torrent but use my default hash tree. In case 
the tracker fails, I can easily query a p2p network (in my case that would be 
Gnutella) for the root hash of a file because this root hash will be created by 
default by any node in the network. Of course I could also use a non-standard 
extension to the torrent file I create but that would not be in my best interest.

As a side note, SHA512 is on 32bit systems about 3 times slower than SHA-1 and 
for the purpose of verifying a file. The digest is 3 times larger. Why exactly 
would you use SHA512 when SHA-1 is really secure for the purpose of transferring 
files? On the other hand, you should naturally be allowed to use what ever md 
you like...

>>>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).
> I suppose so. Though this requires you to run the hash over the block
> twice (the SHA functions are fairly expensive). If you really want to use
> this as an indicator, better to append the flag to the input; that way
> you can save the hash state at the end of the input and not have to run
> the hash over all of the input twice.

No, you do not run the hash over the block twice, you prepend one byte to the 
data you hash to avoid collisions as I mentioned in my other mail.


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