Standards (was [BitTorrent] Back to Merkle Hash Trees...)

Olaf van der Spek OvdSpek at LIACS.NL
Tue Feb 8 04:47:56 EST 2005

Justin Cormack wrote:
>>>32 bits for the piece. I thought everyone had pretty much agreed that 1k/4k
>>2^47 bytes doesn't look like a 'big' limitation.
> Its a bit too small, 128TB, as it is within range of the size of filesystems
> people have now, let alone a few years in the future.

Let's just say I'd love to hit that limitation.

>>>your xbt url doesnt support a multifile torrent.
>>Why not?
>>It's the info_hash that's included, not the root hash of a single file.
> But the info_hash isnt sufficient information to verify a torrent. Of course

Why not?
With the info_hash, you can verify the info key and with the info key 
you can verify the rest.

> one logical thing would be to Merkle hash the individual file hashes into
> one hash...
> ok re see belows above.
> One of the points of Merkle hashes is that you dont really need the piece/chunk
> distinction.
> I can see what you are doing, keeping the distinction means fewer have messages
> (though you negate this somewhat as the chunk_have messages clearly have a
> useful purpose, even if only at some times).

It's not just that. It's also a smaller bitfield message and smaller 
in-memory bitfields.

> There are a lot of options available once one gets this flexibility, and it
> is probably best to scrap the piece/chunk distinction.
> Call the smallest verifiable unit SVU (say 4k).
> One option would be that if have messages are a range of SVUs (or SVU + length)
> and requests have lengths then you could have a standard algorithm to ramp
> up request sizes as downloads progress, for example, or make this rarity
> based. This would amortise the slightly large have and request messages for
> small requests with those for larger requests later.

I thought about something like that, but someoone else suggested I kept 
the protocol as simple as possible. I wanted to include a 32-bit vector 
in the request, along with a piece index. That'd allow you to request 
between 0 and 32 chunks of one piece with one request. Another 
optimization would be to allow multiple requests per request message.
The same could be done for have and cancel messages.

Another issue is random access IO. If a seek takes 10 ms, you can only 
do 100 seeks per second and with chunks of 4 kb, that'd mean a top of 
400 kb. If you don't have pieces and peers requests chunks completely at 
random, you can't do read-ahead.

Yahoo! Groups Links

<*> To visit your group on the web, go to:

<*> To unsubscribe from this group, send an email to:
    BitTorrent-unsubscribe at

<*> Your use of Yahoo! Groups is subject to:

More information about the BitTorrent mailing list