Proof of Workってなんだろう？
Bitcoinを勉強していると必ず出てくるワード、「Proof of Work」。「仕事の証明」ってなに？、タイムシートのこと？と思われる方も多いかと思います（いない）。自分の中でも細かな点はモヤモヤがあった部分ですので、今回はこのProof of Workを少し深掘りして説明することで、モヤモヤを解消していこうと思います。
Proof of Workの辞書的定義
まず言葉の定義からしたいと思います。Bitcoin界の聖書、サトシナカモト論文では次のようにProof of Workを記載しています。
The proof-of-work involves scanning for a value...The proof-of-work (also) solves the problem of determining representation.
「Proof of Workはある値を探し出すという行為である。（中略）これにより、（分散型ネットワークで）一意に合意するという問題を解決する」（ざっくり訳）
ここでいう「一意に合意する」とは、「トランザクションを含んでいるブロック」を一意に確定させることを指しています。それでは、まず一意にブロックを確定させるアプローチの概要を説明し、その次に技術的にどのように実現しているか（ある値とは何か？どのように探し出すのか？）を確認していこうと思います。
Proof of Workの概要
まずはBitcoinの取引の流れを振り返り、そこから生じる疑問を解決することでProof of Workによって、どのようにブロックが確定するの確認していこうと思います。
Bitcoinの取引の流れ
まず、Bitcoinの取引の流れを簡単におさらいします。
最初にBitcoinの送金者は送金内容をネットワーク上にアナウンスします。アナウンスされた送金内容は各ノードで検証され、取引内容に問題がなければ各ノードで保存されます。非常に単純な仕組みですが、この仕組みだけでは二重送金の問題を解決できていません。
例えばAさんがBさんに対して1BTCを送金した後で、Aさんが同じコインを利用して、1BTCをCさんに送金したとします。このとき、各ノードとしてはA→Bの取引と、A→Cの取引のどちらを正当なものと扱うかを決めないといけません。ノードによって正当な取引が異なっていると、決済ネットワークとしての機能を果たせていないことになってしまいます。
アプローチとしてはいくつかありますが、まず一番に考えつくのは、最初に受信した取引を正当なものとして扱うというアプローチです。しかし、Bitcoinには中央集権のサーバはなく、分散ネットワーク上で各ノードが取引内容を検証するので、あるノードはA→Bの取引を正当なものとして扱い、別のノードはA→Cの取引を正当なものとして扱うという状態になってしまう可能性があります。
逆に、「受信したタイミングではなく、送金したタイミングを基準に正当性を確認すればよいのでは？」と考えることもできるかもしれませんが、送金時間は送金者が自由に変更できてしまうので、いつまでたっても取引が安全ではないことになってしまいます。
このように送金した時間や受信した時間など、「タイミング」を基準に取引の正当性を保証することは、分散型ネットワークでは難しいことがわかります。
ブロックチェーンとPoWによるトランザクションの確率的証明
そこで、Bitcoinでは「タイミング」を取引完了の基準に利用せず、「取引が台帳に含まれているかどうか」を基準とするというアプローチで解決しています。つまり、ブロックチェーンという各ノードが管理する台帳を作成し、その台帳に記載されている取引を正当なものとして扱う、というアプローチです。
もちろん、すぐに疑問がわいてくるかと思います。受信したタイミングを基準にしていたときと同じように、「どうやってブロックチェーンを全員同じ形で保有するんだ」という疑問です。ここで登場するのが、マイニングという概念です。冒頭で触れた「ある値を探し出す」という問題を解くことができたノードのブロックを正当なブロックとして定義することで、全員が同じブロックチェーンを参照できる仕組みにしています。この問題を解く一連の行為をマイニングと呼び、マイニングを行うノードをマイナーと呼んでいます。
これで一件落着しそうですが、もうひとつ問題が残っています。「問題を解くことができたブロックを正当なブロックとするアプローチ」では、ほぼ同じタイミングで問題を解くことができたノードが複数現れた場合に、各ノードはどちらのブロックをブロックチェーンにつないだらよいか判断できません。
もちろんこのことをBitcoinでは想定しており、各ノードはどちらのブロックも正当なものとしてブロックを取り扱い、保持することにしています。そして、一番長いブロックチェーンを正当なものとして定義しています（正確には累積Difficultyが最も大きなチェーン）。
以下の図を使って簡単に説明します。まず、最初に受け取ったブロック（ブロック3 (A)）をブロックチェーンにつなぐとともに、2番目に受け取ったブロック (ブロック3 (B)）はセカンダリチェーンという領域に格納されます (下図のInitial Condition)。
各マイナーはどちらのブロックに対して次のブロックを繋ぐかを決定した上で、マイニングを実施します。仮にあるマイナーがセカンダリチェーンのブロックに対してマイニングを行って、一番最初にブロックを発掘したとします。マイナーはそのブロックをBitcoinネットワーク上に通知し、各ノードはそのブロックを検証した上で受け入れていきます。セカンダリチェーンに格納されていたブロックは、プライマリブロックチェーンに移動し、そのブロックに対してマイナーが発掘した新ブロックを繋ぎます。
このようにブロックチェーンは時に分岐し、プライマリブロックチェーンの入れ替えが起こることを許容した仕組みになっています。ブロックチェーンの分岐は過去のどの時点に対しても発生しうるので、Bitcoinは取引を100%は保証できない仕組みになっています。ただ、このことがBitcoinの欠点かというとそんなことはありません。ブロックの作成には次の章で説明するように計算量が必要になり、過去のブロックを変更してあるトランザクションをなかったことにすることは、そのトランザクションを含むブロックから現在のブロックに至るまでの計算量と同じだけの計算量を必要とします。そのため、ブロックが蓄積されるにつれて実質的に100%に近い確率でトランザクションを保証できます。
ナカモト論文内で確率的な証明がされていますが、例えばトランザクションを覆そうとする悪意を持った人がマイニングパワーの10%を保有している場合でも、5ブロック蓄積されれば0.01%の確率でしかそのトランザクションが覆されることはありません。
Proof of Workの技術的な実現方法
次にProof of Workの核となる、「Work」 とはどのようなものなのか、技術的な点も含めて確認していきます。
Bitcoinにおける「Work」のオリジナルな解説は、ナカモト論文でも参照している以下の論文で紹介されています。どのようなものかというと、「先頭N桁が0であるハッシュ値」が見つかるまで、ブロックヘダー（ブロックの要約情報）に対してひたすらハッシュ値の計算を行うというものです。
http://www.hashcash.org/papers/hashcash.pdf
ブロックヘダーにはトランザクションを要約した情報（マークルツリー）、ハッシュ値の何桁目までが0である必要があるかを決定するDifficultyなどの情報とともに、Nonceとよばれる情報が保持されています。このNonceを変更しながらブロックヘダーに対してハッシュ計算を繰り返すことで、先頭N桁が0になるハッシュ値を探していきます。なお、桁数Nを決めるDifficultyは2016ブロックごとに計算し直され、約10分でNonceが発見されるように調整されます。
ハッシュ計算のイメージ
このWorkには重要な特徴があり、最も早く先頭に0がN個並んだハッシュ値を見つける特殊な解法（アルゴリズム）があるわけではなく、ブルートフォース、つまり総当たりをするしかないという点です。これにより、アルゴリズムの優越ではなく、純粋に計算量の多寡に基づいてハッシュ値が発見されることになります。
また、ブロックに含めるトランザクションを変更することで、ブロックヘダー内のマークルルートの値は変化しますので、計算結果として必要なNonceは各マイナーによって異なります。これにより、基本的には計算量の多寡に基づきつつも、必ずしも計算量が多くはないマイナーでもブロックを発掘するチャンスがあります。例えば、計算量の多いマイナーAが取り込んだトランザクションをもとにして作成したブロックヘダーはNonceが1,000,000,000,000,000,000、マイナーBが取り込んだトランザクションをもとにして作成したブロックヘダーはNonceが10の場合、Nonce=0から順番にハッシュ値を検証していった場合は、マイナーBが（計算量にあまりにも差がある場合は負けるかもしれませんが）勝利することになります。
つまり、試行回数を多くすれば計算量の割合に応じて発掘できるブロック数が決まるものの、一回一回の試行では誰でも発掘できるチャンスがある仕組みになっています。ルーレットを続けていくと最終的には確率通りの割合で勝率が決まってきますが、一回一回の試行では2の黒とか3の赤とかどれが出るかはわからないのと同じです。
この計算には大量のメモリは不要で、純粋にコンピューティングパワーのみが必要になってくるので、一般にこのマイニングにはASICとよばれるハッシュ値の計算に特化したハードウェアが利用されます。ASICはハッシュ計算のスピードが圧倒的に早いため、一般のCPUやGPUを使用したPCではマイニングで勝利することはほとんど不可能と言われています。
一方、Ethereumなどで使用されているWorkは、計算に大量のメモリを必要とする仕組みにしています。そのため、ASICを利用したマイニングが原則できない仕組みになっています。思想的には、資本が少ない個人は資本投資ができないためマイニングによる利益を全く享受できない一方、資本の多い特定のマイナーのみが集中的にマイニング利益を得ることができるのは、富の偏りを産むとともに、特定のマイナーが取引の承認行為を支配することによりネットワークの安全性が低下するという発想があるようです。
ASICを利用できる場合の収益イメージ
