紙と鉛筆でビットコインをマイニング:1日に0.67ハッシュ

紙と鉛筆でビットコインをマイニングするのは現実的なのか? それを試してみることにしました。マイニングに使用されるSHA-256アルゴリズムはかなりシンプルなので、実は手計算でもできることが分かりました。当然ながら、この処理はハードウェアマイニングに比べれば極端に遅くて、全く実用的ではありません。しかし、手作業でアルゴリズムを実行してみると、そのアルゴリズムがどのように働くのか正確に理解するための良い方法になります。


紙と鉛筆によるSHA-256の1ラウンド

マイニングのプロセス

ビットコインのマイニングは、ビットコインシステムのセキュリティの鍵となる部分です。その概念は、ビットコインのマイナーたちが、たくさんのビットコイントランザクションを1つのブロックにグループ化してから、ハッシングと呼ばれる暗号操作を、非常に稀少な特別なハッシュ値を誰かが見つけるまで、膨大な回数だけ繰り返すということです。この時点で、そのブロックはマイニング済みとなり、ビットコインブロックチェーンの一部となります。ハッシング作業そのものが何か有益なことを成し遂げるわけではありませんが、「当たり」のブロックを見つけるのはとても難しいので、ビットコインシステムを乗っ取れるだけのリソースを個人的に持っている人が存在しないことは確実です。マイニングの詳細については、私のビットコインのマイニングについての記事を参照してください。

暗号ハッシュ関数は、入力データのブロックをとり、それよりも小さくて予測不可能な出力を作成します。ハッシュ関数は、所望の出力を得るために「近道」がないように設計されています。ですから、それが見つかるまで、力ずくでブロックをハッシングし続けなければなりません。ビットコインでは、ハッシュ関数は、SHA-256と呼ばれる関数です。セキュリティを高めるために、ビットコインはSHA-256関数を2回適用します。これは、ダブルSHA-256として知られるプロセスです。

ビットコインでは、「当たり」のハッシュとは、十分な数のゼロで始まるハッシュです。[1]複数のゼロで終わる電話番号やナンバープレートが滅多に見つけられないのと同じように、複数のゼロで始まるハッシュはなかなか見つけられません。しかし、ビットコインでは、問題は指数的に難しくなります。現在のところ、当たりのハッシュであるためには約17個のゼロで始まる必要があるので、当たりのハッシュは、$1.4×10^{20}$個のうち1つしかありません。言い換えれば、当たりのハッシュを見つけるのは、地球上のすべての砂粒から特定の砂粒を見つけるよりも難しいのです。

次の図は、ビットコインのブロックチェーンの中の1つのブロックと、そのハッシュを示します。黄色のバイトがハッシングされてブロックハッシュが生成されます。この図では、結果のハッシュは十分なゼロで始まるので、マイニングは成功です。しかし実際には、ハッシュは、ほぼ必ず「はずれ」になります。その場合、マイナーはnonce値または他のブロックコンテンツを変更し、再びマイニングを試みます。


ビットコインブロックの構造

ビットコインで使われるSHA-256ハッシュアルゴリズム

SHA-256ハッシュアルゴリズムは、複数の512ビット(すなわち64バイト)ブロックを入力にとり、データを暗号的に結合して、256ビット(32バイト)の出力を作成します。SHA-256アルゴリズムでは、比較的単純なラウンドが64回繰り返されます。下の図は1回のラウンドを示し、AからHの8つの4バイト入力をとり、いくつか演算を行ってから、AからHの新しい値を生成します。


SHA-256アルゴリズムの1回のラウンドの、A~Hの8つの入力と、処理ステップと、新しいブロック。元の図はkockmeye作、出典CC BY-SA 3.0

青いボックスでは、暗号的な分析が困難な、非線形な方法で値を混ぜ合わせます。このアルゴリズムは異なる関数をいくつか使用するので、攻撃的な手法を見つけ出すことは困難になっています(もしも当たりのハッシュを生成する数学的な近道を考えつけるなら、ビットコインのマイニングを制覇できるでしょう)。

過半数(majority)ボックスMaは、A、B、Cのビットに注目します。各位置について、ビットの過半数が0であれば0を出力し、それ以外の場合は、1を出力します。つまり、A、B、C内の各位置で、1のビットの数を調べます。その数がゼロまたは1であれば、0を出力します。その数が2または3であれば、1を出力します。

Σ0ボックスは、Aのビットを回転させた3種類の回転バージョンを作り、それらをモジュロ2加算します。言い換えれば、1のビットの数が奇数なら合計は1、それ以外の場合は0になります。加算される3つの値は、Aを右にそれぞれ2ビット、13ビット、22ビット回転させたものです。

選択(choose)ボックスChは、入力Eの値に基づいて出力ビットを選択します。Eの、あるビットが1なら、出力ビットはそれに対応するFのビットです。Eの、あるビットが0なら、出力はそれに対応するGのビットです。このようにして、FとGのビットがEの値に基づいてシャッフルされます。

次のボックスΣ1はEのビットを回転させて加算します。Σ0に似ていますが、シフトするビット数が6、11、25である点が異なります。

赤いボックスは32ビット加算を行い、AとEの新しい値を生成します。入力Wtは入力データに基づき、少し処理を施されます。(ここが、入力ブロックがアルゴリズムに送り込まれる所です)。入力Ktは、各ラウンドについて定められた定数です。[2]

上の図から分かるように、1つのラウンドではAとEのみが変更されます。他の値は変更されずに通過し、古いA値が新しいB値になり、古いB値が新しいC値になり、以下同様になります。SHA-256の各回のラウンドではデータはあまり変更されませんが、64回のラウンドの後には、データは完全にスクランブルされています。[3]

手作業によるマイニング

次の動画は、上記のSHA-256ハッシングの手順を紙と鉛筆で行っている様子です。あるブロックをマイニングするためのハッシングの、最初のラウンドを行ってみました。このラウンドを終えるのに、16分45秒かかりました。

紙に書かれている内容を説明しましょう。ブロックAからHをそれぞれ16進数で別々の行に書き、その下にバイナリ値を書きました。maj演算の結果をCの下に書き、シフト結果とΣ0をAの行の上に書きました。同様に、choose演算の結果はGの下に、シフト結果とΣ1はEの上にあります。右下では、いくつかの項が加算されており、これは、最初の3つの赤い加算ボックスに対応します。右上では、この加算結果を使用して新しいA値が作られ、右の真ん中あたりで、この加算結果を使用して新しいE値が作られています。これらのステップはどれも、図と前述した説明に対応しています。

次に、別のラウンドも手作業でやってみました。これは、このビットコインブロックのハッシングを完了するための最終ラウンドです。次の画像で、ハッシュ結果には黄色のマーカーがついています。このハッシュのゼロを見ると、このハッシュが「当たり」だということが分かります。ゼロがハッシュの後ろにあることに注意してください。その理由は、不便なことに、SHA-256の生成したバイトをすべて、ビットコインが反転させるからです[4]


SHA-256の紙と鉛筆による最終ラウンド。マイニングに成功したビットコインブロックです。

マイニング用ハードウェアにとって、この結果が意味することとは?

SHA-256の各ステップは、単純なブーリアン演算と32ビット加算なので、デジタルロジックに簡単に実装することができます(電子工学を学んだことのある人なら、もう既に回路が頭に浮かんでいることでしょう)。この理由から、SHA-256アルゴリズムをカスタムのASCIチップに非常に効率的にハードウェア実装して、1つのチップで数百ラウンドを並列に行うことができます。次の画像は、1秒あたり20~30億のハッシュ計算が可能なマイニングチップです。Zeptobarsには、さらに多くの画像があります。


Bitfury ASICチップ内の半導体ダイ。このチップは1秒あたり2~3ギガハッシュでビットコインのマイニングを行います。画像出典:Zeptobars(CC BY 3.0)

これとは対照的に、ライトコイン、ドージコインなどの類似の仮想通貨ではscryptハッシュアルゴリズムが使われており、このアルゴリズムはハードウェアへの実装が困難になるように意図的に設計されています。このアルゴリズムは1024の異なるハッシュ値をメモリに格納してから、それらを予測不可能な方法で結合して、最終結果を得ます。その結果、scryptでは、SHA-256ハッシュよりもずっと多くの回路とメモリが必要になります。マイニング用ハードウェアを調べて見ると、その影響が分かります。scrypt(ライトコインなど)用のものは、SHA-256(ビットコイン)用の数千分の1という遅さです。

まとめ

SHA-256アルゴリズムは驚くほど単純なので、手作業でも簡単です(ビットコイントランザクションに署名するための楕円曲線アルゴリズムを手作業で行うとすれば、32バイト整数の乗算が多数あるので、非常に苦痛を伴うでしょう)。SHA-256を手作業で1ラウンド行うのに要した時間は、16分45秒でした。この速度でビットコインのブロック全体をハッシングするには(128ラウンド)[3]1.49日を要し、ハッシュ速度は1日に0.67ハッシュです(練習すれば速くなるでしょうが)。それに比較して、現在のビットコインマイニング用ハードウェアは、1秒に数テラのハッシュを行い、手作業によるハッシングの$10^{18}$倍の速さです。言うまでもなく、手作業のビットコインマイニングは全く実用的ではありません。[5]

あるReddit読者に、私のエネルギー消費に関して質問されました。それほどの身体的活動ではないので、安静時の代謝率1500kcal/日を仮定すると、手作業のハッシングは、1ハッシュあたり約10メガジュールを消費します。マイニング用ハードウェアの典型的なエネルギー消費は、1ジュールあたり1000メガハッシュです。よって、私のエネルギー効率は、ハードウェアの$10^{16}$分の1です。次の問題は、エネルギー費用です。安い食物エネルギー源として、ドーナツは、$0.23で200kcalです。ここの電気料金は$0.15/キロワット時で、ドーナツの6.7分の1の価格です。思ったより差が少ないですね。よって、私の1ハッシュあたりのエネルギー費用は、マイニング用ハードウェアの約$67×10^{15}$倍です。もちろん、手作業のマイニングで大儲けしようとしているわけではありませんし、必要になる紙と鉛筆の全費用も計算に入れていません。

2017年編集:私の手書きビットコインマイニングシステムは、書籍The Objects That Power the Global Economyの一部に収録されています。ぜひご覧ください。

最新のブログ記事については、Twitterで私をフォローしてください。

注記:

[1] 厳密には、重要なのはハッシュの先頭のゼロの数ではありません。正確には、ハッシュは、現在のビットコインの難度に応じた特定の値よりも小さくなければならないのです。

[2] SHA-256で使用される定数のソースは興味深いものです。SHA-256アルゴリズムはNSAが設計し、定数の値を選びました。ハッシュを壊すような特定の値をどうやって避けたのでしょうか? 嫌疑を避けるために、初期のハッシュ値は最初の8つの素数の平方根からとられ、Ktの値は最初の64個の素数の立方根からとられました。これらの定数は簡単な式から作られるので、NSAが(少なくとも定数に関して)疑わしい行為をしなかったと信じることができます。

[3] SHA-256ハッシュは512ビットのブロックに対して機能しますが、残念ながら、ビットコインのブロックヘッダは512ビットより長いのです。よって、ビットコインブロックの後半について、64回のSHA-256ハッシュラウンドからなる第2のセットが必要になります。また、ビットコインはダブルSHA-256を使用するので、SHA-256の2回目(64ラウンド)が、結果に対して行われます。これを加えると、任意のビットコインブロックをハッシングするには合計192ラウンドかかります。ただし、実は他に近道があるのです。マイニングでは、同じブロックを、ブロックの後半に出てくるnonceを変えながら何度も繰り返してハッシングします。よって、最初の512ビットのハッシングの結果をマイニングで再利用することができるので、ビットコインブロックのハッシングに必要なのは128ラウンドだけです。

[4] もちろん、私は当たりのハッシュを見つけられるような信じられないほどの幸運の持ち主ではありません。既にマイニングに成功しているブロックを使ってハッシングのプロセスを始めたのです。具体的には、この記事の前の方に表示されているブロック#286819を使用しました。

[5] 手作業によるマイニングのもう1つの問題は、約10分ごとに新しいブロックがマイニングされることです。もし私があるブロックのマイニングに成功したとしても、作業を終えるときには、そのブロックは完全に期限切れ(オーファン)になっているでしょう。