【翻訳】GitTorrent: 分散化されたGitHub

Translation of "GitTorrent: A Decentralized GitHub"

Posted by midchildan on June 3, 2015

(これは私が2015年の5月にData Terra Nemo会議で話したことを書き起こしたものである。実際の話した時の様子が見たい人は、もうすぐビデオが公開されるのでぜひ見て欲しい。)

私は分散化したGithubの開発に取り組んでいるので今回はまずその意義と実装について話す。

なぜ分散化したGithubが必要なのか

まずは実際的な理由から話すと、Githubが信頼できなくなるなったり攻撃される可能性は否定できない。現に私がこのプロジェクトに取り組んでいる時期にGithubは中国からDDoS攻撃を受けていた。今のところGithubが多くのことを正しくやっている様子なのは私も十分承知しているが、ベンチャーキャピタルから1億ドルも資金を調達した企業がユーザーの意に強く反した行動をとるようになる事例は数えきれないほどある。

これとは別に、思想上の理由もある。Githubはクローズドソースであり私たちの手でより良くすることは出来ない。Mako Hillフリーソフトウェアには自由なツールが必要であるというエッセイでフリーソフトウェアの開発がプロプライエタリなソフトウェアに頼ることの問題点を指摘しているが、彼の意見は正しいと思う。別の見方をすればオープンソースのプロジェクトで共同開発するときの体験はGithubが決めたツールによって定められてしまうのだ。

以上が実際的な理由と思想的な理由であったが、3つめの理由は皮肉なものである。多くのプロジェクトが集中型のCVSやSubversionプロトコルから分散化を謳うGitプロトコルに移行した。この際プロジェクトをホストするサーバーはバラバラのサーバーからひとつの中心的なサーバーに移行した。これは大きな皮肉である。Google Codeは数ヶ月前にサービスの閉鎖を発表したが、その理由は「どうせみんなGithubを使ってる訳だから存在理由がなくなった」に近い内容だった。私たちは世界中のソースコードをひとつの中心的なサービスで管理する方向に急速に向かっている。

この会議ではここまでの一極集中化が得策では無いと納得してもらったという前提で話をすすめる。

Gitはすでに分散されているはずではないのか?

あなたは今次のように考えてるかもしれない。GitHubは集中型であっても、Gitプロトコルは分散化されている。あなたがクローンしたレポジトリは他の人が持ってるレポジトリのコピーと全く同じである。それで十分ではないかと。

私はそうは思わない。これはFTPあるからBitTorrentは不要ではないかと言ってるようなものだ。FTPでBitTorrentを置き換えることはおすすめできないし、意味不明だ。そもそもどのファイルがどのホストにあるかのインデックスも存在しないしからファイルをどこから取ってくればいいかが分からない。そして欲しいファイルを誰が所持しているかがわかったとしても、その人が匿名FTPサーバーを公開してる保証はない。

レポジトリをGitTorrentで公開しよう!

ではGitTorrentのデモに移ろう。BitTorrentで公開されたレポジトリをクローンする:

1
2
3
4
5
6
7
8
9
10
11
$ git clone gittorrent://github.com/cjb/recursers
Cloning into 'recursers'...

Okay, we want to get: 5fbfea8de70ddc686dafdd24b690893f98eb9475

Adding swarm peer: 192.34.86.36:30000

Downloading git pack with infohash: 9d98510a9fee5d3f603e08dcb565f0675bd4b6a2
Receiving objects: 100% (47/47), 11.47 KiB | 0 bytes/s, done.
Resolving deltas: 100% (10/10), done.
Checking connectivity... done.

はい、たった今BitTorrentからgitレポジトリをクローンできた。何が起きたか一行ずつ確認していこう。

1-2行目: 実はGitにはネットワークプロトコルの拡張機構が存在する。私が git clone と打ち込んだ行は git-remote-gittorrent コマンドに変換されてURLが引数として渡される。したがって実際のダウンロードをどのように行うかは自由であり、gitオブジェクトを新しいディレクトリーに書き込んで終了したらGitに知らせれば良く、Gitそのものに全く変更を加えることなく目的が実現ができた。

では git-remote-gittorrent は何をしたかについて説明しよう。まずはGitHubに接続してレポジトリの最新のレビジョンを調べ、何を取得するべきか把握した。Githubによると、5fbfea8de.. らしいことがわかった。

4-6行目: 次に、BitTorrent同様に分散ハッシュテーブルであるGitTorrentネットワークにコミット 5fbfea8de.. のコピーを持っている人がいないかを問い合わせる。実際持っている人がいたらその人とBitTorrentのコネクションを作る。BitTorrentの分散ハッシュテーブルの仕組みとして、 get_nodes(hash) という単一の操作によって次のように誰が自分の欲しいファイルを送信できるか知ることができる:

1
2
get_nodes('5fbfea8de70ddc686dafdd24b690893f98eb9475') = 
	[192.34.86.36:30000, ...]

なお、標準的なトラッカー不要トレントでは欲しいファイルの内容を指定すればファイルが取得できて幸せになれる。だがLinuxカーネルのように400万コミットあるような巨大なレポジトリではコミット1つ分だけ取得しても意味はなく、残りのコミットを取得するためにさらに400万リクエスト送る必要がある。また git pull するたびにすべてのコミットを取得したくはない。したがって何か別のことをする必要がある。

8-12行目: Gitは「スマート・プロトコル・フォーマット」というGitオブジェクトのやり取りについて交渉する手段を開発したことによってこの問題を解決した。

例えばあなたのレポジトリが20コミットあるとしよう。15番めのコミットが bbbb であり、一番最近である20番目のコミットは aaaa である。このとき、Gitプロトコルでの交渉は次のようなものになる:

1
2
3
ノード1> aaaaを持っている
ノード2> aaaaが欲しい
ノード2> bbbbを持っている

Gitグラフの仕組み上ノード1は bbbb がグラフ上でどこにあるかを調べて5コミット分送信すれば十分であることを確認し、その分のオブジェクトだけを含んだ「パックファイル」を作ればいい。これもたった3段階の通信だけで実現できるのだ。

これがGitTorrentで行うことである。欲しいコミットがあるか確認し、BitTorrentのノードに接続する。接続ができたらBitTorrent拡張という仕組みを使ってBitTorrentプロトコル上で先ほどのスマート・プロトコルによる交渉を行う。そしたら次に遠隔ノードはパックファイルを作り、そのハッシュを私たちに伝える。ハッシュを受け取ったら標準のBitTorrentプロトコルを使ってい、そのパックファイルをシードしてるノードからダウンロードする。パックファイルを受け取ったらそれを展開してどのGitコミットでグラフが終わるかを確認し、それが欲しかったコミットと一致するか確かめることによって内容の検証が可能だ。もし欲しかったコミットと違ったなら、スマート・プロトコルによる交渉で嘘をつかれたということであり、他のノードに問い合わせるべきだろう。

以上がターミナルで起こったことである。ハッシュからパックファイルを作ってもらい、ダウンロードして展開すればローカルgitレポジトリの出来上がりである。今回は新しくレポジトリをクローンしたため、パックファイルにはすべてのgitオブジェクトが含まれる。

これは通常のGitHubレポジトリをクローンするのと流れは変わらない。もしGitHubのディスク容量や帯域が持たなくなった場合、今のような方法でGitTorrentを使用することを推奨することもできる。この場合、GitHubにとってはP2P型のCDNを所有してるも同然になり、CDNに存在しないコミットに関してはGitHubのサーバーにフォールバックすれば良い。

何が実際に分散化されたのか

先ほど実演したことは確かに進歩ではある。だが最初にしたことが、一番大事なハッシュ値をGitHubから取得することであったことに引っかかりを覚えただろう。私たちが本当にGitHubを分散化したいのであればもっとうまくやる必要がある。そのためにはレポジトリの所有者が最新のバージョンのハッシュ値を知らせる仕組みが必要だ。もっと簡単に言えば、この段階で私たちはダウンロード可能なGitオブジェクトのデータベースを持っているがそもそもどのオブジェクトをダウンロードするべきなのかが分からない。したがって、GitHubで /ユーザー名/レポジトリ にアクセスして最新のレポジトリを取得する部分を再現する必要がある。

ではこれを実際にやってみよう。金槌しか持っていないとすべてのものが釘に見えると言われてるが、この場合における金槌とはどのノードがどのコミットを所持してるかの管理に使用した分散ハッシュテーブルだ。つい最近、substackはすべてのノードにネットワーク規模のキー・バリュー・ストアを維持する役割の一端を担わせるBitTorrent拡張が存在することに気づき、これに基づいて分散ハッシュテーブルに2つ操作、 get()put() を追加した。 put() はキー1つあたり1000バイト分のメッセージを格納することができる。このメッセージはあなたがネットワークから離脱したあとも他のノードに複製され、参照することができる。キーには2つ種類が存在し、そのひとつはイミュータブルキーである。イミュータブルキーは大体の人が想定するように動く。具体的には格納したいデータのハッシュを取れば、そのハッシュをキーとしてデータが格納されるというものである。

2つ目の種類はミュータブルキーといって、この場合のキーは鍵ペアの公開鍵のハッシュであり、鍵ペアの所有者は署名されたアップデートをそのキーに対応した値として発行できる。アップデートには番号がついてるため、クライアントはミュータブルキーのアップデートを見つけたら自分が記録してるよりも新しい番号が割り振られてないか見て、もしそうであればアップデートがキーに対応した公開鍵によって署名されてるかも確認する。両方確認がとれて大丈夫であった場合には新しい値に更新して再配布を開始する。これには様々な使い道が考えられるが、私はレポジトリの名前と最新のレビジョンを格納するために使用した。したがって流れとしてはGitでコミットしてネットワークにプッシュし、自分のミュータブルキーが最新のコミットを反映するよう更新してやればよい。以下がこの操作を説明したコードである:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// イミュータブルキーへのput操作
hash(value) = put({
	value: '何かしらのデータ'
})

// ミュータブルキーへのput操作
hash(key) = put({
	value: '何かしらのデータ',
	key: キー,
	seq: 番号
})

// Get操作
value = get(hash)

したがって今度誰かにGitTorrentのレポジトリをクローンして欲しい場合には、github.comのURLの代わりに分散ハッシュテーブルのミュータブルキーとして使われてる私の公開鍵のハッシュを伝えれば良い。

次がこのデモである:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
$ git clone gittorrent://81e24205d4bac8496d3e13282c90ead5045f09ea/recursers

Cloning into 'recursers'...

Mutable key 81e24205d4bac8496d3e13282c90ead5045f09ea returned:
name:	Chris Ball
email:	chris@printf.net
repositories:
	recursers:
		master: 5fbfea8de70ddc686dafdd24b690893f98eb9475

Okay, we want to get: 5fbfea8de70ddc686dafdd24b690893f98eb9475

Adding swarm peer: 192.34.86.36:30000

Downloading git pack with infohash: 9d98510a9fee5d3f603e08dcb565f0675bd4b6a2

Receiving objects: 100% (47/47), 11.47 KiB | 0 bytes/s, done.
Resolving deltas: 100% (10/10), done.
Checking connectivity... done.

今回のデモでは再びBitTorrent上でGitレポジトリをクローンしたが、GitHubと通信する代わりに分散ハッシュテーブルを使用して欲しいコミットがどれであるかを調べた。これで今回こそGitダウンロードの分散化を達成できた。

まだ残る不満として長い16進数はユーザー名として使うには不便である。だがこれは分散ハッシュテーブルでは解決できない問題だ。なぜならばユーザー名は衝突するものであり、2人が同じユーザー名の所有を主張した場合それを解決する手段がない。したがってユーザー名の所有者をめぐる統一的な合意を分散ネットワークで実現する方法が必要になる。これについて私が一番期待してる手段はブロックチェーンという、ビットコインを可能にする合意形成のための技術だ。

ビットコインのトランザクションにはOP_RETURNトランザクションと呼ばれる種類のものが存在する。これはウォレット間で金をやりとりする代わりにブロックチェーンで永久に保存されるメッセージを埋め込む。つい最近までは1つのトランザクションあたり40バイトのコメントに限られてたが、BitCoin Core 0.11移行は1つのトランザクションあたり80バイトに引き上げられた。ビットコインでトランザクションを行なうためには確か1回につき米ドルで約8セント、マイニングを行ってる人々やネットワークに対して負担しないといけなかったはずだ。

ブロックチェーンにコメントを残すことさえできれば、「ユーザーネームChrisに私の公開鍵のハッシュXを登録してくれ」とコメントを残せばいい。ブロックチェーンは末尾に書き足すことしか許されないデータ構造で誰でも全履歴を確認できるため、もし複数の人が同じユーザーネームを割り当てるよう要求しても誰が最初にその要求をしたか合意が取れる。これがビットコインが真に美しいところである。正直通貨云々の話は私には興味が湧かないが、肝心なのは分散ネットワークで合意を取るしっかりとした方法を確立したことだ。以上を踏まえるとトランザクションにい埋め込むコメントは次のようにすればいいだろう:

1
2
3
@gittorrent!cjb!81e24205d4bac8496d3e13282c90ead5045f09ea

(@サービス名!ユーザー名!公開鍵 になっている)

とても興味深いことにこれはgittorrent以外でも応用できそうだ。ビットコインの技術に基づいて分散化されたユーザーアカウントに興味があるサイトがこれを採用すれば、1つのユーザーアカウントで複数のサイトにログイン出来る。これを独立したモジュールやソフトウェア・プロジェクトにして分散化されたアプリケーションでもPythonやNodeやGoや他の言語で簡単にユーザーアカウントが使えるようにすることも出来るだろう。アプリケーションはブロックチェーンを監視してデータベースのテーブルに書き込み、テーブルの内容を解釈するウェブやネットワークサービス向けのプラグインを作るなどが考えられる。

このようなものが分散化界隈ですでに存在しないようで驚いた。私はこのようなプロジェクトに取り組んでその上にGitTorrentを載せたいと考えているので協力したい人がいればぜひ教えて欲しい。

ちなみにユーザー実際のユーザー登録は先ほど述べたよりはやや複雑になる。なぜならマイニングを行ってる人はトランザクションにあるメッセージを見て、ブロックチェーンに付け足内容を改変することが出来る。メッセージを改変してユーザー名の所有者をトランザクションを行った人ではなくマイニングを行ってる人を指すようにしてしまえばユーザー名の乗っ取りも可能だ。これはドメイン登録業者のページを訪問して検索ボックスに欲しいドメインが無いかを探すことと実質的に同じだ。検索した瞬間に登録業者がドメインを取得し、欲しければ1000ドル払えと要求することも出来てしまう。これでは使えない。

これを回避したければビットコインには解決策が用意されていて、登録を2段階にすればいい。最初のメッセージではユーザー名のハッシュ値だけを書き込み、ユーザー名の予約を行なう。マイニングする人はハッシュ値からユーザー名を逆算することは出来ないので先を越してユーザー名を登録することは出来ない。ブロックチェーンの予約が確保できて他の誰も先に予約してないことを確認できたら「予約トークンを使ってユーザー名を登録する。これが予約したユーザー名の平文だ」と言うことが出来る。これでそのユーザー名はあなたのものだ。

(この方式は私が考案した訳ではない。Jeremie MillerによるBlocknameというプロジェクトがこの方式を採用して、ビットコインOP_RETURNトランザクションを利用してビットコインのブロックチェーンでDNS登録を行っている。違いといえばブロックネームはドメインネームの登録を行っているのに対し、私が行おうとしてるのはユーザー名から公開鍵のハッシュ値へのマッピングであるということぐらいだ。また、Blockstoreも同様のことを行っているという指摘を受けた。)

まとめると、私たちはGitオブジェクトのBitTorrentスウォームを作り、ユーザー名登録に取り掛かった。はじめは次のようにコマンドを打ち込んだ:

1
$ git clone gittorrent://github.com/cjb/foo

そして次のように変わり:

1
$ git clone gittorrent://81e24205d4bac8496d3e13282c90ead5045f09ea/foo

最終的には次のようになった:

1
$ git clone gittorrent://cjb/foo

この時点でGitHubの中心的な機能、Gitレポジトリを探してダウンロードする部分は分散化出来ただろう。

最後に

やるべきことはまだ多い。例えば、GiHubの重要な機能であるissueやプルリクエストは再現出来てない。

issueに関して私が良いと思った解決策はissueをレポジトリのファイルとして保存することである。これにより、ブランチをマージすればコードの変更とissueを両方同時に適用できる。この案を実際に実装したものとしてBugs Everywhereがある。

他にもissueやプルリクエストをSecure Scuttlebuttのように末尾への書き足しのみが許可されてるメッセージストリームを分散ネットワークで同期する技術を使って実現することも考えられる。

とはいえ、ここまで進んだだけで結構うれしい。多くの人の意見を聞くべく、GitTorrentの設計は(皮肉にも)GitHub上に上げてあるので積極的にプルリクエストや改善案を送ってほしい。

ここで何人かの方々にお礼を言いたいと思う。まずは私が使用したBitTorrentのライブラリを開発したFeross Aboukhadijeh。FerossのP2P技術に対する情熱と彼の「マッド・サイエンス」プロジェクトのコミュニティ運用の仕方に惹かれ、このプロジェクトに取り組んで貢献するきっかけを得ることが出来た。

また私がこれにとりかかることが出来たのはニューヨークのRecurse Centerに参加するため仕事を休むことが出来たからだ。これは以前ハッカー・スクールと呼ばれていたが、最近名称を変更した。一つ目の理由は何かを教わる学校という説明はそぐわないからだ。実際はプログラマーが一旦仕事を離れて3ヶ月間プロジェクトにとりかかることで技術力の向上を目指す場であり、私に参加を許可してくれて方々には感謝している。

名称を変更した第二の理由は、世界各国の参加者がアメリカの国境を通る際に「ハッカー・スクールに参加します!」のような発言をし…まああまり良い思いはしなかったようだ。

最後に、なぜこのような取り組みが重要で面白いかについて話したい。GiHubやWikipediaのような大きくて国際的なプロジェクトは国際的な規模のまま存続するために年間数千万ドルもお金を稼ぎ、巨大なデータセンターでディスク容量や帯域を大量に確保する必要があり、儲からないプロジェクトは維持できない。分散化したP2Pアルゴリズムによってそのレベルの投資を必要とせず、ユーザーが協調・共有し合えば野心的なソフトウェアを開発出来るような環境が整えられることを夢見てる。

ご静聴ありがとうございました。

元記事: Announcing GitTorrent: A Decentralized GitHub