« [P2P]分散ハッシュの匿名性について(回答編) | トップページ | [GRID]ゴールドバッハ予想 »

2004.05.08

[P2P]分散ハッシュの匿名性について(回答編その2)

昨日の回答に対して質問があったので、それについて御回答させて頂きます。

Fw◆GOZl+HH8q/gOQw氏の質問:

>Chordにおいてハッシュ空間が2^4=16の場合について考えます。
>tomo氏のページに習い、以下ではNode_ID=0のノードをノード0と示します。
>以下では、ノード0があるurlのリクエストを受けた場合について考えます。
中略:
>3:hash(url)=6 宛ての場合
>この場合も上と同様に考えると、まずノード1~5と9~15はリクエスト送信元では
>ないことが分かります。すると、ノード0への接続経路として考えられるのは
>「8→0→4→6」、「7→(15が不在)→0→4→6」のように、リクエスト
>送信元のノードがプロキシを介さず(多段中継なしで)ノード0に直接接続して
>いることが確定します。従って、ノード0には現在自分と接続しているノードが
>リクエスト送信元であることが分かってしまいます。接続してきたノードの
>IPアドレスを調べることは可能なので、匿名性が失われます。
>このように、Chordの中継を利用した多段プロキシでは匿名性が保証されない場合が
>あるように思うのですが、いかがでしょうか?

まず、ノード1~5についてはリクエスト送信元でないのは自明です。ただし、参加しているノードの一部がネットワークから離脱しているのにノードのルーティングテーブルに残っている場合、ルーティングテーブルに参加している他のノードに検索を依頼する場合もありますので、「非常に」レアなケースですが完全には否定できないかもしれません。

ノード9~15については、この場合ルーティングテーブルで丁度ハッシュ空間を1/2にするところ(つまりルーティングテーブルで一番遠くのノード)にジャンプ(すなわちノード1~5)すると思われるのでノード0には接続しないでしょう。ノード0はノード1~5に少なくとも一つノードが存在するかどうか自分のルーティングテーブルから推測できます。
このような事を踏まえるとノード0に接続しているノードが直接接続していることが推測できます。もちろん先ほど述べたような準安定状態ではこれが完全には肯定できないかもしれませんが。(あるノードが例えばノード1と回線の混雑等で上手く通信できない場合など)

一般的な非常に大きな空間で多数のノードが存在する場合でも通常のChordでは直接接続が推論できる場合があるでしょう。Pastryも同様です。

CANではこのような推測は難しいと思われます。(CANは単なるN次元空間ではなく、N次元空間の「トーラス」なので、ご指摘の四隅のノードが匿名性が低いと言う事はないでしょう。)

このような中間のノードによって要求元ノードに対する推測を回避するには各ノードが次にジャンプするノード(すなわちルーティングテーブルに含まれるノード)をある程度ランダムで決定すれば良さそうです。つまりいきなりルーティングテーブル内で一番最適なノードに飛ばすのではない可能性を作るのです。この方法はChordでもPastryでも有効です。もちろん、匿名性が高まった分だけ検索スピードは犠牲になります。

最初にこのシステムを考えた時には、はっきり言ってURLにアクセスする最後のノードから要求元を推測できるかどうかしか考えていませんでした。このような中間プロキシにおける匿名性に対する指摘を受けた事は大変ありがたいと思います。

|

« [P2P]分散ハッシュの匿名性について(回答編) | トップページ | [GRID]ゴールドバッハ予想 »

P2P」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/18781/560096

この記事へのトラックバック一覧です: [P2P]分散ハッシュの匿名性について(回答編その2):

« [P2P]分散ハッシュの匿名性について(回答編) | トップページ | [GRID]ゴールドバッハ予想 »