GitTorrent Protocol -- GTP/0.1

Abstract

This document describes the GitTorrent Protocol version 0.1, referred to as "GTP/0.1". The GitTorrent Protocol (GTP) is a protocol for collaborative git repository distribution across the Internet. It is best classified as a peer-to-peer (P2P) protocol, although it also contains centralized elements.

Git is a decentralized version control system (VCS) created in the beginning of 2005 by Linus Torvalds. To date only client-server based distribution has been supported. Although git is already able to densely exchange updates between repositories and thereby minimize the overall resource requirements for distribution, this will occasionally involve clients cloning a complete repository. This places much strain on sites hosting many git repositories in terms of request-processing and sheer bandwidth. It is the goal of GTP to facilitate such hosting sites in reducing resource demands by using P2P distribution.

Normally a client does not use their upload capacity while downloading a repository. The GTP approach capitalizes on this fact by having clients upload bits of the repository data to each other. In comparison to the original client-server distribution, this adds huge scalability and cost-management advantages. People can set up "mirrors" of torrents, and have them advertised with less administration and more convenience to the user than setting up a regular mirror.

Table of Contents

1.  Introduction
1.1.  Compatibility and Extensions
1.2.  Audience
1.3.  Terminology
1.4.  Overall Operation
2.  Bencoding
2.1.  Scalar Types
2.2.  Compound Types
3.  Discovering Peers
4.  Repository References
5.  Objects, Commit-Reels and Blocks
5.1.  Objects
5.2.  Commit-Reels
5.3.  Blocks
6.  The Metainfo File
6.1.  The Structure of the Metainfo File
7.  The Tracker HTTP Protocol
7.1.  Request
7.2.  Response
7.3.  Tracker Considerations
8.  The Peer Wire Protocol
8.1.  Peer Wire Guidelines
8.1.1.  Explorative Phase
8.1.2.  Path Evaluation
8.1.3.  Download Phase
8.1.4.  Changing paths
8.2.  Handshaking
8.3.  Message Communication
8.3.1.  Peer States
8.4.  Peer Wire Messages
8.5.  State-oriented Messages
8.5.1.  Choke
8.5.2.  Unchoke
8.5.3.  Interested
8.5.4.  Uninterested
8.5.5.  Peers
8.5.6.  References
8.5.7.  Reels
8.5.8.  Blocks
8.6.  Data-oriented Messages
8.6.1.  Scan
8.6.2.  Request
8.6.3.  Play
8.6.4.  Stop
9.  Security Consideration
9.1.  Tracker HTTP Protocol Issues
9.2.  Denial of Service Attacks on Trackers
9.3.  Peer Identity Issues
9.4.  DNS Spoofing
9.5.  Issues with File and Directory Names
9.6.  Validating the Integrity of Data Exchanged Between Peers
9.7.  Transfer of Sensitive Information
10.  IANA Considerations
11.  References
§  Authors' Addresses

1.  Introduction

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 (Bradner, S., “Key words for use in RFCs to Indicate Requirement Levels,” March 1997.) [RFC2119].

The existing distribution protocols provide secure and reliable transmission of large git repositories over the Internet. However, their highly centralized client-server approach also means that it is inadequate for mass publication of files, since a single point may expect to be requested by a critically large number of clients simultaneously. To remedy this situation many organizations either implement a cap on the number of simultaneous requests, or spread the load across multiple mirror servers. Needless to say, both approaches have their drawbacks, and a solution that addresses these problems is required.

The approach in the GitTorrent Protocol (GTP) is to spread the load not only across mirror servers, but across the clients themselves, by having them upload objects from the repository to each other while downloading it. Since the clients usually do not utilize their upload capacity while fetching a file, this approach does not disadvantage the clients. This has the added advantage that even small organizations with limited resources can publish large files, or small changes to large projects, on the Internet without having to invest in costly infrastructure.

The basic architecture of GTP is inspired by the BitTorrent protocol, a mature file distribution protocol. Readers familiar with the BitTorrent protocol will find that GTP has many similar concepts. One of the key differences between the GitTorrent Protocol and BitTorrent, is that GitTorrent is specifically designed to deal with repositories that are added to over time, allowing for continual updates. Another difference is that while BitTorrent synchronises "flat" files, GitTorrent synchronises a tree of objects which can grow in any direction.

1.1.  Compatibility and Extensions

The GTP/0.1 should be considered experimental protocol. Future versions of GTP may add new optional features to the protocol. As a result, clients with differing version and feature set can exist. Peers should be designed to be compatible with peers implementing a different version of GTP and not rely on a specific feature set being implemented by another peer. The extensions chosen for the first GTP version are similar to those considered "best practice" by the Bittorrent community.

1.2.  Audience

This document is aimed at developers who wish to implement GTP for a particular platform. Also, system administrators and architects may use this document to fully understand the implications of installing an implementation of GTP. In particular, it is advised to study the security implications in more detail, before installing an implementation on a machine that also contains sensitive data. Security implications are discussed in Section 9 (Security Consideration).

It is assumed that developers are familiar with the git version control system, more specifically the layout of the repository and the design of the object store. This includes the concepts of the commit and general object tree, "thin" pack files and how to validate signed tag objects.

1.3.  Terminology

Peer:

A peer is a node in a network participating in repository sharing. It can simultaneously act both as a server and a client to other nodes on the network.

Neighboring peers:

Peers to which a client has an active point to point TCP connection.

Client:

A client is a user agent (UA) that acts as a peer on behalf of a user.

Torrent:

A torrent is the term for the group of branches that are being shared or downloaded, including all of their associated objects.

Swarm:

A network of peers that actively operate on a given torrent.

Seeder:

A peer that has a complete copy of a torrent.

Tracker:

A tracker is a centralized server that holds information about one or more torrents and associated swarms. It functions as a gateway for peers into a swarm.

Metainfo file:

A text file that holds information about the torrent, e.g. the URL of the tracker. It usually has the extension .gittorrent.

Peer ID:

A 20-byte string that identifies the peer. How the peer ID is obtained is outside the scope of this document, but a peer must make sure that the peer ID it uses has a very high probability of being unique in the swarm. [anchor1] (Persistence across crashes?)

Repo hash:

A SHA1 hash that uniquely identifies the torrent. It is calculated by digesting the 'repo' key in the metainfo file.

Reference object:

A signed git tag object used for distributing the list of repository references, i.e. branches and tags.

Object ID:

All git objects are uniquely identified by a SHA1 value, derived from digesting the object type, length and content.

1.4.  Overall Operation

GTP consists of two logically distinct protocols, namely the Tracker HTTP Protocol (THP), and the Peer Wire Protocol (PWP). THP defines a method for contacting a tracker for the purposes of joining a swarm, reporting progress, notifying branch additions, etc. PWP defines a mechanism for communication between peers, and is thus responsible for carrying out the actual download and upload of the torrent.

In order for a client to download a torrent the following steps must be carried through:

1. A metainfo file must be retrieved.
2. Instructions that will allow the client to contact other peers must be periodically requested from the tracker using THP.
3. The torrent must be downloaded by connecting to peers in the swarm and trading objects using PWP.

To publish a torrent the following steps must be taken:

1. A tracker must be set up.
2. A metainfo file pointing to the tracker and containing information on the structure of the torrent must be produced and published.
3. At least one seeder with access to the complete torrent must be set up.

2.  Bencoding

Bencoding encodes data in a platform independent way. In GTP/0.1 the metainfo file and all responses from the tracker are encoded in the bencoding format. The format specifies two scalar types (integers and strings) and two compound types (lists and dictionaries).

The Augmented BNF syntax (Crocker, D., Ed. and P. Overell, “Augmented BNF for Syntax Specifications: ABNF,” November 1997.) [RFC2234] for bencoding format is:

   dictionary = "d" 1*(string anytype) "e" ; non-empty dictionary
   list       = "l" 1*anytype "e"          ; non-empty list
   integer    = "i" signumber "e"
   string     = number ":" 1*CHAR
   anytype    = dictionary / list / integer / string
   signumber  = number / ("-" number)
   number     = 1*DIGIT
   CHAR       = %x00-FF                    ; any 8-bit character
   DIGIT      = %x30-39                    ; 0-9

2.1.  Scalar Types

Integers are encoded by prefixing a string containing the base ten representation of the integer with the letter "i" and postfixing it with the letter "e". E.g. the integer 123 is encoded as "i123e".

Strings are encoded by prefixing the string content with the length of the string in bytes, followed by a colon. E.g. the string "announce" is encoded as "8:announce". [anchor2] (SV - Consideration should be made of content encoding.)

2.2.  Compound Types

The compound types provides a mean to structure elements of any bencoding type.

Lists are an arbitrary number of bencoded elements prefixed with the letter "l" and postfixed with the letter "e". It follows that lists can contain nested lists and dictionaries. For instance "li2e3:fooe" defines a list containing the integer "2" and the string "foo".

Dictionaries are an arbitrary number of key/value pairs delimited by the letter "d" at the beginning and the letter "e" at the end. All keys are bencoded strings while the associated value can be any bencoded element. E.g. "d5:monthi4e4:name5:aprile" defines a dictionary holding the associations: "month" => "4" and "name" => "april". All keys within a dictionary MUST be sorted alphabetically.

3.  Discovering Peers

Two methods exist for discovering other peers in the swarm. Either peer information can be requested from the tracker, or it can be requested from a neighboring peer. A tracker MAY be used as the initial method for seeding the peer's list of other peers in the swarm, after which the peer SHOULD prefer to discover peers through its neighboring peers to reduce resource demands on the tracker.

While downloading, a peer SHOULD continously discover new peers while it is connected to the swarm to find peers that provide better download rates than its current neightboring peers. Peer rating and selection are discussed in Section 8.1 (Peer Wire Guidelines). Periodically connecting to new peers will also help ensure that reference updates are distributed throughout the swarm faster.

Once a peer has a complete copy of the current torrent, it becomes a Seeder and MAY quiesesce, only passively processing requests for downloads and receiving reference updates, and contacting the tracker at the minimum negotiated frequency. If it receives a suitably authorized reference update via PWP or THP, it MUST no longer consider itself a Seeder, and start fetching the new content. Seeders MAY check with the tracker more frequently to determine whether new updates have been received, but this is not necessary - as once the first peer gets the reference, that peer will start attempting to transfer the new reference list and objects to its peers that used to be considered Seeders. [anchor3] (JF: This section is not so much about discovering peers but the recommended "role" or behavior of a seeder vs. a downloading peer.)

4.  Repository References

New tags and branch updates are announced using reference lists, that contain information about the git commit SHA1 of branch heads and the name and SHA1 of available tags. The reference list enables a peer to know which revision history to trust and consequently which objects to request. The reference list MAY be distributed using both THP and PWP, however, peers SHOULD prefer using the PWP to reduce resource demands on the tracker. Since references lists can be fetched from untrusted neighboring peers, trust is ensured by requiring that all reference information distributed in the swarm is signed. A peer SHOULD verify the signature of all reference lists using the public key available in the metainfo file.

Repository references are distributed in a signed git tag object. It is RECOMMENDED that each new reference tag object refer to its successor to indicate the relation between a newer and older reference object. However, when a peer does not have all reference objects it MAY use the creation date indicated in the tag object to infer a relation between two reference objects. How to verify the authenticity of the signed git tag is beyond the scope of this document.

The format of data embedded in the tag object is the same as the format of the "info/refs" file in the git repository. It is line-oriented, where each line contains a SHA1 and a reference name separated by a tab. Details on how peers should interpret the reference names are beyond the scope of this document. Following is an example:

bd562ca1ef05b91e6dbcddf3ace0c897ef76567e	HEAD
bd562ca1ef05b91e6dbcddf3ace0c897ef76567e	refs/heads/master
bd562ca1ef05b91e6dbcddf3ace0c897ef76567e	refs/heads/origin
7113a59591aab60f979c6993bffa4cdd66236fdf	refs/tags/initial
8dec84bb6b5eb7eb8831582dfd7ebbadb0403474	refs/tags/initial^{}
8567d6dfb446364b823190b9e6c988f0ba72e1ba	refs/tags/review-0.1
bdb69c0458215a761d5ae36c143a8b37cf20e103	refs/tags/review-0.1^{}
f41e03ffa9b0d46f466bb73408c7562e49fcb435	refs/tags/review-0.2
094308b52456b21dd00988f5fc3ee3e5cb1d5a75	refs/tags/review-0.2^{}

The references object may be partial in that not all tags or branches are listed in it. The entity in charge of signing the references objects must make decisions regarding how to best distribute the repository references. For repositories with many branches or tags, it is RECOMMENDED to split up the list of references so as not to require massive reels to be exchanged over the wire. The same applies for repositories with frequent updates, in that partial and smaller reference lists can help to reduce the overhead of of exchanging many reference objects.

A peer MAY choose to only fetch a subset of the references offered in the torrent. GTP/0.1 does not offer a method for peers to announce which references they are fetching, and must therefore fetch all reference objects to stay updated. [anchor4] (JF - [RFC] Pruning objects from rebased branches There is the issue of how a peer should handle branches that fast-forward and branches that may be rebase. Rebasing means that data can actually also dissappear from the swarm. This adds the problem of pruning these objects from the swarm. A peer might have to cancel outstanding requests for objects that are made obsolete. Obsolete objects may reside in packs that are still being exchanged on the wire. Should the peer then repack or not? In the worst case, many objects can be exist that need to be pruned. SV - "repacking" is not really a concept to PWP. The closest concept is 'splicing' Reels (I'm just loving this tape thing...). Any client can choose to eliminate a redundant references object by replacing a number of Reels with a single, longer Reel, which starts at the start point of the first replaced Reel and ends at the end point. So, some clients in the swarm will hold onto the references object which has the abandoned commits; without any subsequent references object which fast- forwards it, it won't be able to make a clean splice. Then it is (hopefully) up to the user to decide whether they want to honour the master server dropping revisions or not.)

5.  Objects, Commit-Reels and Blocks

This section describes how a torrent is organized in objects, commit-reels and blocks.

The torrent is considered to be the entire tree of "objects" referred to by its current list of references. Each object is named using a SHA1 hash which allows the peer to verify the contents of a single object, as well as refer to any object in the repository using a single namespace. Using the repository references as the starting point, and walking all downloaded objects according to the git object hierarchy, the peer is able to verify the complete object store.

When distributing data over PWP, peers request all the new objects between two reference lists as a "commit reel". The new objects are sorted in a defined way and then logically divided into roughly even "blocks" by uncompressed size, dividing only on commit boundaries. The blocks are a logical concept only; responses are "thin" git pack files, which SHOULD be delta compressed against commits preceding them in the commit reel or any other commit reachable from the starting reference list. The results MUST also be gzip compressed, conformant to the requirements of the git pack file format. Specifically, these commit-reels are not merely the structure of the pack files in the underlying git repository.

5.1.  Objects

An object is a single git object, like a commit, tree, blob or tag. Peers can exchange information about what new objects they have by requesting the list of references a neighboring peer makes available, and checking for unknown object IDs in the list.

5.2.  Commit-Reels

A commit reel is defined as a deterministically sorted serialization of objects between two sets of references. It contains all of the new objects that you would get if you already had all the objects required for the first set of references, but not yet the second set. The objects are sorted in such a way that all of the objects that a given object refers to are already available before the object itself. This is called "topological order". However, by itself this leads to ambiguity, so some extra rules are drawn to make the positions of objects within the commit-reel deterministic.

      Level   Sort Order
       1st    Topological sort
       2nd    "commit" time
       3rd    Object SHA1

5.3.  Blocks

The size of a block is an implementation defined value that is not dependent on the size of the commit-reel being requested. Once a block size is determined, the number of blocks in a commit-reel can be calculated using the formula:

        number_of_blocks = (total_reel_size / fixed_block_size)
                         + !!(total_reel_size % fixed_block_size)

where "%" denotes the modulus operator, and "!" the logical negation operator. The logical negation operator is used to ensure that the last factor only adds a value of 0 or 1 to the sum. Given the block number of the block, its offset within a commit-reel can be calculated using the formula:

        reel_offset = block_number * fixed_block_size

To keep the protocol simple, only complete commits are considered to be within blocks, to simplify the generation of "thin" pack files. In optimal operation, these are the only parts that will be transferred. Commits are considered to be "in" a block if the previous commit object completes on or after the beginning of the block. This implies that if single commits span several block boundaries, that some blocks will contain no commits. However, this irregularity of blocks is balanced by the fact that it is expensive to determine the real size of the pack without making it; and this cannot be performed deterministically over the entire swarm without sacrificing much compression ratio and hence the total download requirements of peers.

6.  The Metainfo File

The metainfo file provides the client with information on the tracker location as well as the torrent to be downloaded. Besides listing which branches will result from downloading the torrent, it also provides the client with a public key to verify reference objects.

In order for a client to recognize the metainfo file it SHOULD have the extension ".gittorrent" and the associated the MIME type "application/x-gitttorrent". How the client retrieves the metainfo file is beyond the scope of this document, however, the most user-friendly approach is for a client to find the file on a web page, click on it, and start the download immediately. This way, the apparent complexity of GTP as opposed to FTP or HTTP transfer is transparent to the user.

6.1.  The Structure of the Metainfo File

The metainfo file contains a bencoded dictionary where a key is REQUIRED unless otherwise noted. The dictionary has the following structure:

'comment':

This is an OPTIONAL string value that may contain any comment by the author of the torrent.

'created by':

This is an OPTIONAL string value and may contain the name and version of the program used to create the metainfo file.

'creation date':

This is an OPTIONAL string value. It contains the creation time of the torrent in standard Unix epoch format.

'repo':

This is a dictionary containing information on the repository offered in the torrent.

'alternatives':

This is an OPTIONAL list of string values. It may contain repo hashes for repositories that can be used as an alternative object source for this branch. This tells clients when the object store of a repository can be shared between different torrents.

'description':

This is an OPTIONAL string value that may contain a description of the repository. It may simply be the content from the description file in the git repository.

'pubkey':

This is a string value. It MUST contain the public PGP key that is used by GTP/0.1 to verify reference objects.

'references':

This key points to a list of strings each containing a reference object. The values can be sent to neighboring peers over the wire using the References message. See Section 4 (Repository References) for instructions on how to handle reference objects.

Repository references obtained through reference objects from a metainfo file may be out of date, either with regard to the listed SHA1 or because a new branch or tags has been added. After successfully joining a swarm, a peer SHOULD request new reference object from its neighboring peers to update its repository references. The primary reason for listing reference objects in the metainfo file is to allow peers to present a list of references for the user before beginning downloading the repository.

'trackers':

This is a list of string values. Each value is a URL pointing to a tracker. If multiple trackers are listed, the peer SHOULD choose a tracker at random, and if connection fails, proceed through the list. A peer SHOULD only connect to one tracker at a time.

7.  The Tracker HTTP Protocol

The Tracker HTTP Protocol (THP) is a simple mechanism for introducing peers to each other. A tracker is a HTTP service that is normally contacted by a peer in order to join a swarm. As such, the tracker constitutes the only centralized element in GTP/0.1. A tracker does not by itself provide access to any downloadable data. A tracker records peer advertisements, which expire after a time period negotiated between the peer and the tracker.

7.1.  Request

To contact the tracker a peer MUST send a standard HTTP GET request using an URL from the "trackers" entry of the metainfo file. If one of the tracker URLs are not available another one may be tried. The GET request must be parametrized as specified in the HTTP protocol. The following parameters must be present in the request:

'repo_hash':

This is a REQUIRED 20-byte SHA1 hash value. In order to obtain this value the peer must calculate the SHA1 of the 'repo' key in the metainfo file.

'peer_id':

This is a REQUIRED string and must contain the 20-byte self-designated ID of the peer.

'port':

The port number that the peer is listening to for incoming connections from other peers. GTP/0.1 does not specify a standard port number, nor a port range to be used. This key is REQUIRED.

'uploaded':

This is a base ten integer value. It denotes the total amount of bytes that the peer has uploaded in the swarm since it sent the "started" event to the tracker. This key is REQUIRED.

'downloaded':

This is a base ten integer value. It denotes the total amount of bytes that the peer has downloaded in the swarm since it sent the "started" event to the tracker. This key is REQUIRED.

'completed':

This is a base ten integer value. The value must be 0 if the peer does not have the complete torrent and 1 if it has the complete torrent. Since a peer cannot guarantee that it is a seeder, this value should only be interpreted as an approximation that can help to estimate how many seeders are in the swarm.

'address':

This is an OPTIONAL value, and if present should indicate the true, Internet-wide address of the peer, either in dotted quad IPv4 format, hexadecimal IPv6 format, or a DNS name. When not present, the tracker will derive the IP address from the request connection.

'peers':

This is an OPTIONAL value. If present, it should hold a base ten integer value indicating the number of peers that the local peer wants to receive from the tracker. If not present, the tracker uses an implementation defined value.

'references':

This is an OPTIONAL value. If present, it should hold a base ten integer value indicating the number of references that the local peer wants to receive from the tracker. If not present, the tracker uses an implementation defined value. The references objects returned by the tracker MAY be randomly determined.

'event':

This parameter is OPTIONAL. If not specified, the request is taken to be a regular periodic request. Otherwise, it MUST have one of the two following values:

'started':

The first HTTP GET request sent to the tracker MUST have this value in the "event" parameter.

'stopped':

This value SHOULD be sent to the tracker when the peer is shutting down gracefully.

'valid':

This parameter is OPTIONAL, and specifies the amount of time that our peer address should be advertised, in seconds. If not specified, the tracker may assume it to be an implementation-defined value.

7.2.  Response

Upon receiving the HTTP GET request, the tracker MUST respond with a document having the "application/x-gittorrent" MIME type. This document MUST contain a bencoded dictionary with the following keys: [anchor6] (JF - [RFC] Load balancing trackers using peer redirection Allow the tracker to "redirect" peers to a secondary tracker as a form of "load balancing". Question is if this is really needed, and it also adds the problem that peers can end up being constantly redirected between trackers. SV - perhaps just say that they can just issue a 307 response to the next tracker, but they should not do it multiple times for the same client. A 503 response could also indicate "back off".)

'failure reason':

This key is OPTIONAL. If present, the dictionary MUST NOT contain any other keys. The peer should interpret this as if the attempt to join the torrent failed. The value is a human readable string containing an error message with the reason for failure.

'expires':

This is a value, in seconds, that your address will be advertised for. A peer SHOULD send another THP request to the tracker before this amount of time elapses. It is recommended to wait at least half of this time before contacting the tracker again. If this value is 0, it means that the tracker is not avertising your IP address - for instance, it is a "static tracker". This key is REQUIRED.

'complete':

This is an integer that indicates the number of seeders. This key is OPTIONAL.

'incomplete':

This is an integer that indicates the number of peers downloading the torrent. This key is OPTIONAL.

'peers':

This is a bencoded list of dictionaries containing information about the peers in the swarm. This key is REQUIRED. It has the following structure:

'peer id':

This is a REQUIRED string value containing the self-designated ID of the peer.

'address':

This is a REQUIRED string value indicating the Internet-wide address of the peer. This may be given as a dotted quad IPv4 format, hexadecimal IPv6 format or DNS name.

'port':

This is an integer value. It must contain the self-designated port number of the peer. This key is REQUIRED.

'references':

This is a list of string values containing information about the references in the repository. Each value contains a reference object that can be sent to neighboring peers over the wire using the References message. See Section 4 (Repository References) for instructions on how to interpret the string.

7.3.  Tracker Considerations

The simplest conformant "tracker" is a static file, which is the THP response body. In this case, peers have no option except to discover new peers through its neighboring peers. In this case, the 'expires' value in the response SHOULD be set to 0.

A tracker SHOULD advertise new peers by including their address in the peer list of responses. It SHOULD only advertise it for the amount of time specified by the peer, and return the amount of time that it intends to advertise your address for in the response. This MAY be longer or shorter than the time requested, depending on the implementation of the tracker.

A tracker MAY return its list of peers randomly, and MAY respond with a different number of peers than was asked for. A tracker SHOULD prefer to return peers who have reported that they have downloaded something in responses to new peers, to avoid connecting peers that have no data to exchange with each other. However, they SHOULD return information on all the peers that have requested to be advertised, when repeatedly requested for more peers by individual peers.

A tracker SHOULD start new peers off with a lower value of 'expires' than the maximum configured value, and gradually increase its value as the peer demonstrates its ability to refresh its advertisement with the tracker in a timely fashion. When configuring the maximum honored advertisement length, administrators will have to weigh up the benefits of less load on the tracker against the performance degradation of occasionally sending new peers to "dud" peers who have reneged on their advertising promises. Similarly, unless peers have been specifically configured otherwise, they SHOULD be reserved about the intentions of their users when it comes to choosing advertisement time lengths.

8.  The Peer Wire Protocol

The aim of the PWP, is to facilitate communication between neighboring peers for the purpose of sharing the content of a git repository. PWP describes the steps taken by a peer after it has read in a metainfo file and contacted a tracker to gather information about other peers it may communicate with. PWP is layered on top of TCP and handles all its communication using asynchronous messages.

8.1.  Peer Wire Guidelines

PWP does not specify a standard algorithm for selecting the neighboring peers with which to share objects, although the guidelines in this section should result in an overall more effective swarm.

An important consideration to get the most out of the protocol is to avoid the "Scan" and "Request" messages where possible; they involve transferring unnecessary data (Scan) and do not make best use of delta compression (Request). A perfect session should be possible using only "Play" and "Blocks".

Considerations not mentioned on this section may also come into play; for instance, if a node is found to respond quickly to messages in the explorative phase, then it may help to score more highly paths that include that node. This protocol is designed to replace the global network of software mirrors; and for those it is commonplace to prefer a single nearby mirror. It is reasonable to assume that GitTorrent users may request node selection in this way.

8.1.1.  Explorative Phase

The first thing that a peer does is look for other peers that have useful data.

The tracker may have given enough peers to start with, but the "Peers" message (Section 8.5.5 (Peers)) may also be used at the beginning to expand this net, especially if only a small number of peers can be reached.

Each of the peers should be asked for which commit reels they are tracking via the "Reels" message (Section 8.5.7 (Reels)). If there are any unknown references SHA1s given, then it should ask the peer for those references objects using the "References" message (Section 8.5.6 (References)). The peer would then sort these references in date order and decide which one is the latest (or, in some cases, user-selected).

Then, starting from the beginning of history, it has to try to find a set of paths of connecting reels which lead to the latest references. There may be multiple possible paths, especially if there are many peers available. A preference should be made for paths which contains large reels which are shared among many visible peers.

8.1.2.  Path Evaluation

Once a valid path has been established, the peer would send out "Blocks" messages (Section 8.5.8 (Blocks)) to each of the peers with which it is connected - one for each of the reels included in the paths it is evaluating. The block size chosen should be initially have a mantissa in base 2 expressable in 2-3 digits (eg, a power of 2) and be chosen such that the complete returned "Blocks" message fits into a typical MTU (eg, 1500 bytes).

This can be used to determine how many "effective copies" each of the paths has in the swarm. In general, a peer would exclude paths which fell below a critical level of effective copies.

By this time, the peer may have received a "Choke" message (Section 8.5.1 (Choke)) from the peer to which it has connected. Paths may also be initially excluded if there are no peers which are able to service them.

8.1.3.  Download Phase

Once a path has been decided, blocks can be downloaded. All of the peers in the swarm which are downloading a common set of reels are sent an "Interested" message, and those that are not are sent an "Uninterested" message.

Downloading in rarest-first order can lessen the wait time for objects. This is achieved by scaling all of the received "Blocks" bitmaps to the same block size, then producing an array of integers. For this stage, accuracy of scaling is not important. Blocks should be selected for download randomly, with a bias towards those blocks held by the lowest number of peers.

The connections which are not currently in the "choked" state are picked off, and any number of blocks may be requested, one by one, via the "Play" message (Section 8.6.3 (Play)). No matter what the block size being used by a peer, it is likely to be able to return blocks in the size you are working with. If not, it should hang up.

If there are only a small number of peers in the swarm, it may pay to start with the earliest blocks in the reel, rather than being random. This will facilitate returning to this mode later. In this state, the peer should be more actively checking for more peers, so that it can be sure that it is on the right path.

8.1.4.  Changing paths

As the connected state of the swarm changes over time, new information may come to light that call into question the original decisions made. For instance, there may be no peers which are able to return blocks for the requested reels, or perhaps the download rate is too low. The new challenge becomes how to speed up downloading the new reels most effectively using the reel fragments already downloaded.

The peer switches to a degraded state - it first needs to stocktake all of the packs it has already received. It goes about requesting blocks on the new reel. For each block, instead of requesting it straight away with a "Play" message, it should send a "Scan" message (Section 8.6.1 (Scan)), and check to see whether any of the objects in the block are already locally held. Depending on the relative number of objects already held locally, it might make more sense to issue a "Request" message (Section 8.6.2 (Request)) to fill the gaps.

At some point, the decision is made that the overhead of the "Scan" messages is unlikely to pay off, and the regular download mode is returned to. This decision may be made by checking off all of the loose objects' position in the new reel, or using a gross estimate. The first method is likely to be appropriate if download commenced from the beginning of the initial reel, as described in the previous section.

8.2.  Handshaking

The local peer opens a port on which to listen for incoming connections from remote peers. This port is then reported to the tracker. As GTP/0.1 does not specify any standard port for listening, it is the sole responsibility of the implementation to select a port.

Any remote peer wishing to communicate with the local peer must open a TCP connection to this port and send a handshake message. A handshake message MUST be received before any other messages are sent to the remote peer. If the handshake in any way violates these rules the local peer MUST close the connection with the remote peer.

A handshake is a string of bytes with the following structure:

-----------------------------------------------------------------------
| Name Length | Protocol Name | Extension Flags | Repo Hash | Peer ID |
-----------------------------------------------------------------------

Name Length:

The unsigned value of the first byte indicates the length of a character string containing the protocol name. In GTP/0.1 this number is 7. The local peer knows its own protocol name and hence also the length of it.

Protocol Name:

This is a character string which MUST contain the exact name of the protocol in ASCII and have the same length as given in the Name Length field. The protocol name is used to identify to the local peer which version of GTP the remote peer uses. In GTP/0.1 the name is 'GTP/0.1'.

Extension Flags:

The next 8 bytes in the string are reserved for future extensions, so that peers can exchange information about what optional features they implement. Peers should interpret it according to what extensions they support else it should be read without interpretation. [anchor7] (SV - How are extension designers supposed to know what to put in here?)

Repo Hash:

The next 20 bytes in the handshake specify the repo hash. Presumably, since both the local and the remote peer contacted the tracker as a result of reading in the same ".gittorrent" file, the local peer will recognize the repo hash value and will be able to serve the remote peer. If this is not the case, then the connection MUST be dropped. This situation can arise if the local peer decides to no longer serve the file in question for some reason. The repo hash may be used to enable the peer to serve multiple torrents on the same port.

At this stage, if the connection has not been dropped, the local peer MUST send its own handshake back, which includes the last step:

Peer ID:

The last 20 bytes of the handshake are to be interpreted as the self-designated name of the peer. The local peer must use this name to identify the connection hereafter. Thus, if this name matches the local peers own ID name, the connection MUST be dropped. Also, if any other peer has already identified itself to the local peer using that same peer ID, the connection MUST be dropped.

In GTP/0.1 the handshake has a total of 56 bytes.

8.3.  Message Communication

Following the PWP handshake both ends of the TCP channel may send messages to each other in a completely asynchronous fashion. PWP messages have the dual purpose of updating the state of neighboring peers with regard to changes in the local peer, as well as transferring data blocks between neighboring peers.

PWP Messages fall into two different categories:

State-oriented messages:

These messages serve the sole purpose of informing peers of changes in the state of neighboring peers. A message of this type MUST be sent whenever a change occurs in a peer's state, regardless of the state of other peers. The following messages fall into this category: Interested, Uninterested, Choked, Unchoked, References, Reels, Blocks, and Peers.

Data-oriented messages:

These messages handle the requesting and sending of data portions. The following messages fall into this category: Scan, Request, Play, and Stop.

8.3.1.  Peer States

For each end of a connection, a peer must maintain the following two state flags:

Choked:

When true, this flag means that the choked peer is not allowed to request data.

Interested:

When true, this flag means a peer is interested in requesting data from another peer. This indicates that the peer will start requesting blocks if it is unchoked.

A choked peer MUST not send any data-oriented messages, but is free to send any other message to the peer that has choked it. If a peer chokes a remote peer, it MUST also discard any unanswered requests for blocks previously received from the remote peer.

An unchoked peer is allowed to send data-oriented messages to the remote peer. It is left to the implementation how many peers any given peer may choose to choke or unchoke, and in what fashion. This is done deliberately to allow peers to use different heuristics for peer selection.

An interested peer indicates to the remote peer that it must expect to receive data-oriented messages as soon as it unchokes the interested peer. A peer MUST not assume a remote peer is interested solely because it has pieces that the remote peer is lacking. There may be valid reasons why a peer is not interested in another peer other than data-based ones.

8.4.  Peer Wire Messages

All integer members in PWP messages are encoded as a 4-byte big-endian number. Furthermore, all object block specific offset members in PWP messages are zero-based.

A PWP message has the following structure:

-----------------------------------------
| Message Length | Message ID | Payload |
-----------------------------------------

Message Length:

This is an integer which denotes the length of the message, excluding the length part itself. If a message has no payload, its size is 1. Messages of size 0 MAY be sent periodically as keep-alive messages. Apart from the limit that the four bytes impose on the message length, GTP does not specify a maximum limit on this value. Thus an implementation MAY choose to specify a different limit, and for instance disconnect a remote peer that wishes to communicate using a message length that would put too much strain on the local peer's resources.

Message ID:

This is a one byte value, indicating the type of the message. GTP/0.1 specifies 11 different messages that are presented below.

Payload:

The payload is a variable length stream of bytes.

If an incoming message in any way violates this structure then the connection SHOULD be dropped. In particular the receiver SHOULD make sure the payload matches the the expected payload, as given below.

For the purpose of compatibility with future protocol extensions the client SHOULD ignore unknown messages. There may arise situations in which a client may choose to drop a connection after receiving an unknown message, either for security reasons, or because discarding large unknown messages may be viewed as excessive waste.

Following, are the messages specified in GTP/0.1.

8.5.  State-oriented Messages

8.5.1.  Choke

This message has ID 0 and no payload. A peer sends this message to a remote peer to inform the remote peer that it is being choked.

8.5.2.  Unchoke

This message has ID 1 and no payload. A peer sends this message to a remote peer to inform the remote peer that it is no longer being choked.

8.5.3.  Interested

This message has ID 2 and no payload. A peer sends this message to a remote peer to inform the remote peer of its desire to request objects.

8.5.4.  Uninterested

This message has ID 3 and no payload. A peer sends this message to a remote peer to inform it that it is not interested in any objects from the remote peer.

8.5.5.  Peers

This message has ID 4 and a variable payload length. The payload is a list of peers each with the self-designated peer ID, the port number, and the Internet address of the peer. The address may be given as a dotted quad IPv4 format, hexadecimal IPv6 format or DNS name. A peer can send this message with no payload to request peer lists from the remote peer. See Section 3 (Discovering Peers) for guidelines for using Peers messages.

------------------------------------------------------------------
| Peer ID | Peer Port | Peer Address Length | Peer Address | ... |
------------------------------------------------------------------

8.5.6.  References

This message has ID 5 and a variable payload. To request references from the remote peer, a peer can send this message with no payload. To announce to the other peer that it has a reference object available it can send this message with a reference SHA1 and an empty reference object. A peer MUST NOT send its current reference objects unless they have been requested by the remote peer using this method. This reduces the impact of new reference objects flooding the network.

The reference object is similar to the "references" string returned in the tracker response. A peer receiving this message SHOULD validate the resulting object(s) using the public key from the metainfo file and drop the connection if the object has a false signature. See Section 4 (Repository References) for more instructions on how to interpret the reference object.

----------------------------------------------------------------
| Reference SHA1 | References Length | References Object | ... |
----------------------------------------------------------------

Peers MUST send only references objects which the other end has not already announced to them. Peers MUST only advertise references objects once during the lifetime of a PWP connection.

8.5.7.  Reels

This message has ID 6 and a variable payload length. The payload is a list of Reels that the sender can offer parts of, or is in the process of trying to get. Each commit-reel is listed with a pair of SHA1 objects uniquely identifying the reference objects that identify the start and end of it, and an 8-byte big-endian number telling the total (uncompressed) size of all of the objects in the reel. In all, 48 bytes per commit-reel. A peer can send this message with no payload to request the list of reels from the remote peer. If a reel spans to the beginning of history, then the SHA1 value to use for the "Start" is the SHA1 of the empty string ("da39a3..."). A peer MUST be able to return the corresponding references objects for all of the references' SHA1s returned by this message when asked with the "References" message.

A peer receiving this message SHOULD send a request for the blocks list to the sender to keep it informed of any new objects the remote peer has downloaded.

------------------------------------
| Reel SHA1 Pair | Reel size | ... |
------------------------------------

8.5.8.  Blocks

This message has ID 7 and a variable payload length. The payload is a SHA1 pair identifying the commit-reel of which block download status are being queried or notified. A message sent without a Bitmap is a query, and one sent with one is a notification (or a response to a query). The block size is a 32-bit integer.

A peer receiving this message SHOULD send a blocks message to the sender to keep it informed of the new status, if it has changed since the last corresponding response to the sender. The sender should only set bits in the bitmap when it knows that it has all the objects that start in this block. The bitmap is interpreted byte by byte, with the lowest bit in the first byte of the bitmap corresponding to the first block in the range reported on. Bits which refer to blocks beyond the end of the reel should be set to 0.

----------------------------------------
| Reel SHA1 Pair | Block size | Bitmap |
----------------------------------------

To allow for simplicity of implementation, the answer to this message does not have to be in terms of the requested block size.

8.6.  Data-oriented Messages

8.6.1.  Scan

This message has ID 8 and a variable payload. The payload always contains a two references SHA1s identifying the commit-reel, a block offset and length. Without the Index Data set, it is a request for an index of objects in that block. Otherwise, it is a response to a query, and the data takes the form described later.

-------------------------------------------------------------
| Reel SHA1 Pair | Block offset | Block Length | Index Data |
-------------------------------------------------------------

The index data is an offset into the block that the first object starts, followed by a list of index records. Each index record is an Object ID, a byte for the type and a 4-byte integer for the length of the object. If a block is requested that a complete list of objects is not available for, the Offset will be -1, and no list will follow. If no objects start within the block, the Offset will be 0, and no list will follow. [anchor8] (SV - I'm wondering whether it might be better to use BER integers than specify exactly how long each integer field is... not being able to send large objects might seem limiting, but at the moment we're not splitting objects within blocks (too complicated, and inefficient anyway), so let's not worry about it...)

-----------------------------------------------------
.. | Offset | Object ID | Type | Object Length | ...
-----------------------------------------------------

Note that it is only necessary to use this request when dealing with multiple peers which are downloading different reels. Also note that it is only guaranteed that peers have the necessary information to answer this request if they have all of the previous blocks in the reel to this one downloaded already, or happen to have the index around. [anchor9] (SV - Quite. This means that this request is effectively only useful against seeds of a reel. This could be relaxed to return information about the objects held in the fragment the other node has, I guess. There should also be some kind of error response defined perhaps.)

8.6.2.  Request

This message has ID 9 and a variable length payload. The payload is a count of objects, a list of object IDs that the sender is interested in downloading from the recipient, followed by a count and a list of Commit IDs that defines the start of a range of objects that may be used as delta bases for the transmitted pack.

The peer SHOULD send the Commit IDs for all of the complete head references that it posesses. The remote end MAY ignore this list and produce a "deep" pack, which does not refer to any other objects for deltas.

-----------------------------------------------
| Count | Object ID | ... | Count | Commit ID |
-----------------------------------------------

This message should be considered an auxiliary method for getting small amounts of missing objects when all else fails, or for situations where it is determined to be a light-weight alternative to the regular "Play" request mechanism.

8.6.3.  Play

This message has ID 10 and a variable length payload. The payload holds a pair of reference SHA1 objects to which this commit-reel corresponds, and the block offset and block length as per the Scan message. The "Offset" returned is the offset into the block's computed beginning that the first object starts. If the "Block Length" is zero, the pack is a response to the auxiliary "Request" method above, and the "Reel SHA1 Pair" arbitrarily set to values that may be used for the "Stop" message. If the "Offset" and "Pack" fields are not present, it is a request for the specified block. The generated pack may use as a delta base any object prior to it in the commit-reel, or any object reachable from the commit-reel's start references.

----------------------------------------------------------------
| Reel SHA1 Pair | Block offset | Block Length | Offset | Pack |
----------------------------------------------------------------

The response to a "Play" request MAY contain more objects than are defined to exist in that portion of the reel, but MUST contain all of the objects that do.

8.6.4.  Stop

This message has ID 11 and a payload of length 48. The payload is a pair of reference SHA1s indicating the commit reel (or token from the "Request" message, and offset and block length values identifying a block that the sender has requested, but is no longer interested in. The recipient MUST refrain from, or stop sending the block specified upon processing this message. The payload has the following structure:

------------------------------------------------
| Reel SHA1 Pair | Block offset | Block Length |
------------------------------------------------

9.  Security Consideration

This section examines security considerations for GTP/0.1. The discussion does not include definitive solutions to the problems revealed, though it does make some suggestions for reducing security risks.

9.1.  Tracker HTTP Protocol Issues

The use of the HTTP protocol for communication between the tracker and the client makes GTP/0.1 vulnerable to the attacks mentioned in the security consideration section of RFC 2616 (Fielding, R., Gettys, J., Mogul, J., Frystyk, H., Masinter, L., Leach, P., and T. Berners-Lee, “Hypertext Transfer Protocol -- HTTP/1.1,” June 1999.) [RFC2616].

9.2.  Denial of Service Attacks on Trackers

The nature of the tracker is to serve many clients. By mounting a denial of service attack against the tracker the swarm attached to the tracker can be starved. This type of attack is hard to defend against, however, the metainfo file allows for multiple trackers to be specified, making it possible to spread the load on a number of trackers, and thus containing such an attack.

9.3.  Peer Identity Issues

There is no strong authentication of clients when they contact the tracker. The main option for trackers is to check peer ID and the IP address of the client. The lack of authentication can be used to mount an attack where a client can shut down another client if the two clients are running on the same host and thus are sharing the same IP address. In addition, a rogue peer may masquerade its identity by using multiple peer IDs. Clients should there refrain from taking the peer ID at face value.

9.4.  DNS Spoofing

Clients using GTP/0.1 rely heavily on the Domain Name Service, which can be used for both specifying the URI of the tracker and how to contact a peer. Clients are thus generally prone to security attacks based on the deliberate mis-association of IP addresses and DNS names. Clients need to be cautious in assuming the continuing validity of an IP address/DNS name association.

In particular, GTP/0.1 clients SHOULD rely on their name resolver for confirmation of an IP number/DNS name association, rather than caching the result of previous host name lookups. If clients cache the results of host name lookups in order to achieve a performance improvement, they MUST observe the TTL information reported by DNS.

If clients do not observe this rule, they could be spoofed when a previously-accessed peers or trackers IP address changes. As network renumbering is expected to become increasingly common according to RFC 1900 (Carpenter, B. and Y. Rekhter, “Renumbering Needs Work,” February 1996.) [RFC1900], the possibility of this form of attack will grow. Observing this requirement reduces this potential security vulnerability.

9.5.  Issues with File and Directory Names

The reference object provides a way to suggest a name of the downloaded branches for torrents. If the GTP client stores references in individual files it SHOULD verify that the suggested reference names in the reference object do not compromise services on the local system when translated to a path in the repository structure.

Using UNIX as an example, some hazards would be:

• Creating startup files (e.g., ".login").
• Creating or overwriting system files (e.g., "/etc/passwd").
• Overwriting any existing file.

It is very important to note that this is not an exhaustive list; it is intended as a small set of examples only. Implementers must be alert to the potential hazards on their target systems. In general, the GTP client SHOULD NOT name or place files such that they will get interpreted or executed without the user explicitly initiating the action.

9.6.  Validating the Integrity of Data Exchanged Between Peers

By default, all content served to the client from other peers should be considered tainted and the client SHOULD validate the integrity of the data before accepting it. The metainfo file contains a public key for checking the integrity of reference objects. Using the branch and tag references the client is able to verify the revision lists they point to. Finally, individual objects can be checked using the SHA1 name of the object.

Trusting the validity of the resulting repository ends up being a matter of trusting the content of the metainfo file and reference objects distributed by the tracker and over the wire. Ensuring the validity of the metainfo file is beyond the scope of this document.

9.7.  Transfer of Sensitive Information

Some clients include information about themselves when generating the peer ID string. Clients should be aware that this information can potentially be used to determine whether a specific client has a exploitable security hole.

10.  IANA Considerations

This document makes no request of IANA.

11. References

Authors' Addresses