Bittorrentの複雑な仕様について調査してみた。まだ理解できていない点もあるけれど、一旦まとめてみる。
Bittorrentにはv1とv2の２つのバージョンがあるが、ここではv1について解説する。(現在の主流もv1である)
1.bencode
bencodeはBitTorrent特有のエンコードで、トレントファイルや通信の中では、この記法が使われている。
仕様はhttps://wiki.theory.org/BitTorrentSpecification#Bencodingを参照
2.トレントファイルの中身
仕様では"metainfo file"と呼ばれている。拡張子が.torrentの、いわゆるトレントファイルのこと。ファイル全体が1.のbencodeで書かれている。
詳細な仕様はhttps://wiki.theory.org/BitTorrentSpecification#Metainfo_File_Structureを参照
2.1 info
トレントファイルの最重要部分がinfo。主に以下のような情報が含まれている。
2.1.1 ファイルの情報
各ファイルのファイル名、ファイルサイズ、ファイルのパスの情報が書かれている。
2.1.2 ピースの情報
以下の情報が含まれている。
- piece length : 一つのピースのサイズ
- pieces : 各ピースの SHA1 ダイジェスト（20バイト）を、ピース数ぶん連結したバイト列
ピースについては下記に後述
2.2 その他
info以外に、トレントファイルには以下のような情報が含まれる。
- announce : トラッカーのURL
- creation date : 作成日時
- created by : トレントファイル作成に使ったソフトウェア
3. ピース
ピースとは、共有対象とするファイルの中身を分割したデータのこと。共有するファイルが複数ある場合は、 トレントファイルのinfo内に書かれている順番にファイルを結合したデータ を分割する。
一つのピースのサイズは自由だが、だいたい256KBか512KBくらいになる。すべてのピースは同一サイズである必要がある(最終ピース以外)。
4. トラッカー
トラッカーは、各トレントのピアのIPアドレスやポートを取得するためのサーバ。P2P通信を行う前に、トラッカーにアクセスして、どこに接続すれば良いのかを確認する。
トラッカーは基本的に、普通のHTTP(S)サーバとして動く。拡張としてUDPトラッカーの仕様もあるが、ここでは説明を割愛する。
詳細な仕様はhttps://wiki.theory.org/BitTorrentSpecification#Tracker_HTTP.2FHTTPS_Protocolを参照
4.1. リクエスト
クライアントから、HTTP GETでサーバ(トラッカー)に通信する。URLの後ろに?を続ける形式でクエリを送信する。そのため、送信時はデータに対してURLエンコーディングが行われる。
以下のようなデータを送信する。
4.1.1. info_hash
info_hash は、トレントファイルのinfoの値をSHA1ハッシュ化した、160ビット(20バイト)のバイト列。info_hashは各トレントを識別するための重要な値で、他の場所でも使われる。
4.1.2. peer_id
peer_idは各ピアを識別するためのid。BitTorrentソフトウェアが内部的に自動生成している。慣習的な命名規則があり、使用しているソフトウェア名などがidを見ると分かるようになっている。
4.1.3. その他
info_hash、peer_id以外には、ポート番号、今までダウンロード・アップロードしたデータサイズの合計、ダウンロード完了までの残りサイズ、などの情報を送信している。
4.2. レスポンス
トラッカーからのレスポンスは、上で述べたbencodeでエンコードされた文字列で返される。
トラッカーのレスポンスには、以下のような情報が含まれる。
- complete : 共有するピースが100%揃っているピアの数
- incomplete : ピースが揃っていないピアの数
- interval : 次にトラッカーにリクエストするまでの待機時間
- peers : ピアのリスト。各ピアのid、IPアドレス、ポート番号の情報が含まれる。
5. ピア通信
BitTorrentでのピア同士の通信(いわゆるP2P)通信は、TCPを用いて行われる。
UDPを用いた拡張(uTP)もあり、uTPでは細かい輻輳制御を行って通信が効率化されている。これについては割愛する。
バイナリデータのやり取りになるので、ここでは細かい仕様を省略して、どのような情報が送信されるのかを大まかにまとめておく。
詳細な仕様はhttps://wiki.theory.org/BitTorrentSpecification#Peer_wire_protocol_.28TCP.29を参照
5.0. ハンドシェイク
前述のトラッカーへのリクエストでも送信した、info_hashとpeer_idを含むデータを片方が送り、もう片方が同様のデータを送信したら接続が確立したとみなす。
5.1. メッセージ
ハンドシェイクが完了したあとに送信するメッセージを以下に挙げる。
5.1.0. keep-alive
接続が切断されないよう、通信がないときに定期的に送信する。
5.1.0-3. choke、unchoke、interested、not interested
BitTorrentでは、相手ピアとの関係について、以下の二つの状態を用いる。
- choke : 相手ピアからのデータ送信リクエストを受け付けないことを、「チョーク(choke)している」と表現する。
- interested : 相手ピアからデータを送ってもらいたい状態であるときに、「興味ある(interested)」と表現する。
上の二つをまとめて言うと、「自分が相手ピアからchokeされていない(=unchoke)、かつ、自分が相手ピアに対してinterested」の状態のときだけ、相手ピアからデータを送信してもらうためのリクエストを送ることができる。
逆から見ると、「自分が相手ピアをchokeしていない(=unchoke)かつ、相手ピアが自分に対してinterested」の状態のとき、相手ピアが自分にリクエストを送れる。
choke、unchoke、interested、not interestedのメッセージは、chokeとinterestedの状態を変更するメッセージになる。(接続開始時はchoked、not interestedの状態になる)
5.1.4. have
ダウンロード完了したピースの情報を伝える。
5.1.5. bitfield
ハンドシェイク完了直後に送ることができる(送らなくてもよい)。自分がダウンロードが完了しているピースと、完了していないピースをビットで表して送信し、ダウンロード状態を伝える。
5.1.6. request
相手ピアにデータの送信を依頼する。
ピースと、そのピースのどの部分のデータが欲しいかを伝える。(BitTorrentでは基本的に、一度にピースをすべて送るのではなく、ピースの一部分(ブロック)ごとに送信する)
5.1.7. piece
requestに応じて、データをピアに送信する。
5.1.8. cancel
requestをキャンセルする。(他のピアからダウンロードできたときなど)
5.2. 拡張メッセージ
上記のメッセージ以外にも、使用できる拡張(extension)のメッセージがいくつかある。Fast Extension、Extension Protocolは標準化されている。また、標準化されていない拡張も実際の通信では使われることがある。
メタデータ送信の拡張(これも標準化されている)は重要で、トレントファイルに含まれるinfoの情報を相手ピアから取得できる。この拡張によって、トレントファイルをダウンロードしなくても、マグネットリンクを使ってピア通信することが可能になっている。
5.3. メッセージ暗号化の拡張(PE、MSE)
BitTorrentには、ピアとの通信を暗号化する拡張がある(PEもしくはMSEとも呼ばれる)。これは標準化されていないが、BitTorrentソフトウェアの多くはデフォルトで使用するよう。
この拡張の仕様については、下記リンクが参考になる。
https://jwodder.github.io/kbits/posts/bt-encrypt/
Wiresharkでパケットキャプチャして通信を見る場合は、この暗号化を無効にしないと通信内容が見えなかったので、勉強時は注意すること。
6. DHT(分散ハッシュテーブル)
DHTはトラッカーを使わずにピアを発見するための仕組み。P2P通信だけでピアを発見することで、単一障害点のないPure P2Pが実現できる。(トラッカーを使う場合、トラッカーとの通信はクライアントサーバモデルになるので、純粋なP2Pではない)
仕様は以下で標準化されている。
https://bittorrent.org/beps/bep_0005.html
ただ、この仕様は曖昧なところが残っていたりして分かりにくいので、以下の実装(webtorrentの一部)を主に参考にした。
https://github.com/webtorrent/bittorrent-dht
6.1. ピアとノード
DHTの項では、「ピア」と「ノード」を(公式仕様にのっとって)以下のように使い分ける。
- ピア(peer) : 上で述べた、共有ファイルをやりとりする通信をしているクライアント。
- ノード(node) : DHT通信をするクライアント。
ピアの通信とノードの通信は異なるものである。ネットワークは別々に分かれており、混ざることはない。
6.2. ノードが保持する情報
DHTの各ノードは、各々が以下の情報を保持する。
- ノードID : 160ビット(20バイト)のランダムなID。各ノードがそれぞれ固有のIDを持つ。
- ピアの情報 : トレントのinfo_hashと、そのトレントの通信をしているピアの情報(IPアドレス、ポート)を保持する。
- ルーティングテーブル : 他のノードの情報(IPアドレス、ポート、ノードID)を保持する。ルーティングテーブルはバケット(bucket)と呼ばれる単位で分けて管理される。
6.3. DHTの通信プロトコル(KRPC)
DHTではKRPCと呼ばれるプロトコルでノード同士の通信を行う。通信にはUDPを用いる。
KRPCには以下の3種類の通信がある。
- クエリ(query)
- レスポンス(response)
- エラー(error)
あるノードが相手ノードに対してクエリを送信したら、相手ノードがレスポンスもしくはエラーを返す、というだけの通信となっている。
クエリは、さらにping、find_node、get_peers、announce_peerの4種類に分かれるので、以下で解説する。
相手ノードが返答できる状態か確認する。
6.3.2. find_node
ノードの情報の送信を相手に依頼する。
パラメータとして160ビット(20バイト)のIDを渡す。相手は、そのIDに近いIDのノードをレスポンスとして返す。受け取ったノードの情報はルーティングテーブルに追加し、管理する。
(「近いID」の意味については後述)
6.3.3. get_peers
トレントのピアの情報の送信を、相手に依頼する。
トレントのinfo_hashをパラメータとして渡す。もし相手がそのinfo_hashのピアの情報を持っていたら、その情報がレスポンスとして返される。
info_hashの情報を持っていなかった場合、 そのinfo_hashに近いIDのノードがレスポンスとして返される。この場合、レスポンスとして返されたノードそれぞれに対して、再度get_peersクエリを送信する。新しいノードが見つからなくなるまで、これを繰り返す。 この動作はDHTの仕組みの核となる。詳細は後述。ピアやノードの情報を受け取ったら、上記のように、それらの情報は保持して管理する。
また、get_peersのレスポンスではtokenも一緒に返される。これはannounce_peerで使用する。
6.3.4. announce_peer
自分のピアが参加しているトレントのinfo_hashを送信し、自分がそのトレントに参加していることを宣伝する。送信時に、同じ相手ノードから前に受け取ったtoken(get_peersのレスポンスに含まれる)が必要(これは送信元IPアドレス偽装の攻撃を防ぐためのもの)。トレントのinfo_hashに近いノードに送信する。
announce_peerを受け取った側は、この情報を上記のように保持する。
6.4. 距離の算出(distance metric)
ノードID、トレントのinfo_hashはどちらも160ビット(20バイト)のデータである。DHTでは、これらのデータに対して 距離(distance metric) を定義する。
160ビットのデータを二つ与えたとき、この二つの間でビット演算のXOR(排他的論理和)を行う。その結果を符号なし整数(unsigned integer)として解釈した結果が「距離」となる。
二つのデータの「距離」が小さいとき、「近い」と表現する。
上記のfind_node、get_peers、announce_peerではノードIDやinfo_hashの「近さ」の評価に基づいた操作を行っている。
6.4.1. 「距離」をなぜ使うか？
この「距離」はBitTorrentのDHTプロトコルの根幹となるアイディアである。
Kademliaという分散ハッシュテーブルの仕組みがベースとなっており、二分木探索によって、広大な空間から目的のデータに高速にたどり着くための仕組みとなっている。Kademliaについては以下が参考になる。
https://hazm.at/mox/distributed-system/algorithm/distributed-hash-table/kademlia/index.html
二分木で、自分のIDと近いノードの情報をより多く保持するような仕組みになっている(このあたり理解不足)。
トレントのピアの情報は、announce_peerによって、info_hashに近いIDを持ったノードに送信される。そのため、ピア情報を取得するときは、info_hashに近いノードに問い合わせることで発見できる。
6.5. bootstrap
DHTに参加するとき、最初に通信するノードの設定が事前に必要となる。この初期通信のことはbootstrapと呼ばれる。(ただし公式の仕様には記載がない)
bootstrapにおいては、find_nodeのクエリを使って、自分のノードIDと近いノードの情報を集める。このbootstrap通信の相手ノードとなる、初期ノードの情報は、BitTorrentクライアントのソフトウェアがデフォルトで設定していることが多い。
dht.transmissionbt.comやdht.libtorrent.orgなど、有名BitTorrentクライアント作成者の提供するノードが使われていたりする。
DHTにもいくつか拡張が存在する。任意のkey-valueをDHTで送信する拡張は自由度が高いかもしれない。
7. PEX(Peer Exchange)
トラッカー、DHTの他に、ピアを発見する方法としてはPEXがある。
PEXは、ピア通信の拡張メッセージの一つであり、ピア同士の通信で新しいピアの情報をやり取りする。トラッカーやDHTとは違い、すでにピア通信をしていることが前提となるので、まだ一つもピアを発見していない場合は使うことができない。
8. LSD(Local Service Discovery)
LSDは、マルチキャストを使用してピアを発見する方法。
仕様は以下
https://bittorrent.org/beps/bep_0014.html
9. WebSeed
WebSeedは、トレントの共有ファイルが置いてあるHTTPなどのサーバを、BitTorrentのシード(全ピースを持っているピア)かのように扱う仕組み。
サーバ側は通常のサーバから設定を変える必要はない。クライアント側で工夫して実装する。
WebSeedの仕様は以下
https://bittorrent.org/beps/bep_0019.html
参考リンク
開発者による非公式の仕様解説。公式の仕様より具体的でわかりやすい。ただし、基本的な仕様の解説のみ
https://wiki.theory.org/BitTorrentSpecification
公式仕様。DHT、uTPなどの拡張仕様もここに載っている。
https://bittorrent.org/beps/bep_0000.html
libtorrent。開発者のArvid Norberg氏は、BitTorrent Inc.の元開発者のようで、公式仕様の策定などにも関わっている。
https://libtorrent.org/
Arvid Norberg氏によるlibtorrentの解説動画。輻輳制御など細かい通信性能の話が多い。
https://www.youtube.com/watch?v=Z6Os8HD80A4
webtorrentのDHT実装。コードがシンプルなので参考になった。
https://github.com/webtorrent/bittorrent-dht
Kademlia(BitTorrentのDHT実装の下敷きになっている)の論文。
https://cs.nyu.edu/~anirudh/CSCI-GA.2620-001/papers/kademlia.pdf
分散ハッシュテーブル(DHT)、Kademliaに関する日本語の解説。
https://hazm.at/mox/distributed-system/algorithm/distributed-hash-table/index.html
https://hazm.at/mox/distributed-system/algorithm/distributed-hash-table/kademlia/index.html
首藤一幸(現・京都大学教授)氏によるKademliaの解説。
http://www.shudo.net/article/20040727-Kademlia/shudo-Kademlia.pdf
その他、Kademliaの解説
https://codethechange.stanford.edu/guides/guide_kademlia.html
https://kelseyc18.github.io/kademlia_vis/basics/1/
https://pub.tik.ee.ethz.ch/students/2006-So/SA-2006-19.pdf
