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

Elliott Mitchell ehem at m5p.com
Fri Jun 25 23:47:26 EDT 2004

After spending about a week attempting to resolve what I'm guessing is
a Yahoo Groups vs SpamAssassin fight...

>From: "pg94au" <yahoo_alias at blinkenlights.org>
> --- In BitTorrent at yahoogroups.com, Elliott Mitchell <ehem at m...> wrote:
> > This adds to anonimity by allowing for lack of a better term, better
> > "zombie" clients that simply obey instructions to get such pieces
> via
> > such and such a tracker. This could be used by a group of peers
> with a
> > high-bandwidth secondary connection (such as 802.11, or
> sneakernet), and
> > allowing the clients to get files much more quickly while the
> "zombie"
> > clients can have full deniability (without knowledge of how to
> reassemble
> > pieces, they cannot know what they're getting).
> Unless you're talking about setting up a zombie that just finds random
> pieces and reshares them (ie. no instructions on which specific pieces
> to get are given to it), then you can't deny anything.  Those watching
> you will find out what piece X is a part of, the same way you did
> before you requested it.

How? In acting as a helper; the helper would need the hash of the whole
(for the handshake), and the hash of pieces to request; no other
information is ever required to be present.

Given this there are three things that may or may not be present and are
required in order to recreate the file. First, the entirety of the file,
a helper doesn't need the entire file to be useful and as pieces are
designated by hash it doesn't even know what additional pieces would be
needed to complete. Second, which pieces belong to the particular file,
the helper can help with multiple torrents and only track piece hashes
(save each piece as a file named by the hash of the piece), these can be
mixed together and make untangling the pieces without additional
knowledge of the torrent near impossible. Third, what order the pieces go
in, the hashes don't carry this information, and given enough pieces this
is a very difficult proposition.

Each of these is very hard to solve without knowledge of the full
torrent, and none of that is required to be available on a helper; so the
helper can deny knowledge of the torrent, and the master can be assured
of privacy. This can be obtained with with traffic analysis, mainly an
adjusted client, but not purely by what is present on the helper.

>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > >From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > > Elliott Mitchell wrote:
> > > >>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > > >>Elliott Mitchell wrote:
> > > >>
> > > >>>>From: Olaf van der Spek <OvdSpek at LIACS.NL>
> > > >>>>Yes, a piece size of between 16 kb and 64 kb would be required and
> that
> > > >>>>would significantly increase the protocol overhead compared with 2
> mb
> > > >>>>pieces.
> > > >>>
> > > >>>
> > > >>>Really?
> > > >>
> > > >>You'd have to send more HAVEs and you need more hashes.
> > > >
> > > > Yes, but how large is that? 8-12 additional bytes is not much
> additional
> > > > data unless you're sending out *lots* of them (either a tiny block
> size
> > > > or a massive number of peers).
> > >
> > > Or both.
> > > What's your definition of a tiny block size?
> > > And of a massive number of peers?
> >
> > Well, I've already pointed out that for 256K blocks (current default for
> > the mainstream) and 50 peers (towards the upper end for the mainstream),
> > the overhead is less than 0.5% of the size of the payload.
> >
> > So looking at the worst case. Is 100 peers and 16KB chunks a sufficiently
> > ridiculous for you? At this point we get 1 REQUEST message, 1 PIECE
> 100 peers isn't that much, but it's a reasonable case.

Quite a bit more than the defaults in the mainline client though, and I
suspect more than needed for a fast download.

> > message, and 100 HAVE messages for each chunk. So an additional 1632
> 16 bytes per HAVE?
> You'd need extra HAVE combining logic for that and even then you probably
> need to take into account IP/TCP overhead.

16 additional bytes per HAVE. 9 total bytes for the V1 protocol, or 25
total bytes for my proposal. The really nasty part is an additional 40
bytes of TCP/IP headers may be required.

> > bytes of overhead will be used, for a little less than 10% additional
> > overhead for a *really* bad case.
> >
> > Of these two numbers I think the first (0.5%) is the better estimate,
> A chunk size of 256 kb doesn't sound realistic.

Again this was taken straight from the mainline client. There are a lot
of optimizations that can be done though. First, you can skip sending out
HAVE messages to peers that already have the piece (as part of the sample
implementation I've implemented this). Second, this is a place where
using partial hashes is a big win; as interested clients are likely not
to have collision issues, and the ones where collisions are likely will
be large caches which aren't in the process of downloading anyway (and
will therefore ignore ambiguous HAVEs).

Looking at these numbers, there seem to be two places where protocol
bandwidth consumption is an issue. The initial handshake of perhaps 100
bytes with a moderate size torrent per connection, and the HAVE messages
at 9 (or up to 25) bytes per piece per connection. A quick estimate
suggests only about 5 HAVE messages (with the mainstream) need to be sent
before the HAVE bandwidth overtakes the handshake overhead. Given that 5
pieces is a pretty small torrent, this places HAVE messages as the
greatest bandwidth consumer of the BitTorrent protocol.

So looking for savings with the HAVE messages...  What about the approach
of not advising peers of what pieces you have, and instead simply
randomly asking for pieces and sending "don't have it" messages if one
doesn't have a particular piece? For peers with 50% of the pieces
(the average case), an average of two request messages need to be sent
to obtain one partial piece. The bandwidth of denying one has a piece is
noticeable, but likely less than the bandwidth needed for all that
broadcasting of pieces that you just got. There are two special cases,
a new client that has say less than 35% of the pieces for which the
BITFIELD message (or with instead of a super-sparse BITFIELD, a few HAVE
messages) message takes care of things. The second is the case of having
95% of the pieces and the last 5% are rare, normally by pure chance this
shouldn't happen; a possible solution is to note pieces that get
requested repeatedly and rerequest those from peers, not those peers that
initially requested and once a piece is requested twice it should be
noted to send a HAVE if that piece is obtained (or the peer could send a
HAVE to indicate obtaining it). Possibly ask for an updated BITFIELD to
check whether the torrent really is stranded.

Hmm, suddenly it seems like the original topic is back.  :-)

The case I'm interested in, that of a helper/cache, has an additional
optimization possibility. Also additional consequences. Imagine a group
that together has the entirety of a file (and is using sneakernet to
coalesce the entirety) but none has the entirety. Should each of these
clients report to the tracker as a seed? How do they supress HAVE
messages? Despite not having all pieces they're uninterested in being
updated about pieces that peers just got...

> > since with 16KB chunks the BT protocol overhead is already huge (on the
> > order of 25% overhead by itself, without this feature; both are dying
> > because of all the HAVE messages). Is this sufficient to settle bandwidth
> > being an issue?
> >
> > > > So I'll admit care will be needed, but care will be needed anyway. If
> > > > some requirement makes it absolutely impossible, _then_ this will need
> to
> > > > be removed. Until that time do you object to this remaining an idea to
> > > > _try_ to put in place?
> > > >
> > > No.
> >
> > Why not? This seems like a pretty simple and reasonable idea.
> I agree (and that's why I didn't object).

Doh! Misread that, sorry.  %-)

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.

This code allocates the lsb of the 7th (zero-based) of the option bytes
to signal that the client implements by hash mode. AS THIS BIT HAS NOT
EXPERIMENTAL! The messages are pretty similar to the standard protocol;
messages that would carry a piece# have the piece# removed and the hash
placed at the END of the message.

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.

In the case of the piece message the first four bytes are the offset into
the piece. Next in the piece message is a byte indicating the hash
length (the better to keep it small), the two lsbs encode fraction bits
and should be masked off and the next bit left should be set followed by
shift by the value of the rest of the byte for the length of the hash
(hash length = ((lenbyte&0x3)|0x4)<<(lenbyte>>2)), this encoding allows
for longer hashes in the future or the top three bits could be used as
flags, care must be taken that an overflow does not occur when decoding
the hash length byte. The remaining portion of the message is piece data.

Finally the KEYAMB (0x9) message is introduced, first is a byte
designating the original message type that caused the problem, possibly
followed by an offset into a piece, and then the ambiguous hash value.

With this new varient I'd like to suggest these recommendations. As they
are a large consumer of bandwidth, using partial hashes should first be
implemented on HAVE messages. A client should use no fewer bits of hash
in a PIECE message than were used in the REQUEST message to obtain that
piece (and should consider always using the full hash in PIECE messages).
Be careful when implementing responses to KEYAMB messages, there is a
significant danger of security holes with nieve implementations. Notably
a malicious client could send a KEYAMB message claiming to be a response
to a PIECE message never having sent a REQUEST message and induce the
sending of a piece without the bandwidth being accounted for.

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.

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.

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.

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

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

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

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