ゲームマスターを排除した公平な人狼“Mental Jinro”

はじめに

この記事では人狼というゲームから、公平な審判的役割をする“ゲームマスター”を排除して、なおも公平性を保つ人狼について考える。この文書を読んで、よりよくするための方法を考えた場合や、欠陥を見つけた場合は気軽にコメントなどで指摘して欲しい。

続報

より洗練された方法を考えました。

Mental Pokerによるゲームマスターなし人狼

人狼のルール

人狼にはいくつかのルールが存在するため、この節ではこの記事で扱う人狼のルールについて述べる。

役職

次の2つのみが存在する。

• 人狼
• 村人

ゲームを単純にするために、予言者などは省略した。

セットアップ

参加者はまず、全員の中から抽選などで人狼と村人を決める¹。役職決めが終了した後、ゲームは次にあげる夜と昼というターンを交互に繰り返す。

夜

人狼に選ばれた参加者は、他の人狼と協議するか投票するなどして村人の中から一人を選びだし、殺害する。殺害された村人はゲームから退場する。なお、この時、村人には誰が夜に活動しているのか分からないものとする。

昼

全ての参加者は、退場した参加者を除く他の参加者と自由に会話する。一定時間が経過した後に、参加者全員の投票により処刑する参加者を一人決定する。処刑された参加者はゲームから退場する。

勝利条件

人狼、村人による勝利条件は次のようになる。

人狼

人狼の数と村人の数が等しくなる

村人

全ての人狼を処刑する

なお、いずれの陣営が勝利した場合でも最初にどの参加者が人狼であったかを明らかにする必要がある。

準備

説明を始める前に、説明に必要な記号や前提について述べる。

記号の定義

この記事では次のように記号を使う。

記号	意味
$n$	参加者の総数
$m$	人狼の総数
$P_i$	$i$番目の参加者

前提

参加者がどのような振る舞いをするのかについて、次のような前提を置く。

• 参加者の間で協調して悪意のある振る舞いをすることはない
• 参加者は、自らの所属する陣営が不利になるような不正はしない

悪意ある振る舞いをする参加者に協調された場合、ゲームマスターがいる人狼でも不正ができてしまうため、この人狼でも考慮しないものとする。

$\def\Z{\mathbb{Z}^*_p}$

コミットメント

この人狼で用いるコミットメントについて説明する。コミットメントとは「ある数を明らかにしないまま、ただしある数を後で反故にできない」ための仕組みである。具体的な例で説明すると、例えば$A$と$B$が電話で会話をしている時に、$A$がコインの裏か表を予想して、$B$がコイントスをするというゲームを考える。

1. $B$は$p = 2q + 1$となるような大きな素数$p, q$をランダムに生成して、$\Z$²の位数$q$の部分群$G$から生成元$g, v$をランダムに選択して、$p, q, g, v$を$A$に送信する
2. $A$は次のことを検証する
   • $p = 2q + 1$である
   • $p, q$が素数である
   • $g, v$が位数$q$の元である
3. $A$は表と予想するならば$m := 1$、裏と予想するならば$m :=q-1$を選択し、乱数$r \in \{1, \dots, q-1\}$から$c := g^r v^m \bmod p$を$B$に送信する
4. $B$はコイントスをして、結果を$A$へ送信する
5. $A$は$r$と$m$を$B$へ送信する
6. $B$は$c = g^r v^m$を検証する

これは離散対数問題を利用して、$c$から$m$を推測したり、$c$と等しくなるような$r'$や$m'$を生成できなくしているため、公平なコイントスができる。$m$を$\{1, \dots, q-1\}$から選んでもよいので、いくつかの選択肢をコミットメントできるように拡張するのは容易である。
この後コミットメントについて言及する場合は、既に$p, q, g, v$ついては共有されているものとして、かつこれらのパラメータの検証は暗黙のうちに行っているものとする。また、コミットメント$c := g^r v^m \bmod p$を計算する際の$\bmod p$は省略する。

役職決定プロトコル

まず、ゲームを開始するにあたっては役職を決めなければならない。ただし、人狼は誰がどの役職かを識別できてよいが、一方で村人は誰がどの役職であるかを識別できてはならない。

1. 全ての参加者が知る集合$X := \{x_1, x_2, \dots, x_n\}$を用意する。
2. シャッフルプロトコル³で$X$をシャッフルし、参加者は一つずつドローする（ここでは参加者$P_i$がドローした情報を$x_i$と書く）
3. 全ての参加者はコミットメント$y_i := g^{r_i}v^{x_i}$を計算して公開する（$r_i$は参加者$P_i$しか知らない乱数）
4. 全参加者で投票を行うなどして、集合$X$からひとつを選び全員で共有する（選ばれた数字を$x_j$とする）
5. $x_j$を持つ参加者$P_j$は、他の参加者の中から$m - 1$人を選び、その参加者に$a := r_j$を送信する

6. $P_j$から$a$が送られてきた参加者$P_l$は、$a$が次を満すことを検証する

       y_j = g^a v^{x_j}
   

7. $P_l$は自分のコミットメントの情報$b := r_l, c := x_l$を$P_j$へ送信する

8. $P_j$は次が成り立つことを検証する

       y_l = g^b v^c
   

9. $P_j$と$P_j$が情報を送信した参加者$P_l$が人狼となる。

役職決定プロトコルの議論

最初の人狼が村人の数と等しいか、それよりも多い人狼を指名する可能性はないか

その可能性はあるが、その場合、最終的にゲームが終了した時に人狼が多すぎて不正が明らかになる。

人狼と指名した参加者がゲーム終了時に村人側だと主張した時に、それを見破る方法はあるか

その方法はある。役職決定プロトコルの（7）において指名した人のコミットメントに用いた情報を参加者$P_j$が受け取っている。なので、人狼に指名した参加者が裏切った場合はコミットメントに用いた情報を使うことで不正を検知できる。

人狼と指名していない参加者がゲーム終了時に人狼側だと主張した時に、それを見破る方法はあるか

村人はプロトコルの（6）で人狼となった者のコミットメントに用いた情報$r_j$を知らないので、このような不正はできない。

人狼による村人殺害プロトコル

役職決定プロトコルにより、人狼は他の人狼と村人を区別することができるので、これらの間で投票などを行って誰を殺害するかを決めればよい。問題となるのは、人狼側から村人側にどうやって殺害された村人の情報を伝えるかということである。

1. 人狼の中で一人、殺害を担当する者を決める。これは適当で構わない（この人狼を$P_k$とする）

2. 参加者$P_i$は乱数$r_i$を生成して$z_i := y_j \cdot g^{r_i}$のコミットメント$g^{s_i}v^{z_i}$を公開する（$y_j$は役職決定プロトコルで用いた人狼$P_j$の$y_j = g^{r_j}v^{x_j}$である）

       z_i = y_j \cdot g^{r_i} = g^{r_j}v^{x_j}g^{r_i} = g^{r_j + r_i}v^{x_j}
   

3. 参加者$P_i$は$g^{r_i}$を参加者$P_1$に送信する

4. 参加者$P_1$は参加者$P_2$へ$g^{r_i}$を送信する（これを、$P_l (l = 3, \dots, i-1, i+1, \dots, n)$に対して繰り返す）

5. 殺害担当の人狼$P_k$が$g^{r_i}$を受け取った時、
   

   
   

   $P_i$が殺害する対象である場合

   
   

   人狼$P_k$は$g^{r_i} \cdot g^{r_j} = g^{r_i + r_j}$を計算して次の参加者へ送信する

   
   

   $P_i$が殺害する対象ではない場合

   
   

   人狼$P_k$は$g^{r_i}$を次の参加者へ送信する

   
   

6. 参加者$P_n$は参加者$P_{n-1}$受け取ったデータ$c$のコミットメント$d := g^{t_n}v^{c}$を公開する（もし全ての参加者が誠実であれば、$c = g^{r_i}$または$c = g^{r_i + r_j}$となる）

7. 参加者$P_n$は$c$を参加者$P_i$へ送信

8. 参加者$P_i$は$z_i / c$を計算する（ただし、$z_i / c = g^{r_j + r_i}v^{x_j} / c$）
   

   
   

   $c = g^{r_i}$の場合

   
   

   $g^{r_j + r_i}v^{x_j} / c = g^{r_j + r_i}v^{x_j} / g^{r_i} = g^{r_j}v^{x_j} = y_j$となり、この場合は殺害されていない

   
   

   $c = g^{r_i + r_j}$の場合

   
   

   $g^{r_j + r_i}v^{x_j} / c = g^{r_j + r_i}v^{x_j} / g^{r_j + r_i} = v^{x_j}$となり、この場合は殺害された

   
   

9. 参加者が一人でも殺害された場合、昼をスタートする。誰も殺害されなかった場合、直ちに村人が勝利する

村人殺害プロトコルの議論

参加者が本当は殺害されているにも関わらず、殺害されていないと主張するのではないか

その可能性はあるが、この場合は次のようにすることで不正を検知できる。

1. 不正を察知した人狼はそのことを全員に周知する⁴
2. 参加者$P_i$は（2）でコミットメントに用いた情報$s_i$を公開する
3. 参加者$P_n$は（6）でコミットメントに用いた情報$t_n$を公開する

4. 全ての参加者は次を検証する

       g^{r_j + r_i}v^{x_j} / c = g^{r_j + r_i}v^{x_j} / g^{r_j + r_i} = v^{x_j}
   

5. $v$と$x_j$は既知であるので、全員で検証することができる

参加者が殺害されていないにも関わらず、殺害されたと主張するのではないか

この不正は村人にとって不利であるため、意味がないので考える必要はないが、上記と同じ方法で不正を明らかにすることができる。

回していた数値cを不正に改竄するのではないか

このパターンについては誰が改竄するかによって分かれるので、村人側と人狼側について考える。

村人が改竄した場合

村人は$r_j$を知らないので$g^{r_j}$を計算することができず、改竄するとしても何か意味のない数字を渡すなどしかできない。そうした場合は次の方法で判断できる。

1. （8）で参加者$P_i$が受け取った数字が不正であったことを全員に周知する
2. 参加者$P_i$は（2）でコミットメントに用いた情報$s_i$を公開する
3. 参加者$P_n$は（6）でコミットメントに用いた情報$t_n$を公開する

4. 全ての参加者は次を検証する

       g^{r_j + r_i}v^{x_j} / c \ne g^{r_j}v^{x_j} \land g^{r_j + r_i}v^{x_j} / c \ne v^{x_j}
   

この際、実は（3）で参加者$P_i$が送信した$g^{r_i}$が不正であった可能性もあるが、少なくとも参加者の誰かが不誠実な振る舞いをしたことが明らかになる。

人狼が改竄した場合

全ての人狼は$r_j$を知っているので、上記の村人による改竄に加えて人狼による投票で決った者以外を殺害したり、あるいは殺害するべき者を助けたりできる。しかし、いずれにしても人狼の陣営が有利になることはないので、この不正については対策しない。

その他

ゲームマスターなしで匿名な投票ができるのか

これについては、“mix-net”などすでによく知られた方法があるので、それを使えばよい。

人狼側が勝利したことをどう宣言するのか

人狼側は殺害の後もしくは処刑の後に勝利を宣言することができる。人狼側が勝利を宣言した場合は、その時点で誰が人狼なのかを明らかにして、生き残った参加者の中に何人の人狼がいるのかを数える。もし生き残った参加者に含まれる人狼の数が村人の数と同数もしくはそれよりも多い場合は人狼側の勝利となり、そうでない場合は敗北となる。

まとめ

このように、コミットメントなどを用いることで、シンプルな人狼をゲームマスターなしで実現することができたと思う。今後の課題は全体的なプロトコルを見直して欠陥を洗い出したり、よりシンプルな実装を考えたりしたい。また、今回考えた人狼には予言者など役職の一部が脱落しているので、これらの役職を加えても成り立つような実装を考えたい。

---

1. ただし、最初の人狼の数は村人の数より必ず少ない必要がある。 ↩

2. $\Z$とは、整数$x \bmod p$かつ$xy \equiv 1 \pmod{p}$となる逆元$y$が存在する$x$の集合である。 ↩

3. これはMental Pokerなどで用いられている審判なしのシャッフルである。直感的な説明についてはこちらを参照する。 ↩

4. この時、どの参加者が人狼であるかという情報が明らかになるが、不正が発生した時点でゲームの継続は放棄するものとする。 ↩