はじめに

誰かが不正を働いたり、利潤追求のために動いても安全...それを保証した技術の例にブロックチェーンがある。この記事では、それを一般化したRational Adversaryという研究分野について書く。まだ理解の浅い部分があるので気持ちだけわかってもらえれば嬉しい。

はじめに
忙しい人ためのまとめ
出てくる暗号と関係のない用語の簡単な解説
MMPCモデル
- 特徴と記号の意味
- MMPCモデルの構成
  - チャンネル
  - プロトコルの処理の定式化
MMPCモデルでのインセンティヴ
まとめ
参考文献

忙しい人ためのまとめ

利己的に動くパーティとそれに対して非合理的な動きをするパーティがいるMMPCというMPCモデルがある。
各プレイヤーのインセンティヴの指標として満足度やユーティリティというものを使う。
各プレイヤーはt-NCCという性質を持つ関数の下ではマルチパーティ計算から逸脱できない。

出てくる暗号と関係のない用語の簡単な解説

maximal set

ある性質Pを満たすAとBがある。この時、 $A \subseteq B$ なら $A=B$ である。つまり、集合Aは性質Pを満たすようなmaximal setである。これがあると、小さい集合について考えなくてよいのである性質を満たすような集合の定義が簡略化される。

ナッシュ均衡

どのプレイヤーもその戦略を選ばざるを得ないような状態のこと。「囚人のジレンマ」で有名。

支配

どの戦略を選ぶよりも有効な戦略を支配戦略という。

MMPCモデル

特徴と記号の意味

どのパーティもhonestではないのが特徴。Rationalなパーティはユーティリティを最大化するように行動するパーティで、Adversarial なパーティはそれに対して非合理的な行動で敵対するパーティで最終的には全パーティがプロトコルに従わざるをえなくなる。

$\mathcal{R}$

MPCをゲームと見なして、プロトコルに逆らう

$\mathcal{A}$

最大tまでのパーティが連携して、 $\mathcal{R}$ に敵対的な行動をする

Pが使用可能なチャンネルとよばれるチューリングマシンのこと。4つ組で表される。

C(P)

Pが使用可能なチャンネルの集合。

MMPCモデルの構成

$\mathcal{P}=\mathcal{R}\cup \mathcal{A}$ と表す。RationalとAdversarialの集合が全体のパーティであることを表す。

チャンネル $C= \{ \mathcal{P_I},F_C,state,\mathcal{P_O},\}$

プロトコルの通信方法をモデル化したもの。

チャンネルでの一連の処理

$\mathcal{P_I}$ に含まれる各 $P_i$ がテープ $t_i ^ I$ に $I_i$ を書き込み、すべての $\mathcal{P_i}$ が書き込むまで待つ。もしタイムアウトしたら $\perp$ をそうでなければ $I_i$ をCにインプットする。
このインプットをもとに状態操作関数 $F_C$ で $F_C(I,state)→F_C(O,state')$ のように適用して、チャンネルの状態を変化させる。
テープ $t_i ^ O$ に $\mathcal{P_O}$ の各 $P_i$ に向けて $O_i$ を書き込む。

プロトコルの処理の定式化

上の一連の処理をラン $R:=(p,r,\mathcal{A})$ とする。

$VIEW_i(r_i,M_i)$ は各 $P_i$ の受け取ったメッセージである。
$VIEW_i(r_A,M_A)$ は $\mathcal{A}$ の受け取ったメッセージである。 $\mathcal{A}$ はまとめて１つの連合とされていることに注意。
各パーティが最後に受け取ったメッセージを $OUT_i(R)$ という。

これが意味するのは、 $\mathcal{P_I}$ に含まれる各 $P_i$ が $p_i$ をそれぞれ実行し、 $r_i$ を介して、 $M_i$ を受け取っているということだ。そして、Rを繰り返すうちに最後に入手したメッセージは $OUT_i(R)$ と呼ばれる。

MMPCモデルでのインセンティヴ

ユーティリティ

ユーティリティはこのプロトコルのインセンティブにあたるものだ。今回は $\mathcal{R}$ が利益のために動くので、その利潤をプロトコルにおいて数値化する。各パーティ $P_i$ は関数 $f_i$ について知りたいという状況を考える。各ランRに対する関数をプロトコルユーティリティ関数 $\mathbf{u}$ とする。

$\mathbf{u}={u_1,\dots}$

Rationalなパーティはユーティリティ関数 $u_i$ と関連付けられる。そしてユーティリティを計算するために、満足度 $\mu$ というものがある。

$\mathbf{\mu}={\mu_1,\dots}$

例えば、 $\mu_i$ は $VIEW_i(R)$ においてどれだけ望むような計算が結果が返ってきたかを表す。

$\mathbf{\mu}$ は $\mathcal{P}$ 全体の満足度。各満足度 $\mu_i$ は以下のように閉区間[0,1]か $\perp$ にマッピングされる。 $\mathcal{A}$ は邪魔をするだけなので、特にユーティリティを持たない。

$\mu_i: \{0,1\}^* \rightarrow [0,1] \cup \perp$

$\mu _ i(\cdot) =\begin{cases} [ 0,1 ]\ P _ i \in \mathcal{R}\\ \perp\ P _ i \in \mathcal{A}\\ \end{cases}$

この個人満足度から全体の満足度を計算するような関数を定義する。ここで、全員の満足度 $\mu_i$ から個人のユーティリティ $u_i$ を評価するのは、後述のような性質をユーティリティが持つため、個人の満足度だけでは測れないポイントがあるからだ。

さて、各パーティ $P_i$ はそのランRで $\mathcal{R}$ が得られた全体の満足度 $\mu(R)$ を計算できる $u'={u_1,\dots}$ という関数の集合とする。定義は

$u'_i: \{0,1\}^* \rightarrow [0,\infty]$

この $u' _ i$ は $u _ i(R)=u' _ i(\mu(R))$ という性質を持ち、Rの関数であった $\mathbf{u}$ を満足度を介することで評価できる。ユーティリティには以下の３つのような性質がある

$P_i$ は学習すると $u_i(R)$ が上昇する。
$P_i$ は $i\neq j$ であるような $P_j$ が学習すると $u_i(R)$ が下降する。
$P_i$ は $i\neq j$ であるような $P_j$ が $OUT_i(R)=f_i(x)$ だと $u_i(R)=0$ になる。

t-NCC関数

定義に向けた準備

関数の入力をビットから文字列に一般化することを考えたい。 $\mathbf{f}:X \rightarrow Y$ の $n$ 変数関数とし、 $\mathcal{P = R\cup A}, |P| = n$ 、そして $\mathbf{u}$ をプロトコルユーティリティ関数とする。各パーティの入力 $\mathbf{x}$ と $\mathbf{x'}$ は以下のように定義される。

$\mathbb{x}=\{\mathbf{x} _ \mathcal{A},\mathbf{x} _ \mathcal{R}\}\\ \mathbb{x'}=\{\mathbf{x'} _ \mathcal{A},\mathbf{x'} _ \mathcal{R}\}$

ここで、 $\mathbf{x'} \leftarrow X$ とし、 $\mathbf{x}' _ {\mathcal{R}}=\mathbf{x} _ {\mathcal{R}}$ かつ、 $\mathbf{x} _ A$ をAによる入力 $\mathbf{x'} _ A$ に置き換えるという処理 $\mathbf{x'} _{\mathcal{A}}\leftarrow A(\mathbf{x} _ {\mathcal{A}})$ を使っている。すなわち、 $\mathbb{x'}$ と $\mathbb{x}$ はAによって置き換えられた部分だけ違う。これは $\mathcal{A}$ が自分の入力を変えるようなシナリオを想定している。

新しい概念を導入する。入力から任意の値を得ようとする行為を戦略（strategy）という。

$Eqv _ f(i, x _ i)$ は $\forall \mathbf{x} _ {−i}$ と $\forall x \in Eqv_f(i, x _ i)$ について、 $f(x _ i,\mathbf{x _ { -i}})=f(x,\mathbf{x _ { -i}})$ を満たすような $x$ のmaximal setである。なお、ここ以降で登場する記法の意味は以下である。

$(x _ i,\mathbf{x _ { -i}}) = \mathbf{x} = \{ x _ 1,x _ 2,\dots,x _ {i-1},x _ i,x _ {i+1},\dots,x _ n \} \\ (x' _ i,\mathbf{x _ { -i}}) = \{ x _ 1,x _ 2,\dots,x' _ {i-1},x _ i,x _ {i+1},\dots,x _ n \}$

$\Sigma ' _ i(x_i)$ を、ある $x \in Eqv f(i, x_i)$ をCに送った後、 $y_i$ を出力する $P_i$ の戦略の集合する。
$\sigma^* _ i(x_i)$ を $x_i$ を C に送った後、 $y_i$ を出力として得る戦略とする。

この定義から分かるように、 $\Sigma ' _ i(x_i)$ と $\sigma^* _ i(x_i)$ は $i$ 番目の入力が変わっているが、 $f$ の値は変えていない。戦略に関する記号は4つ登場するが意味は以下である。

$\mathbf{\Sigma}'$ は $\mathcal{R}$ の戦略のベクトルの集合。
$\mathbf{\sigma^{*} }$ は $\mathcal{R}$ の戦略のベクトル。各パーティに戦略が定まっている。 $\mathbf{\sigma^{*}}=\{ \sigma^{*} _ 1(x _ 1),\sigma^{*} _ 2(x _ 2),\sigma^{*} _ 3(x _ 3),\dots \}$ 。
$\Sigma'(x _ i)$ は $x_i$ を別の入力 $x$ に変えても変わらない $P _ i$ の戦略の集合
$\sigma^{*}(x _ i)$ は $P _ i$ が $x_i$ を入力する戦略
$\mathbf{\sigma _ {-i} }=\mathbf{(\sigma _ {\mathcal{R}}) _ {-i}}$

t-NCC関数の定義

以上の定義を利用して、 $\mathbf{f}$ をt-Non-Cooperatively Computable Function (t-NCC 関数) と呼び、すべての $P_i \in R$ に対して、 $\mathcal{A}, \mathcal{|A|} \leq t$ かつ、入力の分布 $X$ の下で以下を満たすような関数として定義できる。

$μ _ i(x _ i, \mathbf{x _ \mathcal{A}})=0$ ,、つまり $x_i$ と $\mathbf{x_A}$ のみから $f_i(\mathbf{x})$ については何も知ることができない．（これは $\mathcal{A}$ が $\mathbf{x}_\mathcal{A}$ を $P_i$ に与えるような例を回避するため）
すべての $\mathcal{A},i$ について, $fi(\mathbf{x'}) = fi(\mathbf{x})$ 、つまり $\mathcal{A}$ は入力を変えることで関数の値を変えられない・.
すべての $\mathcal{A}$ について， $P_i$ は，自分の正しい入力 $x_i$ をCに与えることで，他の異なる入力を与えるのと同じくらいのユーティリティを得られる。つまりプロトコルに従わざるを得ない。数式としてはすべての $1 \leq i \leq n$ とすべての $\sigma_i\notin\Sigma '_i(x_i)$ について以下のようにあらわせる。

この数式の意味は直感的には、 $P_i$ が自分の入力を正規の入力から変更しても、正規の入力 $\mathbf{x_R}$ より低いユーティリティの期待値しか得られないことを意味する。

MMPCのナッシュ均衡

パーティ $\mathcal{P}=\mathcal{R}\cup \mathcal{A}$ 、 $\mathcal{R}$ の戦略 $\mathbf{\sigma}*$ が( $\epsilon-$ )ナッシュ均衡であるとは、すべてのパーティと全ての戦略と全ての $\mathcal{A}$ について以下を満たすことである。ここで $\mathcal{P}$ は $\mathbf{X}$ から入力を手に入れ、チャネル構造C(P)とプロトコルユーティリティ関数 $\mathbf{u}$ を持つ。

f:id:ATen:20200605115544p:plain — (ε-)ナッシュ均衡

この式は、直感的には戦略のユーティリティの期待値に無視可能な程度にしか差がない状態を意味する。ゲーム理論のナッシュ均衡をうまく確率的なものに置き換えている。（？）

$E_{\mathbf{X}}[u_i( (\sigma_{-i},\mathbf{\sigma^{*} _{-i} } ),\mathbf{r} , \mathcal{A} )$ ]

これの意味を見てみるとまず $((\sigma _ {-i},\mathbf{\sigma^{*} _ {-i} } ),\mathbf{r} , \mathcal{A})$ はラン $R$ のことである。さらに $u _ i( (\sigma _ {-i},\mathbf{\sigma^{*} _ {-i} } ),\mathbf{r} , \mathcal{A} )$ となっていることからこれは、ラン $R$ における $P _ i$ のユーティリティである。 $(\sigma _ {-i},\mathbf{\sigma^{*} _ {-i} } )$ はひとつの戦略のベクトルのうち $P _ i$ に対応(ベクトルの $i$ 番目)する戦略を入れ替えたものである。

入力は分布 $X$ から与えられるから、数式全体としては $P _ i$ が戦略を変えたときのランRにおける $P_i$ のユーティリティの $X$ における期待値である。

弱支配戦略の繰り返し削除

$\mathbf{\sigma}$ が以下のような二つの条件を満たすとき、

$[ \mathbf{\sigma} < \mathbf{\sigma}^{'} | \mathbf{\Sigma}' ]$

であるような $\mathbf{\sigma}'$ の被弱支配戦略という。ここで $\mathcal{P}$ は $\mathbf{X}$ から入力を手に入れ、チャネル $C$ とプロトコルユーティリティ関数 $\mathbf{u}$ を持つ。

(1) この時、 $i$ 番目の入力が入れ替えられた全ての戦略 $\mathbf{\sigma} _ {-i} \in \mathbf{\Sigma}'$ と全ての $\mathcal{A}$ に対して、 $i$ 番目を戦略 $\mathbf{\sigma}'$ で入れ替えたときは、 $\mathbf{\sigma}$ で入れ替えたとき以上のユーティリティの期待値を得られる。

(2)　 $i$ 番目の入力が入れ替えられたある戦略 $\mathbf{\sigma}'_{-i} \in \mathbf{\Sigma}'$ とある $\mathcal{A}$ に対して、 $i$ 番目を戦略 $\mathbf{\sigma}$ で入れ替えたときは、 $\mathbf{\sigma}'$ で入れ替えたときよりも一定の値小さいユーティリティの期待値を得られる。(正しいか分からない、εをどう扱うか)

さて、この条件を参考に、弱支配戦略の繰り返し削除を以下のように行える。

この式は直感的にはある戦略よりもユーティリティが小さい戦略が存在する限り、それを再帰的に引いていくという処理である。 $\mathbf{\Delta^{l}}$ は被支配戦略の集合のベクトルともいえる。実際 $l=1,i=1$ とすると初期値 $\Sigma_{i}^{l-1}=\Sigma^{0}$ となり

$\begin{eqnarray} \Sigma^1 _ 1　&= \Sigma^0 _ 1- \Delta^{1} _ 1\\ \Sigma^2 _ 1　&= \Sigma^1 _ 1 - \Delta^{2} _ 1\\ \Sigma^3 _ 1　&= \Sigma^2 _ 1 - \Delta^{3} _ 1\\ \Sigma^4 _ 1　&= \Sigma^3 _ 1 - \Delta^{4} _ 1\\ &\vdots \end{eqnarray}$

これを行うと、

$[ \mathbf{\sigma} < \mathbf{\sigma}^{'} | \mathbf{\Sigma}' ]$

であるような $\mathbf{\sigma}$ は残らない。よって被支配戦略は消え、支配関係にない選択されうる戦略だけが残る。

t-secure preferred protocol

MMPCモデルによるプロトコルはt-secure preferredを満たすのが望ましい。戦略のベクトル $\mathbb{\sigma^{*}}$ が以下の３つの性質を持つなら入力の分布が $\mathbf{X}$ の関数のベクトル $\mathbf{f}$ に対するt-secure preferredプロトコルを構成する。ここで $\mathcal{P}$ は $\mathbf{X}$ から入力を手に入れ、チャネル構造C(P)とプロトコルユーティリティ関数 $\mathbf{u}$ を持つ。