[BitTorrent] BT2 & hash trees

Elliott Mitchell ehem at m5p.com
Mon Jul 19 18:28:45 EDT 2004

Gregorio, would you mind setting your mailer to wrap lines at less than
80 characters, rather than 88? It is rather irritating to deal with lines
that are 88 characters wide.

>From: Gregorio Roper <gregorio at gmx.li>
> Elliott Mitchell wrote:
> >>From: Gregorio Roper <gregorio at gmx.li>
> >>Is there any chance of using a block size of 1024 bytes for the hash tree, since it 
> >>completely removes any limitations imposed by the block size, even for small files and 
> >>it's also the block size recommended by THEX[1] which is used by several p2p networks that 
> >>could then be used as a backup in case the tracker fails.
> > 
> > 1024 would make sense if the protocol could address blocks that small.
> > As only a few discrete block sizes make sense (somewhere in the 16KB or
> > 32KB range), trying to limit the block# to be a byte makes sense. If a
> > bit is allocated to indicate block size, you can address 128 blocks,
> > which means a minimum of 2K blocks for 256KB pieces (and then the issue
> > of whether to allow selectible larger block sizes comes up).
> 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?

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?

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

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

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

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