| 26 | | <h1>Fast Extension</h1> |
| 27 | | <p>The Fast Extension packages several extensions: <i>Have None/Have All</i>, |
| 28 | | <i>Reject Requests</i>, <i>Suggestions</i> and <i>Allowed Fast.</i> |
| 29 | | These are enabled by setting the third least significant bit of the |
| 30 | | last reserved byte in the BitTorrent handshake: |
| 31 | | </p> |
| 32 | | <pre> reserved[7] |= 0x04 |
| 33 | | </pre> |
| 34 | | <p>The extension is enabled only if both ends of the connection set this bit. |
| 35 | | </p><p>The following proposed messages adhere to the syntax of messages found |
| 36 | | in v1.0 of the BitTorrent protocol. All integers are four bytes |
| 37 | | big-endian. All messages start with an integer message length. All messages |
| 38 | | but the Keep-Alive follow the message length with a single byte opcode |
| 39 | | and zero or more opcode-dependant arguments. |
| 40 | | </p><p>The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL |
| 41 | | NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and |
| 42 | | "OPTIONAL" in this document are to be interpreted as described in |
| 43 | | IETF <a href='http://www.ietf.org/rfc/rfc2119.txt' class='external' title="http://www.ietf.org/rfc/rfc2119.txt">RFC 2119</a>. |
| 44 | | </p> |
| 45 | | <table id='toc' class='toc'><tr><td><div id='toctitle'><h2>Contents</h2></div> |
| 46 | | <ul> |
| 47 | | <li class='toclevel-1'><a href="#Modifications_to_Semantics_of_Existing_Messages"><span class="tocnumber">1</span> <span class="toctext">Modifications to Semantics of Existing Messages</span></a></li> |
| 48 | | <li class='toclevel-1'><a href="#Have_All.2FHave_None"><span class="tocnumber">2</span> <span class="toctext">Have All/Have None</span></a></li> |
| 49 | | <li class='toclevel-1'><a href="#Suggest_Piece"><span class="tocnumber">3</span> <span class="toctext">Suggest Piece</span></a></li> |
| 50 | | <li class='toclevel-1'><a href="#Reject_Request"><span class="tocnumber">4</span> <span class="toctext">Reject Request</span></a></li> |
| 51 | | <li class='toclevel-1'><a href="#Allowed_Fast_Set_Generation"><span class="tocnumber">5</span> <span class="toctext">Allowed Fast Set Generation</span></a></li> |
| 52 | | </ul> |
| 53 | | </td></tr></table> |
| 54 | | <p><script type="text/javascript"> if (window.showTocToggle) { var tocShowText = "show"; var tocHideText = "hide"; showTocToggle(); } </script> |
| 55 | | </p> |
| 56 | | <h2 id="Modifications_to_Semantics_of_Existing_Messages"> Modifications to Semantics of Existing Messages </h2> |
| 57 | | <p>The Fast Extension modifies the semantics of the |
| 58 | | <i>Request</i>, <i>Choke</i>, <i>Unchoke</i>, and <i>Cancel</i> |
| 59 | | messages, and adds a <i>Reject Request.</i> Now, every request |
| 60 | | is guaranteed to result in EXACTLY ONE response |
| 61 | | which is either the corresponding reject or corresponding piece |
| 62 | | message. Even when a request is cancelled, the peer receiving |
| 63 | | the cancel should respond with either the corresponding reject or |
| 64 | | the corresponding piece: requests that are being processed are |
| 65 | | allowed to complete. |
| 66 | | </p><p>Choke no longer implicitly rejects all pending requests, |
| 67 | | thus eliminating some race conditions which could cause pieces |
| 68 | | to be needlessly requested multiple times. |
| 69 | | </p><p>Additionally, if a peer receives a piece that was never requested, |
| 70 | | the peer MUST close the connection. |
| 71 | | </p> |
| 72 | | <h2 id="Have_All.2FHave_None"> Have All/Have None </h2> |
| 73 | | <pre> <i>Have All</i>: <len=0x0001><op=0x0E> |
| 74 | | </pre> |
| 75 | | <pre> <i>Have None</i>: <len=0x0001><op=0x0F> |
| 76 | | </pre> |
| 77 | | <p><i>Have All</i> and <i>Have None</i> specify that the message sender |
| 78 | | has all or none of the pieces respectively. When present, <i>Have All</i> |
| 79 | | or <i>Have None</i> replace the <i>Have Bitfield.</i> Exactly one of <i>Have All</i>, |
| 80 | | <i>Have None</i>, or <i>Have Bitfield</i> MUST appear and only immediately after |
| 81 | | the handshake. The reason for these messages is to save bandwidth. Also |
| 82 | | slightly to remove the idiosyncrasy of sending no message when a peer |
| 83 | | has no pieces. |
| 84 | | </p><p>When the fast extension is disabled, if a peer receives <i>Have All</i> or |
| 85 | | <i>Have None</i> then the peer MUST close the connection. |
| 86 | | </p> |
| 87 | | <h2 id="Suggest_Piece"> Suggest Piece </h2> |
| 88 | | <pre> <i>Suggest Piece</i>: <len=0x0005><op=0x0D><index> |
| 89 | | </pre> |
| 90 | | <p><i>Suggest Piece</i> is an advisory message meaning "you might like to |
| 91 | | download this piece." The intended usage is for 'super-seeding' |
| 92 | | without throughput reduction, to avoid redundant downloads, and so that |
| 93 | | a seed which is disk I/O bound can upload continguous or identical |
| 94 | | pieces to avoid excessive disk seeks. In all cases, the seed SHOULD |
| 95 | | operate to maintain a roughly equal number of copies of each piece in |
| 96 | | the network. A peer MAY send more than one <i>suggest piece</i> message at |
| 97 | | any given time. A peer receiving multiple <i>suggest piece</i> messages |
| 98 | | MAY interpret this as meaning that all of the suggested pieces |
| 99 | | are equally appropriate. |
| 100 | | </p><p>When the fast extension is disabled, if a peer receives a |
| 101 | | <i>Suggest Piece</i> message, the peer MUST close the connection. |
| 102 | | </p> |
| 103 | | |
| 104 | | <h2 id="Reject_Request"> Reject Request </h2> |
| 105 | | <pre> <i>Reject Request</i>: <len=0x000D><op=0x10><index><begin><offset> |
| 106 | | </pre> |
| 107 | | <p><i>Reject Request</i> notifies a requesting peer that its request will not be satisfied. |
| 108 | | </p><p>If the fast extension is disabled and a peer receives a reject |
| 109 | | request then the peer MUST close the connection. |
| 110 | | </p><p>When the fast extension is enabled: |
| 111 | | </p> |
| 112 | | <ul><li> If a peer receives a reject for a request that was never sent then the peer SHOULD close the connection. |
| 113 | | </li><li> If a peer sends a choke, it MUST reject all requests from the peer to whom the choke was sent except it SHOULD NOT reject requests for pieces that are in the <i>allowed fast set.</i> A peer SHOULD choke first and then reject requests so that the peer receiving the choke does not re-request the pieces. |
| 114 | | </li><li> If a peer receives a request from a peer its choking, the peer receiving the request SHOULD send a reject unless the piece is in the <i>allowed fast set.</i> |
| 115 | | </li> |
| 116 | | <li>If a peer receives an excessive number of requests from a peer it is choking, the peer receiving the requests MAY close the connection rather than reject the request. However, consider that it can take several seconds for buffers to drain and messages to propagate once a peer is choked.</li></ul> |
| 117 | | |
| 118 | | <h2 id="Allowed_Fast">Allowed Fast</h2> |
| 119 | | <pre><i> Allowed Fast: <len=0x0005><op=0x11><index></i></pre> |
| 120 | | <p>With the BitTorrent protocol specified in <a href="protocol.html">[1]</a>, new peers take several minutes to ramp up before they can effectively engage in BitTorrent's tit-for-tat. The reason is simple: starting peers have few pieces to trade.</p> |
| 121 | | <p><i>Allowed Fast</i> is an advisory message which means "if you ask for this piece, I'll give it to you even if you're choked." <i>Allowed Fast</i> thus shortens the awkward stage during which the peer obtains occasional optimistic unchokes but cannot sufficiently reciprocate to remain unchoked.</p> |
| 122 | | <p>The pieces that can be downloaded when choked constitute a peer's <i>allowed fast set.</i> The set is generated using a canonical algorithm that produces piece indices unique to the message receiver so that if two peers offer <i>k</i> pieces fast it will be the same <i>k</i>, and if one offers <i>k+1</i> it will be the same <i>k</i> plus one more. <i>k</i> should be small enough to avoid abuse, but large enough to ramp up tit-for-tat. We currently set <i>k</i> to 10, but peers are free to change this number, e.g., to suit load.</p> |
| 123 | | <p>The message sender MAY list pieces that the message sender does not have. The receiver MUST NOT interpret an Allowed Fast message as meaning that the message sender has the piece. This allows peers to generate and communicate allowed fast sets at the beginning of a connection. However, a peer MAY send Allowed Fast messages at any time.</p> |
| 124 | | <p>A peer SHOULD send Allowed Fast messages to any starting peer unless the local peer lacks sufficient resources. A peer MAY reject requests for already Allowed Fast pieces if the local peer lacks sufficient resources, if the requested piece has already been sent to the requesting peer, or if the requesting peer is not a starting peer. Our current implementation rejects requests for Allowed Fast messages whenever the requesting peer has more than <i> k </i> pieces.</p> |
| 125 | | <p> When the fast extension is disabled, if a peer recieves an Allowed Fast message then the peer MUST close the connection.</p> |
| 126 | | |
| 127 | | <h2 id="Allowed_Fast_Set_Generation"> Allowed Fast Set Generation </h2> |
| 128 | | <p>The canonical algorithm for computing a peer <i>P'</i>s <i>allowed fast set</i> |
| 129 | | follows. All integers in this pseudocode are four bytes represented in network (big-endian) byte order. <i>[a:b]</i> denotes the sequence of consecutive integers from <i>a</i> to <i>b</i> excluding <i>b</i>, i.e., <i>(a, a+1, a+2,..., b-1)</i>. <i>x[a:b]</i> denotes a subsequence of elements in an array <i>x</i> starting from index <i>a</i> to but not including index <i>b</i>. |
| 130 | | </p><p>Let <i>ip</i> denote <i>P'</i>s IPv4 address. We currently have no |
| 131 | | provisions for IPv6. If a peer is behind a Network Address Translator |
| 132 | | (NAT) then <i>ip</i> should be the externally facing IP address of the |
| 133 | | NAT. Since the node sending the <i>Allowed Fast</i> messages computes |
| 134 | | the set, the correct <i>ip</i> is usually the <i>ip</i> address on the other |
| 135 | | end of the connection. The host computing the set MAY use the <i>ip</i> |
| 136 | | address on the other end of the connection regardless |
| 137 | | </p><p>Let <i>sz</i> denote the number of pieces in the torrent. |
| 138 | | </p><p>Let <i>a</i> denote the allowed fast set. |
| 139 | | </p><p>Let <i>k</i> denote the final number of pieces in the allowed fast set. |
| 140 | | </p> |
| 141 | | <pre> x = 0xFFFFFF00 & ip (1) |
| 142 | | x.append(infohash) (2) |
| 143 | | while |a| < k: |
| 144 | | x = SHA1(x) (3) |
| 145 | | for i in [0:5] and |a| < k: (4) |
| 146 | | j = i*4 (5) |
| 147 | | y = x[j:j+4] (6) |
| 148 | | index = y % sz (7) |
| 149 | | if index not in a: (8) |
| 150 | | add index to a (9) |
| 151 | | </pre> |
| 152 | | <p>Step (1) selects the most significant octets in peer <i>P'</i>s |
| 153 | | ip address. We do this to prevent a user that obtains more than one |
| 154 | | IP address on the same network from obtaining more than one |
| 155 | | <i>allowed fast set.</i> Use of three bytes is heuristic and |
| 156 | | historical. |
| 157 | | </p><p>Step (3) generates a 20-byte random number on each call. By |
| 158 | | performing a SHA-1 hash on the previous iteration's hash, we can |
| 159 | | generate an arbitrarily long pseudorandom sequence. |
| 160 | | </p><p>Steps (4) through (9) partition the 20-byte hash into piece indices |
| 161 | | and add them to the allowed fast set. |
| 162 | | </p> |
| 163 | | </div><a name="Example_Implementation"></a><h2> Example Implementation </h2> |
| 164 | | <p>The following C++ implementation was provided by CacheLogic: |
| 165 | | </p> |
| 166 | | <pre>void generate_fast_set( |
| 167 | | uint32 k, // number of pieces in set |
| 168 | | uint32 sz, // number of pieces in torrent |
| 169 | | const char infohash[20], // infohash of torrent |
| 170 | | uint32 ip, // in host byte order, ie localhost is 0x7f000001 |
| 171 | | std::vector<uint32> &a) // generated set of piece indices |
| 172 | | { |
| 173 | | a.clear(); |
| 174 | | std::string x; |
| 175 | | char buf[4]; |
| 176 | | *(uint32*)buf = htonl(ip & 0xffffff00); |
| 177 | | x.assign(buf, 4); |
| 178 | | x.append(infohash, 20); // (3) |
| 179 | | while (a.size()<k) { |
| 180 | | x = SHA1(x); // (4) |
| 181 | | for ( int i=0 ; i<5 && a.size()<k ; i++ ) { // (5) |
| 182 | | int j = i*4; // (6) |
| 183 | | uint32 y = ntohl(*(uint32*)(x.data()+j)); // (7) |
| 184 | | uint32 index = y % sz; // (8) |
| 185 | | if (std::find(a.begin(), a.end(), index)==a.end()) { // (9) |
| 186 | | a.push_back(index); // (10) |
| 187 | | } |
| 188 | | } |
| 189 | | } |
| 190 | | } |
| 191 | | </pre> |
| 192 | | <p>Example results generated by this function: |
| 193 | | </p> |
| 194 | | <pre>7 piece allowed fast set for torrent with 1313 pieces and hex infohash |
| 195 | | aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200: |
| 196 | | 1059,431,808,1217,287,376,1188 |
| 197 | | 9 piece allowed fast set for torrent with 1313 pieces and hex infohash |
| 198 | | aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for node with IP 80.4.4.200: |
| 199 | | 1059,431,808,1217,287,376,1188,353,508 |
| 200 | | </pre> |
| | 27 | <h2>DHT Protocol</h2> |
| | 28 | <p>BitTorrent uses a "distributed sloppy hash table" (DHT) for storing peer contact information for "trackerless" torrents. In effect, each peer becomes a tracker. The protocol is based on Kademila and is implemented over UDP.</p> |
| | 29 | <p>Please note the terminology used in this document to avoid confusion. A "peer" is a client/server listening on a TCP port that implements the BitTorrent protocol. A "node" is a client/server listening on a UDP port implementing the distributed hash table protocol. The DHT is composed of nodes and stores the location of peers. BitTorrent clients include a DHT node, which is used to contact other nodes in the DHT to get the location of peers to download from using the BitTorrent protocol.</p> |
| | 30 | <h3>Contents</h3> |
| | 31 | <ul> |
| | 32 | <li><a href="#Overview">1 Overview</a></li> |
| | 33 | <li><a href="#Routing_Table">2 Routing Table</a></li> |
| | 34 | <li><a href="#BitTorrent_Protocol_Extension">3 BitTorrent Protocol Extension</a></li> |
| | 35 | <li><a href="#Torrent_File_Extensions">4 Torrent File Extensions</a></li> |
| | 36 | <li><a href="#KRPC_Protocol">5 KRPC Protocol</a> |
| | 37 | <ul> |
| | 38 | <li><a href="#Contact_Encoding">5.1 Contact Encoding</a></li> |
| | 39 | <li><a href="#Queries">5.2 Queries</a></li> |
| | 40 | <li><a href="#Responses">5.3 Responses</a></li> |
| | 41 | <li><a href="#Errors">5.4 Errors</a> |
| | 42 | <ul> |
| | 43 | <li><a href="#Example_Error_Packets">5.4.1 Example Error Packets</a></li> |
| | 44 | </ul> |
| | 45 | </li> |
| | 46 | </ul> |
| | 47 | </li> |
| | 48 | <li><a href="#DHT_Queries">6 DHT Queries</a> |
| | 49 | <ul> |
| | 50 | <li><a href="#ping">6.1 ping</a> |
| | 51 | <ul> |
| | 52 | <li><a href="#example_packets">6.1.1 Example Packets</a></li> |
| | 53 | </ul> |
| | 54 | </li> |
| | 55 | <li><a href="#find_node">6.2 find_node</a> |
| | 56 | <ul> |
| | 57 | <li><a href="#example_packets_2">6.2.1 Example Packets</a></li> |
| | 58 | </ul> |
| | 59 | </li> |
| | 60 | <li><a href="#get_peers">6.3 get_peers</a> |
| | 61 | <ul> |
| | 62 | <li><a href="#example_packets_3">6.3.1 Example Packets</a></li> |
| | 63 | </ul> |
| | 64 | </li> |
| | 65 | <li><a href="#announce_peer">6.4 announce_peer</a> |
| | 66 | <ul> |
| | 67 | <li><a href="#example_packets_4">6.4.1 Example Packets</a></li> |
| | 68 | </ul> |
| | 69 | </li> |
| | 70 | </ul> |
| | 71 | </li> |
| | 72 | <li><a href="#Footnotes">7 Footnotes</a></li> |
| | 73 | </ul> |
| | 74 | <a name="Overview"></a> |
| | 75 | <h3>Overview</h3> |
| | 76 | <p>Each node has a globally unique identifier known as the "node ID." |
| | 77 | Node IDs are chosen at random from the same 160-bit space as BitTorrent |
| | 78 | infohashes. A "distance metric" is used to compare two node IDs or a node |
| | 79 | ID and an infohash for "closeness." Nodes must maintain a routing table |
| | 80 | containing the contact information for a small number of other nodes. |
| | 81 | The routing table becomes more detailed as IDs get closer to the node's |
| | 82 | own ID. Nodes know about many other nodes in the DHT that have IDs that |
| | 83 | are "close" to their own but have only a handful of contacts with IDs |
| | 84 | that are very far away from their own.</p> |
| | 85 | <p>In Kademlia, the distance metric is XOR and the result is |
| | 86 | interpreted as an unsigned integer. distance(A,B) = |A ⊗ B| Smaller |
| | 87 | values are closer.</p> |
| | 88 | <p>When a node wants to find peers for a torrent, it uses the |
| | 89 | distance metric to compare the infohash of the torrent with the IDs of |
| | 90 | the nodes in its own routing table. It then contacts the nodes it knows |
| | 91 | about with IDs closest to the infohash and asks them for the contact |
| | 92 | information of peers currently downloading the torrent. If a contacted |
| | 93 | node knows about peers for the torrent, the peer contact information is |
| | 94 | returned with the response. Otherwise, the contacted node must respond |
| | 95 | with the contact information of the nodes in its routing table that are |
| | 96 | closest to the infohash of the torrent. The original node iteratively |
| | 97 | queries nodes that are closer to the target infohash until it cannot |
| | 98 | find any closer nodes. After the search is exhausted, the client then |
| | 99 | inserts the peer contact information for itself onto the responding |
| | 100 | nodes with IDs closest to the infohash of the torrent.</p> |
| | 101 | <p>The return value for a query for peers includes an opaque value |
| | 102 | known as the "token." For a node to announce that its controlling peer |
| | 103 | is downloading a torrent, it must present the token received from the |
| | 104 | same queried node in a recent query for peers. When a node attempts to |
| | 105 | "announce" a torrent, the queried node checks the token against the |
| | 106 | querying node's IP address. This is to prevent malicious hosts from |
| | 107 | signing up other hosts for torrents. Since the token is merely returned |
| | 108 | by the querying node to the same node it received the token from, the |
| | 109 | implementation is not defined. Tokens must be accepted for a reasonable |
| | 110 | amount of time after they have been distributed. The BitTorrent |
| | 111 | implementation uses the SHA1 hash of the IP address concatenated onto a |
| | 112 | secret that changes every five minutes and tokens up to ten minutes old |
| | 113 | are accepted.</p> |
| | 114 | <a name="Routing_Table"></a> |
| | 115 | <h3>Routing Table</h3> |
| | 116 | <p>Every node maintains a routing table of known good nodes. The nodes |
| | 117 | in the routing table are used as starting points for queries in the |
| | 118 | DHT. Nodes from the routing table are returned in response to queries |
| | 119 | from other nodes.</p> |
| | 120 | <p>Not all nodes that we learn about are equal. Some are "good" |
| | 121 | and some are not. Many nodes using the DHT are able to send queries and |
| | 122 | receive responses, but are not able to respond to queries from other |
| | 123 | nodes. It is important that each node's routing table must contain only |
| | 124 | known good nodes. A good node is a node has responded to one of our |
| | 125 | queries within the last 15 minutes. A node is also good if it has ever |
| | 126 | responded to one of our queries and has sent us a query within the last |
| | 127 | 15 minutes. After 15 minutes of inactivity, a node becomes |
| | 128 | questionable. Nodes become bad when they fail to respond to multiple |
| | 129 | queries in a row. Nodes that we know are good are given priority over |
| | 130 | nodes with unknown status.</p> |
| | 131 | <p>The routing table covers the entire node ID space from 0 to 2<sup>160</sup>. |
| | 132 | The routing table is subdivided into "buckets" that each cover a |
| | 133 | portion of the space. An empty table has one bucket with an ID space |
| | 134 | range of min=0, max=2<sup>160</sup>. When a node with ID "N" is |
| | 135 | inserted into the table, it is placed within the bucket that has min |
| | 136 | <= N < max. An empty table has only one bucket so any node must |
| | 137 | fit within it. Each bucket can only hold K nodes, currently eight, |
| | 138 | before becoming "full." When a bucket is full of known good nodes, no |
| | 139 | more nodes may be added unless our own node ID falls within the range |
| | 140 | of the bucket. In that case, the bucket is replaced by two new buckets |
| | 141 | each with half the range of the old bucket and the nodes from the old |
| | 142 | bucket are distributed among the two new ones. For a new table with |
| | 143 | only one bucket, the full bucket is always split into two new buckets |
| | 144 | covering the ranges 0..2<sup>159</sup> and 2<sup>159</sup>..2<sup>160</sup>.</p> |
| | 145 | <p>When the bucket is full of good nodes, the new node is simply |
| | 146 | discarded. If any nodes in the bucket are known to have become bad, |
| | 147 | then one is replaced by the new node. If there are any questionable |
| | 148 | nodes in the bucket have not been seen in the last 15 minutes, the |
| | 149 | least recently seen node is pinged. If the pinged node responds then |
| | 150 | the next least recently seen questionable node is pinged until one |
| | 151 | fails to respond or all of the nodes in the bucket are known to be |
| | 152 | good. If a node in the bucket fails to respond to a ping, it is |
| | 153 | suggested to try once more before discarding the node and replacing it |
| | 154 | with a new good node. In this way, the table fills with stable long |
| | 155 | running nodes.</p> |
| | 156 | <p>Each bucket should maintain a "last changed" property to |
| | 157 | indicate how "fresh" the contents are. When a node in a bucket is |
| | 158 | pinged and it responds, or a node is added to a bucket, or a node in a |
| | 159 | bucket is replaced with another node, the bucket's last changed |
| | 160 | property should be updated. Buckets that have not been changed in 15 |
| | 161 | minutes should be "refreshed." This is done by picking a random ID in |
| | 162 | the range of the bucket and performing a find_nodes search on it. Nodes |
| | 163 | that are able to receive queries from other nodes usually do not need |
| | 164 | to refresh buckets often. Nodes that are not able to receive queries |
| | 165 | from other nodes usually will need to refresh all buckets periodically |
| | 166 | to ensure there are good nodes in their table when the DHT is needed. |
| | 167 | </p><p>Upon inserting the first node into it's routing table and when |
| | 168 | starting up thereafter, the node should attempt to find the closest |
| | 169 | nodes in the DHT to itself. It does this by issuing find_node messages |
| | 170 | to closer and closer nodes until it cannot find any closer. The routing |
| | 171 | table should be saved between invocations of the client software.</p> |
| | 172 | <a name="BitTorrent_Protocol_Extension"></a> |
| | 173 | <h3>BitTorrent Protocol Extension</h3> |
| | 174 | <p>The BitTorrent protocol has been extended to exchange node UDP port |
| | 175 | numbers between peers that are introduced by a tracker. In this way, |
| | 176 | clients can get their routing tables seeded automatically through the |
| | 177 | download of regular torrents. Newly installed clients who attempt to |
| | 178 | download a trackerless torrent on the first try will not have any nodes |
| | 179 | in their routing table and will need the contacts included in the |
| | 180 | torrent file.</p> |
| | 181 | <p>Peers supporting the DHT set the last bit of the 8-byte |
| | 182 | reserved flags exchanged in the BitTorrent protocol handshake. Peer |
| | 183 | receiving a handshake indicating the remote peer supports the DHT |
| | 184 | should send a PORT message. It begins with byte 0x09 and has a two byte |
| | 185 | payload containing the UDP port of the DHT node in network byte order. |
| | 186 | Peers that receive this message should attempt to ping the node on the |
| | 187 | received port and IP address of the remote peer. If a response to the |
| | 188 | ping is recieved, the node should attempt to insert the new contact |
| | 189 | information into their routing table according to the usual rules.</p> |
| | 190 | <a name="Torrent_File_Extensions"></a> |
| | 191 | <h3>Torrent File Extensions</h3> |
| | 192 | <p>A trackerless torrent dictionary does not have an "announce" key. |
| | 193 | Instead, a trackerless torrent has a "nodes" key. This key should be |
| | 194 | set to the K closest nodes in the torrent generating client's routing |
| | 195 | table. Alternatively, the key could be set to a known good node such as |
| | 196 | one operated by the person generating the torrent. Please do not |
| | 197 | automatically add "router.bittorrent.com" to torrent files or |
| | 198 | automatically add this node to clients routing tables.</p> |
| | 199 | <p><code>nodes = [["<host>", <port>], ["<host>", <port>], ...] |
| | 200 | nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]]</code></p> |
| | 201 | <a name="KRPC_Protocol"></a> |
| | 202 | <h3>KRPC Protocol</h3> |
| | 203 | <p>The KRPC protocol is a simple RPC mechanism consisting of bencoded |
| | 204 | dictionaries sent over UDP. A single query packet is sent out and a |
| | 205 | single packet is sent in response. There is no retry. There are three |
| | 206 | message types: query, response, and error. For the DHT protocol, there |
| | 207 | are four queries: ping, find_node, get_peers, and announce_peer.</p> |
| | 208 | <p>A KRPC message is a single dictionary with two keys common to |
| | 209 | every message and additional keys depending on the type of message. |
| | 210 | Every message has a key "t" with a single character string value |
| | 211 | representing a transaction ID. This transaction ID is generated by the |
| | 212 | querying node and is echoed in the response, so responses may be |
| | 213 | correlated with multiple queries to the same node. The other key |
| | 214 | contained in every KRPC message is "y" with a single character value |
| | 215 | describing the type of message. The value of the "y" key is one of "q" |
| | 216 | for query, "r" for response, or "e" for error.</p> |
| | 217 | <a name="Contact_Encoding"></a> |
| | 218 | <h4>Contact Encoding</h4> |
| | 219 | <p>Contact information for peers is encoded as a 6-byte string. Also |
| | 220 | known as "Compact IP-address/port info" the 4-byte IP address is in |
| | 221 | network byte order with the 2 byte port in network byte order |
| | 222 | concatenated onto the end.</p> |
| | 223 | <p>Contact information for nodes is encoded as a 26-byte string. |
| | 224 | Also known as "Compact node info" the 20-byte Node ID in network byte |
| | 225 | order has the compact IP-address/port info concatenated to the end.</p> |
| | 226 | <a name="Queries"></a> |
| | 227 | <h4>Queries</h4> |
| | 228 | <p>Queries, or KRPC message dictionaries with a "y" value of "q", |
| | 229 | contain two additional keys; "q" and "a". Key "q" has a string value |
| | 230 | containing the method name of the query. Key "a" has a dictionary value |
| | 231 | containing named arguments to the query.</p> |
| | 232 | <a name="Responses"></a> |
| | 233 | <h4>Responses</h4> |
| | 234 | <p>Responses, or KRPC message dictionaries with a "y" value of "r", |
| | 235 | contain one additional key "r". The value of "r" is a dictionary |
| | 236 | containing named return values. Response messages are sent upon |
| | 237 | successful completion of a query.</p> |
| | 238 | <a name="Errors"></a> |
| | 239 | <h4>Errors</h4> |
| | 240 | <p>Errors, or KRPC message dictionaries with a "y" value of "e", |
| | 241 | contain one additional key "e". The value of "e" is a list. The first |
| | 242 | element is an integer representing the error code. The second element |
| | 243 | is a string containing the error message. Errors are sent when a query |
| | 244 | cannot be fulfilled. The following table describes the possible error |
| | 245 | codes:</p> |
| | 246 | <table> |
| | 247 | <tr> |
| | 248 | <td class="shade">201</td><td class="shade">Generic Error</td> |
| | 249 | </tr> |
| | 250 | <tr> |
| | 251 | <td>202</td><td>Server Error</td> |
| | 252 | </tr> |
| | 253 | <tr> |
| | 254 | <td class="shade">203</td><td class="shade">Protocol Error, such as a malformed packet,<br />invalid arguments, or bad token</td> |
| | 255 | </tr> |
| | 256 | <tr> |
| | 257 | <td>204</td><td>Method Unknown</td> |
| | 258 | </tr> |
| | 259 | </table> |
| | 260 | <a name="Example_Error_Packets"></a> |
| | 261 | <h5>Example Error Packets</h5> |
| | 262 | <p><code>generic error = {'t':0, 'y':'e', 'e':[201, "A Generic Error Ocurred"]} |
| | 263 | bencoded = d1:eli201e23:A Generic Error Ocurrede1:ti0e1:y1:ee</code></p> |
| | 264 | <a name="DHT_Queries"></a> |
| | 265 | <h3>DHT Queries</h3> |
| | 266 | <p>All queries have an "id" key and value containing the node ID of the |
| | 267 | querying node. All responses have an "id" key and value containing the |
| | 268 | node ID of the responding node.</p> |
| | 269 | <a name="ping"></a> |
| | 270 | <h4>ping</h4> |
| | 271 | <p>The most basic query is a ping. "q" = "ping" A ping query has a |
| | 272 | single argument, "id" the value is a 20-byte string containing the |
| | 273 | senders node ID in network byte order. The appropriate response to a |
| | 274 | ping has a single key "id" containing the node ID of the responding |
| | 275 | node.</p> |
| | 276 | <p><code> arguments: {"id" : "<querying nodes id>"} |
| | 277 | response: {"id" : "<queried nodes id>"}</code></p> |
| | 278 | <a name="example_packets"></a> |
| | 279 | <h5>Example Packets</h5> |
| | 280 | <p><code>ping Query = {"t":"0", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}} |
| | 281 | bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t1:01:y1:qe</code></p> |
| | 282 | <p><code> Response = {"t":"0", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}} |
| | 283 | bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t1:01:y1:re</code></p> |
| | 284 | <a name="find_node"></a> |
| | 285 | <h4>find_node</h4> |
| | 286 | <p>Find node is used to find the contact information for a node given |
| | 287 | its ID. "q" == "find_node" A find_node query has two arguments, "id" |
| | 288 | containing the node ID of the querying node, and "target" containing |
| | 289 | the ID of the node sought by the queryer. When a node receives a |
| | 290 | find_node query, it should respond with a key "nodes" and value of a |
| | 291 | string containing the compact node info for the target node or the K |
| | 292 | (8) closest good nodes in its own routing table.</p> |
| | 293 | <p><code>arguments: {"id" : "<querying nodes id>", "target" : "<id of target node>"} |
| | 294 | response: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"}</code></p> |
| | 295 | <a name="example_packets_2"></a> |
| | 296 | <h5>Example Packets</h5> |
| | 297 | <p><code>find_node Query = {'t':0, 'y':'q', 'q':'find_node', 'a': {'id':'abcdefghij0123456789', 'target':'mnopqrstuvwxyz123456'}} |
| | 298 | bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:ti0e1:y1:qe</code></p> |
| | 299 | <p><code>Response = {'t':0, 'y':'r', 'r': {'id':'0123456789abcdefghij', 'nodes': 'def456...'}} |
| | 300 | bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:ti0e1:y1:re</code></p> |
| | 301 | <a name="get_peers"></a> |
| | 302 | <h4>get_peers</h4> |
| | 303 | <p>Get peers associated with a torrent infohash. "q" = "get_peers" A |
| | 304 | get_peers query has two arguments, "id" containing the node ID of the |
| | 305 | querying node, and "info_hash" containing the infohash of the torrent. |
| | 306 | If the queried node has peers for the infohash, they are returned in a |
| | 307 | key "values" as a list with a single string containing "compact" format |
| | 308 | peer information concatenated together. If the queried node has no |
| | 309 | peers for the infohash, a key "nodes" is returned containing the K |
| | 310 | nodes in the queried nodes routing table closest to the infohash |
| | 311 | supplied in the query. In either case a "token" key is also included in |
| | 312 | the return value. The token value is a required argument for a future |
| | 313 | announce_peer query.</p> |
| | 314 | <p><code>arguments: {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>"} |
| | 315 | response: {"id" : "<queried nodes id>", "values" : ["<compact peer info string>"]} |
| | 316 | or: {"id" : "<queried nodes id>", "nodes" : "<compact node info>"}</code></p> |
| | 317 | <a name="example_packets_3"></a> |
| | 318 | <h5>Example Packets</h5> |
| | 319 | <p><code>get_peers Query = {'t':0, 'y':'q', 'q':'get_peers', 'a': {'id':'abcdefghij0123456789', 'info_hash':'mnopqrstuvwxyz123456'}} |
| | 320 | bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:ti0e1:y1:qe</code></p> |
| | 321 | <p><code>Response with peers = {'t':0, 'y':'r', 'r': {'id':'abcdefghij0123456789', 'token':'aoeusnth', 'values': ['axje.uidhtnmbrl']}} |
| | 322 | bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl15:axje.uidhtnmbrlee1:ti0e1:y1:re</code></p> |
| | 323 | <p><code>Response with closest nodes = {'t':0, 'y':'r', 'r': {'id':'abcdefghij0123456789', 'token':'aoeusnth', 'nodes': 'def456...'}} |
| | 324 | bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:ti0e1:y1:re</code></p> |
| | 325 | <a name="announce_peer"></a> |
| | 326 | <h4>announce_peer</h4> |
| | 327 | <p>Announce that the peer controlling the querying node is downloading |
| | 328 | the a torrent on a port. announce_peer has four arguments: "id" containing the node ID of the |
| | 329 | querying node, "info_hash" containing the infohash of the torrent, |
| | 330 | "port" containing the port as an integer, and the "token" received in |
| | 331 | response to a previous get_peers query. The queried node must verify |
| | 332 | that the token was previously sent to the same IP address as the |
| | 333 | querying node. Then the queried node should store the IP address of the |
| | 334 | querying node and the supplied port number under the infohash in its |
| | 335 | store of peer contact information.</p> |
| | 336 | <p><code>arguments: {"id" : "<querying nodes id>", "info_hash" : "<20-byte infohash of target torrent>", "port" : <port number>, "token" : "<opaque token>"} |
| | 337 | response: {"id" : "<queried nodes id>"}</code></p> |
| | 338 | <a name="example_packets_4"></a> |
| | 339 | <h5>Example Packets</h5> |
| | 340 | <p><code>announce_peers Query = {'t':0, 'y':'q', 'q':'announce_peers', 'a': {'id':'abcdefghij0123456789', 'info_hash':'mnopqrstuvwxyz123456', 'port' : 6881, 'token' : 'aoeusnth'}} |
| | 341 | bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:<br /> |
| | 342 | mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q14:announce_peers1:ti0e1:y1:qe</code></p> |
| | 343 | <p><code>Response = {"t":"0", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}} |
| | 344 | bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t1:01:y1:re</code></p> |
| | 345 | <a name="Footnotes"></a> |
| | 346 | <h3>Footnotes</h3> |
| | 347 | <ol> |
| | 348 | <li><a href="http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf" class="external text" title="http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf" rel="nofollow">"Kademlia: A Peer-to-peer Information System Based on the XOR Metric"</a>,<br />Petar Maymounkov and David Mazieres, |
| | 349 | </li> |
| | 350 | <li>Use SHA1 and plenty of entropy to ensure a unique ID</li> |
| | 351 | </ol> |
