Le protocole BitTorrent et ses extensions
Accueil
A propos de ce site
Ce site a été réalisé par Mathieu Sornay, dans le cadre des Xposés de 3ème année, au cours de la formation Informatique et Réseaux à l'ESIPE.
Ces exposés sont encadrés et dirigés par Dominique Revuz
Le but des exposés et de découvrir ou d'approfondir des notions au-delà des cours dispensés lors de la formation. Les exposés comportent en fait deux composantes : une présentation orale, ainsi que la restitution des informations sous forme de site web.
Le protocole BitTorrent
Si vous êtes intéressé par ces lignes, il y a de bonnes chances pour que vous ayez déjà utilisé le protocole BitTorrent. Il est très répandu et a un statut un peu particulier parmi les protocoles applicatifs courants. On le mentionne, mais on l'étudie peu dans les salles de classe ; certainement parce qu'il est souvent utilisé pour échanger des fichiers dont le contenu est protégé par du droit d'auteur. C'est dommage, car en tant que protocole peer-to-peer déployé à très grande échelle, il présente des algorithmes et des structures de données intéressantes.
J'ai voulu ici décrire les principaux mécanismes qui entrent en jeu lorsqu'un client télécharge (et donc partage) un fichier avec BitTorrent. Si on capture le trafic pendant un tel transfert, on s'aperçoit bien vite que les échanges ne sont pas entièrement décrits par la spécification officielle. Je me suis donc ensuite concentré sur les extensions que j'ai considérées à la fois largement utilisée et dignes d'intérêt.
BitTorrent est un protocole de transfert de fichier. Dans le cas client/serveur classique, on a un serveur qui transmet N copies du fichier vers N clients. Problème : pour gérer beaucoup de clients, le serveur coûte cher. La solution du peer-to-peer en général, et de BitTorrent en particulier, est de faire participer les clients à la diffusion du fichier
Fichiers metainfo
La première action d'un client qui souhaite obtenir un fichier en utilisant BitTorrent est de récupérer un fichier metainfo (aussi appelé torrent, dont l'extension est généralement .torrent). On les trouve principalement sur des serveurs web, le plus connu étant bien évidemment www.debian.org.
Un fichier metainfo contient des informations B-encodée. Le B-encoding est un format binaire qui permet d'encoder :
- des chaînes de caractères ;
- des entiers ;
- des listes ;
- des dictionnaires.
Peu importe le flacon, un fichier metainfo contient un dictionnaire où l'on trouve deux clés : announce qui est associée à une chaine de caractère (une URL vers un tracker, élément qui fait l'objet de la partie suivante) et la clé info où l'on trouve un autre dictionnaire. Il possède les champs suivants :
- name : le nom sous lequel le client va enregistrer le fichier (C'est un nom purement indicatif, on peut le changer avec la plupart des clients logiciels) ;
- piece length : Pour partager un fichier avec BitTorrent, on le découpe en fragments. Ce champs indique la taille des fragments. Les valeurs typiques sont 256kB ou 1MB ;
- pieces : Pour chaque fragment du fichier on calcule un hash en SHA-1, ce qui donne une chaîne de 20 octets pour chaque fragment. Le champs pieces est la concaténation de toute ces hash dans l'ordre des fragments du fichier ;
- Le dernier champ est différent selon que l'on télécharge un seul fichier ou plusieurs. Dans le premier cas, on a un champs length qui indique la taille totale du fichier. Sinon, si le torrent permet de télécharger un dossier, on aura une liste de dictionnaires nommée files (au format {’length’ : xxx, ’path’ : xxx}). Dans ce cas, le champs pieces précédent est calculé sur la fragmentation de la concaténation de tout les fichiers dans l'ordre défini par le champs files
Le dictionnaire info est b-encodé dans le fichier metainfo. Si on calcule le hash SHA-1 de la forme b-encodée de ce dictionnaire, on trouve 20 octets qui constituent l'info_hash du torrent. Cet info_hash servira d'identifiant pour le torrent dans toute la suite des échanges.
Trackers
Après avoir récupéré le torrent, on cherche à connaître les autres clients qui partagent le fichier. Pour cela, on va faire des requêtes HTTP GET sur le tracker (l'URL que l'on a récupéré dans le champs announce). On retrouve différents paramètres dans cette requête :
- info_hash : Les 20 octets (160 bits) définis plus haut, qui permettent d'identifier le fichier qui nous intéresse ;
- peer_id : Notre identifiant, 20 octets choisis aléatoirement ;
- ip : notre adresse ip (c'est optionnel, le tracker va certainement regarder celle qu'il trouve dans le paquet) ;
- port : port d'écoute. C'est important car après avoir requêté le tracker, nous serons sûrement contacté par d'autres peers intéressées par le fichier et ils nous contacterons sur ce port.
- uploaded/downloaded : Nombre d'octets envoyés / reçus depuis le début de la session. On peut tricher ? Oui, on peut tricher. Mais attention, les trackers qui portent de l'intérêt à cette information risquent fort d'implémenter un système qui recoupent nos affirmations avec celles des autres participants, et on risque d'être sanctionné en cas de contradiction.
- left : nombre d'octets qu'il nous reste à télécharger. Ce n'est pas calculable à partir du paramètre précédent car on peut télécharger un fichier pendant plusieurs sessions.
- event : Parfois absent, parfois positionné à "started" pour la première requète, "completed" pour annoncer la fin du téléchargement ou bien "stopped" lorsqu'on arrête le client logiciel.
La réponse du tracker est (encore) un dictionnaire b-encodé avec les champs :
- interval : nombre de secondes que l'on doit attendre avant de demander de nouvelles peers au tracker
- peers : Adresse IP et port de tout les clients qui participent à la diffusion du fichier.
On imagine assez bien le fonctionnement d'un tracker à partir de ces échanges. Lors de notre première requete sur le tracker, il ajoute notre IP et notre port à la liste des clients associés à l'info_hash du torrent. Lorsque d'autres client font une requête ensuite sur le même info_hash, ils récupèrent notre adresse IP et notre port et nous contactent directement.
Ci-dessus, j'ai décris la spécification officielle. En réalité, les choses se passent un peu différement. La liste des peers n'est pas une liste b-encodée mais une compact peer list , une simple chaine de caractère dont la longueur est multiple de 6 (4 octets pour l'IP, 2 pour le port, en network byte order). De plus, très rares sont les trackers qui utilisent encore HTTP. Ils utilisent directement UDP, ce qui réduit le trafic d'environ 50% par rapport à HTTP. Ces deux optimisations sont infimes du point de vue du client, mais elles sont importantes pour un tracker qui gére plusieurs millions de peers
Il faut noter que même si on utilise aujourd'hui UDP, un mécanisme de sécurité est implémenté. Le client doit demander une connection au tracker, qui renvoie un connection_id. Cet identifiant doit être inclus dans tout les échanges suivants. Cela permet d'éviter que le tracker soit polué avec de fausses information en provenance d'IP spoofées (si l'adresse source est spoofée dans la demande de connection, l'attaquant ne reçoit pas le connection_id en retour)
Quid des trackers dit "privés" ? Généralement, les trackers privés sont basés sur une application web où les clients sont loggés lorsqu'ils téléchargent le torrent. L'application personnalise le champs announce (l'URL du tracker) contenu dans le fichier torrent. Chaque requête que l'on fait sur le tracker est donc associée à notre compte, même si l'on change d'IP. Cela permet par exemple à l'application de calculer notre ratio upload/download. Certaines extensions implémentent d'autres manières de découvrir des peers, sans passer par un tracker. C'est gênant pour les trackers privés, une extension permet donc de rajouter un champs "private" dans les torrent pour désactiver ces mécanismes.
Peer protocol
A ce stade, on a récupéré la liste des peers qui partagent le fichier. Nous allons maintenant les contacter directement avec le peer protocol pour télécharger le fichier. C'est un protocole applicatif basé sur TCP, et il necessite que les peers sachent (à peu près) quels clients possedent tel ou tel fragment du fichier. La communication entre deux peers commence par un handshake où l'on trouve :
- La chaîne "BitTorrent Protocol"
- 8 octets à 0 par défaut. Ils sont utilisable par les extensions.
- L'info_hash du torrent sur 20 octets, pour annoncer à la peer que l'on est intéressé par ce fichier en particulier.
- Le peer_id obtenu sur le tracker. Etant donné que les trackers ne renvoient pas de peer_id depuis qu'ils fonctionnent en UDP, je pense que le champs est ignoré aujourd'hui.
Après le handshake, on échange des messages, ou au minimum des keep-alive pour conserver la connection TCP. Il y en a plusieurs types :
- bitfield : Généralement le premier message envoyé. C'est un tableau de bits qui va décrire les fragments que l'on possède (Si le premier bit est à 1, cela veut dire que l'on possède le premier fragment du ficher, etc.)
- request Pour demander à télécharger des données du fichier. Le téléchargement se fait par sous-fragments de 16kB. On requête par exemple les 16kB (length) à l'octet 32 (begin) du quatrième fragment (index).
- cancel : pour annuler des requêtes de données.
- piece : reponse à une requête, ou l'on trouve (enfin !) les données du fichier que l'on cherche à télécharger.
- have : Lorsqu'on termine le téléchargement d'un fragment, on calcule le hash SHA-1 des données que l'on a reçu et on le compare avec celui trouvé dans le torrent. Si ils sont identiques, on prévient toutes les peers qu'on connait qu'on détient le fragment.
Quatres autre messages existent mais ne transportent pas de données. Ils servent juste à signaler des changement de status. Quand deux peers se connectent, elles sont not interested et choked (étranglées) :
Quand on veut télécharger, on commence par envoyer un message à la peer en lui disant que l'on est interested :
La peer nous répondra (éventuellement...) avec un message unchoke :
Dans cet état, on sait que la peer en face répondra à nos request avec des piece (i.e. on pourra obtenir des morceaux du fichier)
Pourquoi ce mécanisme ? Il permet à la peer qui upload des données de savoir que quand elle envoie un unchoke à une peer qui est interested, cette dernière va télécharger directement. Cela permet de mettre en place une gestion fine de la distribution des données. Les algorithmes sont mal définis et diffèrent à mon avis d'un client logiciel à l'autre. Malgré tout on trouve les recommendations suivantes :
- Toutes les dix secondes :
- Si on ne posséde pas le fichier complet : unchoke des 4 peers qui nous envoient des données avec le meilleur débit. Ici, la spécification cherche à encourager la réciprocité dans les échanges.
- Si on a le fichier en entier : unchoke des 4 peers qui reçoivent avec le meilleur débit. L'idée ici est d'optimiser la diffusion du fichier parmi les peers. En effet, plus il y a de peers qui possedent le fichier, plus les transferts suivants seront facilités.
- Toutes les trentes secondes : optimistic unchoking , on unchoke une peer au hasard.
D'autres optimisations du peer protocol concernent l'ordre dans lequel les clients demandent les fragments du fichier. On trouvre trois politiques selon l'avancement du téléchargement:
- Random first piece : le premier fragment à télécharger est choisi au hasard, et on concentre nos effort pour le compléter au plus vite. En effet, dès qu'on posséde un fragment complet, on peut le partager. On pourra alors éventuellement bénéficier des algorithmes qui encouragent la réciprocité.
- Rarest piece first : On cherche ensuite a télécharger les fragments les plus rares d'abord, pour éviter la situation ou personne ne possède un certain fragment, car personne ne pourrais compléter le fichier.
- Endgame mode : Les derniers fragments sont requeté plusieurs fois chacun à plusieurs peers différentes. Cela évite de dépendre d'une peer unique pour le/les derniers fragments (les plus vieux se souviendront avec angoisse des 99.9% statiques à l'époque où les protocoles et les clients était moins évolués). Lorsqu'un fragment est terminé, on cancel les requêtes de ce même fragment.