«

»

ビットコインの原論文を読む 4節 演算量証明

4 演算量証明

P2Pベースで分散タイムスタンプサーバを実装するためには、新聞やネットニュースなどよりも、むしろアダム・バックのハッシュキャッシュ[6]のようなシステムが必要である。これは、演算に費やした時間を他人に頼らずに証明する手法で、例えば「SHA-256のようなハッシュ関数を通すと最初のnビットがすべて0となるような値」を総当たりで発見することによって実現できる。そのような演算にかかる平均時間は、nに対して指数関数的に増大する。それに対して、検証する側はハッシュ関数を1回計算するだけで良い。

提案するタイムスタンプネットワークでは、ブロックデータとNonceと呼ばれる数字を組み合わせる。Nonceを適当な値から1ずつ増やし続けて、ハッシュ値の最初のnビットがすべて0になる場合を探索する。このようにCPUを使って演算量を証明しておけば、ブロックの内容を改ざんして辻褄を合わせるためには、同じ計算をもう一度行わなくてはならなくなる。さらにその後ろにブロックがチェーンでつながっていたら、それらすべてに対する演算をやり直す必要がある。

fig3

[6] A. Back, “Hashcash – a denial of service counter-measure,” http://www.hashcash.org/papers/hashcash.pdf, 2002.

アダム・バックのハッシュキャッシュというものが出てきました。本来は、電子メールによるSPAM(迷惑メール)を防止するために考案されたシステムです。例えば、すべてのメールシステムが「演算を1秒間実行した証拠が付属していなければメッセージを受け取らない」というポリシーで作られていたとします。するとSPAM業者は、1秒間に1通以上はメールを送れなくなります。それでも1時間に3600通、複数台の高性能コンピュータを使えばさらに大量のメールを送れますが、無制限に送信可能な現状と比べれば、多少はましになるでしょう。

その演算量証明の実装を説明したのが、本節です。ビットコインでは、「全参加者が協力して平均で10分かかる問題」を解きます。演算量証明をチェーンでつなげることによって、例えば24時間前の取引データには、24時間分の演算量証明が重ねられるわけです。

演算量を証明することにより、集団における意思決定をどう行うべきかという問題も解決する。多数決方式を採用し各IPアドレスに1票ずつを割り当てるような方法では、誰かがIPアドレスを大量に確保した時点で制度が崩壊してしまう。

それに対して、演算量証明に基づく本システムは、各CPUに1票を与えるようなものである。実際には、最もCPU能力を費やして作られた情報、すなわち最も長いチェーンを、集団の意思決定の結果であると取り決める。CPU能力の大多数が善良なノードによって構成されていれば、不正がないチェーンが最速で成長し、ねつ造した情報を含むどのチェーンよりも長くなるはずである。もし、攻撃者が過去のブロックを改ざんしようとしたら、それ以降のブロックをすべて計算し直し、善良なノード群が計算するチェーンの長さに追いつき追い越す必要がある。後に示すが、計算能力的に劣る攻撃者が正しいチェーンに追いつける確率は、追いつくべきブロック数に対して指数関数的に小さくなる。

年月が経つと、ハードウェアの速度が向上したり、世間の注目度合いによって参加ノード数が変動したりするだろう。生成されるブロック数がそのような影響を受けないように、演算量証明の難易度(difficulty)が、過去一定期間の生成ブロック数をもとに設定される。ブロックの生成間隔が短すぎる時には、難易度が高くなる。

この辺りがビットコインシステムの神髄で、参加者全員が同じ取引履歴を共有することに関係します。図がないと分かりにくいので、Wikipediaのビットコインの項目も併せて読むと良いでしょう。

これまで「ノード」という単語を未定義で使ってきましたが、ビットコインでは、「採掘」を行っているPCやサーバ、専用マシンなどを指します。ただし、現在は参加者の増大により、一人でブロックを発見できる確率がほとんど0になったため、プール(共同採掘場)に登録して採掘している人がほとんどではないでしょうか。プールはプール全体で見ればノードですが、協力している各PCだけでは、ノードとは言えません。各PCはハッシュ関数を総当たりで試しているだけで、チェーンのデータを持っていないからです。

つまり、現在は集団ではなくプールの管理者が大きな権限を握っています。これは、当初想定されていなかった状況かもしれません。ごく小数の管理者が悪意を持ってネットワークを崩壊させる可能性があるので、将来への課題とすべきでしょう。

difficultyは、ハッシュ値の最初の何ビットを0とするNonceを見つけるかで調整します。平均で10分に1つのブロックを生成するというのは、これで設定します。


コメントを残す

メールアドレスが公開されることはありません。

次の HTMLタグおよび属性が使えます: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>