[BitTorrent] BT2 & hash trees

Olaf van der Spek OvdSpek at LIACS.NL
Wed Jul 21 06:15:11 EDT 2004

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

>>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.
>>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.
Olaf van der Spek

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