無印吉澤（※新エントリはhatenablogに掲載中）

■[年表][P2P]年表ウェブ：位置に依存しないID / IDと署名

※年表ウェブ：年表データのポータビリティ（2005/06/24）の続きです。

前回は「年表データにはポータビリティが必要だ」という話をしましたが、そのためには年表データそのもの、特にそのID（識別子）が位置非依存である必要があります。つまり、年表ウェブを固定サーバのみで運用するとしても、WWWと違ってURLが使えない、ということです。

そこで、今回はそのような要求を満たすIDの設計案と、IDにまつわるその他の問題について考えてみます。

■ データ構造とID

年表ウェブについて書いた最初の日記（2005/05/24）では、年表ウェブのデータ構造を、以下のような簡単な図式で示しました。

（クリックして拡大）

年表ウェブを実現するのにどんなIDが必要かは、これを具体的にどういうデータ構造で表現するかに依存します。ここでは、以下の図のような単純なデータ構造を考えます*1。

（クリックして拡大）

この場合、必要になるIDは下の3つです。

• 人ID（Person ID、以下P-ID）
• 年表ID（Chronology ID、以下C-ID）
• 出来事ID（Event ID、以下E-ID）

それぞれが、リレーショナルデータベースの主キー（primary key）相当のものだと思ってください。これらのIDが世界的に一意なら、年表データのポータビリティが実現されます。そのようなID決定方法として有名なのは、P2PフレームワークのJXTAでも採用されているUUIDです*2。

Insider's Computer Dictionary [GUID](＠IT)
http://www.atmarkit.co.jp/icd/root/52/94084052.html

A UUID URN Namespace(draft-mealling-uuid-urn-05)
http://www.ietf.org/internet-drafts/draft-mealling-uuid-urn-05.txt

また、P-IDは通常ユーザ当たり1つしか必要ないため、（年表データの位置には関係しないという前提で）メールアドレスのようなURIを利用するという方法も考えられます。

ここまでが、年表データとそのIDに関する基本的な話で、ポータビリティを確保するだけなら一応これだけでOKだと思います。

■ IDの重複、データの偽造を電子署名で防止

ただ、IDの重複やデータの偽造に対処しようと思うと、もう少し機能が必要になります。

IDの重複というのは、他のID……例えばIPアドレスでも起こりうる話ですけど、この場合はUUIDのようなものを使うと、IDが重複しても「こちらの利用が正当、そちらは不正」と言い切れないのが問題です。

一方、データの偽造は「他人の作ったイヤな年表データが自分の名前で公開」されたときに問題になるため、これは「年表データや出来事データに含まれる作者のP-IDを偽造できる」と問題がある、と言い換えられます。

で、これらの問題を簡単に解決するには、

• C-IDとE-IDに、必ず作者のP-IDを前置する
• 人、年表、出来事それぞれのデータに電子署名を付ける

として、IDの重複＝P-IDの偽造と言い切る、という方法が考えられます（下図参照）。

（クリックして拡大）

まぁ、「簡単に」と言ってもあくまで理屈の上では簡単、というだけのことで。実際にこういう方法を取るとなるとユーザ側での鍵管理が面倒になるので、それもまた問題なんですけどね……。

■ 電子署名で気になる点

しかしこの方法では、鍵管理が面倒という以外にも2つ気になる点があります。

1つ目は、P-IDと公開鍵の対応関係が「正しい」ことを証明する方法です。例えば、P-IDと公開鍵証明書を発行する機関が別れていると、任意のP-IDに対応する正当な公開鍵証明書を誰でも取得できてしまいます（下図）。

（クリックして拡大）

C/S型CertifierではP-IDと公開鍵証明書を同じ機関が発行する、という対策が可能です。しかしP2P型Certifierではそれも難しいので、何かうまい解決策が必要になりそうです。

そして2つ目は、公開鍵証明者の発行者の変更、つまりCertifier間のポータビリティを実現する方法です。通常の証明書利用ではこのような権限委譲は考えられていないので、何か対策が必要になります。

例えば、ユーザが既に新しいCeritifierに乗り換えていたとしても、前のCertifierがCRL（Certificate Revocation List；証明書失効リスト）を発行すると、その公開鍵は全く使えなくなってしまいます。まぁ、Certifierを変えるぐらいなら、鍵も変えて、署名し直したデータを再度流通させろという話かもしれませんけど……。

----

さて、ここまで長々と机上の空論を書いてきたわけですけど、現時点で僕が描いているイメージはここまでで一通り書き終えました。あとは、実際に動く形にしてみないと、どういう効果や、課題があるかは良く分からなそうです。

そこで、ひとまず年表ウェブ関連の連載日記はここまでということにして、あとは暇を見てプロトタイプを実装してみます。いつ出来るかはわかりませんけど、他に作ってくれそうな人もいないしなぁ……まぁ、気長にお待ち頂ければ幸いです。

■[P2P][Wiki]P2PWiki

P2PWiki
http://p2pwiki.ikejisoft.com/?FrontPage

SkypeやろうぜのIkejiさんが立てた、P2P関連の情報をまとめるWikiです。

この間のDHTオフ会のときに構想はちらっと聞いていたんですけど、さすがに早いですね。当人曰く、理想としては

• P2P用語解説
• P2Pのアルゴリズム解説
• P2Pニュース

と3本柱を備えたP2Pまとめサイトを作りたい、とのこと。OS関係でそういうサイトがあるらしくて、それのP2P版を狙ってるとか言ってたんですけど……そのサイトの名前は忘れちゃいました。ごめんなさい。

まあ、そういうわけで、何かネタがあったらヘルプを見ながらじゃんじゃん書いていきましょう。

■[P2P]P2P Baton（残り4本）

ついでに、そんなP2PWikiの宣伝企画として（？）、IkejiさんからP2P batonなんてのが回ってきました。

P2PBaton
http://ikejisoft.com/?%BF%EC%B5%AD%2F2005-07-01%2FP2PBaton

特にネタもないんですけど……一応答えてみます。

■ 今、コンピュータに入っているP2Pソフトウエアの数、また、そのリスト

• Alpha2（RinGOch）
• Ariel AirOne Pro
• P2P地震情報
• Skype
• Indy

つい最近OSを再インストールしてしまったので、余計なソフトがほとんど入ってないんですよねえ……。Indyは、Ikejiさんにおすすめされてインストールだけしてみたんですけど、なんかちゃんと動いてません。なんで？

■ 今、起動しているP2Pソフト

• Skype

MSN Messengerも同時起動。IM機能だけ比べると、相手が文字を入力中だというのが分かるMSN meggengerの方がやっぱり少し便利なので、ほとんど会話とカンファレンスにしか使ってません。やっぱり、Skypeの楽しさの95%以上はカンファレンスですよ。

■ 最後にインストールしたP2Pソフト

• P2P地震情報

揺れてもあまり気にしない方なので、たまに思い出した時だけ起動してます。

■ よく使う、または特別な思い入れのある5ソフト

WinMX
大学院のとき、後輩がP2Pの研究をやり出したいと言い出して、紹介してくれたのがこのソフトです。最初は、Web上で大っぴらに出来ないことを隠れてこっそりやってるだけだと思ってたのですが、実際に使ってみて、その桁外れのファイル数にびっくり。お前ら一体何やってるんだ、と。

それが、P2P関係の技術に興味を持ったきっかけでしたね。だから僕、実はNapstar使ったことないんです。OpenNapなら知ってるんですけど。

JXTA
ソフトじゃないんですけど……研究に使ってたから思い入れがあるので。仕組み自体は割と良くできてると思うんですけど、その上で動くキラーアプリが出ないおかげで、未だに一部でしか知られていないみたいですね。むしろ最近は、JXTAよりもSkypeの方が汎用的なP2Pフレームワーク（インフラ？）になりそうだし_|￣|○

Winny
Gnutella型のネットワーク（Pure P2Pとか呼ばれるもの）でも大規模かつ実用的なファイル交換が可能だということを知らしめたソフト。47氏がどんなことを考えてWinnyを作ったかはともかく、実際に違法なファイル交換をしている人間は野放しのままで、彼が逮捕されたことは未だに納得できずにいます。

そういや、「Winnyの技術」って本が出るって話はどうなったんですかねえ。

Alpha2（RinGOch）
機能の詰め込みまくりに感動。ちょうど僕が社会人になって少し荒んでいた頃に出会ったので、とにかく開発メンバの若さが身に染みた、という印象が強いです（おじさんは付いていけないよ……）。仕組みは未だによくわかってません。ごめんなさい。

ある時期から荒らしが酷くなってしまいましたけど、最近久しぶりに2.02.07へバージョンアップしてました。若さでファイト！（テキトーな応援）

Skype
最後はこれ。「P2P技術をいくら極めても商売にはならない」というのが僕の持論だったんですけど、そんな先入観をあっさり打ち砕いてくれたソフトです。P2P技術でサービス提供のコストを下げて、社員数も減らして、従業員一人当たりの売上高（Revenue per Employee）で勝負するなんて、全然思い付きませんでしたよ……。

技術的な部分は、聞けばなんとなく「そんなもんだろうなぁ」という感じですけど、こういうビジネスモデルの転換を最初にやったのは、やっぱりすごいですね。

■ バトンを渡す5人

うーん。しかし、これほど他人に渡しにくいバトンも無いなぁ。P2Pソフトって言ってもそんなに数多くないから、どんどんネタが被っていっちゃいそうだし……。

適当な人が思い付かないので、誰か、サイトを更新するネタに困っている人は僕のところまでバトンを取りに来てください（残り5本）。もし万が一、6人目の人が来るようなことがあったら、その時は最後の人のバトンを半分に切ってお渡しします。

----

（2005/07/10追記）
昨日開催された 第２回オーバレイネットワーク研究会（リンク先はmixi内）で、SilphiumのAkiさんにP2P batonを1本渡してきました。それでは、よろしくお願いします（笑）

■[P2P]Free SkypeOut Days / 初SkypeOut

最近（主にあまりメジャーでない）VoIPソフトウェアの宣伝として、PSTN（公衆電話交換網）への通話を一時的に無料にするキャンペーンをよく見かけますが、とうとうSkypeまでその手のキャンペーンを始めたようです。その名も「Free SkypeOut Days」。

Free SkypeOut Days
http://www.skype.com/campaigns/freeskypedays/

On Free SkypeOut Days you’ll be able to redeem 10 minutes of credit for SkypeOut calls and it won’t cost you a thing.

要するに、7月中はこれから毎週いずれかの日が「10分間相当のSkypeOut Creditをタダで配布してくれる日」になるそうです。で、今更ですけど、昨日（7月11日）がその最初のFree SkypeOut Dayでした。あと3回あるそうなので、どの日がFree SkypeOut Dayになるかはshare.skype.comをチェック、そして具体的な入手方法はHKさんのサイトをご参照下さい（↓）。

Free SkypeOut Day 1(HK's Page)
http://hkspage.livedoor.biz/archives/27753446.html

さて。

Skypeサイトの混雑にも負けず、僕も無事にSkypeOut Creditを入手できたので、今まで試したくても試せなかったSkypeOutを初めて試してみました。とりあえずSkypeに興味のありそうな友達の中で、一番暇そうな某ニュースサイトの人の携帯電話にSkypeしてみることに。

……まず、発呼する（ぷるるるーとか鳴る）までに10秒くらいかかります。課金管理のやり取りに時間がかかってるんでしょうか。

で、しばらくして繋がったんですけど、ダメですねこりゃあ……。ちょうどFree SkypeOut Dayの影響で混み合ってるときだったのかもしれませんけど、音質があまりよくない上に、遅延が2秒くらいあって、お互いに「もしもーし、もしもーし」とか言ってる間にSkypeOut Creditが無くなって回線を切られちゃいました。

履歴を見ると、通話時間は1分6秒。Skype Global Rate（0.017ユーロ/分）なら10分話せるところなのですが、日本の携帯電話はSkypeOut Ratesを見ると0.125ユーロ/分（7月12日現在）なので、こんなものでしょうか*1。

まあ、日本にはまだSkypeOutのゲートウェイがないので、これが限界なのかも。今後に期待します。

■[ネットワーク][P2P]Small WorldとScale Freeって結局どっちがいいの？

最近、SNS等との絡みでネットワーク構造に関する本が流行っていて、僕も今までに何冊か読んでみました。

• 新ネットワーク思考（Scale Free Networkを提唱したバラバシの著書）
• スモールワールド・ネットワーク（Small World Networkを提唱したワッツの著書）
• SYNC（ワッツの共同研究者のストロガッツの著書）
• 人脈づくりの科学（主にソーシャルキャピタルを扱った和書）

それで、Small World NetworkやScale Free Networkのモデルが、社会、自然界、インターネット等で見られる実世界のネットワークをうまく説明できるというのはなんとなく分かったんですけど……ただ、コンピュータネットワークに関わる人間にとってこれがどういう意味を持つのかは、ほとんど飲み込めないままでした。

ただ、最近DHTオフ会で小島氏の講演*1を聞いてから、そのあたりのモヤモヤした部分がなんとなく整理できそうな気がしています。とはいえ、まだ完全には飲み込めてなくて、この日記を書くのにも1週間以上かかっちゃってるんですが、とりあえず現時点での僕の理解を少しまとめてみます。

■ スモールワールド現象（Small World Phenomenon）

イベント等で会った初対面の人と話してみると、実は自分と共通の知り合いが居たりする。そういう「世間は狭いなあ！（It's a small world!）」と言いたくなる実世界の友人・知人関係を、社会学の世界ではスモールワールド現象と呼んでいます。この現象に対する疑問点は、以下のQ1のように言い換えられます。

Q1. 知人関係にある任意のXとYは、共通の知人Zを持つか？

これは、人間関係のネットワークがどういう形をしているか、という疑問でもあります。

一方、スモールワールド現象と呼ばれるもので更に有名なものとしては、社会心理学者スタンレー・ミルグラムによる「小さな世界」実験から推測された「人はすべての人と平均5.5人を介して繋がっている（Six Degrees of Separation）」という現象があります*2。

この平均値はあくまで知人からその知人へ、そしてまた次の知人へ……と手紙を転送していって「最後まで届けることのできた手紙」の辿った人数の平均値なので、最後まで届かなかった手紙を考慮に入れればもっと平均値は大きくなると思われます。また、人間にはネットワーク全体の構造が分からないため、「最後まで届けることのできた手紙」についてもそれが最短の経路を通ったかどうかは分からない、という意見もあるようです。

ただ、それを考慮しても、この実験は全く関係のない人同士が（人類の総人口と比較して）かなり少ない人数を介して繋がっている可能性を示しています。この現象に対する疑問点は、以下のQ2のように言い換えられます。

Q2. 知り合いでない任意のXとYは、他人を通して繋がっているのか？　またその仲介数は？

任意のノードXからノードYに辿り着くまでに経由しなくてはならないリンクの平均数は、そのネットワークの直径（Diameter）と呼ばれます。従って、上記のミルグラムの実験結果は、社会的なネットワークの直径が人類の総数（全ノード数）と比較して極端に小さいことを示している、と言い換えられます。直径の小さいネットワークは、1つのノードから全体へ効果的にアクセスできるネットワークです。

実世界のネットワークは、Random Networkでもないのに何故直径が小さくなるのか？　それを説明できるモデルとして登場したのが、Small World NetworkとScale Free Networkです。

■ Small World Networkのモデル

これは、ノードが密接に結びついたクラスタ（high clustered）と、それぞれのクラスタを繋ぐ少数のリンク（shortcut links）があれば、ネットワーク直径が小さくなる（low diameter）というモデルです。

high clustered + shortcut links -> low diameter

このモデルでは、ノードがどれくらい密接に結びついているかをクラスタリング係数で示します。クラスタリング係数は、ネットワーク上の任意のノードにリンクされたノード2つを選択したときに、その2つのノード間にリンクが存在する可能性を示す値（Q1を数値化したもの）です。要するに、この値が大きいほど、知り合いの知り合いが知り合いである可能性が高いわけです。

一方、クラスタを繋ぐ少数のリンクがどれくらい効果的かなものかは、単純に数値化できません（違ってたらすみません……）。従って、クラスタリング係数とネットワーク直径を計算することで、そのネットワークのSmall World性を調べることができます。

■ Scale Free Networkのモデル

これは、非常に多くのリンクを持つ少数のハブ（hub node）が存在することで、ネットワーク直径が短くなる（low diameter）というモデルです。

hub node -> low diameter

Scale Free Networkはリンク数xと、x個のリンクを持つノードの数yの関係が、べき乗則（Power Law）に従うという特徴を持っています。従って、各ノードのリンク数の分布（次数分布）を調べることで、そのネットワークのScale Free性を調べることができます。

Small World Networkのモデルとは異なり、こちらのモデルにはクラスタという概念はなく、Q1については何も答えていません。

■ で、どっちがいいの？

ネットワーク構造だけを単純に見てみると、コンピュータネットワーク（やそのオーバレイネットワーク）の構造としてはScale Free NetworkよりもSmall World Networkの方が優れていそうに見えます。どちらの構造にしてもネットワークの小直径性という効果が得られるなら、アクセスが極端に集中してボトルネックになりそうなノード（＝ハブ）をわざわざ作る必要なんて無いのでは？という理屈です（Scale Free Networkのアタック脆弱性）。

かといって、そのコンピュータネットワーク上でデータの送受信を行うことを考えると、Small World Networkでは経路制御の仕組みが複雑になりそうな気がします（Random Networkよりはだいぶましだと思いますけど）。

ノードはSmall World Network全体の構造を知り得ないために、データを運ぶ際にショートカットを利用できず、結果としてそのステップ数がネットワーク直径を大幅に超えてしまう……なんてことが起きても何も不思議ではありません。一方、Scale Free Networkならばハブがルーティングテーブルを管理して、それ以外のノードは経路制御に関与しないという解決方法が取れそうです（例：インターネット上のルータとエンドノードの関係）。

そう考えていくと、結局のところコンピュータネットワークはSmall World Networkであるべきなのか、Scale Free Networkであるべきなのかが、よく分からなくなってきます。もちろん、実際のネットワークは二者択一でどちらか一方のモデルのみに従う、というものでは無いと思いますけど……そう結論づけてしまうのも、あまりにも実入りがなさすぎてイヤな感じです。

■ Kleinbergの問題

上記の疑問のうち、Small World Networkでの経路制御問題について疑問を投げかけたのが、2000年に発表されたJon Kleinbergの論文"The small-world phenomenon: An algorithmic perspective"です。

この研究、僕は小島氏の講演を聞いて初めて実質的な意味が分かったのですが、実際に論文を読んでみても割と参考になることが書かれています。で、この研究の先に、Small World Networkの考え方を導入したDHTであるSymphonyや、Gnutellaよりも性能の良いP2P検索エンジンを目指したTellaGateがあるわけなのですが、ここまでが少し長くなりすぎてしまったので、続きは次回にまとめてみます。

（続く）