[BitTorrent] BT2 & hash trees

John Prevost j.prevost at gmail.com
Tue Jul 20 07:52:01 EDT 2004


The key argument I've seen to having two different hash functions is
that it reduces the amount of information that has to be shared
securely.  If you use the same hash function for both, you can do
something like this:

  H(H(H(A)+H(B))+H(H(C)+H(D)))
         /             \
    H(A)+H(B)       H(H(C)+H(D))
     /     \           /      \
  H(A)    H(B)       H(C)    H(D)

File: A B C D

Here we have a file with four blocks (let's say they're 16kB blocks),
so the file size is somewhere between 48kB and 64kB.)  The same root
hash can be created by doing the following:

  H(H(H(A)+H(B))+H(X))
       /         \
   H(A)+H(B)     H(X)
    /    \         \
  H(A)   H(B)      H(X)

File: A B X

The root hash here is identical, if the data contained in X is
H(H(C)+H(D)).  Now the file size is 32kB + 20B.  In short, it's
trivial without a different internal hash function to produce a
different shorter message with the same hash value.

In BitTorrent version 1, the info_hash of the file is based on the
filename, file size, and concatenated hashes of all of the block
hashes.  In BitTorrent version 2, we could choose to leave out the
filename and file size and use only the root hash of the merkle tree
for each file.  (With a good Merkle hash, the file size cannot be
changed trivially, although it also cannot be known without receiving
all of the hashes.)

It's unclear to me whether this is really useful or not.  Being able
to have the file names change without changing the torrent info is in
some ways useful: there are some torrents where this sort of change is
not unreasonable.  On the other hand, certain other torrents
(especially batch torrents of, say, a Linux distribution) you'd like
to have an overall hash validating "all of these files with these
specific pathnames and root hashes go together."

Again, I'm trying to wait for more input from Bram Cohen on what he
intends to do with the tree hashes and cross-torrent trading before
speculating too much more.

John.


------------------------ Yahoo! Groups Sponsor --------------------~--> 
Yahoo! Domains - Claim yours for only $14.70
http://us.click.yahoo.com/Z1wmxD/DREIAA/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