Re: Back to Merkle Hash Trees...

> 
> 
> >From: Justin Cormack <[email protected]>
> > > I would tend to use the block hash in REQUEST and PIECE messages because
> > > that is enough to uniquely identify the block, offset, and which torrent
> > > it belongs to without any additional information.
> > 
> > no it isnt, 2 torrents could have the same leaf hash somewhere, but be part
> > of different trees. This would be a problem, as they have different parents.
> > Also hashes are 20 bytes which is quite long.
> 
> Replaces piece#, offset and length, 12 bytes for 20. On a multi-torrent
> connection, also takes care of which of the multiple torrents is being
> mentioned (either 4 or 20 bytes). So exchanging 12/16 bytes for 20. Given
> that REQUEST and PIECE messages occur once per piece, these messages are
> less than 0.1% of the bandwidth used. So bandwidth isn't an issue.

true.
 
> As to collisions. You've claimed knowledge of Cryptography, so you should
> know the numbers just as well as I do. 2^80th blocks before you hit a 50%
> chance of a collision with SHA1. We're discussing block sizes of 16KB or
> 32KB. So the combined torrents will have to be 2^96 bytes for a 50%
> chance. More than 65,536 yottabytes (the listing of prefixes I found
> topped out at 10^24/2^80/yotta).
> 
> Such a large collection is a vague concern for a super-huge cache in
> maybe 30 years time. By that point we'd be worrying about having to go to
> something larger than 64-bit data types in the protocol to handle so much
> data. I'll admit this is something to be aware of and a concern for the
> future, but the chance of two leaves on two distinct torrents on the
> whole of the planet Earth having the same hash value within the next ten
> years is pretty well zero. You're okay to mention it as a concern for the
> future, but your Cryptography reputation with me it fading for suggesting
> it is a severe concern now.

I am talking about the case where the leaf data is the same hence the hash
the same for 2 different torrents.

I was thinking that if this happens you get a rather messy data structure.

However I think you could work around it quite nicely.

Issues:

1. Means you have to fix the piece size, and no requests for smaller chunks
can be made.
2. for Merkle trees, you still have to number internal hashes. It would be
nice if it removed all necessity for numbering, so the protocol became data
structure independent. (It fits very well with a modified BT1).
3. You need a have torrent message so when you connect to a peer you know
which torrents it has, and if it joins any later on.

j



 
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:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/