Posts Tagged ‘distributed hash table’

Torrent

implementing bittorrent – DHT (teil 3)

by nks · oktober 2 2009 · one comment

Eigentlich wollte ich ja was über den BitTorrent Message-Flow schreiben, aber aus aktuellem Anlass gibt es heute einen “kleinen” Artikel über DHT.

DHT

Aus gegebenem Anlass schreibe ich nun etwas früher als geplant über DHT. Die ThePirateBay-Tracker sind nun schon etwas länger Down, es sind zwar etliche Ersatz-Tracker aus dem Boden gesprossen, aber meiner Meinung nach ist das dezentrale Tracking nun an der Reihe. Die Tracker waren bis jetzt einer der grössten Angriffs/Schwachpunkte der BitTorrent Technologie/ des BitTorrent Protokolls.
Doch das muss nicht so sein, denn es gibt ja DHT (BEP005). Ich will mich hier mal etwas näher mit DHT beschäftigen und das DHT Protokoll näher erklären.

Die Technologie hinter DHT im BitTorrent-Protokoll basiert auf Kademlia. Kademlia wurde von Petar Maymounkov und David Mazières entwickelt und “implementiert” bzw spezifiziert Distributed Hashtables in P2P-Netzen. Verschaffen wir uns erstmal einen kleinen Überblick über Kademlia.

BEP005 spezifiziert das die Daten per UDP übertragen werden. Zuerst generiert der Client eine Node ID, diese wird genauso wie der BitTorrent Infohash errechnet, bzw nutzt den selben Bit-raum (160Bit). Danach beginnt das Bootstrapping, der Client muss sich ja erstmal im DHT zurechtfinden und einen anderen Client finden dieser Teilt dann weitere IPs mit. Meist ist die erste Node “router.bittorrent.com” da ein Scannen durch die eigene IP-Range oder willkürliches suchen nach anderen Nodes nicht so erfolgversprechend ist.
Zur Indizierung von BitTorrent-Hashes wie es ein Tracker macht trägt bei DHT jeder Peer/Node bei.
Wenn wir nun einen bestimmten Hash suchen kann die Entfernung zu diesem Hash ausgerechnet werden. Dafür werden entweder Node IDs und Node IDs verglichen, oder Infohashes und Node IDs, durch den “Algorithmus” lässt sich die “nähe” der Node ID zur gesuchten ID (Infohash oder Node ID) errechnen. Die Routing Tabelle die der Client nun erstellt wird immer detaillierter je näher wir an den gesuchten ID-Wert kommen und die Node mit der gewünschten Information gefunden haben. Jede Node hat “Kontaktdaten” zu den Nodes mit “nahen” IDs.

Die Distanz zwischen 2 IDs wird per XOR berechnet:

distanz(A,B) = |A xor B|

Je kleiner das Ergebnis desto näher Liegen sich A und B.

Wenn nun eine Node (im DHT) Peers (für BitTorrent) finden will passiert folgendes:
Ich gehe davon aus das das Bootstrapping schon fertig ist, wir also ein Paar Nodes schon in unserer Routing-Tabelle haben. Unser Client nimmt nun den Infohash aus der Torrent-File. Wir nehmen Beispielsweise den Hash
362b0a1151013916896a9c98b52e0ead803c4ac3 (ubuntu-7.10-alternate-hppa.iso). Unser Client wird die Node mit dem geringstem Abstand zum Infohash nun Kontaktieren und diese Node nach Peer-Kontaktdaten Fragen. Wenn diese Node Peer-Kontaktdaten besitzt werden diese zu unserem Client übermittelt und dieser baut dann über das BitTorrent-Protokoll eine Verbindung zum Peer auf. Wenn die Node keine Peer-Kontaktdaten hat wird sie uns Kontaktdaten zu den Nodes aus ihrer Routing-Tabelle geben die am Nächsten an unserer ID liegen, und so weiter und so fort! :D

Die Antwort der Nodes auf die Anfrage nach Peers zu einem Infohash beinhaltet immer einen “token”. Wenn wir nun dem Node von dem wir die Peer-Kontaktdaten bekommen haben mitteilen wollen (wie beim Tracker ein sogenannter “announce”), müssen wir dem Node neben dem Announce auch den Token schicken den wir zuvor
von ihm erhalten haben.
Es liegt auf der Hand das dies eine Sicherheitsmaßnahme ist, damit nicht irgendwelche unbekannten Hosts (Bots von der MI) den DHT verseuchen. Die BEP005 spezifiziert das die Tokens alle 5 Minuten neu generiert werden, sie bestehen aus einem SHA1-Hashes auf die IP Adresse verknüpft mit einem Salt (welches alle 5 Minuten wechselt).

Routing
Kommen wir nun zum Aufbau der Routing Tabelle unseres Nodes. Die Routing Tabelle ist beinhaltet alle Bekannten Nodes die noch errechbar sind (das wird in einem Zeitraum von 15 Minuten getan) und diese Nodes dienen als Startpunkte für neue anfragen im DHT.

Die Nodes in unserer Routing Tabelle werden je nach ihrer Erreichbarkeit eingestuft. Die Erreichbarkeit jeder Node wird alle 15 Minuten überprüft. Eine Node wird als “good” eingestuft wenn sie uns eine Anfrage geschickt oder beantwortet hat innerhalb der letzten 15 Minuten. Wenn eine Node innerhalb von 15 Minuten nicht aktiv war wird sie  “questionable” also Fragwürdig eingestuft. Ein Node wird als “bad” eingestuft wenn er auf mehrere Anfragen nicht geantwortet hat. Unsere Routing-Tabelle sollte nur “good”-Einträge enthalten.

Die Routing Tabelle deckt den kompletten Raum an möglichen IDs ab (von 0 bis zu 2^160). Die Routing-Tabelle ist in “Buckets” (Eimer) unterteilt. Eine leere Routing-Tabelle enthält einen Bucket mit dem ID-Raum von 0 (min) bis 2^169 (max). Wenn wir nun eine Node mit der hypothetischen ID “A” (normal ist die ID natürlich 20byte lang wie beim Infohash) dann wird diese in einen Bucket eingefügt der min < A < max ist. Also in einem Bereich bei dem
min kleiner als A ist und A kleiner als max :D
In einer leeren Routing-Tabelle ist nur ein Bucket also passen in diesen Bucket alle möglichen IDs rein. Allerdings kann ein Bucket nur K verschiedene Einträge enthalten, im Moment ist K=8. Wenn der Bucket voll mit “good”-Nodes ist, werden keine Nodes mehr hinzugefügt – AUßER die eigene Node ID fällt in den Bereich, in diesem Fall wird der Bucket durch zwei neue Buckets ersetzt und die Nodes aus dem Vorherigem Bucket werden auf die zwei neuen Buckets aufgeteilt. Diese zwei Buckets könnten bei einer Routing-Tabelle mit nur einem Bucket dann jeweils die Bereiche vor und nach unserer ID abdecken (min/max werte).

Jeder Bucket sollte (das ist natürlich jedem selbst überlassen, wenn man es denn Implementiert) eine “last changed” Eigenschaft haben um die “frische” des Buckets ablesen zu können. Auch hier sollte alle 15 Minuten die Erreichbarkeit der enthaltenen Nodes überprüft werden. Laut BEP005 wird dies folgendermaßen gemacht:
Eine zufällig ausgewählte ID aus dem Bereich des Buckets (min/max) wird mit einer “find_nodes” (dazu weiter unten im Protokoll-Bereich mehr) Anfrage kontaktiert – bei Antwort ist die Node noch zu gebrauchen, wenn
nicht sollte die Node aus dem Bucket entfernt werden. Wenn eine Node Anfragen von anderen Nodes nicht beantworten kann, z.B. wegen schlechten Router-Settings, dann sollte Sie ihre Buckets öfter Auffrischen als eine Node die auf Anfragen antworten kann, den eine solche Node erhält ja eh immer wieder neue Node IDs.
Die Node sollte zudem versuchen ihr selbst nahe liegende Nodes zu finden.

BitTorrent Protokoll

Wenn unser BitTorrent-Client DHT unterstützt, wird bei den Protokoll-Flags im Handshake das letzte Byte gesetzt. Wenn nun ein anderer Peer uns beim Handshake das er DHT Supported, senden wir ihm mit der PORT-Message des BitTorrent-Protokolls unseren UDP-Port auf dem unsere DHT-Implementierung lauscht. Die DHT-Implementierung Pingt dann die neue Node und wenn eine Antwort kommt wird diese nach den oben definierten Regeln in einen Bucket eingefügt oder auch nicht (bei keiner Antwort).

Torrent File

Die Torrent-File enthält keine “announce”-URL mehr, sondern einen “nodes”-Key. Dieses Nodes Dictionary enthält die K (K=8) nähsten bekannten Nodes von dem Client der die .torrent-File erstellt hat. Oder halt eine Liste mit K bekannten “good”-Nodes. Das Nodes-Dictionary ist wie folgt aufgebaut:

nodes = [["",], ["",], ...]
nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]]

Protokolle

Kademlia RPC Protololl

KRPC ist relativ schnelle und einfach erklärt. Die Einzelnen Messages sind wie bei BitTorrent üblich BEncoded. Auf einen Request kommt eine Antwort/Response. Es gibt drei Message-Typen: query, reponse und error.
Beim DHT-Protokoll sind es vier: ping, find_node, get_peers und announce_peer. Eine KPRC-Message besteht aus einem Dictionary mit zwei Keys, sowie zusätzlich je nach Message-Typ zusätzliche Felder.
Der Key “t” beinhaltet die “transaction id”, die “tansaction id” wird beim Query errechnet und dient dazu Anfragen und Antworten zuzuordnen. Sie besteht meistens nur aus 2 Buchstaben, da diese vollkommen ausreichen um eine große Anzahl von Anfragen abzudecken.
Der andere Key ist “y” und beinhaltet als Wert nur einen einzigen Buchstaben:

  • q: query
  • r: response
  • e: error

Um die Kontaktdaten von Peers zu übertragen werden diese Kodiert. Hier kommt die selbe Kodierung wie beim Compact-Encoding bei BitTorrent zum Einsatz, ein 6-Byte String – wobei die ersten 4 Byte die IP repräsentieren und die letzten 2 den Port.
Um die Kontaktdaten von anderen Nodes zu übertragen werden diese ebenfalls Kodiert, dies geschieht jedoch mit dem “Compact Node Encoding”. Hier ist es ein 26-Byte String. Die ersten 20byte enthalten die Node ID die restlichen 6 sind die Compact-Encodierte IP und der Port wie oben.

Queries/Anfragen
Der “y” Key enthält als Wert “q” wie weiter oben schon erklärt. Zusätzlich noch die die zwei Keys “a” und “q”.

  • q: enthält den Methodennamen des Queries (DHT Protokoll z.B. Ping)
  • a: enthält die Argumente

Responses/Antworten
Der “y” Key enthält hier den Wert “r” für Response.
Zusätzlich enthält diese Message den Key “r”:

  • r: ist ein Dictionary mit den Ergebnissen der Anfrage

Errors/Fehler
Der “y” Key enthält den Key “e” für Error.

  • e: enthält eine Liste:
    • das erste Element der Liste enthält den Fehler Code
    • das zweite Element die Fehlermeldung

Mögliche Fehler und ihre Entsprechenden Messages:

Code Beschreibung
201 Generic Error
202 Server Error
203 Protocol Error, such as a malformed packet, invalid arguments, or bad token
204 Method Unknown

Beispielhaftes Error Packet aus BEP005:

generic error = {"t":"aa", "y":"e", "e":[201, "A Generic Error Ocurred"]}
bencoded = d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee

DHT Queries

Bei den DHT Anfragen enthält jeder Query einen “id”-Dictionary als Argument, neben etwaigen anderen Argumenten, welcher die Node ID der anfragenden Node beinhaltet (20-Byte String in Network Byte
Order) die Antworten enthalten natürlich die Node ID der antwortenden Node.

Hier die Möglichen Queries:

ping
Der Key “q” für den Query-Typ beinhaltet hier den Wert “ping”. Der Key “a” für die Argumente enthält einen Dictionary mit dem Key “id” und als Wert wie oben schon erklärt die Node ID in Network Byte Order.

Example Packets aus BEP005:

ping Query = {"t":"aa", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}}
bencoded = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe
 
Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}
bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

find_node:
Dieser Query wird benutzt um die Kontaktinformationen zu einer bestimmten Node anhand ihrer ID herauszufinden. Der “q”-Key enthält hier logischerweise “find_node”.
Die Argumente im “a”-Key enthalten wie immer die eigene Node ID und hier noch das Target-Dictionary welches folgende Keys enthält:

  • “target”:  ID der gesuchten Node

Als Antwort auf einen “find_node”-Query sollte die Antwort einen Key namens “nodes” enthalten der die Compact-Encoded-Node Informationen der gesuchten Node oder 8 (K) der nähsten bekannten “good”-Nodes enthalten.

Beispiel aus BEP005:

find_node Query ={"t":"aa", "y":"q", "q":"find_node","a":{"id":"abcdefghij0123456789","target":"mnopqrstuvwxyz123456"}}
bencoded = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe
 
Response = {"t":"aa", "y":"r", "r": {"id":"0123456789abcdefghij", "nodes": "def456..."}}
bencoded = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:t2:aa1:y1:re

get_peers:
Mit diesem Query erhält man Peers für den Torrent Download. “q” entspricht hier “get_peers”. Die Argumente sind “id” mit der Node ID und “info_hash” mit dem Infohash des Torrents. Die Antwort enthält den Key “values” der eine Liste von Strings enthält die entweder Compact-Encoded IP der Peers enthält, oder wenn keine Peers bekannt sind: einen Key “nodes” der eine Liste mit 8 (K) Nodes im Compact-Encoded Format enthält. In jedem Fall wird bei der Antwort ein Key “token” übertragen (der Token wird bei einem “announce” gebraucht).

Beispiele aus BEP005:

get_peers Query = {"t":"aa", "y":"q", "q":"get_peers", "a": {"id":"abcdefghij0123456789", "info_hash":"mnopqrstuvwxyz123456"}}
bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe
 
Response with peers = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "values": ["axje.u", "idhtnm"]}}
bencoded = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl6:axje.u6:idhtnmee1:t2:aa1:y1:re
 
Response with closest nodes = {"t":"aa", "y":"r", "r": {"id":"abcdefghij0123456789", "token":"aoeusnth", "nodes": "def456..."}}
bencoded = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:t2:aa1:y1:re

announce_peer:
Der “q” Key enthält logischerweise den String “announce_peer”. Dazu kommen noch 4 Argumente in “a”, die da wären:

  • id: Node ID
  • info_hash: Infohash des Torrents
  • port: BitTorrent Client Port (zb 6881)
  • token: der token der beim vorherigem query nach peers vomentsprechendem Node gesendet wurde (dem Node welches usn die Peers geschickt hat)

Beispiel aus BEP005:

announce_peers Query = {"t":"aa", "y":"q", "q":"announce_peer", "a": {"id":"abcdefghij0123456789", "info_hash":"mnopqrstuvwxyz123456", "port": 6881, "token": "aoeusnth"}}
bencoded = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe
 
Response = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}
bencoded = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

Ich hoffe das war ein Verständlicher “kleiner” Überblick uber DHT im BitTorrent-Protokoll. Und im naechstem teil gehts dann ueber den Message-Flow im BitTorrent-Protokoll xxD Bevor wir dann auch zu anfassbarem Code kommen, bzw einem Release :D

Links:

Trotzallem noch tolle Ersatz-Indexer :D

  • torrentbox Hier finde ich vor allem das Global-Search Feature ganz nettm da dort auch Torrentbox-Verified Torrents angezeigt werden
  • 1337x Noch etwas kleines aber sympathisches Projekt
  • h33t Die Oberfläche ist gewöhnungsbedürftig, ansonsten auch sehr nice xD

Tagged: , , , , , , , ,