[BitTorrent] Hash Mode (was: bt2 protocol features)

Elliott Mitchell ehem at m5p.com
Tue Jun 29 19:53:00 EDT 2004

>From: Elliott Mitchell <ehem at m5p.com>
> Okay, time for showing off what I was suggesting in the most precise
> method available, code. Attached are patches for two clients that
> implement the by hash mode I'm suggesting.

> Now the sample implementations. Both of these support refering to pieces
> by partial hash. The mainline client patch uses this capability with HAVE
> messages (as I've established above that this is where bandwidth is
> consumed), additionally this will NOT send out HAVE messages to clients
> that already claim to have a piece (reducing bandwidth use by HAVE
> messages by 50% on minimally seeded torrents). On other messages this
> capability is understood, but unused. The BitTorrent one appears to
> correctly interoperate with the unchanged client, as well as with itself
> in hash mode, and libbt.

> [Non-text portions of this message have been removed]

Doh! Perhaps not text/plain, but they were definitly human
understandable...   Guess on to secondary methods.

> BitTorrent patch. This is the a patch against the mainline client version
> 3.4.2. I've tried to keep to strictly the changes needed to make by hash
> mode work. There are a few changes that aren't strictly needed for by
> hash, notably Encrypter.py:Connection was renamed "RawConnection" as this
> is a TREMENDOUS aid in understanding how the original code works. I'm
> concerned about how the hash-to-index mapping is done, this
> implementation feels like it is shortcircuiting layers, but this was the
> quickest method to get this working. Also retrieval of the
> hash-order/piece-order array feels wrong. Moving the call to tostring()
> on Bitfield though _is_ in the correct place.
> I hereby release the file, BitTorrent.patch, under the terms of the
> original (MIT-style) BitTorrent License, which is included with
> BitTorrent-3.4.2 in the file LICENSE.txt.

Available at http://www.m5p.com/~ehem/BitTorrent.patch

> libbt patch. This is against libbt 1.02. Again I've tried to confine it
> to strictly needed changes. I've been able to successfully download a
> torrent from the mainline client. This /should/ work, problems are most
> likely due to bugs already in libbt (sorry, but this is the truth, libbt
> deserves to be maybe 0.25, an alpha release).
> I hereby release the file, libbt.patch, under the terms of the GNU Public
> License, which is included with libbt-1.02 in the file COPYING.

Available at http://www.m5p.com/~ehem/libbt.patch

I've pointed at the goal I'm looking towards. Be better able to have
multiple systems aid the download of a torrent while preserving the
privacy of the person/system attempting to retrieve the torrent. Taking
advantage of the fact that most end systems aren't using their full
bandwidth 24/7, and aiding the download of large torrents that are of
common interest to a group.

Moving to designating pieces by their hash in the PIECE and REQUEST
messages is one step in this direction because it inhibits the easy
reconstruction of the file(s) with the knowledge a helper is required
to have. The question arises are there more things that can be done
towards aiding this goal?

> The order of bits in the BITFIELD is changed. Instead of the first bit
> designating having piece 0, second indicating having piece 1, etc. The
> first bit designates having the piece with the least numerical hash, and
> the rest of the bits correspond to pieces with increasing hashes. The
> rational for this change is it means helper clients can be given an index
> into the bitfield string without gaining knowledge of where in the file
> the particular piece is located.

This is one thing that comes to mind. I'm pretty sure the reordering of
the BITFIELD message is a correct step to make, as it definitely gives
less information to helpers. Even with traffic analysis they still don't
get any idea what order pieces go in.

I'm now forced to look again at HAVE messages. With the above patches it
is simplest for helpers to get all the hashes as they can then easily
figure out how many peers have which pieces. Requiring helpers to know
all the hashes though is bad if one can avoid it, one option is to have
them pass HAVE messages back to the master but this is wasteful of
bandwidth (though compression would work as the hashes would be
repeated). This forces me to consider reverting HAVE messages back to a
form similar to what they look like in the standard protocol.

This is an interesting thought. Perhaps using a piece# that corresponds
to the ordering in the BITFIELD (order by hash value, rather than by
where in the file it is) might work. This doesn't reintroduce knowledge
of how the pieces go together as the relationship will be arbitrary.
This also allows the helpers to fully analyze the information they have,
and simply tell the master index# is a good choice for them to retrieve
(at which point the master then needs either reject that choice or
resolve the BITFIELD/HAVE index into a REQUEST/PIECE hash).

This doesn't full inhibit traffic analysis as connecting to a non-seed
peer and sending a BITFIELD message with a single-bit set may cause that
peer to ask for that piece, returning a hash without the master's
permission, but at least the master need not give all the hashes.

Using the hash in REQUEST and PIECE messages does still serve a useful
purpose though; as caches can store pieces by hash without gaining the
knowledge of how to fully reconstruct the original file(s). Such caches
simply need to store the bitfield to designate which pieces they have
and you've got a fully useful cache.

(\___(\___(\______          --=> 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 --------------------~--> 
Yahoo! Domains - Claim yours for only $14.70

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