「分割」できる疑似乱数生成器

プログラミング

この記事ははてなエンジニア Advent Calendar 2018 の 6 日目の記事です.

こんにちは, id:susisu です. Mackerel のアプリケーションエンジニアをしています. 最近は新しいカスタムダッシュボード機能を開発したりしていました.

mackerel.io

この記事ではタイトルにある通り, ある種の疑似乱数生成器について紹介します. 内容は社内の技術勉強会 (兼 ???) にて LT として話したものの増補改訂版となっています.

乱数の話をしようと思ったのにはきちんと背景がありますが, これは長い上に直接関係のない話が多くなってしまったので, 一番最後に書きました. お時間のある方は最後までどうぞ.

Splittable PRNG

通常の疑似乱数生成器 (pseudorandom number generator, 以下 PRNG) については, きっとこの記事を読みに来るような人には説明は必要ないでしょう. 一応 Wikipedia の記事 を置いておきます.

Splittable PRNG はその名の通り「分割」が可能な PRNG の一種です. ここでは以下の二つの操作が行えるものとします:

  • rand: PRNG から疑似乱数を生成する
  • split: PRNG を二つの新しい PRNG に分割する
    • 以降 split で分割される前の PRNG を親, 分割した後の二つの PRNG を子と呼びます

これに加えて, split で分割された子の PRNG 同士は独立, つまり生成された乱数同士に相関を見出したり, 片方の生成した擬似乱数からもう片方が生成するものを推測するなど, 互いを関連付けることが不可能か, あるいは少なくとも困難であるとします.

Haskell における (旧) 標準ライブラリ random がこのようなインターフェースを定義しています1.

Splittable PRNG を使うモチベーション

Splittable PRNG の利点として, 第一に, 新しい PRNG を生成する際に, ハードウェアの状態や時刻を参照するなどの副作用が必要がないということが挙げられます. これは Haskell のような副作用の使用に制限がある言語では良い性質となります.

また, 副作用の使用に制限がない場合でも, 例えばグローバルに PRNG を一つ用意してプログラムの複数の部分から直接使用した場合, 順番によってそれぞれの部分が得る乱数の値が異なるため, 実行のたびにプログラム全体の結果が異なってしまったり, PRNG の状態の変更を行う際にロックを取得する必要があるために, パフォーマンス悪化の原因となったりします. これに対して split で分割した PRNG を予め渡しておけば, 各部分が独立に乱数を得られるようになるため, このような問題は発生しなくなります.

他にもランダムな関数を生成したいような場合に, splittable PRNG を用いることで, 引数ごとに (ランダムに生成した) 返り値を覚えておく必要がないような実装が可能になります. テストフレームワークである QuickCheck の内部ではこのような使われ方がされています.

Splittable PRNG の作り方

きちんと上で挙げたような性質を満たす splittable PRNG を作るのはそこまで単純な話ではありません. 例えば派生した PRNG を作る方法として「PRNG が生成した疑似乱数を乱数の種として新しい PRNG を作成する」というものが真っ先に考えられますが, 通常これでは split で分割した子同士が独立となるという条件を満たせません. Haskell の標準ライブラリの実装にも問題があり, 分割後の PRNG 同士がなんらかの相関を持ってしまう場合があるようです.

高品質な splittable PRNG を提供するライブラリとして tf-random があります. これは暗号学的ハッシュ関数を使用することでその品質を保証しています. 詳細については Splittable Pseudorandom Number Generators using Cryptographic Hashing (K. Claessen and M. Pałka, 2013) を参照していただくとして, ここでは簡単に概略を紹介します.

アイデア

基本的なアイデアは以下のような対応づけです.

乱数の世界 ハッシュ関数の世界
乱数の種 鍵
PRNG の状態 ハッシュ関数への入力
乱数 ハッシュ値

ここでの PRNG の状態というのは, 例えば親や先祖が split で二つに分割された内のどちらに由来するかといったもので, その PRNG を一意に特定できるものです2.

暗号学的ハッシュ関数を使うことで,

  • 状態が異なれば全く異なった乱数が生成される
  • 乱数が真の乱数でないと見破ること, または状態を復元して他の PRNG との関連を見出すことが困難である

といった性質が得られます.

実際の tf-random の実装では PRNG はいくつか状態を持っていますが, ここでは簡単化して, PRNG の状態が split の分割の経路のみの場合を例として考えてみます. PRNG を以下のように乱数の種 key と状態 (経路) path のペアで表すとします.

{
    key  = 乱数の種,
    path = 状態 (経路)
}

一番最初の PRNG の状態は空のリストとします. split で生成される子の PRNG は, 親と同じ乱数の種を持ちつつ, 状態に 0 または 1 をそれぞれ付け加えます.

split(g) = ({ key = g.key, path = g.path ++ [0] },
            { key = g.key, path = g.path ++ [1] })

rand で乱数を生成するときは, なんらかのハッシュ関数 hash に対して, 鍵として key と, 入力として path を与えます.

rand(g) = hash(key = g.key, input = g.path)

アイデアとしては簡潔ですが, これできちんと splittable PRNG として動作します.

状態の保存

上の例で無事 splittable PRNG はできたものの, これには split を n 回繰り返した状態を保持するために最低 n bit のメモリが必要になる, という問題があります. 当然プログラムの実行中に split は何回も行われるので, これではどんどん必要なメモリが増えていってしまうので困ります.

この問題は rand による乱数の計算方法を少し変更することで解決できます. まず, PRNG の持っている状態を, 適当な bit 数ごとに区切ってブロックに分割します. rand はこのブロックに分けられた状態を, ハッシュ関数を使って畳み込む (fold) ことで乱数を計算します. つまり, 最初は乱数の種を鍵として先頭のブロックのハッシュ値を計算し, さらにそのハッシュ値を鍵として次のブロックについてハッシュ値を計算し, ... と繰り返して, 末尾のブロックまで計算して得られたハッシュ値を rand の出力 (乱数) とします.

f:id:susisu:20181205201045p:plain

この計算を rand で一気に行うのではなく, split 時に状態が一定のブロック長 m に達したら, その時点でのハッシュ値を計算してしまうことにします. こうすることで, PRNG としては直前に計算した鍵と直近のブロックのみを状態として持っておけば良いということになり, メモリ使用量の問題が解決されます.

split(g) =
    if length g.path == m - 1 then
        ({ key = hash(g.key, g.path ++ [0]), path = [] },
         { key = hash(g.key, g.path ++ [1]), path = [] })
    else
        ({ key = g.key, path = g.path ++ [0] },
         { key = g.key, path = g.path ++ [1] })

rand(g) = hash(key = g.key, input = g.path)

実際の tf-random では他にも高速化のための工夫などが凝らされていますので, 興味を持った方は論文や実装を読んでみると良いでしょう.

JavaScript による再実装

こういったアルゴリズムを隅々まで理解するには自分で実装してみるのが一番です (?) というわけで JavaScript による再実装を行ってみました.

github.com

tf-random は Threefish というハッシュ関数 (ブロック暗号) を用いていますが, これ自体は Haskell ではなく C で書かれています. この実装は http://www.skein-hash.info で配布されている最適化された実装を改変したものになっていますが, より読みやすい参考実装も配布されていて, 今回の再実装にあたってはこちらの方を参考にしました.

また再実装しながら tf-random のソースコードを精査していく過程で, どうやらバグがあることも発見しました. tf-random では split の他に splitn という, PRNG を 2n 個に分割する関数も提供されているのですが, この中で行われているビット演算が間違っているため, 分割した子がいくつかのステップを踏んだ後に同じ状態を持ってしまうことがありました. 生き別れた 4,294,967,296 つ子同士が出会う瞬間は感動的です. いや出会ってはいけないんですけれども.

まとめ

というわけで splittable PRNG の紹介でした. 気まぐれ半分で調べ始めましたが, 私にとって全く知らなかった世界が広がっていて, なかなか面白いものでした.

はてなエンジニア Advent Calendar 2018, 明日は id:taketo957 さんです.

おまけ: 背景

プログラムのテスト手法の一つとして, property based testing3 と呼ばれるものがあります. 一般にプログラムのテストと言った場合, プログラムに与えた入力に対して, 得られる出力が正しいか確認する, というものが多いと思います. これに対して, property based testing では, 具体的なプログラムの入出力よりも, プログラム自身が満たす性質 (property) に注目します.

具体例として, 足し算をする関数 add(x, y) を考えてみましょう. 普通のテストでは, 例えば add(1, 2) == 3 のように, 手で入力を与えて, 具体的な出力が正しいかを見ます. それに対し property based testing でテストする内容は, 例えば交換法則「すべての整数 x, y に対して, add(x, y) == add(y, x)」のような, 具体的な入出力によらない性質です.

記事の一番最初でちょっと紹介した Mackerel の新しいカスタムダッシュボードにおいても, レイアウトを編集したときに正しくない状態 (領域からはみ出してしまったり, 互いに重なったりしてしまう) になってしまわないことを「すべての正しいレイアウト layout とすべての編集 (新規作成や移動) edit に対して, newLayout(layout, edit) は正しい」という, プログラム newLayout の性質と解釈してテストをしています.

f:id:susisu:20181205042146g:plain

さて, ここまで挙げたプログラムの性質の例に共通して「すべての ...」という言葉がついている通り, property based testing は具体的な入力によらない性質に注目してるので, あらゆる入力について性質が満たされているか確認することになります. しかし, もちろん可能な入力をすべて試したり, あるいはプログラムを解析して反例を導出したりすることができれば良いのですが, 一般にはそれが困難または不可能であるため, 通常はランダムに入力を生成して一定回数試行することで「すべての入力」をエミュレートしたことにします4. ようやく乱数が絡んでくるわけですね.

ここで白状すると, 上で挙げたのダッシュボードのレイアウト編集のテストを書いたときは, property based testing のフレームワークを使わず, それどころか「なんかランダムにテストしておけば良いんでしょう?」という雑な理解で書いてしまったため, 動作こそするものの, あまり使い勝手の良いものにはなりませんでした. もしかすると, これらはフレームワークを使っておけば解決できた問題だったのかもしれません.

では既存のフレームワークでは一体どのようなことしているのでしょうか? Property based testing のフレームワークとしてはこの記事中でも既に言及した QuickCheck が有名です. ヘルプや解説記事を読んでみると, 主に以下の二つを担っていることがわかります.

  • 入力となる各種データをランダムに生成する
  • テストを実行して, 統計情報の表示や, 失敗時には反例の提示を行う

なるほど, 自分で雑に書いたときの使い勝手の悪さは, 主に生成した入力データの質や, 失敗時の反例の提示方法によるものであったため, 確かにこういったフレームワークを使えば問題はいくらか解決されそうです.

これらのフレームワークの役割は一見簡単そうですが, 実はきちんと考慮しなければならないことがあったり, または裏では何か非自明なことをしているかもしれません. さらに理解を深めるために QuickCheck のコードを読んでいくと, ランダムな入力を生成する部分で, なにやら tf-random というライブラリを使っています. やっぱり非自明でした.

  • なぜ QuickCheck は標準ライブラリの疑似乱数生成器を使わないのでしょうか?
  • そうでないにしても, なぜ一般によく知られた高品質あるいは高速な疑似乱数生成器 (例えば Mersenne Twister など) ではないのでしょうか?

というわけで今回の話に繋がったのでした.

ここまでお付き合いいただきありがとうございました.

  1. 実際に random や tf-random といったライブラリが提供するのは rand ではなく, 疑似乱数と次の PRNG のペアを返す操作 next ですが, ここでは以降の議論が簡単になるためこちらを使います. rand と split があれば next 相当の操作を定義できますし, 逆に next があれば自明に rand は定義できます.↩

  2. 実装上は一意に特定できない形で経路を保存していたりしますが, 操作に対して制約をかけることで, 実行時に出現するものについては一意になるようにしています.↩

  3. 日本語での定訳を知らない.↩

  4. もちろんこうするとエッジケースに弱くなるので, そのあたりは別途具体的な入力を指定したテストを追加することになると思います.↩