Skip to content

Instantly share code, notes, and snippets.

@pixie-grasper
Last active November 30, 2015 07:58
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save pixie-grasper/35a43d0c15d9fe49814b to your computer and use it in GitHub Desktop.
過激なノイズの存在下に於けるPure P2P上の掲示板の構築アイデア

前提

  • Pure P2P
  • 高匿名性
    • ある2つの書き込みが存在する時に、その2つの書き込みの書き込み主が同一人物か否かを判定できないunlinkability性を持つ
    • ある書き込みに対し、その書き込みを行った人物が自分と同一人物であるか否かを判定できないundeniability性を持つ
    • 書き込み時等にIPアドレスが十分少ないノードに知らされる事は許容するものとする。
  • 高攻撃耐性
    • 但し、次の攻撃を考慮し、その他の攻撃は考慮しない
      1. クライアントによる任意の間隔・任意のメッセージの送信
      2. クライアントが受信したメッセージの改竄、不正処理、及び削除
      3. クライアントサイドに保持されるデータの改竄
    • 過半数以上のクライアントが結託する攻撃は考慮しない
    • 考慮されていない攻撃を受けた場合のネットワークの状態は未定義とする。

プロトコル概要

スレッド読み込み時の挙動としては

  1. 0番のデータを分散データベースx(以下DDBx, DDBy等)から取得する。0番のデータには掲示板の各板のデータ番号等が記述されている。
  2. 取得したい板のデータ番号を用いてDDBxから板情報を取得する。板情報には各スレッドのデータ番号等が記述されている。
  3. 取得したいスレッドのデータ番号を用いてDDBxからスレッドを取得する。

となる。一方で、書き込み時の挙動としては

  1. ユーザIDを生成し、認証を済ませておく。
  2. DDBxへ書き込む。
  • スレッドへの書き込みの場合は
    1. 読み込み時と同じ要領でスレッドを入手する。
    2. 書き込みたい内容からスレッドの差分を生成し、DDBxへ書き込む。
  • スレッド生成の場合は
    1. 読み込み時と同じ要領で板を入手する。
    2. 建てたいスレッドの内容から板の差分を生成し、DDBxへ書き込む。

となる。

ユーザIDの生成と認証

ユーザIDは、擬似乱数を使って生成する。サーベントはDDByにそのユーザIDを送り、認証をしてもらう。

認証するDDByの挙動は

  1. 認証される側のIPアドレス等からユーザのダイジェストを計算する。
  2. ダイジェストからユーザIDを引けるなら認証成功と返す。
  3. ユーザIDからダイジェストへのmappingの取得と登録をDDBzへ要求する。もし既に違うダイジェストがユーザIDに紐付けられていた場合、認証失敗と返す。
  4. ダイジェストからユーザIDへのmappingを登録する

となる。

スレッドへの書き込み

書き込みメッセージには、次を含む。

  • スレッドのデータ番号
  • スレッドの差分
  • ユーザID

書き込みを受けるDDBxの挙動は

  1. ユーザのダイジェストを計算し、DDByに問い合わせる。もしもDDByにユーザIDが登録されていなければ書き込みを拒否する。
  2. スレッドへの最近の書き込み情報を取得し、ユーザIDを持つユーザが連続投稿していない事を確かめる。もし最近書き込み過ぎて居るようであれば書き込みを拒否する。
  3. スレッドを取得し、スレッドの差分を使って更新する
  4. スレッドへの最近の書き込み情報を更新する

となる。板に対するスレッド生成時の挙動も、ほぼ同じ。

DDBの動作

各DDBは、冗長度kによる合意によって動作する。ここで冗長度とは「取得」及び「書き込み」を行う際にその要求を行うサーベントが発信するメッセージの数である。 つまり、取得時にはk個のメッセージを発信し、返信されたメッセージのうちk/2個より多くの戻り値が等しい場合にその値を採用するという単純なアルゴリズムである。 DDBzは一度にDDByからのk個の取得/登録要求を受け付けることになるので、もしまだmappingが行われていない場合、k/2個より多くの同一の要求が最初に揃うまでは要求を受理しないという選択をする事が出来、又、攻撃耐性を上げるためにもそうするべきである。 自分自身が保持するアイテムの情報を定期的にDDB上から取得する事によって同期を行うことが出来る。

連投判定

ユーザIDをu(0)、u(i)のダイジェストをu(i+1)とする。又、それらの下位Lbitの値をv(u(i), L)により定義する。 又、「スレッドへの最近の書き込み情報」を2^L要素のビット配列により定義し、Wと置く。又、Wの濃度をdと置く。 W[v(u(i), L)]が0であれば1を代入するという操作を、代入出来るまで繰り返すのにn回掛かったと仮定する。すると、既にr回書き込んだユーザーについて、dの変化が十分小さければ、nは(r+1)/(1-d)で近似できる。今d=1/2で初期化されていると仮定すれば、n≒2r+2, r≒n/2-1となる。この値を使って連続投稿か否かを判定する。 Wは非常に小さい確率で再生成する事。例えば、長さ2^(L-16)の区間をランダムに選び、その区間の値が変更された場合に擬似乱数列で最初期化する、といった具合に。 Wはそのスレッドを担当するサーベント間で共有する必要はない。配列が十分長い期間生存しているならば、幾つかのサーベントが短期的に判定をしくじっても、依然として残り多くのサーベントが連投判定を正しく行えるためである。

終わりに

このドキュメントのライセンスはNYSLとします。 つまり、このドキュメントの内容がどう扱われても構いません。

ぶっちゃけるとデータ圧縮を専門にするへっぽこ大学院生な私がてきとーに頭を捻ったら出てきたようなアイデアなので 抜けがあったり効率が悪かったりするかもしれませんが責任は取れませんということです。 誰か検証and/or実装よろしく。 シミュレート結果とか纏めて論文にしてくれたら喜んで読みます。

コメントや突っ込みなんかは2ch/ム板の「P2P型の完全匿名掲示板はまだ出来ないの?」の現行スレなんかに投げると そのうち誰かが返信くれると思うです。

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment