2012年06月26日

天鳳: 乱数種公開

天鳳ブログの記事が「牌山が作為なく生成されていることを検証可能」ということを主張している。 これについて解説したいと思う。 理解できない用語が出てきても、そのまま読んでいただければ後から解説がなされるように書いたつもりだ。

乱数による牌山の生成方法は別の記事で示されている。 その主張は「乱数の種が決まれば、牌山は一意に決まる」ということになる。 したがって、検証の手順は「牌譜に記録された乱数の種、公開されている牌山生成アルゴリズムを使って牌山生成を行う。その結果が実際に牌譜に記録された牌山と等しいかどうかを確かめる」ということになる。

しかし、実はこれだけで検証がなされたとはいえない。 なぜなら「まず牌山を操作し、後から乱数の種をうまく選び、そこから生成された牌山が操作した牌山と一致するようにしたのではないか」とか「乱数の種によっていくつかの牌山を生成し、プレイヤーが決まってから特定のプレイヤーに有利な種と牌山の組を使ったのではないか」とかいう疑問がありうるからである。 それらの疑問に答え、疑いをほぼ完全に晴らすのが今回の記事の目的である。 記事には

対戦で使用する乱数種が、対戦を開始する前、予約する前、さらには、ログインする前に、事前に決定済みであったこと、それが作為なく順番に消費されていることが検証できます。

とある。 これを実現するには、どうすればよいであろうか? それには、乱数の種をゲーム開始 (牌山生成より前に行われる、座位の決定なども含む) より前に公開しておけばよい。 そうすればゲーム開始時に乱数の種を変えることはできなくなり、乱数種に不公平な介入の余地がないことを証明できる。

しかし、実際に乱数の種を公開することはできない。 なぜなら、乱数の種と牌山生成アルゴリズムを公開してしまえば、そこから牌山を計算することができるからである。 ゲーム開始前に種を公開してしまえば、悪意をもったプレイヤーは先回りして牌山を生成し、それを知って有利にゲームを進めることができてしまう。

ここでは 'SHA512' という暗号学的ハッシュ関数を使って、この問題を解決する。 暗号学的ハッシュ関数とは、関数 f であって

第1原像計算困難性
y が与えられたとき f(x) = y をみたす x を見つけるのが難しい
第2原像計算困難性
x が与えられたとき f(x) = f(x') をみたす x' (≠ x) を見つけるのが難しい
衝突困難性
f(x) = f(x') をみたす x ≠ x' を見つけるのが難しい

という3つの性質をみたすもののことである。 SHA512 はこれらをみたすと考えられている。

天鳳が行った手順は以下の通りである:

  1. 対戦開始前に、乱数の種を作っておき、それを SHA512 へ通したもの (以下では H と呼ぶ) を公開しておく。
  2. 対戦開始時 (以降) に、乱数の種と牌山生成アルゴリズムを使って座位や牌山を生成する。
  3. 対戦終了時に、乱数の種を牌譜へ記録し、公開しておく。

この手順を踏んだ場合に考えられる牌操作は「所望の牌操作を実現した上で、その牌山になる乱数種を計算し、さらにその乱数種を SHA へ通して得られる値を H と等しくする」という条件をみたさなければならない。 そして、それを実現する方法のうち「最初に H をでたらめに作って公開し、それに合わせて乱数種を作る」のは第1原像計算困難性によって否定される。 「最初に乱数種を作ってあるが、H に合わせた他の乱数種を作って牌山生成に使う」のは第2原像計算困難性によって否定される。 「最初に複数の乱数種を作り、同じ H が計算されるようにし、どのユーザが対戦するかを考慮して牌山を選ぶ」のも、衝突困難性によって否定される。 これで天鳳の牌山にイカサマがないことを証明可能になるというわけだ。

それでも天鳳の牌山にイカサマがあるとしたら、つの氏は世界的に認められた暗号を破ったことになってしまう。 オンライン麻雀なんて運営している場合ではなくなるのだ。

牌山生成アルゴリズムについての追記。

上では牌山と乱数種との関係については「決定的なアルゴリズム (乱数種を入力すれば他の情報を使わずに牌山が自動的に決まるような計算の手順) が公開されている」ということのみを用いている。 かずっち氏の記事には問題の混同が見られる。 彼は乱数種のことを単に乱数と (おそらく誤解によってではなく大雑把な説明のために) 表記しているが、牌山と乱数/乱数種の関係に一方向性は必要とされていない。

それでは、任意の牌山を作る乱数種を見つけることは可能だろうか? 現実的にできるかといえば答えは No だが、理論的には Yes ということになる。

まず乱数種として異なるものがどれくらいあるかということだが、サイズが 1024 bit であるから 21024 > exp(709) 通り。 これに対して牌山の並び方は高々 136! < exp(536) 通りである (exp: e の累乗を使った表記にしているのは階乗を計算しやすくするためである)。 したがって1種類の牌山に対し、それを実現する乱数種は平均で exp(173) > 1075 通りということになる。 そしてメルセンヌツイスタのFAQにあるとおり、メルセンヌツイスタは十分な長さの出力から後ろの出力を予測できるという。 任意の牌山に対応する乱数 (種ではない) 自体を構成することは難しくはないので、それを出力列として与え、その後の出力を予測することができる。 これは乱数種を求めるのと同値になる。

ここから先は私の理解が不十分でありうる。

上で引いたFAQは1998年版のMTに関するものであり、(天鳳で使っている) 2002年版ではいくつかの問題点が改善されているという。 1998年版の実装を見つけることができなかったのもあって検証できていないが、出力から以降の出力、内部状態、種を求めることも難しくになっているように見える。

Trackback URL

Make a Comment

Name:
URL:
  Remember me:
 
 
About

我打麻将

我打麻将の研究ノート

  • 各種ルールによって行われる麻雀の研究記録ブログです。
  • 研究課題や未知のルールは常に探しております。
  • 研究課題、未知と思われるルールを考え付いた・どこかで見た方は、e-mail またはコメントにてご連絡ください。

Sponsor

  • 当ブログの牌画は「雀のお宿」百貫雀氏によるものをフォーマット変更の上、利用しています。2次(実質3次)利用などは、氏の「雀のお宿」にて示されているガイドラインに従ってください。
Recent Comments
QR Code
QRコード
  • ライブドアブログ