P2Pのような中央集権型でない環境や、信頼できるノードが存在しないときは、合意形成が難しいため様々な手法が提案されています。
ここでは、麻雀を例にとり、各クライアントが自身の動作を悪意を持って制御可能な状況下で、 定められた手順通り正しく動作をしていて正しく動作し続けたことを後から検証する方法について述べます。
麻雀では山（壁牌）から牌を取り（自摸、ツモ）、手牌に加えたのち1枚を捨てる（打牌）ことを繰り返して役を揃えることを目指します。
山は各ユーザ間で共有しなければツモれず、またどのユーザがどの牌を捨てたのかも共有する必要がありますが、これは本来非公開情報のため、ツモった牌が観測可能になるのは好ましくありません。
つまり、ここでは「何をツモったか」は他のユーザに知らせずに、かつ和了ったときに今までに正しい操作をしつづけたことを全ユーザに示す必要があります。ここではこの点についての解決策を述べます。
どのユーザが親になるかや、サイコロの目をどう共有するかといった点についてはここでは述べませんが、たとえば分散合意形成アルゴリズムなどによって容易に決定可能です。
ここでは、効率的ではありませんが、非常にわかりやすい方法を紹介します。今回紹介する方法の特徴は、摸打時には通信がほとんど発生せず、局の終了時になってから各プレイヤーが今まで正しい操作をしてたのかをいっぺんに検証する点です。
各プレイヤーは、各々秘密の数字 P を決めます。これは使い捨てでも構いませんが、ここではゲーム中は固定し、局ごとに生成しなおすことにします。
P については、実際にプログラムを行う際は、数字である必要はなく、十分に長い文字列で構いません。ただし総当りで容易に P が特定できない程度に複雑で長いものにする必要があります。
プレイヤーがツモったときに、ツモった牌、捨てた牌、山の情報をまとめ、さらに P を加えたデータからハッシュを生成し、全ユーザに送ります。各ユーザは送られてきたハッシュを記録しておきます。
ゲームが終了したら、各プレイヤーの行動の正当性を検証します。
まずは各プレイヤーは自分の P を全ユーザに公開します。
そして、P をもとに、ゲームの進行を遡って各手番でユーザが正しい行動をしたのかを、検証対象のユーザの P を使ってハッシュを計算していきます。
この検証用に求めたハッシュ値と、そのときにプレイヤーが公開していたハッシュ値が同じであれば不正はしていないことになります。
最後に、「このユーザは不正をしていませんでした」という情報についての合意形成を行います。こうしないと、「不正をしていないのに不正を報告する」という不正が行われる可能性があります。ここでは他の適当な分散合意形成アルゴリズムを使って行います。
全ユーザについて不正をしていないという合意がとれればその局は終了します。各ユーザは今まで使っていた P はもはや秘密ではなくなっているので破棄し、再度別の秘密の数字 P を生成します。
他のより効率的でモダンな手法について知りたい場合は、
- 分散合意形成アルゴリズム
- ゼロ知識証明
- マジックプロトコル
などについて調べてみてください。