Mathematicaには、Ver8.0頃から強力な確率・統計計算機能が搭載されています。しかし、あまり利用されているという話を聞きません。そこで、とある確率上の難問を取り上げつつ、この機能を使ってみたいと思います。
数学の分野で、定期的に話題になる確率の問題に、「モンティー・ホール問題」があります。
テレビ番組で、司会者のM氏（モンティー・ホール氏）が3つの扉を提示する。出場者は、そのうち1つだけを開けて良い。いずれかの扉の裏側に景品があり、当たった場合はそれを貰える。
出場者が左の扉を選んだところ、M氏は真ん中の扉を開け、そこに景品がないことを示した。出場者は、選んだ扉を変更すべきか否か。
１２ 結論
信頼関係を必要としない電子取引システムを提案した。まず、電子署名だけに頼った通貨を考えたが、所有権を強力に制御できるものの、多重使用を防げないことが判明した。この問題を解決するため、各利用者が取引を公開し、演算量証明を利用してその履歴を記録するP2Pネットワークを考案した。もし、善良なノードがCPU能力の大半を占めていれば、攻撃者による偽造は計算論的にほとんど不可能である。本ネットワークの形は決まっておらず、素朴な仕組みなので、堅牢性に優れている。さらに、各ノードは協調せずばらばらに動いて良い。そしてすべての情報について、必ず届かなければならないという場所を設ける必要は無く、またベストエフォートで広がれば良い。つまり、ノードはすべて平等に扱える。各ノードはいつネットワークから離れ、再接続しても構わない。その間の演算量証明は他のノードから得られる。ネットワークはCPU能力をもとに投票を実施し、現行のチェーンに対して、正しいブロックを追加し不正なブロックを拒否する。この同意メカニズムによりルールが守られ、ネットワークの維持に貢献した各利用者が報酬を得る。
この節は数式が多いので、MathJaXを使用します。古いブラウザでは読めないかもしれません。
個人的には、論文の中で一番面白い節です。
１１ 数学的根拠
正しいチェーンよりも速く、攻撃者が自身のチェーンを伸ばすには、どれ程の計算能力を持てば良いだろうか。ただしこれが成功しても、正当な量以上のコインを生成したり、扱ったことがないコインを他人から盗み出せるようになったりするわけではない。善良なノードは、不正な取引を受け付けず、また不正な取引が埋まったブロックも受け付けないからだ。攻撃者がなし得る詐欺行為は、他人に支払った過去の取引を無効にし、コインを奪い戻すことのみである。それも、取引から時間が経つほど困難になる。
善良なチェーンと攻撃者のチェーンとの闘いは、±1歩ずつのランダムウォークと見なせる。善良なチェーンが1ブロック伸びた場合は1歩進み、攻撃者のチェーンが1ブロック伸びた場合は1歩下がる。
攻撃者のチェーンが、より長い善良なチェーンに追いつく確率は、「ギャンブラー破産問題」の理論を使って計算できる。ギャンブラーは一定額の赤字から開始するが、無限の資金を持ち何回でも賭け続けられるとする。そして、一度でも損益無しの状態になれば勝ちである。その確率は、攻撃者が善良なチェーンに追いつく確率と同じで、次のような式になる[8]。
１０ プライバシー
既存の銀行モデルでは、取引情報へのアクセスを関係者や第三者信頼機関のみに限定することによって、ある程度のプライバシーを維持している。本システムでは、全ての取引を公開するのでこの手法は使えないが、情報の流れを別の方法でせき止め、プライバシーを確保する。それは、公開鍵を匿名にすることである。ある額を誰かが誰かに送金したことは全参加者に知られるが、他に情報がなければ、どういった人物が取引に関わったかは見抜かれない。株式市場で言えば、取引の時刻や額を示すティッカーテープが公になっても、誰が売買したかはわからないのと同じことである。
９ コインの融合と分離
ビットコインでは、コインを一枚一枚別々に処理するので、そのままではすべての送金を最小単位に分割せざるを得ず、不便である。そこで、1度の取引に複数のインプット（前回の取引への参照）と複数のアウトプット（支払先のビットコインアドレスと支払額）を設け、コイン額を融合・分離できるように作られている。あらかたの場合、インプットは、過去のより大きな取引への参照か、複数の小さな取引への参照を寄せ集めたものになるだろう。対してアウトプットは、受取人への支払いと、もしあればお釣りの返却とで成り立つ。
８ 取引の簡易検証法
取引を検証するだけで良いなら、ノードの役割をすべて果たす必要はない。その代わりに普段は、最長チェーン内の各ブロックヘッダーを、それを確実に持っているノードに要求して手に入れておけば良い。そして検証時には、その取引を含むブロックのハッシュ木を要求する。ユーザ単独では取引を検証できないが、そのブロックを調べれば、ネットワーク上のいずれかのノードが取引を受け入れたと確認できる。また、その後にブロックが連なっていれば、ネットワーク全体が取引を承認したこともわかる。
７ 使用ディスクスペースの節約
コインの取引履歴が十分な数のブロックに埋め込まれたら、使用ディスクスペースを節約するために、古い履歴を消去しても構わない。取引情報のデータ構造にはハッシュ木[7][2][5]を採用しているので、データを消去しても、ブロックのハッシュ値は変わらない。ハッシュ木の性質により、そのルートハッシュ値は取引データ全体のハッシュ値になる。この値はブロックのヘッダーに格納されている。古くなったブロックでは、ハッシュ木の枝を刈り取ってサイズを縮小できるが、この際、途中の不要なハッシュ値も削除可能である。
ビットコインのシステムは、誰かが演算量証明を行うことにより成り立ちますが、演算量証明には電気代などのコストがかかります。コストを嫌がって誰もコンピュータを動かさなかったら、僅かなCPU能力でビットコインの世界を乗っ取れてしまいます。ではどうするか。そこも考えてあります。
６ ネットワーク参加者への報酬
ブロックの最初には、特殊な取引が記述される。ここに書かれるのは、コインが新たに生まれ、それをブロックの生成者が所有したという情報である。ブロックの生成者にコインを与えることは、各ノードがネットワークを維持する動機となり、また中央機関が権力を使ってコインを配分する代わりの枠組みともなる。新たなコインが一定量ずつ生まれることは、金鉱採掘に例えれば、資金を投入して金を採掘し流通に乗せることに該当する。資金に当たるのは、本システムではCPU時間や電力である。
博物ふぇすてぃばる！という、博物学に関連したイベントが8月に開催されます。これにピッチブレンドも参加させていただくことになりました。同人誌中心のサークルなので大丈夫だろうかとためらったのですが、主催者さんにも是非と言われたので、出展してみることにしました。が、参加する他サークルさんの情報を見て、正直ビビっています……。
ピッチブレンドが持って行くのは、
を予定しています。クルタ計算機の実物も持参したいですね。ブースの詳しい情報は、追ってお知らせします。
最近のコメント