[BitTorrent] BT2 & hash trees

Elliott Mitchell ehem at m5p.com
Tue Jul 20 02:25:24 EDT 2004

>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > > 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?)?

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

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

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?

The scheme of seeding the hash for leaf nodes versus hash nodes merely
depends on all the blocks being the same size. The branching factor is
irrelevant (and in fact the larger hashes will require a lower branching
factor as they can't pack as many hashed into a block).

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

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.

(\___(\___(\______          --=> 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 --------------------~--> 
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