わかりやすくブロックチェーンを説明してみる（第3回）：時間のかかる計算問題とは？
はじめに
ブロックチェーンの本質は「データ分散（コピー）」技術です。
前回（第2回）は世界中のコンピュータで同じデータを持たせるには「誰か1人」を決めればよい、そして「時間のかかる計算問題」を一番早く解いた人をその「誰か1人」とする、ということについてお話しました。
今回（第3回）は「時間のかかる計算」の具体的な内容について説明します。
なお本連載はビットコインやブロックチェーンを技術的な側面から解説することを目的としています。ビットコインへの投資を勧める連載では決してありません。
ハッシュ関数とSHA-256
「時間のかかる計算問題」として必要な要素は、
- 解くのには時間がかかる
- 検算（答え合わせ）は一瞬で完了する
でした。
実はこれにうってつけの計算問題があります。それは「ハッシュ関数」を利用するものです。
「ハッシュ関数」というと何か仰々しく聞こえますが、「ハッシュ」は「ハッシュドビーフ」の「ハッシュ」です。なぜ「ハッシュ関数」と呼ばれるかについては以降の説明を読んだ後にわかるかと思います。
ハッシュ関数の特徴を下図に示します。
ハッシュ関数の特徴１：出力の長さはいつも同じ
上図に示したようにハッシュ関数はどんな長さのデータを入力しても常に同じ長さの0と1の並びが出力されます。例えば1文字だけを入力した場合でも、1000文字入力した場合でも、どちらに対しても同じ長さの0と1の並びが出力されます。長さは同じですが、0と1の並び方は変わります。
そして出力の長さが256個となるハッシュ関数の1つに、SHA-256(Secure Hash Algorithm 256-bit)と呼ばれる関数があります。
SHA-256関数は、どのような入力列に対しても必ず256個の0と1の並びを出力します。
ハッシュ関数の特徴2：入力が少し変わっただけでも出力はがらりと変わる
ハッシュ関数は入力列が少し変わっただけでも出力はがらりと変わります。例えばSHA-256に1000文字を入力する場合と、1000文字のうちの1文字だけを変えて入力した場合では、256個の出力は0と1の並びががらりとかわります。
ただしSHA-256への入力列が前回と同じであれば、SHA-256の出力も必ず前回の出力と同じになります。つまり、入力列が変わらなければ出力は同じで、入力列が少し変わっただけでも出力ががらりと変わります。
入力列が異なれば出力も必ず異なります。ただし、同じ出力を持つ異なる入力列が理論上は存在します。しかしそのような入力列に出会う確率は非常に低く、実用上は「入力列が異なれば出力も必ず異なる」として問題ないとされています。
ハッシュ関数の特徴3：出力を見ても入力の値は推測できない
ハッシュ関数はその出力の値を見て、入力がどのような値だったのかを推測することができません。
「ハッシュ」の意味
以上がハッシュ関数の特徴です。ではなぜ「ハッシュ」と呼ばれるているのでしょうか？「ハッシュドビーフ」の「ハッシュ」は「細切れにする」という意味です。ハッシュ関数への各入力列に対して、IDとしてハッシュ値を割り当てるとします。このとき、よく似た2つの入力列があってもそれぞれの入力列に対して全く違うID（ハッシュ値）が割り当てることができます。これはよく似た複数のデータをバラバラにしていることに他なりません。
ハッシュ関数の具体的な中身についてはここでは説明しません。SHA-256については多くの書籍やWEBサイトにおいて説明されていますので興味のある方はそれらを参考にして下さい。ハッシュ関数の中身について知らなくてもブロックチェーンの本質について理解するこは可能です。
ハッシュ関数(SHA-256)を使った計算問題
「時間のかかる計算問題」にハッシュ関数を利用するのですが、実はハッシュ関数の実行そのものはそんなに時間はかかりません。ではどうやって時間のかかる計算問題を作っているのでしょうか？
nonce
「時間のかかる計算問題」について以下の図を使って説明します。
上図に示したようにビットコインのマイニングでは、以下のデータをSHA-256関数に入力します。実際には以下のデータを連結し1つのデータ列としてSHA-256に入力します。
- ブロックのデータ
- nonce(ナンス）と呼ばれるデータ
ブロックは前回（第2回）で説明したように、送金情報の集まりです。
nonce（ナンス）はなにやら難しそうな用語ですが、単なる整数値です。nonceは「その場限りの」とか「臨時の」などという意味です。
上図にあるようにビットコインではSHA-256を2回実行します。実行の手順は以下の通りです。
- nonce=0にします。
- ブロックデータとnonceを連結してSHA-256を2回実行します。
- SHA-256の出力をみます。上図では出力は011011011010・・・（全部で256個の0と1の並び）となっています。
- 次にnonce=1にします。
- ブロックデータとnonceを連結してSHA-256を2回実行します。(ブロックデータはnonce=0のときと同じデータを使用）
- SHA-256の出力を見ます。上図では出力は101010100111・・・（全部で256個の0と1の並び）となっています。
- 次にnonce=2にします。
- 以降、nonceを増やしながら上記を繰り返します。
以降、nonceの値を次々と変化（増加）させて各nonceごとにSHA-256の出力を見ていると、あるnonce値のときに偶然に先頭から何桁（何ビット）も0が連続する場合があります。このようにSHA-256の出力に0が連続するような入力nonceの値を見つけることが、ビットコインにおける「時間のかかる計算問題」なのです。
難易度の見直し
2021年4月の時点では先頭から0が約80個連続するようなnonceの値を求める必要があります。0が約80個連続するようなnonceを見つけるには平均して10分程度かかるようになっています。では、すごい高性能なコンピュータが出てきてあっという間にnonceを見つけらるようになった場合はどうするのでしょうか？その場合は、計算問題の難易度が上がります。例えば連続数を80個ではなく81個にするといった具合です。この難易度はビットコイン・ネットワークが自動的に調整します。ようは、やたら短時間にnonceを見つける人が増えてきたら難易度を上げるわけです。
難易度の見直しについてもう少し説明しておきます。ビットコインでは2016ブロックごとに難易度を見直します。過去の2016個のブロックにおいて各ブロックに対するnonce発見時間が平均して10分以下になっていれば難易度を上げます。10分という時間はあくまでも平均であり、あるブロックに対しては1分でnonceを見つけることができ、あるブッロクに対しては30分でnonceを見つけられた、という具合にnonce発見にかかる時間にはブロックによりバラつきがあります。
このようなnonceを見つけるにはnonceを0,1,2,3…と値を変えてSHA-256を計算し、しらみつぶしに調べていくしかありません。目的のnonce値を素早く求める方法を見つけたとしたらその時点であなたは大金持ちです。なぜならマイニングのたびに常に誰よりも1番早くnonceを見つけ、そのたびに報酬としてビットコインがもらえるからです。
しかし残念ながらそのような効率の良い方法は今のところ見つかっていないとされています。
nonceの検算（答え合わせ）
Tさんが見つけたnonceとブロックデータは、ビットコイン・ネットワークを通して世界中のコンピュータに転送されます。世界中の各コンピュータは転送されてきたブロックデータとnonceを使ってSHA-256の計算をし、0が80個（80個はあくまでも例です）連続していることを確認します。この確認はSHA-256の計算を1度だけすればよいので一瞬で完了します。0が80個連続していることを確認したらTさんを代表者として認め、Tさんから転送されてきたブロックデータとnonce値を取引台帳に書き込みます。
これにより、ビットコイン・ネットワークに接続しているすべてのコンピュータは同じ内容の取引台帳を持つことになります。
SHA-256への入力は「ブロック」
先の図にもあったようにSHA-256の入力はブロックなのですが、もう少し具体的にビットコインにおける「ブロック」について見ておきたい思います。
上図に示したようにブロックは前回（第2回）で説明した通り、トランザクション（各送金情報）の集まりです。ブロックには「ブロックヘッダ」と呼ばれる部分があります。ブロックヘッダは上図の右側に示してあります。実はSHA-256へはこのブロックヘッダを入力列として入力します。
ブロックヘッダの中身を少し見てみます。
ブロックヘッダにはnonceが書かれています。これはマイニングによりnonceを見つけた人が書いたものです。
またブロックヘッダには「1つ前のブロックのハッシュ値」が書かれています。
マイニングによりnonceを見つけた人は自分が保存しているブロックチェーン（取引台帳）においてこれまで最新であったブロックOLDの先に新しいブロックNEWをつなげます。どうやってつなげるかというと、新しいブロックNEWのヘッダに「1つ前のブロックヘッダハッシュ値」としてブロックOLDのハッシュ値を書きます。ちょっとややこしいですが、後で図が出てきます
こうしておけばブロックNEWの一つ前のブロックを探す必要が出た場合は、ブロックNEWに書かれている「1つ前のブロックヘッダハッシュ値」と同じハッシュ値を持つブロックを探せばよいわけです。ただし、各ブロックのハッシュ値はブロックチェーン（取引台帳）には記録されていません。このための各ブロックのハッシュ値を計算しながら探していく必要があります。しかしさすがに検索のたびに各ブロックのハッシュ値を計算していては時間がかかるので一度各ブロックとハッシュ値の対応表を作ってディスクではなくメモリ上に保管されます。
ブロックヘッダには「マークルツリーのrootハッシュ」というものも書かれてます。詳細は割愛しますが、ざっくり言うとブロック内の各トランザクションを連結してSHA-256に入力して求めたハッシュ値です（正確には少し違いますが）。つまりブロックの内容を代表した（ID化した）ものです。
取引台帳を改ざんするには・・・
取引台帳にある過去の取引内容を改ざんする場合をここで考えてみます。これは世の中でよく説明される点です。しかしマイニングの主目的はこの「改ざん防止」ではないことに注意してください。マイニングの目的はあくまでも「1人を決める」ことです。そして何のために「１人を決める」かというと、全員が持つ取引台帳（ブロックチェーン）の中身を同じするためです。以下で説明する「改ざん防止」効果はあくまでもマイニングによる副産物のようなものです。
以降、長々と説明が続きますが、ようは「ブロックチェーンを改ざんするには多数のブロックのnonceを1人で再度計算（発見）しなおす必要があり、それはほぼ不可能」ということです。本来なら各種「改ざん」の定義を行い、「改ざん」の種類ごとに説明する必要があるのですが、雰囲気をつかむだけなら以降の説明でよいかと思います。
過去の取引内容を改ざんする例として、過去のブロックNの中にあるトランザクション（送金情報）を書き換えることについて考えてみます。実はそもそもこの「書き換え」の意味があいまいなのですが、よくそのように説明されているのでまずはこのシナリオで説明してみたいと思います。
下図に改ざん前のブロックチェーンの様子を示します。
上図においてブロックN内のトランザクション（送金情報）を改ざんした場合の様子を以下に示します。
上図にあるように、ブロックN内のトランザクションを書き換えるとブロックヘッダ―内の「マークルツリーのrootハッシュ」の値が変わります。この結果ブロックNのブロックヘッダ・ハッシュ値が変わります。ブロックNのブロックヘッダ・ハッシュ値が変わってしまうと、ブロック(N+1)からはもうブロックをさかのぼることができません。この場合は、ブロックNが何等かの理由でまだ来ていないと判断され、ブロックNの到着を待つことになります。
また「マークルツリーのrootハッシュ」の値も変わった状態でブロックヘッダに対してハッシュ値を計算すると、ハッシュ値の先頭から0が連続しなくなります。SHA-256の入力（ブロックヘッダの内容）が変わったためです。これにより取引台帳の改ざんが検知できます。
下図に示したように取引台帳に保存されている過去のブロック内のトランザクションを書き換えたのなら、そのブロックヘッダ内の「マークルツリーのrootハッシュ」も書き換える必要があります。これは単にハッシュ値を計算するだけなので簡単です。
改ざんが検知されないようにするためには、ブロック内の「マークルツリーのrootハッシュ」の変更とともにnonce値も書き換える必要があります。つまり書き換えたブロックヘッダに対してSHA-256の結果の先頭から0が連続するようなnonceを見つける必要があります。まさに「マイニング」が必要になります。
しかしこれだけではこの書き換えたブロックNはまだどこからも参照されていません。このため上図にあるように、ブロック(N+1)のブロックヘッダ内の「１つ前のブロックヘッダのハッシュ値」を書き換える必要があります。
ブロック(N+1)のブロックヘッダを書き換えると、今度はブロック(N+1)のブロックヘッダハッシュ値の先頭が0連続にならなくなってしまいます。このため、ブロック(N+1)のnonceを新たに見つける必要があります。
このようににブロックN、N+1、N+2と最新のブロックに至るまですべてのブロックのnonceを自力で見つけなおす必要があります。1つのnoneを見つけるだけでも大変なのに、これはほぼ不可能だ、というのが一般的な説明です。
ところで取引台帳（ブロックチェーン）を書き換える、とは具体的にどこの何を書き換えることを言っているのでしょうか？
- ビットコイン・システムが稼働している１つのコンピュータのディスク上にあるファイル？
- ビットコイン・システムが稼働している世界中のすべてのコンピュータのディスク上にあるファイル？
- とあるコンピュータがバックアップとして保存しているファイル？
- スマホにあるファイル？
- ビットコイン・ネットワーク上を転送中のブロック（送金情報のあつまり）？
- ビットコイン・ネットワーク上を転送中のトランザクション（送金情報）？
このあたりの話をし出すとややこしくなるので、今の時点では「改ざんするには多数のブロックのnonceを求めなおす必要があり大変」くらいな理解でよいかと思います。
結局やりたかったことは
これまで説明してきたことをまとめると以下のようになります。
「時間のかかる計算問題」と解くことを、ブロックチェーンの分野ではPoW(Proof of Work)と呼んでいます。
余談
PoWにnonce問題を採用するアイデアはサトシ・ナカモト氏オリジナルのアイデアではありません。
以下に示すように1990年代からアイデアはあったようです。
マイニングプールとは
1人でマイニングすることをソロマイニングと言います。
世界中に競争相手がいるので1人でマイニングをする場合は成功する可能性は低いです。へたをすると一度も成功しないかも知れません。マイニング用のコンピュータのために多額の電気代を支払い、結局何も得られない、というケースも考えらます。
そこで考え出されたのがマイニングプールです。マイニングプールの概念を下図に示しました。
マイニングプールでは複数人数でマイニングを行います。複数人数で行うの意味は、しらみつぶしに調べるnonceの各値をそれぞれ分担するという意味です。例えばAさんはnonceとして0~1000000を使ってハッシュ値を計算し、ハッシュ値の先頭に0が連続するかを調べます。Bさんはnonceとして1000001~2000000を使ってハッシュ値を計算し、ハッシュ値の先頭に0が連続するかを調べます。0~1000000といった値の範囲はあくまでも説明のために示した例であり実際の分担方法とは関係ありません。
といった具合に複数人でマイニングをして誰かが目的のnonceを見つけたら報酬として得られるビットコインを山分けをするのがマイニングプールです。
次回
今回（第3回）は、誰か1人を決めるたの「時間のかかる計算問題」としてハッシュ関数(SHA-256)とnonceの話をしました。そしてその「時間のかかる計算問題」を解くにはしらみつぶしに調べる方法しかないことが特徴でした。
以上、第1回から第3回においてビットコイン、ブロックチェーン、マイニングの本質についてはすべて説明しました。
ただし、まだ以下のような数々の疑問が残るのではないでしょうか？
- みんなが同じ計算問題を解いたら、ほぼ同時に解ける人がやっぱり多数出てくるのでは？
- サトシ・ナカモトは送金手数料を安くしたかったのでは？送金手数料の話は？
- ブロックにどれだけ送金情報がまとまったらマイニングをするの？
- 残高情報はどこに？
- ビットコインをスマホで使う場合、スマホでも340GBものファイルを保存するの？
- ビットコインよりも高速に取引可能なブロックチェーンがあるようだけどマイニングには10分必要なのでは？
- そもそも「暗号技術」の話がまったく出てこないが？
次回（第4回）はこれらの疑問について明らかにしていきたいと思います。
