たまには中の人（うどん）も記事を書いてみようかと思います。主に昨年私が見に行ったDevcon 4 Ethereum 2.0 Randomness をもとに記事を書いてます。
はじめに
乱数は、日常よく使われるものです。ガチャ、パスワード生成などなど、ランダムに数字を発生させて決めるという行為は一般的なものです。
くじ引きという行為をデジタルな場で行う際、乱数は非常に大切になってきます。
当然ブロックチェーン上でも乱数を扱いたいという需要はあります。
1. ギャンブル
ギャンブルにおいて乱数の重要性はいうまでもありません。もしも勝敗を決する数字が真にランダムな値ではなく、操作されてたとしたら...。ギャンブルは成り立ちません。
SatoshiDiceという一時期かなり流行ったギャンブルでは
- 運営側が秘密の文字列を用意する（24時間毎に変更、秘密の文字列のハッシュ値は2日後のまで公開）
- ユーザーがDice側に送った際のトランザクションハッシュと、その秘密の文字列をハッシュする
- ハッシュして出たハッシュ値の先頭の文字列を乱数とみなしギャンブルする（ユーザーは後日公開された秘密の文字列を見て不正がないかどうかチェックできる）
といった仕組みを使いフェアにしてました。ですがこの仕組みでは「何らかの方法で秘密の文字列を知ればズルできる」などの欠点があります
2. Sharding
Shardingとはざっくりいってしまうと、ランダムにグループ分けして、それぞれのグループがトランザクションを並列処理することで処理速度をあげようっていう仕組みのことです。そして定期的にグループをランダムに入れ替えます
太字にしたのでお分りかと思いますが、このランダムにというのが非常に重要になってくるのです。そうでなければ悪意のある攻撃者がある一意のShard（グループ）に振り分けられることを意図できてしまい、攻撃されてしまう恐れがあるからです。攻撃コストはネットワーク全体で処理するよりn個のShardに分けられた方が1/nになりますし。
そんなこんなで、Shardingにもこのランダムさというのは非常に大切になってくるのです。
これ以外にもゲームなどにも重要になってくるでしょう。
乱数を生成する際のゴール
ブロックチェーン上で乱数を生成する仕組みとして満たすべき理想のゴールが3つあります
- 予測不可能（unpredictable）であること
- 偏りのない公平なもの（unbiasable）であること
- いつでも必ず乱数を生成できる（unstoppable）こと
それぞれ順番に見ていきましょう
（Devcon 4 Ethereum 2.0 Randomnessより）
予測不可能（unpredictable）であること
例えばこれまでに生成された値からパターンを見出され、次の値が何となく予測されてしまうのは非常にまずいです。そもそもそんなものは乱数とは呼べないでしょう。ですがそれは一方向性のハッシュ関数によって普通に実現されてます
偏りのない公平なもの（unbiasable）であること
ブロックチェーンにはそもそもランダムに近い値がいくつかあります。例えばこれ
これはたまたま記事執筆中に生成されたEthereumのブロックの情報です。見ての通り、ランダムに生成された値がいくつもあります。ですがこういったものは、生成された乱数をマイナーが知っていることになります。こちらの記事には高額な証券のパターンについて触れられてますが、それらは高額なお金がかかっているもの、例えばギャンブルなどでは重要な課題になります。
実際昔懐かしVDiceとかではOraclizeという外部からデータを取ってくるシステムクォ使って乱数を取り込んだりしていましたが、これもOraclizeなどに依存する仕組みです。
いつでも必ず乱数を生成できる（unstoppable）こと
いつでも必ず乱数が生成できるということは、unstoppableなブロックチェーンの世界において大事なことです。ガチャを引こうとしたら無反応になったり、Shardingでグループの入れ替えをしようとしたのに乱数が生成できなくてブロックチェーンが止まったりといったことが起きたらやばいです。Livenessは非常に大事です。
乱数を生成する際のジレンマ
ですが既存の方法にはジレンマが存在します。
1. Commit-reveal（最後に処理する人が覗き見できる）
満たされるもの：予測不可能性・高可用性
満たされないもの：公平性
先述したように、PoWではブロックに含まれる数字を乱数（またはその種）とした場合、ブロックを採掘したマイナーが最初に答えを知っていることになります。都合が悪い場合（金銭的利益がブロックをブロードキャストしないことを上回る場合）はブロードキャストしないということが考えられます。
また上の図にあるものも見ていきましょう
Algorandについてはこちらがわかりやすいです
新たなプロトコル「Algorand」の発想から現在のブロックチェーンの課題を見直す- MIT Business of Blockchain #1
まあでもこの仕組みでも新しくブロックを生成するノードは全てをしれます。
RANDAOについてはこちらがわかりやすいです
https://qiita.com/yama_mo/items/a65c6a058264ee282601
ですがRandao側もQ&Aで認めている通り、マイナーにより恣意的選択をされる可能性はゼロではないです。ですが、仕組み上6ブロック以上というある程度時間をかけて生成しているので、恣意的選択をされる可能性を下げているようです。
また、後述するDfinityでも採用されているBLS署名も実装する予定とのことです。
2. threshold crypto（一定程度ダウンしたらネットワークが止まる）
Dfinityに使われている仕組みでは、ざっくり言ってしまえばn/m以上の人が参加すればブロック承認のための署名が生成されるというものを使ってます。n以上であれば必ず発行されるし、そのnに誰が参加するかは署名が生成されるまではわからない。だが後から検証は容易にできるというものです。
Dfinityではこの署名を乱数として扱い、Shardの振り分け先を決定しています。
ですがこの仕組みを見てわかる通り、署名を行うために常時一定程度のノードがオンラインになっている必要があります。もしたくさんのノードがシャットダウンしてしまったら一切の処理が行えなくなる（Stopしてしまう）のです。
Ethereumが取ろうとしているアプローチ
EthereumはRANDAOで作り出した乱数を種に、VDFでさらに処理して乱数を作りだすという仕組みを取ろうとしています。これによりバイアスを取り除くという作業をするようです。
さて、このVDFとはなんでしょうか？
VDFとは
VDFとはVerifiable Delay Fanctionsの略です。ざっくり言ってしまえば、計算して結果を出すのには時間がかかるけど、結果が正しいことは誰ても検証できるという、なんだか普通のProof of Workに近いように思えますが、違いがあります。
通常のProof of Workでは、処理を並列的に行います。なのでたくさんのASICを持った方がそれに比例してたくさんの計算を行うことができます。
ですがVDFは違います。
VDFは連続的です。いわばハッシュチェーンをずーっと計算し続ける（前の計算結果がわからないと次にに進めない）ものです。なので、たくさんASICを用意すればいいというものではなく、一台の超性能のいいコンピューターが勝つというものです。
また、Proof of Workは答えがいくつもあるものですが（要件を満たせば正当なブロックとみなされるため）、VDFでは答えは一つです。
VDFのASIC
さて、このVDFはもちろん攻撃者よりも善良な者がパワーを上回らなければいけません。また、実行する際1台以上のノードがいなくてはいけません。これはProof of Workに近いですね。
ということでEthereumとFilecoinはASICの研究開発をしていくそうです。
ざっとトータルで20億から30億円だそう
rigの仕様です
オープンソースにするそうですが、正直聞いたときはうーんと思いました。Dfinityのアプローチの方がいいなと感じたからです。（そんな半分もノードが一気にオフラインになるのは想像つかないので）
ですが、クライアントがクラッシュしたり（Ethereumでもそういうことがありました）といったことを考えると致し方ないのかな〜とも思います。
あとは99%攻撃耐性とかを導入したいからかもしれません。
