[BitTorrent] Re: Request for protocol extension: get_info/info messages

Bill Cox bill at viasic.com
Tue Jan 18 07:40:18 EST 2005


Hi, Iain.

Ok, the get_info/info mechanism is trivial.  Any incremental scheme is
more work.  That's good enough reason to support get_info/info for now.
Not that my views matter here, but I'll support both of your patches in
btslave.

I've commented more on the Merkle hash trees below, but let's assume I'm
not asking for this as a BT1 extension.

Bill

On Mon, 2005-01-17 at 16:23 +1100, Iain Wade wrote:
> > Would this be a good point to introduce Merkle hash trees, or should we
> > wait for BT2?  The idea is that the get_info/info handshake would return
> > a Merkle hash root for the torrent, rather than the whole info blob.  It
> > would be a tiny message.  Then, we'd have a get_authentication_path /
> > authentication_path handshake to authenticate the piece data.  Only path
> > data up to a requested level in the tree would be returned.
> 
> I'm interested, but have no exposure to these algorithms. I guess for
> them to be usefull I would still like to see them in a validated info
> blob payload and that would require all clients to be updated.. BT2
> perhaps.

Merkle hash trees are simple.  Every piece has a SHA1 hash value, just
as they do now.  These become the leaves of the Merkle tree.  Interior
nodes of the tree have hash values which are the SHA1 of the
concatenation of the hash values of both of it's children.

In a BT protocol, the piece hashes get shared by the peers, and are no
longer in the info-blob.  The info blob only has the SHA1 hash value of
the root of the tree.  This makes torrent info blobs tiny.  AFAIK, this
is the main value of using Merkle hash trees.

To validate data, peers send not only piece data to eachother, but
authentication data as well.  For compatibility with BT1 reasons, it's
probably best to make these separate messages: the old piece message,
and an get_authentication/authentication pair.  The authentication data
is a set of SHA1 hash keys, starting with the piece's sibling leaf in
the tree, and goes up the tree, providing sibling hash keys.  With the
piece, and it's sibling's hash value, you can compute the hash value one
level up in the tree.  With that node's sibling's hash value, you can go
further up the tree.  When you get to the root, you should get the same
value as was advertised in the info-blob.  If there is any false data,
the root value and your value wont match.

The scheme as described by Bram still leaves file names and an info-hash
value per file in the torrent file.  This is good for compatibility with
BT1, but I'd prefer for info-blobs in BT2 to be a very small.  Twenty
bytes would be a good size (just the SHA1 of the root).  Everything else
could be embedded in the piece data (file length, file names, an index
to the files in case you just want part of the data).  There could be an
agreement that piece info hash are computed for every 1K bytes, so piece
size is gone.  You wouldn't waste bandwidth sending SHA1 data down to 1K
byte leaves, because data is sent in bigger gulps than that.

The two things the torrent file needs is a tracker url (8 bytes) and an
info blob (20 bytes).  Then, we could share torrents trivially.

Bill




 
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:
    BitTorrent-unsubscribe at yahoogroups.com

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





More information about the BitTorrent mailing list