The BitTorrent Protocol

The following article was a technical essay I wrote at university many years ago. While it is accurate to my knowledge it is not exhaustive and I have no plans to update it. For a non-technical guide to BitTorrent, please see my Beginners Guide To BitTorrent.


The BitTorrent protocol can be split into the following five main components:

  1. Metainfo File – a file which contains all details necessary for the protocol to operate.
  2. Tracker – A server which helps manage the BitTorrent protocol.
  3. Peers – Users exchanging data via the BitTorrent protocol.
  4. Data – The files being transferred across the protocol.
  5. Client – The program which sits on a peers computer and implements the protocol.

Peers use TCP (Transport Control Protocol) to communicate and send data. This protocol is preferable over other protocols such as UDP (User Datagram Protocol) because TCP guarantees reliable and in-order delivery of data from sender to receiver. UDP can not give such guarantees, and data can become scrambled, or lost all together. The tracker allows peers to query which peers have what data, and allows them to begin communication. Peers communicate with the tracker via the plain text via HTTP (Hypertext Transfer Protocol) The following diagram illustrates how peers interact with each other, and also communicate with a central tracker.

Figure 1 – The interactions between peers and the tracker over the TCP and HTTP protocols.

Data

BitTorrent is very versatile, and can be used to transfer a single file, of multiple files of any type, contained within any number of directories. File sizes can vary hugely, from kilobytes to hundreds of gigabytes.

Piece Size

Data is split into smaller pieces which sent between peers using the bittorrent protocol. These pieces are of a fixed size, which enables the tracker to keep tabs on who has which pieces of data. This also breaks the file into verifiable pieces, each piece can then be assigned a hash code, which can be checked by the downloader for data integrity. These hashes are stored as part of the ‘metinfo file’ which is discussed in the next section.

The size of the pieces remains constant throughout all files in the torrent except for the final piece which is irregular. The piece size a torrent is allocated depends on the amount of data. Piece sizes which are too large will cause inefficiency when downloading (larger risk of data corruption in larger pieces due to fewer integrity checks), whereas if the piece sizes are too small, more hash checks will need to be run.

As the number of pieces increase, more hash codes need to be stored in the metainfo file. Therefore, as a rule of thumb, pieces should be selected so that the metainfo file is no larger than 50 – 75kb. The main reason for this is to limit the amount of hosting storage and bandwidth needed by indexing servers. The most common piece sizes are 256kb, 512kb and 1mb. The number of pieces is therefore: total length / piece size. Pieces may overlap file boundaries.

For example, a 1.4Mb file could be split into the following pieces:

Figure 2 – A file split into 6 pieces.
This shows 5 * 256kb pieces, and a final piece of 120kb.

Metainfo File

When someone wants to publish data using the BitTorrent protocol, they must create a metainfo file. This file is specific to the data they are publishing, and contains all the information about a torrent, such as the data to be included, and IP address of the tracker to connect to. A tracker is a server which ‘manages’ a torrent, and is discussed in the next section. The file is given a ‘.torrent’ extension, and the data is extracted from the file by a BitTorrent client. This is a program which runs on the user computer, and implements the bittorrent protocol. Every metainfo file must contain the following information, (or ‘keys’):

  • info: A dictionary which describes the file(s) of the torrent. Either for the single file, or the directory structure for
    more files. Hashes for every data piece, in SHA 1 format are stored here.
  • announce: The announce URL of the tracker as a string

The following are optional keys which can also be used:

  • announce-list: Used to list backup trackers
  • creation date: The creation time of the torrent by way of UNIX time stamp (integer seconds since 1-Jan-1970 00:00:00 UTC)
  • comment: Any comments by the author
  • created by: Name and Version of programme used to create the metainfo file

These keys are structured in the metainfo file as follows:

{‘info’: {‘piece length’: 131072,
‘length’: 38190848L,
‘name’: ‘Cory_Doctorow_Microsoft_Research_DRM_talk.mp3’,
‘pieces’: ‘\xcb\xfaz\r\x9b\xe1\x9a\xe1\x83\x91~\xed@\…..’,
}
‘announce’: ‘http://tracker.var.cc:6969/announce’,
‘creation date’: 1089749086L
}Figure 3 – The metainfo file structure (taken from btmakemetafile.py written by Bram Cohen [1])

Instead of transmitting the keys in plan text format, the keys contained in the metainfo file are encoded before they are sent. Encoding is done using bittorrent specific method known as ‘bencoding’.

Bencoding

Bencoding is used by bittorrent to send loosely structured data between the BitTorrent client and a tracker. Bencoding supports byte strings, integers, lists and dictionaries. Bencoding uses the beginning delimiters ‘i’ / ‘l’ / ‘d’ for integers, lists and dictionaries respectively. Ending delimiters are always ‘e’. Delimiters are not used for byte strings.

Bencoding Structure:

  • Byte Strings : <string length in base ten ASCII> : <string data>
  • Integers: i<base ten ASCII>e
  • Lists: l<bencoded values>e
  • Dictionaries: d<bencoded string><bencoded element>e

Minus integers are allowed, but prefixing the number with a zero is not permitted. However ‘0’ is allowed.

Examples of bencoding:

4:spam // represents the string “spam”
i3e // represents the integer “3”
l4:spam4:eggse // represents the list of two strings: [“spam”,”eggs”]
d4:spaml1:a1:bee // represents the dictionary {“spam” => [“a” , “b”] }

Figure 4 – Examples of bencoded data types(examples taken TheoryOrg [2])

Metainfo File Distribution

Because all information which is needed for the torrent is included in a single file, this file can easily be distributed via other protocols, and as the file is replicated, the number of peers can increase very quickly. The most popular method of distribution is using a public indexing site which hosts the metainfo files. A seed will upload the file, and then others can download a copy of the file over the HTTP protocol and participate in the torrent.

Tracker

A tracker is used to manage users participating in a torrent (know as peers). It stored statistics about the torrent, but its main role is allow peers to ‘find each other’ and start communication, i.e. to find peers with the data they require. Peers know nothing of each other until a response is received from the tracker. Whenever a peer contacts the tracker, it reports which pieces of a file they have. That way, when another peer queries the tracker, it can provide a random list of peers who are participating in the torrent, and have the required piece.

Figure 5 – A tracker providing a list of peers with the required data
A tracker is a HTTP/HTTPS service and typically works on port 6969. The address of the tracker managing a torrent is specified in the metainfo file, a single tracker can manage multiple torrents. Multiple trackers can also be specified, as backups, which are handled by the BitTorrent client running on the users computer. BitTorrent clients communicate with the tracker using HTTP GET requests, which is a standard CGI method. This consists of appending a “?” to the URL, and separating parameters with a “&”. For example:

http://tracker.com/announce.php?var1=value&var2=value

The parameters accepted by the tracker are:

  • info_hash: 20-byte SHA1 hash of the info key from the metainfo file.
  • peer_id: 20-byte string used as a unique ID for the client.
  • port: The port number the client is listed on.
  • uploaded: The total amount uploaded since the client sent the ‘started’ event to the tracker in base ten ASCII.
  • downloaded: The total amount downloaded since the client sent the ‘started’ event to the tracker in base ten ASCII.
  • left: The number of bytes the client till has to download, in base ten ASCII.
  • compact: Indicates that the client accepts compacted responses. The peer list can then be replaced by a 6 bytes per peer.
    The first 4 bytes are the host, and the last 2 bytes are port.
  • event: If specified, must be one of the following: started, stopped, completed.
  • ip: (optional) The IP address of the client machine, in dotted format.
  • numwant: (optional) The number of peers the client wishes to receive from the tracker.
  • key: (optional) Allows a client to identify itself if their IP address changes.
  • trackerid: (optional) If previous announce contained a tracker id, it should be set here.

The tracker then responds with a “text/plain” document with the following keys:

  • failure message: If present, then no other keys are included. The value is a human readable error message as to why the
    request failed.
  • warning message: Similar to failure message, but response still gets processed.
  • interval: The number of seconds a client should wait between sending regular requests to the tracker.
  • min interval: Minimum announce interval.
  • tracker id: A string that the client should send back with its next announce.
  • complete: Number of peers with the complete file.
  • incomplete: number of non-seeding peers (leechers)
  • peers: A list of dictionaries including: peer id, IP and ports of all the peers.

Scraping

Scraping is the process of querying the state of a given torrent (or all torrents) that the tracker is managing. The result is known as a “scrape page”. To get the scrape, you must start with the announce URL, find the last ‘/’ and if the text immediately following the ‘/’ is ‘announce’, then this can be substituted for ‘scrape’ to find the scrape page.

Examples:

Announce URL Scrape URL
http://example.com/annnounce –> http://example.com/scrape
http://example.com/a/annnounce –> http://example.com/a/scrape
http://example.com/announce.php –> http://example.com/scrape.php
http://example.com/a –> (scrape not supported)
http://example.com/%annnounce –> (scrape not supported)
http://example.com/announce?data=2 –> http://example.com/scrape?data=2
http://example.com/announce?data=2/4 –> (scrape not supported)

Figure 6 – Examples of valid and invalid tracker scrape URL’s (examples taken TheoryOrg [2])

The tracker then responds with a “text/plain” document with the following bencoded keys:

  • files: A dictionary containing one key pair for each torrent. Each key is made up of a 20-byte binary hash value. The value of that key is then a nested dictionary with the following keys:
  • complete: number of peers with the entire file (seeds)
  • downloaded: total number of times the entire file has been downloaded.
  • incomplete: the number of active downloaders (lechers)
  • name: (optional) the torrent name

For example:

d5:filesd20: ….. d8:completei5e10:downloadedi50e10:oncompletei10eeee// showing 5 seeds, 10 leechers and 50 complete downloads. The dots
// represents the 20-byte info_hash which has been omitted.

Figure 7 – Example of a bencoded dictionary, as sent by the tracker.

If the tracker replies with a failure reason, then this can be mapped to a human readable error. The tracker also provides a time interval that the peer should wait before re-trying.

Peers

Peers are other users participating in a torrent, and have the partial file, or the complete file (known as a seed). Pieces are requested from peers, but are not guaranteed to be sent, depending on the status of the peer. BitTorrent uses TCP (Transmission Control Protocol) ports 6881-6889 to send messages and data between peers, and unlike other protocols, does not use UDP (User Datagram Protocol)

Piece Selection

Peers continuously queue up the pieces for download which they require. Therefore the tracker is constantly replying to the peer with a list of peers who have the requested pieces.

Which piece is requested depends upon the BitTorrent client. There are three stages of piece selection, which change depending on which stage of completion a peer is at.

Random First Piece

When downloading first begins, as the peer has nothing to upload, a piece is selected at random to get the download started. Random pieces are then chosen until the first piece is completed and checked. Once this happens, the ‘rarest first’ strategy begins.

Rarest First

When a peer selects which piece to download next, the rarest piece will be chosen from the current swarm, i.e. the piece held by the lowest number of peers. This means that the most common pieces are left until later, and focus goes to replication of rarer pieces.

At the beginning of a torrent, there will be only one seed with the complete file. There would be a possible bottle neck if multiple downloaders were trying to access the same piece. rarest first avoids this because different peers have different pieces. As more peers connect, rarest first will the some load off of the tracker, as peers begin to download from one another.

Eventually the original seed will disappear from a torrent. This could be because of cost reasons, or most commonly because of bandwidth issues. Losing a seed runs the risk of pieces being lost if no current downloaders have them. Rarest first works to prevent the loss of pieces by replicating the pieces most at risk as quickly as possible.

If the original seed goes before at least one other peer has the complete file, then no one will reach completion, unless a seed re-connects.

Endgame Mode

When a download nears completion, and waiting for a piece from a peer with slow transfer rates, completion may be delayed. To prevent this, the remaining sub-pieces are request from all peers in the current swarm.

Peer Distribution

The role of the tracker ends once peers have ‘found each other’. From then on, communication is done directly between peers, and the tracker is not involved. The set of peers a BitTorrent client is in communication with is known as a swarm.

To maintain the integrity of the data which has been downloaded, a peer does not report that they have a piece until they have performed a hash check with the one contained in the metainfo file.

Peers will continue to download data from all available peers that they can, i.e. peers that posses the required pieces. Peers can block others from downloading data if necessary. This is known as choking.

Choking

When a peer receives a request for a piece from another peer, it can opt to refuse to transmit that piece. If this happens, the peer is said to be choked. This can be done for different reasons, but the most common is that by default, a client will only maintain a default number of simultaneous uploads (max_uploads) All further requests to the client will be marked as choked. Usually the default for max_uploads is 4.

Figure 8 – A seed chokes the connection to a peer because it has reached its maximum uploads.
The peer will then remain choked until an unchoke message is sent. Another example of when a peer is choked would be when downloading from a seed, and the seed requires no pieces. To ensure fairness between peers, there is a system in place which rotates which peers are downloading. This is know as optimistic unchoking.

Optimistic Unchoking

To ensure that connections with the best data transfer rates are not favoured, each peer has a reserved ‘optimistic unchoke’ which is left unchoked regardless of the current transfer rate. The peer which is assigned to this is rotated every 30 seconds. This is enough time for the upload / download rates to reach maximum capacity.

The peers then cooperate using the tit for tat strategy, where the downloader responds in one period with the same action the uploader used in the last period.

Communication Between Peers

Peers which are exchanging data are in constant communication. Connections are symmetrical, and therefore messages can be exchanged in both directions. These messages are made up of a handshake, followed by a never-ending stream of length-prefixed messages.

Handshaking

Handshaking is performed as follows:

  1. The handshake starts with character 19 (base 10) followed by the string ‘BitTorrent Protocol’.
  2. A 20 byte SHA1 hash of the bencoded info value from the metainfo is then sent. If this does not match between peers the connection is closed.
  3. A 20 byte peer id is sent which is then used in tracker requests and included in peer requests. If the peer id does not match the one expected, the connection is closed.

Message Stream

This constant stream of messages allows all peers in the swarm to send data, and control interactions with other peers.

Prefix Message Structure Additional Information
0 choke <len=0001><id=0> Fixed length, no payload. This enables a peer to block another peers request for data.
1 unchoke <len=0001><id=1> Fixed length, no payload. Unblock peer, and if they are still interested in the data, upload will begin.
2 interested <len=0001><id=2> Fixed length, no payload. A user is interested if a peer has the data they require.
3 not interested <len=0001><id=3> Fixed length, no payload. The peer does not have any data required.
4 have <len=0005><id=4><piece index> Fixed length. Payload is the zero-based index of the piece. Details the pieces that peer currently has.
5 bitfield <len=0001+X><id=5><bitfield> Sent immediately after handshaking. Optional, and only sent if client has pieces. Variable length, X is the length of bitfield. Payload represents pieces that have been successfully downloaded.
6 request <len=0013><id=6><index><begin><length> Fixed length, used to request a block of pieces. The payload contains integer values specifying the index, begin location and length.
7 piece <len=0009+X><id=7><index><begin><block> Sent together with request messages. Fixed length, X is the length of the block. The payload contains integer values specifying the index, begin location and length.
8 cancel <len=13><id=8><index><begin><length> Fixed length, used to cancel block requests. payload is the same as ‘request’. Typically used during ‘end game’ mode.

Figure 9 – The different types of messages sent between peers (adapted from TheoryOrg [2])

A peer will be ‘interested’ in data if there is a peer which has the required pieces. If the peer which has this data is not choked, then data will be transferred.

After handshaking, by default, connections start out as choked, and not interested.

BitTorrent Clients

A BitTorrent client is an executable program which implements the BitTorrent protocol. It runs together with the operating system on a users machine, and handles interactions with the tracker and peers. The client is sits on the operating system and is responsible for controlling the reading / writing of files, opening sockets etc.

A metainfo file must be opened by the client to start partaking in a torrent. Once the file is read, the necessary data is extracted, and a socket must be opened to contact the tracker. BitTorrent clients use TCP ports 6881-6999. To find an available port, the client will start at the lowest port, and work upwards until it finds one it can use. This means the client will only use one port, and opening another BitTorrent client will use another port. A client can handle multiple torrents running concurrently.

Clients come in many flavours, and can range from basic applications with few features to very advanced, customisable ones. For example, some advanced features are metainfo file wizards and inbuilt trackers. These additional features means different clients behave very differently, and may use multiple ports, depending on the number of processes it is running. As all applications implement the same protocol, there is no incompatibility issues, however because of various tweaks and improvements between clients, a peer may experience better performance from peers running the same client.

7 Comments

VirtualII

about 5 years ago

Brilliant

Reply

Farley

about 6 years ago

This is a very nice introduction though some clarification may be needed.

In the tracker section, you mentioned that "Whenever a peer contacts the tracker, it reports which pieces of a file they have. That way, when another peer queries the tracker, it can provide a random list of peers who are participating in the torrent, and have the required piece."

However, I cannot find the info in the response from the tracker. How did you get that? What's the source you refer to?

Thanks.

Reply

Leave a Comment

Please be polite. We appreciate that.
Your email address will not be published and required fields are marked


css.php