[BitTorrent] BT2 & hash trees

Elliott Mitchell ehem at m5p.com
Thu Jul 22 00:51:10 EDT 2004

>From: Gregorio Roper <gregorio at gmx.li>
> Elliott Mitchell wrote:
> > 
> >>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.

This assumes you can find the same file on their networks. Possible, but
highly non-trivial. This would also require a lot of work to keep them

Does anyone have plans to implement such a feature on any client? I
suppose it is a thought, but I'm *very* doubtful of the usefulness.

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

Please point the way to this...   Until you provide a pointer I'm going
to remain doubtful.

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

I've already pointed out that things that make sense for REQUEST and
PIECE messages may or may not make sense for BITFIELD and HAVE messages,
and vice versa.

It makes sense for REQUEST and PIECE messages to identify pieces by their
hash. As there are not many of them the cost is small.

For this item BITFIELD and HAVE messages are a different matter. Likely
it is best for HAVE messages to stick with an index into the bitfield.
When it comes time to send a REQUEST message, then it is time to do the
bitfield index to hash conversion.

If you're handling multiple torrents over one connection then each
message already has to identify which torrent it belongs to, and
therefore is already transfering a hash with each message. In this case
HAVE messages have already grown and there isn't much you can do about

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

Always depends on circumstances. For a cache identifying pieces strictly
by their hash value makes sense.

>From: Gregorio Roper <gregorio at gmx.li>
> 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.

How does transfering the tree as a whole help security? Or perhaps I
should ask, how does transfering the tree as pieces harm security? Either
method leads back to the security of the root hash.

I think we've got good evidence that Bram is planning to use the peer
protocol to transfer the tree data, at which point the question becomes
what should the encapsulation look like?

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

Depending on how the hashes go over the peer protocol it won't make the
protocol more complex. If the tree is simply placed in some number of
pieces then the lowest layers of the protocol don't change at all. At
higher levels there is some complexity but not too much.

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

Requiring 10 round trips. 5 seconds on a modem (10 if both ends are on
modems), .2 seconds on DSL/cable, worse on satellite. One of the lessons
from the X protocol, round trips are expensive.

These are also going to be tiny packets. 40 bytes for the IP and TCP
headers on *each* request. If there is other traffic on this connection,
then it can be combined together and save bandwidth, but this will harm
latency (oops, can't win).

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

True, but I must bring up the question of whether it is even worth
bothering attempting to verify 1KB blocks, even if you have that ability.
All existing BitTorrent clients transfer data in blocks of 16KB or 32KB.
As a result, every 1KB sub-block of a 16KB block is going to of come from
*one* peer.

TCP is an old protocol, but an adequate one. TCP guarentees reliable
transmission, this includes error-free. As a result the *only* way you're
going to have a corrupt block is a software/hardware failure on the
remote end, or enemy action.

In the case of a software/hardware failure it is unlikely they'll be able
to compute checksums correctly and I'd be surprised that you got anything
out of them (have to be a really subtle failure to manage to send things,
and not get caught somewhere). In a case like this I suppose you /might/
manage to only damage a portion of a block.

Enemy action is far more likely to produce failures that don't get caught
in the network stack. In a case like this is enemy going to bother only
damaging 1KB and send the other 15KB to you intact? Why not send as much
corrupt data as possible, and cause the most damage possible? In this
case it is *highly* unlikely that *any* of the data this peer has sent to
you is valid; so why bother verifying 1KB sub-blocks when almost
certainly the *entire* 16KB (or 32KB with some clients) block that was
sent is bad?

Does this kill 1KB verification for you?

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

I'm not planning to implement them myself either. Does require another
case in a switch statement, so my original statement stands.

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

I have to doubt someone who is grabbing torrents will want to bother with
another P2P network.

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


Unless you plan on breaking SHA collisions will not be a problem.

If you plan on using that flag to distinguish between internal nodes and
data blocks, then you will need to run the hash over it twice to detect
which it is.

(\___(\___(\______          --=> 8-) EHM <=--          ______/)___/)___/)
 \   (    |         EHeM at gremlin.m5p.com PGP 8881EF59         |    )   /
  \_  \   |  _____  -O #include <stddisclaimer.h> O-   _____  |   /  _/
    \___\_|_/82 04 A1 3C C7 B1 37 2A*E3 6E 84 DA 97 4C 40 E6\_|_/___/

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