Winny

2022年10月9日 #Winny #P2P

概要

Winny (ウィニー) は Freenet をモデルに実装された P2P ファイル共有のためのアプリケーションまたはネットワークである。匿名性の高さと効率的で高速なキャッシュ機構で日本ユーザのコミュニティで広まり、日本の P2P ファイル共有ブーム、およびそれにまつわる違法コピー行為とハッキング被害の代名詞ともなった。

Winny 作者は Winny を想念的な WinMX の後継であると位置づけて紹介し、最後の文字 MX をアルファベットの並びで一文字進めた NY に置き換えている。Napstar に代表されるハイブリッド P2P 型の第一世代、Gnutella に代表されるピュア P2P 型の第二世代に対して、ピュア P2P + キャッシュ型の Winny を第三世代と位置づけている [1] (より正確にはキャッシュではなくミラーである)。

Winny は 2002 年に匿名掲示板「にちゃんねる」で最初に公開された (この投稿番号の 47 にちなんで作者である金子勇は名が公表されるまで 47 を自称していた)。WinMX のメンテ放棄によって WinMX ネットワークが崩壊し始め、日本では OpenSNAP を模索していたところに Winny が登場した形となり、元々音楽ファイルなどを違法に交換していたアンダーグラウンドユーザの間で急速に普及した。

RC4 暗号の共通鍵が平文で贈られていたため通信の解読は容易だった。Share という航続サービスがある (Perfect Dark も後続?)。

概要
Winny の設計
参考文献

Winny の設計

ファイルの識別と転送

Winny ネットワーク上のファイルはキーと呼ばれる固定長の値によって識別される。キーは式 ( $\ref{key}$ ) に示すようにファイルの内容の単純なハッシュ値である (Winny ではハッシュ関数 ${\rm hash}$ に MD5 を使っている)。 $\begin{equation} x = {\rm hash}(X) \label{key} \end{equation}$

ファイル本体は 64kB のブロックに分割されてそれぞれ暗号化されて転送される。このブロック分割した送信によって転送に失敗したときの再送コストが小さくなり、複数のノードから同時に別の位置のブロックをダウンロードして転送を速めることができる。当時は ADSL 回線が一般的だったことから送信ノードより受信ノードの方が帯域の余裕があったためである。

通信の暗号については、暗号に使用される固定の共通鍵が Winny プログラム内に埋め込まれていたことが明らかになってからは意味がないものになっている。

Winny ネットワーク

Winny ネットワークはより性能の高いノードにキーとファイルのキャッシュが集まるように設計されている。この戦略によってクエリーがネットワークの一部のノードに到達した時点でおおむね目的のファイルの検索を達成できるようになりネットワーク全体の効率を高めている。

ノードの性能は Winny のセットアップ時に回線速度を指定することで行われる。このユーザ指定の回線速度はノード間で接続を確立するときに互いに交換してどちらが上流/下流かを決定する (速度がほぼ同じ場合は TCP 接続を受け付けた側が上流となる)。ただし、ノード間の回線速度差が大きすぎる場合は、より多くの中間速度のノードをネットワークに取り込むために接続は失敗する。

上流のノードには大量のキーとファイルが流入することからストレージ容量の範囲でどんどんとキャシュの入れ替えが進行する。一方で下流のノードは自身が公開しているファイルか収集したファイル程度のデータが保存されることになる。この非対称性によって比較的低性能なノードでもネットワークに参加することができ、上流に向かってクエリーを発行すればネットワーク全体を検索するより遙かに効率的に目的のファイルを検索することができる。

このような特性は、スーパーピアのような明確な役割分担ではないものの、高性能なノードがネットワークでより重要な位置を任せられることから Winny はピュアP2P ではないという批判もある。

Winny ノードがキーの拡散や検索を行うためのノード間接続を検索リンクと呼ぶ。ノードは起動時になるべく近いクラスタの上流 2 ノードと検索リンクの確立を試みる。また各ノードは下流のノードから 5 つまでの検索リンクを受け付けることができる。もし接続先のノードの検索リンクが上限に達していた場合、他の接続先候補の付随する応答で接続が拒否される。

ファイルの公開

あるユーザが Winny ネットワークのノード $A$ でファイル $X$ を公開したと仮定する。このとき、ファイルのキー $x$ とノード $A$ の接続先情報 (IP アドレスとポート番号) のマッピング $x \mapsto A$ が隣接するノードに対して配布される。Winny ネットワークの各ノードは定期的に隣接するノードと自身がキャッシュしているキーの交換を行う。この動作により時間が経過するにつれてネットワーク全体にマッピング $x \mapsto A$ が拡散する。

ここで注目したい動作は、このマッピング情報は中継するノードによって一定の確率で書き換えられて拡散されることである。例えば Fig 2 に示した図ではノード $B$ が ( $x \mapsto A$ のマッピングを記録した上で) $x \mapsto B$ のマッピングに置き換えて拡散している。これは後述する中継の動作を意図としたものである。

拡散されたキーとノードのマッピングには有効期限があり、一定時間が経過すると各ノードのキャッシュから削除される。ファイルの実体を公開しているノードがネットワークから離脱するとそのマッピングを発信するノードもいなくなるため、一定時間経過後にすべてのノードからマッピング/キャッシュも消えて検索から除外される。

ファイルの検索

あるユーザが Winny ネットワーク上のノード $C$ でキー $x$ のファイルを検索したとする。検索クエリーは上流に向かって拡散され、クエリーを受信したノードはキー $x$ のマッピングがキャッシュされていたらそれをクエリーに含めてさらに隣接するノードに拡散する。クエリーの拡散はある程度のところで同じ経路をたどって検索元のノード $C$ に戻る。

クエリーを中継したノードが $x$ のマッピングのキャッシュを保持していなかった場合、クエリーの応答 (復路) に含まれているマッピングを新しくキャッシュする。つまり、キーはノード間の定期的な交換 (パッシブ) あるいは検索 (アクティブ) によって Winny ネットワーク上に拡散される。そして検索においても意図的に一定の確率でマッピングの置き換えが発生する。

Fig 3 の例ではこの検索手順によってユーザが $x$ の問い合わせ先リスト $(A,B)$ を入手したことを示している。また $x$ のマッピングをキャッシュしていないノード $D$ にクエリーの応答に含まれているマッピング $x \mapsto A$ ( $B$ でもかまわない) が新たにキャッシュされている。

ファイルの取得

ファイル共有を目的とする Winny では取得したファイルはノードにキャッシュされ Winny ネットワーク上で公開される。ノード間のファイル転送は暗号化されている。

ファイル $X$ の実体をキャッシュしているノード $A$ からファイルを入手するケースでは、ノード $C$ はノード $A$ と直接接続してファイルをダウンロードする。ダウンロードしたファイルは $C$ 上でキャッシュされ、通常の公開手順と同様に隣接するノードに新しいマッピング情報 $x \mapsto C$ が配布される。

Fig 4. ファイル $X$ をキャッシュしているノードから直接ダウンロードする動作。

キー $x$ のマッピングを置き換えたノード $B$ からファイルを入手するケースでは、ノード $B$ はノード $A$ と接続してファイル $X$ をダウンロードしつつその内容をノード $C$ にも転送し、最終的にファイル $X$ の実体はノード $B$ 上にもキャッシュされてネットワークで公開される。このようなノード $B$ の動作を中継 (relay) と呼ぶ。

Fig 5. ファイル $X$ のキャッシュを持っていないノードが中継してダウンロードする動作。

ノード間の定期的なマッピングの交換時、あるいは検索時に一定の確率でマッピングの置き換えを起こすことによって、頻繁に検索されるファイルが多くのノードにキャッシュされるというネットワーク特性をもたらしている。

中継の参照先がループになることはあるのか? あるならどう防いでいるのか?

この中継の動作によって、Winny ネットワークではあるノード $A$ から目的のファイル $X$ をダウンロードできたとしても、そのノードがファイルを公開した一次発信者のノードなのか、たまたまそのファイルをキャッシュしていただけのノードなのかを区別することが困難である。同様に、収集目的でのダウンロードなのかキャッシュ目的でのダウンロードなのかを区別することも難しい。このため Winny は (ネットワーク全体を監視している集権的な管理機構が存在しない限り) 秘匿性の高いネットワークと言われている。

クラスタリング

嗜好が似ているノードは、一方が収集したファイルを他方も収集する傾向にあるためネットワーク上で近くに配置するのが効率的である。Winny では自動ダウンロード機能で設定するキーワードを嗜好のクラスタリングに使用する。検索クエリーを送信するときに既知のノードの中でキーワードの似ているノードを選択することで目的のファイルに到達するまでのホップ数を削減することが期待できる。また再接続時にキーワードの似たノードと接続することでネットワークが次第に適切なクラスタで構成される傾向を持つ。

参考文献

金子勇 (2005), Winny の技術, アスキー