P2Pジャンケン解いてみた

P2Pジャンケンは分解すると、以下の3つのフェーズに切れます。

1. ジャンケングループの形成
2. ジャンケン
3. 勝敗の確認

1.では、ジャンケンをするメンバを集めて、確定します。きっかけを作る人をジャンケンリーダと呼ぶことにします。ジャンケンメンバを集める方法は不問とします。メンバの確定ですが、これは、paxos（分散合意アルゴリズム）を使うことでできます。ジャンケンリーダがpaxosにおけるリーダとして機能します。

2.で、実際にジャンケンをしますが、開始のかけ声は誰がかけてもよく、かけ声の合意をpaxosで行います。かけ声の合意のあと、メンバはそれぞれジャンケンの手を決めます。ジャンケンの手は決定後、逆算されないようノイズとなるデータを足してhash値を計算し、そのhash値とノイズデータのhash値の2つをメンバと共有します。その後、手が出そろったことをpaxosを使って合意します。

3.で勝敗の確認をします。このときに実際の手とノイズデータをメンバ内で共有します。手を変えていないことはすでに共有しているhash値で確認できます。

以上、まとめると次のようになります。

1. ジャンケングループの形成
   • ジャンケンの発議（発議者がジャンケンリーダとなる）
   • ジャンケンメンバを募集（方法は不問）
   • ジャンケンメンバの確定（ジャンケンリーダをリーダとするpaxosアルゴリズムを使用）
2. ジャンケン
   • ジャンケンのかけ声（paxosで合意）
   • 手を決める（手＋ノイズデータのhash値とノイズデータのhash値をグループ内に同報）
   • 手の出揃ったことを確認（paxosで合意）
3. 勝敗の確認
   • 実際の手を公開（手とノイズデータをグループ内に同報）
   • 勝敗を確認（hash値を使って手が改竄されていないことを確認）
   • 勝ちが決まらない場合はやり直す。複数メンバが勝ちの場合は、ジャンケンリーダを再選して、1.のメンバの確定から行う。引き分けの時は、2.から行う。

P.S.

• paxosを使うとメンバの過半数が生きている限り大丈夫なのですが、ここでは、ジャンケンメンバはジャンケン中に突然死や離脱しないことを前提にしています。
• リーダを決めているのは、マルチpaxosじゃない通常のpaxosでリーダが必要になるためですが、選出方法はそう厳格でなくても構いません。
• 合意をpaxosで行っていますが、全体を最適化したもっとシンプルなプロトコルがあるかもしれません。
• hash関数を使って手の改竄を防止していますが、本人確認も含めて電子署名を使うとより強くなります。
• Twitter実装には落としきれてません。orz

• • -

その後、effyたんより、グーチョキパーのhashじゃ元データがばれるとコメントもらいました。元データにノイズを足す記述を追加しました。
さらに、ノイズのhash値を取る案もeffyたんよりもらいました。（09/09/23 14:15）