Collaborative coin flipping
アイデア
Collaborative Coin Flippingは複数の参加者が信頼できる第三者なしで公平かつセキュアにランダムな結果を生成するためのプロトコルとしてMPCやゲーム理論で用いられる。
例えばAliceとBobが大事な物事を決めるためにコイントスをする。
この時、お互いにコインを持っておりどちらを使うか決めないといけない。
しかし、相手のコインを信用する必要があり負けた時に「インチキだ」と言われては仕方ない。
つまり、どちらのコインを使うかで合意形成が必要である。
この紛争を解決するアイデアとして二つのコインどちらとも使い、両方とも同じ組み合わせ(両方とも表もしくは両方とも裏)であれば「表」とし、異なる組み合わせ(表と裏が一枚ずつ)であれば「裏」とする。
これにより、一方のコインを信用することなくコイントスと同じ確率で結果を得ることができる。
このアイデアを数学的に見てみると、2PCのXOR演算と捉えることができる。
つまり、(1,1)or(0,0)であれば0を返し、(1,0)or(0,1)であれば1を返す
https://scrapbox.io/files/66fcd93edce91f001cb85764.png
MPCへの応用
XORを使った合成により、1人の参加者が自分のビットを制御しても全体の結果はまだランダムな性質を保持するが、ラストムーバー攻撃には対策が必要で、ランダムビットをすぐに公開せず、まずコミットメントを共有し、全員がランダムビットを公開した後にコミットメントを開くプロトコル(Commit-and-Reveal方式)などが用いられることがある