ブロックチェーンとマイニング

How Bitcoin Mining Works

この記事は、ブロックチェーン Advent Calendar 2017の3日目です、たぶん、知らんけど。なんだか前の人と記事の内容が被ってる気もするが、がんばってやっていき。

Proof of Work

みんな、マイニングしてるか!僕はイーサリアムだけどちょっとやってた。ブロックチェーンはその名の通り、ある程度のトランザクション情報をまとめたブロックをチェーンのように繋いでいく分散型台帳システム。

そのブロックを繋げる際に、ビットコインであればproof of work(PoW)というコンセンサス(合意)アルゴリズムを採用しているので、莫大な計算量(Work)を用いて、新たに台帳に記載されるブロックが正しいかどうか承認する作業(Proof)が行われる。

この作業を一番早く正しく終えた人が、その報酬として一定量のビットコイン(2017年現在:12.5BTC)とブロックに含まれるすべてのトランザクション手数料を貰えることができるので、この作業を金の採掘に例えてマイニングと言っている。

なぜ、このような事をするのかというと、前述の通りブロックチェーンは分散台帳なので、誰でも手元にダウンロードすることができ、もし悪意のある誰かが自分のアドレスに100BTC振り込むといった偽の情報をブロックに入れたとしたら大変。しかし、そのような偽のチェーンはマイニングするのは、微々たる計算量しかもたない、その人しかおらず、チェーンを続けることはできないので、正当性のあるチェーンだけが生き残る算段。

中央集権的なデータベースであれば、このようなマイニングをする必要はないが、特定の誰か(個人・企業)を信じなければならいし、その人が善人であったとしても、また他の誰かからハッキングされるかもしれない。それに比べて、ブロックチェーンであれば誰も信頼する必要がないし、 マイニング報酬というインセンティブで多くのマイナーが計算量を提供しシステムを維持しているので改ざんは極めて困難だ。

と、こんなことぜんぜん分からなくても、僕自身イーサリアムでマイニングしてたので問題はないんだけど、もうちょっと技術的に理解したいと思い、積読してあったマスタリングビットコインを読んでみたよ。

Cryptographic Hash Functions

マイニングで計算、計算って言ってるけど、実際に何してるのってことで、ハッシュ関数をいっぱい実行している。

ハッシュ関数 (ハッシュかんすう、英: hash function) あるいは要約関数とは、あるデータが与えられた場合にそのデータを代表する数値を得る操作、または、その様な数値を得るための関数のこと。ハッシュ関数から得られた数値のことを要約値やハッシュ値または単にハッシュという。

Wikipediaはかくゆう。

実際に動かしたほうが早いので、Node.jsのcryptoモジュールを使って、t32kという文字列をハッシュ化してみる。

const crypto = require('crypto');
const shas256 = crypto.createHash('sha256');
shas256.update('t32k');
const hash = shas256.digest('hex');
console.log(hash);

>> 69511c70d742fda9555512fea208338e1c49cb3e9ab0a1e3246e262952517806

ビットコインではSHA-256(Secure Hash Algorithm)を用いて、ハッシュ化されるので、t32kの元データが64文字の16進数文字列に変換された。これは何回実行したところでt32kの文字列は69511c7...の同じハッシュ値である。

また変換する文字列t32kから、t33kに変更してみると以下のようハッシュ値ができあがる。

>> 719e66ad70e70e39b9627ec4fd5dfb8a7015c3be5ac35f48c4d3a60b8aeed4f9

たった一文字だけ違うのに、全く異なるハッシュ値ができあがるので、生成されたハッシュ値から元データを推測するのは困難であり、暗号数理的性質をもつ。

では、ビットコインのマイニングでハッシュ関数はどのように使われてるか見てみる前に、ここではマイニングをチョー簡略化した例をやってみよう。

t32kの文字列のお尻に数字を付けてインプットとし、出来上がるハッシュ値の先頭が0で始まる数字を見つけることにする。

試しに0~9の数値で試してみることにする。

const crypto = require('crypto');

let n = 0;

while (n < 10) {
	const shas256 = crypto.createHash('sha256');
	const input = 't32k' + n;
	shas256.update(input);
	const hash = shas256.digest('hex');
	console.log(`HASH-${n}`, hash);
	n++;
}
HASH-0 46a26cdf4f1f6825d191e66f2c2c00cea62993909b559ddc9682a102bf5c44ed
HASH-1 ea179996e7010c1cf52a6e291dc8c052fc8e9bad41f5007b2a403bfa8b758ad1
HASH-2 39e402b62052d67cd97d469a792b2147cfde04bea6ed1826a88d1fffff9fccd9
HASH-3 c5015b15ae1f3f7b48bd0a21b93efa36ab5909078e8d0ff6104fc66e8c8281f7
HASH-4 033e3bf0ca03bd4ae08ab1578fce35ae1f1edeeb753cd0ebe1813012e8522d45
HASH-5 f2a87d02c46abbbba83a2d04c600faf4df5a04d438753eb86e92d9f3e4c0899a
HASH-6 8a91c41c4fedacba77199887745996b5064e678dbdee63870253e8cb3e653ddd
HASH-7 ae040ca8afcb5f6ecc5ab21471c1d1064c1612f20b6ab83098f59a4d508cdcc9
HASH-8 7629b92d6e54b01065e17d131215bfae92f1a772e47fe7faf2412d179bcb8e00
HASH-9 1e04407ced654405978eacd00f66537b931f6e5d5c750e7d222b3b7d0b099a5d

運良く、5回目で033e3bf0ca...というハッシュ値を見つけることができた。ということで与えられた課題に対する答え(数値)は4になる。ビットコインのマイニングも掛け合わせる文字列はもっと多いが基本的にやってることといえば、この数値、ナンス(nonce:暗号通信で用いられる使い捨てのランダムな値)を探すことにほかならない。

ただ、求められる難易度はこのサンプルケースの場合と桁違いに難しい。2017年12月現在のビットコインのブロックハッシュ値は先頭から0が18個続くようなとても小さい値になっている。0が1個だけじゃ到底だめだし、16個や17個のような大きな数値はハッシュ値としては認められないのである。

サイコロの例に使えば、2つのサイコロ振り、出た目の総和が12より小さくしろ!と言われれば、両方6が出ない限りほぼ成功できるが、総和が5の場合だったらどうだろう。とたんに難しくなる。このように値が小さければ小さいほど難易度は格段に難しくなるので、ビットコインマイニングの場合は、サイコロを何千兆回と振らなければならない(ナンスを探さなければならない)。

Hash Chaining

フィールド サイズ 説明
Version 4バイト ソフトウェア・プロトコルバージョン番号
Previous Block Hash 32バイト 1つ前のブロックのハッシュ
Merkle Root 32バイト ブロック内すべてのTXに関するマークルツリーのrootハッシュ
Timestamp 4バイト ブロックのおおよその生成時刻(Unix秒)
Difficulty Target 4バイト ブロック生成時のdifficulty
Nonce 4バイト !!!コイツを求める!!!

ブロックチェーンはある程度のトランザクション情報がまとまったブロックがチェーンでつながっていると述べたが、各ブロックは上記のヘッダー情報を持っている。フィールドに Previous Block Hashが入ってるので、求めるハッシュは前のブロックに影響を受ける。

このブロックヘッダをSHA-256で2回ハッシュした値が、Difficulty Targetよりも小さな値(先頭から0が何十個も続くようなハッシュ値)であれば、ブロックをチェーンにつなげることができる。

{
	"hash": "0000000000000000001b09f6b279c46eca668d8403f7667c8420f6af0e091fff",
	"confirmations": 3,
	"strippedsize": 983850,
	"size": 1046572,
	"weight": 3998122,
	"height": 497327,
	"version": 536870912,
	"versionHex": "20000000",
	"merkleroot": "137e5fede907ce0702b5b6fa200887decbeecdd4cfdad924fb253b475ed31c77",
	"tx": [
		"f3810f2f169c43741cf43796d675efe170875af58bfd7577b9da0a1adc84b782",
		........
		"9590f9fecc80b62022ba21c9e3c2eef391d3dfebc42837f18a1a4117bcd49244"
	],
	"time": 1512287387,
	"mediantime": 1512284779,
	"nonce": 3429537634,
	"bits": "1800d0f6",
	"difficulty": 1347001430558.57,
	"chainwork": "000000000000000000000000000000000000000000bf0b7d29b7b36413c84f60",
	"previousblockhash": "000000000000000000883f5ccff5b7140e4d10bf85f6aed570b8bc6f62330542",
	"nextblockhash": "000000000000000000605538204e452c5cfdd9937a3ffe157ff2d91f692ba313"
}

ブロック#497327のブロック情報の例(Transactionは一部省略)

なお、このDifficultyは2016ブロック生成(約2週間)されるたびに、直近の2016ブロック生成にかかった時間を元に調整される。

Merkle Trees

ブロックのヘッダーにひとつ解せさないものがある。Merkle Rootとはなんだ?ということで、マークルツリーに興味を持った。マークルツリーというのは、公開鍵暗号の開発者の一人であるラルフ・マークルによって発明された、データを要約したハッシュツリーのことだ。

ビットコインではブロック内のトランザクション全体の要約のために使われている。ブロック内のトランザクションデータはハッシュ関数にかけられ、さらに隣り合うハッシュ値をあわせてハッシュ関数にかけられる。このようにかけあわせていくことで、何百というトランザクションはひとつのハッシュで表すことができる。これがマークルルートのハッシュだ。

ちなみに、先頭のトランザクションはコインベーストランザクションと呼ばれるものである。通常のトランザクションは必ずインプット元のトランザクションデータがあるが、コインベースにはない。それはマイニングで得た報酬を得るマイナーのアドレスが含まれたトランザクションであるため、無からビットコインが生まれる瞬間である。

さらちなみに、ハッシュレートの向上により、4バイトのナンスでは一瞬で探索できるようになってきたので、コインベーストランザクションの一部をエキストラナンス8バイトも使うことで毎秒2の96乗通り試すことができる。

51% Attack

Hash Rateの推移

マイニングには莫大な計算量が必要だと理解できたが、現在のビットコインマイニングは個人がどうこうレベルではない。CPUやGPUよりも多くの計算ができるASIC(特定用途向け集積回路)を何千台と用意した事業者が幅をきかせている。だからといって、個人はマイニングに参加できないかというとそうでもない。

マイニングプールというマイナー同士が協力しあって計算リソースを提供し、その貢献度によってマイニングで得た報酬を分配されるしくみがある。マイニングプールに参加しているマイナーが、もし実際にナンスを見つけたとしても、その人には12.5BTC全部はもらえない、そのプールに貢献した計算リソース分しかもらえないのである。まぁそんなことは一般個人には確率的にほぼない に等しいので、マイニングプールで少量ながらも稼ぐのが現実的である。

そういうわけで、そんな人のために世界にはいくつかのマイニングプールがある。

上記グラフは2017年12月のマイニングシェアを表したものだが、上位はほぼ中国勢に抑えられている。各プール業者の割合は10%前後だが、もしこれらの業者が5つ、6つ結託して、マイニングシェアの51%以上を取ったとしたらどうなるだろう。多くの個人マイナーが参加しているマイニングプールとはいえ、それはマネージドされた環境であり、我々の計算リソースはプールの管理者に委ねられているので、悪意のあるデータに改ざんしたチェーンを作成、維持していくには十分なりソースがあるということになる。

51%以上のシェアがあるからといって、誰かのビットコインを盗むことも、署名なしにビットコインを使うことも、ビットコインの支払先をか書き換えることも、過去のトランザクションや記録の所有者を変えることもできない。しかし、これから行われる取引に対して、ダブルスペンド(二重使用)が可能となる。ただこれも改ざん不可能と考えられている6承認(Six Confirmations)を待ってからビットコインの支払いを受けつけるようにすれば回避できるかもしれない。

なににせよ、特定の誰かがマイニングシェアを牛耳ることは、非中央集権のシステムではよくない。GMO、DMM、SBIなどの日本勢がマイニング事業に乗り出すということなので、願わくば頑張っていい感じにして欲しい(雑)。

おわり。

4日目の@sonatardがもっと詳しい記事書いてくれてる。

参考