AChord 1 - ぱせりの秘密の開発日誌

(A Variant of the Chord Lookup Service for Use in Censorship Resistant Peer-to-Peer Publishing Systems)
なげーよｗ

Chordの勉強をしつつChordをさらに改良して匿名性を高めたAChordも見ておこうと思います
元ネタはここです。
http://thalassocracy.org/achord/achord-iptps.html

基本的に英語はさっぱりなんで間違いがあるかもしれませんけど、簡単にまとめてみます
間違ってたらつっこんでいただけるとありがたいです。
　
AChordはChordの匿名性を高めた分散ハッシュで、基本的なところはChordと同じです
ただ、他のノードに対しての情報がChordに比べてかなり制限されてます
基本的なところでChordと違うのはAChordではノードのIDについては
ノード自身が勝手に決められない値を使ってくださいというところでしょうか。
基本的にはIPをIDにするといいそうです。
理由は後述するとして、まずAChordのKeyLookupの仕組みの説明です
　
AChordの場合もChordと同じようにfind_successorという動作を使用します。
これは前のChordの説明で出てきたNext関数と同じ動作と一緒です。
ただChordとAChordで意味的には多少異なるようで
Chordの場合はあるハッシュ値を管理するノードを返すという意味でしたが
AChordの場合は、ハッシュ値に対応する値を返すという風に強調されています。
もちろんこの値がノードのIPであればChordとほぼ同じですが
それは特定の状況下においてのみ取得できるといった感じになってます。
　
手っ取り早くAChordのKeyLoopupに行きたいのだけど、その前にChordのfind_successorの動作について少し復習します。
Chordのfind_successorはあるハッシュ値を管理するノードを返すという動作ですが
これを実装するに当たっては、二つの方式が考えられます。
反復的な方式と再帰的な方式の二つです。
　
反復的方式は検索するノード自らが各ノードに直接find_successorして、その場で結果を受け取り
ハッシュ値を管理するノードにたどり着くまで反復する方法となります。
対して、再帰的動作というのは検索するノードがfind_successorをすると、それを受けたノードが
自らのフィンガーテーブル(ルーティングテーブル)に従って次のノードにfind_successorを行い、
数珠繋ぎ的にハッシュ値を管理するノードまでfind_successorを行います。
そしてその結果はそれぞれのノードがfind_successorをされたノードにのみ返すという手順になります。
　
これは例えばネットワーク上の一部にノードA,B,C,Dが存在したとして
反復的方式がAがBにfind_successorしたらCに聞いてくれよといわれ
AがCにfind_successorしたらDに聞いてとなり、やっとDにfind_successorしてたどり着くといった
たらいまわしっぽい流れだとすれば
再帰的方式ではAがBにfind_successorをしたら、Bが責任をもってCに対してfind_successorを行い、
さらにCがDにfind_successorといった感じになる。そしてDからの結果をCが受け取り、CがBに返し
最後にAにまでたどり着くという流れになります。
　
だいたいここまで来れば、どちらが匿名性が高いかは一目瞭然ですが
AChordの場合では再帰的方式をKeyLoopUpの方式として使っています。
しかもconnect_to_successorという新しい名前までついちゃってます。
反復的方式ではそれぞれのノードのIPがばれてしまうし、
あるハッシュ値を管理するノードのIPもばれてしまう。これでは匿名性は保持できません。
これを再帰的方式にすることによって、経路の途中にあるノードの情報は検索者には知ることはできないし、
逆に途中の経路のノードが検索者を知ることもないです。もちろんハッシュ値を管理するノードでさえも。
　
ちなみにこの辺がややこしいのだけど、AChordでは特定の状況において反復的方式を利用したりもします。
んでは、さっきから言っている「特定の状況下」ってのを簡単に説明します。
　
Chordでは新たにネットワークに参加するノードがいたとして、そのIDをnとすると
find_successor(n)によって今までnというハッシュ値を管理していたノードを検索していました。
このnというハッシュ値を管理しているノードのことをsoccessorといいます。
（なのでfind_successorというのはそーいう意味だったんですね）
　
AChordでも同じようにIDがnであるノードがネットワークに参加する場合にはfind_successorを呼び出すのですが
ここはKeyLookupのときと違ってconnect_to_successorではなくて、find_successorを呼び出します。
つまり再帰じゃなくて反復するんです。
そしたら途中のノードにIPがばれちゃうんじゃないかということなんですが
結論から言うとばれてしまいます^^;もちろん相手のIPもばれちゃいますね。
ばれちゃうノードの数はN個のノードがネットワークにいる場合に最大logN個となっています。
これは完璧な匿名ではないですが、例えばSHA-1のような2^160個のネットワークを想定しますと
たいした問題ではなさそうです。もちろんlogの底はeじゃなくて2です。

このfind_successor反復バージョンなんですが、AChordではその使用に当然制限がかかります。
その制限というのが「find_successor(n)を反復的方式で呼び出せるのはノードのIDがnの場合のみ」です。
なかなかピンとこないかもしれませんが、
これは例えば自分のノードのIDが1234だったら、そのノードが他のノードに対してfind_successor(1234)しかできませんよってことです。
find_successor(5678)とかやったらだめです。
そんなこと言ったって勝手に他のIDで呼び出しちゃう悪意のあるノードもいるかもしれません。
でもずるしたら分かるようになってます。
ここではfind_successorを反復的方式で呼び出すわけですが、反復ということはそれぞれのノードにたらい回し、直接接続することになります。
直接接続することで接続されたノードはfind_successor(1234)を呼び出しているノードのIPが分かりますから
そのIPからハッシュ値を導くことでちゃんと1234か確認できるわけです。
初めに言った「AChordでは各ノードのIDを勝手に決めれない」という制限が実はここで生きてきます。
悪意のあるノードががんばってもIPを自由に決めれない限りは無駄なわけです。
この仕組みによって、たとえばあるファイル「X」のハッシュ値が分かったとしても
find_successor(hash(X))を呼び出せない以上、あるドキュメントを管理するノードを任意のノードが知ることはできなくなります。

AChordについては他にも説明しなきゃいけないところがありますが
今日はこの辺で。