[BitTorrent] BT2 & hash trees

Elliott Mitchell ehem at m5p.com
Wed Jul 21 16:43:00 EDT 2004

>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> Elliott Mitchell wrote:
> >>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> >>No, you don't. The minimum block size can be larger than the base segment
> >>size of the tree, the only requirement is that it's a multiple.
> >>So a 1 kb base segment size still allows blocks of 16 kb, 1 mb, 1 gb or 1
> >>tb.
> > 
> > "the only requirement is that it's a multiple." Precisely, you transfer
> > a block of 1024 hashes to cover verification of 1MB of data. Given that
> > at the most sparse, you're verifying 128KB or 256Kb pieces, you've
> That's not what I meant with a multiple. If you start with leaves of 1 
> kb, you could throw away the bottom of the tree to get a tree with 
> 'leaves' of 16 kb, 256 kb, 1 mb or whatever.
> However, while you 'throw away' those layers, the root hash stays the same.
> While if you start with 16 kb leaves right away, you get another root hash.

Ah, just suggesting 1KB blocks at the bottom and sticking with a
branching factor of two. That will work, though not ideal here (packing
more together would use fewer SHA1 passes, and less setup/teardown time).

> >>Not using 1 kb is sure to not allow any compatibility.
> >>I didn't mean new hash functions (my fault :( ), but new uses of existing
> >>hash functions.
> >>Linux distributions for example often publis md5 and sha1 sums. In the
> >>future they could publish merkle-sha1, but that would only be useful if 'we'
> >>'both' used the same base segment size.
> > 
> > And what reason is there for them to publish SHA1 hashes from a Merkle
> > tree? The obvious reason would be if they're using BitTorrent to
> > distribute files; however, in this case interoperability isn't an issue
> > as BT is likely continue working with itself. I don't know of any other
> > tools (existing or planned) that use Merkle trees.
> Well, FTP/HTTP downloads might be one candidate. You get the root from a 
> trusted source and can then download the rest from mirrors.

Yes, but they don't do that. If they do such a thing they're more likely
to resort to sticking all the hashes in a file and signing /that/.
Resulting in a construct that is similar to a Merkle tree, but not
compatible in any way with BT.

> >>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.
> > 
> > I fear there will be a torrent (haha) of answers pointing this out, but
> > no, it is very definitely not trivial. In fact it is near impossible.
> It depends on where you start. If you have 4 kb data and generate a tree 
> of 4 + 2 + 1 = 7 nodes, I could give you a file of 4 kb, a file of 40 
> bytes and a file of 20 bytes that would all result in the same root 
> hash. And that's clearly not what you want.

Yes, in theory it is possible to do that. Thing is it is computationally
infeasible to produce those 20 and 40 bytes strings with the same hash.
Adding the cookie to the SHA1 hash doesn't make this significantly more
difficult. With or without the cookie you're not going to produce one in
the next decade.

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