Freenetでは、どうやって匿名性を確保しているの?

 今日はFreenetの話です。な、なぜいきなり…。なんとなく。一足早い夏休みのじゆうけんきゅうです。

おしながき

 Freenetは、ピュアなP2Pによる、匿名通信を実現するソフトです。WinnyやShareなどよりも遥かに匿名性が高く、Wikipedia曰くあの中国ですら追跡はできないらしいです†1

 で、今回公式サイトに転がってるオリジナル論文を読んだので、論文に書いてあった事とか、論文だけでは分からなかったので実装を直接触って調べた話を書いておきます。

Freenetのコミュニケーションの基本単位は「メッセージ」

 Freenetの基本的なイメージは、ネット上にたくさんの「ノード」と呼ばれるコンピュータがあって、それぞれが他のいくつかのノードと繋がっており、全体として大きな網目状のネットワークになっている、というものです。

20100526_01.png

 これらの中では、ノード同士が「メッセージ」をバケツリレー式にやり取りすることでコミュニケーションしています。TCP/IPとかのパケット通信と似てます。

 「メッセージ」には検索や追加など、いくつか種類があるのですが、どのメッセージも必ず次の属性は持っています。

  • メッセージを区別するユニークなID
  • メッセージの送信先
  • メッセージの送信元
  • HTL(Hops to Live)

 最後のHTLは、IPのTTLと大体同じです。メッセージがノードを通過するたびに一つずつ減っていき、0になった時点でメッセージが破棄され、破棄したノードは「失敗したよ」というメッセージを送信元に送り返します。論文だとTTLと表現されているのですが、実装ではHTLとなっているのでこちらで統一します。

基本的には「多段串」とかと同じ感じ

 匿名性の基本原理は、いわゆる「多段串」とあまり変わらないようです。

 この図において、AさんはCさんが送信したメッセージを、Bさんを経由して受信しています。BさんはAさんに、Bさん自身のアドレスしか教えておらず、送信者がCさんなのか、実はBさんとつながった別のノード、Dさんなのかは教えません。

20100526_02.png

 さらに言えば、BさんはCさんがオリジナル送信者なのかも知りません。実は、CさんもBさんと同じように、他の誰か、例えばEさんのメッセージを転送してるだけなのか、Bさんには分かりません。

 これを何回も繰り返すことで誰がオリジナルの送信者なのかどんどん分かりづらくなっていく、というわけです。

隣のノードへ対してはどうやって発信者を隠すの?

 私が疑問に思ったのは、自分のすぐ隣のノードには、自分がオリジナル発信者であるメッセージはわかってしまうのでは、ってことです。もしHTLの初期値が固定なら、隣のノードが、私から発信されたHTL=初期値のメッセージを受け取った場合、そのメッセージは間違いなく私がオリジナル発信者†2であるとバレてしまう可能性があると思います。

20100526_03.png

 この図で、BさんはCさんからHTL=18のメッセージを受け取っていますが、これはFreenetのデフォルトのHTL初期値と同じです。と、言う事は、このメッセージはまだ一度もHTLが減っていないメッセージなので、Cさんがオリジナル送信者であると推測できてしまうのでは無いでしょうか…?もちろん設定は変えられるので、必ずしもCさんがオリジナル送信者であるとは言い切れませんが、その可能性は高いと言えてしまいそうです。

 これは元の論文には何も書いていなかったので、実際にソースコードを読んで調べてみました。

とりあえず読む

 まず、HTLの初期値はどこで決定されるのでしょうか。freenet/node/Node.java内のこちらです。

        maxHTL = nodeConfig.getShort("maxHTL");

 設定値で固定です。…やはり、私の指摘したような問題が起こるのでしょうか?

 HTLを減らしているのは、同じソース内の、

    public short decrementHTL(PeerNode source, short htl) {
        if(source != null)
            return source.decrementHTL(htl);
        // Otherwise...
        if(htl >= maxHTL) htl = maxHTL;
        if(htl <= 0) {
            return 0;
        }
        if(htl == maxHTL) {
            if(decrementAtMax || disableProbabilisticHTLs) htl--;
            return htl;
        }
        if(htl == 1) {
            if(decrementAtMin || disableProbabilisticHTLs) htl--;
            return htl;
        }
        return --htl;
    }

 このメソッド。自分がオリジナル送信者の時はsource==null、転送するメッセージの場合はsource != nullみたいです。

 自分がオリジナル送信者のとき、source==nullなので処理は移譲されずこのメソッドが最後まで実行されます。decrementAtMaxがtrueな時に予めHTLがひとつ減らされる処理が入っているようです(自分が送信者なので、HTL=maxです)。これは、自分がオリジナル送信者であるメッセージについて、HTLを一つあらかじめ減らしておくことで「いえ、これは他の誰かから転送したメッセージですよ」と言っている事になります。

 ただし、このdecrementAtMaxはFreenetの起動時に決定されるパラメータ†3で、それ以降変更がないので、これだけではあまり十分であるとは言えないように思います。もしこれがFalseになった場合、やはり自分がオリジナル送信者であるメッセージだけ、HTL=最大(初期値)のメッセージを送る事になってしまうのでは?

 そこで、source != nullの時の移譲先を見てみましょう。freenet/Node/PeerNode.javaにあります。

    /**
    * Decrement the HTL (or not), in accordance with our
    * probabilistic HTL rules.
    * @param htl The old HTL.
    * @return The new HTL.
    */
    public short decrementHTL(short htl) {
        short max = node.maxHTL();
        if(htl > max)
            htl = max;
        if(htl <= 0)
            return 0;
        if(htl == max) {
            if(decrementHTLAtMaximum || node.disableProbabilisticHTLs)
                htl--;
            return htl;
        }
        if(htl == 1) {
            if(decrementHTLAtMinimum || node.disableProbabilisticHTLs)
                htl--;
            return htl;
        }
        htl--;
        return htl;
    }

 びっくりするくらい同じコードでした†4。このコードでは、隣のノードから受信したメッセージにおいても、HTLが最大(初期値)だったときに、HTLを減らさずに送る事がある事を示しています。つまり、隣のノードから来たHTL=最大(≒隣のノードがオリジナル送信者である可能性がある)のメッセージについて、HTLを最大値のままにしておくことで「いえ、これは私がオリジナル送信者なんです!」と言ってることになります。また、このパラメータは接続先ノードごとに設定しなおされるため、十分に掻き乱されると考えられます。

 このふたつが組み合わさることで、HTL=最大のメッセージを受け取った場合でも、そのノードがオリジナル送信者かどうか、もはやわからなくなります。他の誰かのメッセージをHTLを減らさずに転送したものかもしれないし、自分のかもしれないし、ということですね。

 さらに、隣のノードもそのように詐称するので、HTL=最大のメッセージを送ってきたノードがオリジナル送信者かかどうかはもちろん、直接隣接するノードかすらも分かりません†5。十分そうですね。

まとめ

 Freenet上では「メッセージ」をやり取りすることで情報が交換される。各メッセージはHTLという、IPのTTLに似たパラメータを持つが、オリジナル送信者の匿名性を守るため、最大HTLのメッセージについてはランダムで減らしたり減らされなかったりする。

まだ残る謎

 htl=1(メッセージが破棄される瀬戸際)のときにもランダムで減らしたり減らさなかったりしてるみたいですが、なぜ…??

どっちかっていうと鍵探索の方が技術的には面白いかも

 今回は論文を読んでいて疑問に思ったのが匿名性の部分だったのでそちらを書きましたが、論文全体を読んだ印象としては、どうやって中央サーバのないP2P上で検索するための「キー」とそれに対応した「情報」を結びつけ、検索させるのか、の方が技術的に面白いな、と思いました(小学生レベルの感想)。

その他

  • System.err.print()を使うとrun.sh consoleで起動したときのログで表示されるよ。
  • †1: 公式サイトの言語が中国語、フランス語、スペイン語なのがなんとなく印象的…
  • †2: 誰かのを転送したわけではないってこと
  • †3: maxHTLの設定を読み込む次の行でrandを使って決定されています
  • †4: でもちょこっとだけ変数名違う…。
  • †5: そのノードも詐称してるかもしれないからです

さきゅばす 2.0β1を公開しました。

 先日のニコニコ超会議でお話した「さきゅばす2」ですが、やっと一般公開するための作業が終了したので公開します。

 DLはさきゅばす公式サイトから

大きく変わったフィーチャーをご紹介

ニワン語へ一部対応しました。

 ニコニコ動画内で使える謎の言語ニワン語に対応しました。対応命令はまだ限られていますが、ニコニコ超会議でもご紹介したProjectNivaや、Nicocococococo!などの動作は確認しております。

正式に投稿者コメントに対応しました。

 上記の変更に合わせ、投稿者コメントにも対応しました。

フルスクラッチで書き直し、Javaのインストールが不要になりました。

 従来のJavaとCを廃止し、すべてをC++とPythonで開発しなおしました。このため、従来必要だったJavaのインストールが不要になっています。(配布サイズが絶望的ですが…)。

動画の変換設定やNGの設定が非常に柔軟になりました。

 Pythonスクリプトで記述するようになったため、非常に複雑なルールも記述できるようになりました。ng-scriptフォルダやrecipeフォルダのサンプルをご覧ください。

フレームレートの低い動画でもスムーズに変換できるようになりました。

 元の動画のFPSが極端に低い(1FPSとか)場合、従来のさきゅばすではそのFPSに合わせてでしか変換できず、カクカクになってしまいましたが、今回書きなおしたため、任意のFPS(デフォルトで25FPS以上)で変換されるようになりました。上記のNicocococococo!でもこの機能が使われています。

変換する動画を一度に指定してしておけるようになりました。

 もうauto.batはいりません。複数の動画IDを登録しておけば、勝手に最後まで変換してくれます。

ありそうでなさそうでやっぱりありそうな質問と答え

使い方は?

 やっつけですが一応使い方を書いておきましたので参考にしてください。サポートは2chのスレでお願いします。

「***」っていう動画が変換できないんだけど…

 バグの投稿はこちらで受け付けています(匿名でできます)。Blogとかメールとか2chに投稿していただいても大丈夫ですが、たぶんこっちに登録した方が早く対処されると思います(他のチャンネルまで目を通しきれてないです、すいません…) その時は__download__内のログの内容とか教えてください(ユーザーIDやパスワードとかは消しておいてね!)。

なんか「変換エラー」が出るんだけど…

 __download__フォルダの中身を全部消してみてね。

ニコニコ動画がアップデートして動画がDLできなくなったんだけど…

 上記でも報告を受け付けてますが、Pythonに詳しい場合はext\SaccubusFront内のスクリプトを書き換えても対処できます。対処したらパッチにしてぜひ投稿してくださいね!

「***」っていう機能ないの?

 バグと同じところで受け付けてます。でもせっかくだから一緒に開発しましょう!! もちろん新機能パッチの投稿もウェルカムです†1

なんかアンチウイルスソフトが反応するんだけど

 「『ffmpegを起動する』バッチファイルを生成して起動」する、という二段構えの形式のため、反応するようです。「さきゅばす」が信用できると思う場合は切ってから実行してみてください。

というわけで私はしばらくこもる

 他にやらなきゃいけない事があるのに随分これに時間を費やしちゃったので、バグとかあってもしばらく対応できません。すいません。その時は2chで配ってる旧バージョン使ってね!!!

  • †1: 私の独断でリファクタの可能性や激しい変更の場合は一時保留の可能性もあります、ご了承下さい…。