[BitTorrent] BT2 & hash trees

Elliott Mitchell ehem at m5p.com
Tue Jul 20 22:33:01 EDT 2004

>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > >From: Olaf van der Spek <OvdSpek at LIACS.NL>

> > > > 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
> 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
transfered 256 times the amount of data you needed. If you've identified
that some part of the piece is bad, you now need to verify 16KB or 32KB
blocks, luckily you've already got that data as you got 1KB granularity
when you only needed 256KB granularity; however, you've now got a minimum
of 16 times the data you needed.

Given this issue, at the baseline you hash 16KB or 32KB blocks (depends
on what the protocol mandates). Next level would hash of 4, 8, or 16
hashes (again depending on the lowest level block size, and the piece
size). After that it comes down to what is efficient to use in BT packets
and a reasonable branching factor.

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

>From: John Prevost <j.prevost at gmail.com>
> 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.

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.
Unless you manage to break the hash algorithm, you're going to need to
generate and test strings until you find out that produces the
appropriate output. With SHA1 you're going to need to test roughly 2^159
strings, if you start now you'll have better odds of winning the lottery
than finding an appropriate string before the Sun exhausts all its fuel
and goes out.

This is one of the attacks secure hashes are *deliberately* designed to
defend against. Given that Merkle trees are *only* useful if used with
secure hashes, the original point holds, how is this useful? Olaf has
pointed out one thing, it can be used to detect leaves (though at a
pretty high computational cost).

I think I best leave the more thorough job of murdering this issue to
private e-mail. Be assured, this is a *very* dead point.

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