ブロックチェーン

実装: crypto/blockchain/ / 実行: go test ./crypto/blockchain/

ブロックチェーンは、改竄の値段を計算量で決めた追記専用のログ。各ブロックが前のハッシュを含むので、過去を1つ書き換えると以降が全部壊れる。隠すには後ろを全部作り直すしかない。値段を数えると、難易度を1上げるごとにブロックあたりの試行が16倍になり、総額はそこに作り直す数を掛けたものになる。掛け算の両側が効く。

この章で作るもの

ハッシュチェーンに Proof of Work を足したミニ・ブロックチェーンを作る。暗号通貨の値動きの話ではなく、「中央の管理者なしに、過去を書き換えられない台帳」がどういう仕組みで成り立つのかを見る。

順に見ていく。

前のハッシュを含む: 過去を1つ書き換えると、それ以降の鎖が全部壊れる
作り直しを高くつかせる: 難易度を1上げると、ブロックあたりの試行が16倍になる
値段は掛け算になる: 難易度あたりの試行 × 後ろに積まれたブロック数

① 前のハッシュを含む

各ブロックは、自分の中身に加えて前のブロックのハッシュを持つ。そして自分のハッシュは「中身 + 前のハッシュ」から計算される。

ブロック0        ブロック1              ブロック2
[data: genesis]  [data: alice→bob 10]   [data: bob→carol 5]
[prev: なし  ]   [prev: hash(0) ────]   [prev: hash(1) ────]
[hash: h0    ]   [hash: h1        ]     [hash: h2        ]
      └──────────────┘   └──────────────────┘

ハッシュチェーン。各ブロックのハッシュは前のハッシュを含んで計算される。だから鎖のどこか1つを変えると、それ以降のハッシュが芋づる式に変わる

// Block は1つのブロック。前ブロックのハッシュ(PrevHash)を含むのが鎖の要。
type Block struct {
	Index    int
	Data     string // このブロックの中身(実物は取引の集まり)
	PrevHash string
	Nonce    int    // Proof of Work で総当たりする値
	Hash     string // このブロックのハッシュ(Nonce 込みで計算)
}

// computeHash はブロックの中身から SHA-256 ハッシュを求める。
// Nonce を含めるので、Nonce を変えるとハッシュが総取っ替えになる(PoW で使う)。
func computeHash(b Block) string {
	record := fmt.Sprintf("%d%s%s%d", b.Index, b.Data, b.PrevHash, b.Nonce)
	sum := sha256.Sum256([]byte(record))
	return fmt.Sprintf("%x", sum)
}

ブロック1の中身をこっそり「alice→bob 1000000」に書き換えると、ブロック1のハッシュ h1 が変わる。するとブロック2が持っている「prev: h1」が古い値のままなので食い違う。1つの改竄が、それ以降の鎖を全部壊す。

// Valid はチェーン全体の整合を検証する。
// 各ブロックについて: (1)保存されたハッシュが中身と一致するか、
// (2)難易度を満たすか、(3)PrevHash が本当に前ブロックのハッシュか、を確かめる。
func (c *Chain) Valid() bool {
	prefix := strings.Repeat("0", c.difficulty)
	for i, b := range c.Blocks {
		// (1) 中身から計算し直したハッシュが、保存値と一致するか(改竄検出)。
		if computeHash(b) != b.Hash {
			return false
		}
		// (2) Proof of Work を満たしているか。
		if !strings.HasPrefix(b.Hash, prefix) {
			return false
		}
		// (3) 前ブロックとの繋がり。
		if i > 0 && b.PrevHash != c.Blocks[i-1].Hash {
			return false
		}
	}
	return true
}

ここまでなら、改竄を検出できるだけだ。辻褄を合わせ直せば通ってしまう。改竄したブロックのハッシュを計算し直し、後続の prevHash も順に直していけばいい。ハッシュチェーンだけでは、作り直しの値段がゼロなので改竄を止められない。

② 作り直しを高くつかせる

Proof of Work のルールは1つだけ。ブロックのハッシュが、決められた数の 0 で始まらないと無効とする。ハッシュは中身を少し変えるだけで予測不能に変わるので、条件を満たすハッシュを得るには、ブロックに入れた nonce という数字をひたすら変えて試すしかない。

// remine は Proof of Work: ハッシュが難易度ぶんの 0 で始まるまで Nonce を総当たりする。
// ハッシュは予測できないので、条件を満たす Nonce を見つけるには「ひたすら試す」しかない。
// この計算こそが、改竄を割に合わなくする「コスト」の正体。
//
// 戻り値はハッシュを試した回数。16進で 0 が1つ増えるごとに、
// 当たりを引く確率が16分の1になるので、試行回数はおよそ16倍になる。
func remine(b *Block, difficulty int) int {
	prefix := strings.Repeat("0", difficulty)
	for b.Nonce = 0; ; b.Nonce++ {
		h := computeHash(*b)
		if strings.HasPrefix(h, prefix) {
			b.Hash = h
			return b.Nonce + 1
		}
	}
}

16進のハッシュなので、先頭の1桁が 0 になる確率は16分の1。 0 を1つ増やすたびに、当たりを引く確率が16分の1になる。8ブロックずつ掘って測った:

難易度	1ブロックあたりの試行
1	29 回
2	200 回
3	3,333 回
4	70,329 回

難易度を3上げただけで、2,400倍になっている。指数で増える量を、線形に見えるつまみ1つで動かしているのがこの仕組みの要点になる。テストで、難易度を1上げるごとに試行が4倍以上になることを固定した。1回の当たりは運で揺れるので、8ブロックの平均で見ている。

③ 値段は掛け算になる

ここでハッシュチェーンと組み合わさる。過去を1つ改竄して隠すには、そのブロックと、それ以降の全ブロックを作り直さないといけない。


// Tamper はブロック i の中身をこっそり書き換える。マイニングはしない。
//
// この時点でチェーンは壊れる。書き換えた本人のハッシュが中身と食い違い、
// 次のブロックが持つ「前のハッシュ」とも食い違うためになる。
func (c *Chain) Tamper(i int, data string) {
	c.Blocks[i].Data = data
}

// Repair は i 番目から末尾まで、繋ぎ直しながら再マイニングする。
//
// 改竄を隠すにはこれをやるしかない。1つ直すだけでは、その後ろが壊れたまま残る。
// 戻り値はハッシュを試した回数で、これが改竄の値段になる。
func (c *Chain) Repair(i int) int {
	n := 0
	for ; i < len(c.Blocks); i++ {
		if i > 0 {
			c.Blocks[i].PrevHash = c.Blocks[i-1].Hash
		}
		n += remine(&c.Blocks[i], c.difficulty)
	}
	c.attempts += n
	return n
}

まず、1つだけ直しても足りないことを確かめた。ブロック1を書き換えて、ブロック1だけを掘り直しても、ブロック2が持つ prevHash は古いままなので鎖は壊れたまま残る。テストで、これが通らないことを固定した。

後ろまで全部やり直すと通る。難易度2で、積まれた数を変えて測った:

後ろに積まれたブロック	作り直す数	ハッシュを試した回数	1ブロックあたり
5	5	761 回	152 回
20	20	5,591 回	279 回
80	80	23,633 回	295 回

1ブロックあたりの値段は難易度で決まっていて動かない。だから総額は作り直す数にそのまま比例する。そしてこの2つは掛け算になる。同じ深さ8で難易度だけ変えると:

	ハッシュを試した回数
難易度2・深さ8	1,030 回
難易度3・深さ8	29,261 回

ここに、この仕組みの安全性の全部がある。古い取引ほど書き換えにくいのは、後ろに積まれたぶんだけ作り直す数が増えるからだ。支払いを受けた側が確認を待つのは、自分の取引を深く埋めて、巻き戻しの値段を上げるためだ。

動かす

ブロックを追加してから、過去のブロックの「中身を改竄」を押すと、そのブロックと後続が赤くなる。「この1つだけ作り直す」では鎖が直らないこと、「ここから後ろを全部作り直す」で何回ハッシュを試したかが見える。

デモブロックチェーンと改竄難易度 2

マイニング中…

過去のブロックを改竄すると、そのハッシュが変わって後続の prevHash と食い違い、鎖が壊れる(赤)。隠すには改竄したところから末尾まで全部を作り直すしかない。値段は「難易度あたりの試行回数 × 後ろに積まれたブロック数」で決まる。

追記ログとしての側面

この構造は、ログ構造KVで見た「追記だけのログ」と同じ形をしている。過去を書き換えず、末尾に足していくだけ。

違うのは、誰が正しさを保証するかだ。log-structured-kv は1台のサーバが管理していた。ブロックチェーンには管理者がいない。誰でもブロックを足せるし、誰でも検証できる。その代わり、改竄を防ぐ仕組みを信頼ではなく値段で担保する。

実物ではブロックの中身は取引の集まりで、各取引には crypto 編の署名が付く。「alice が bob に10払う」に alice が秘密鍵で署名するので、alice 本人しかその取引を作れない。この教科書で作ってきたものの合流点になっている。

暗号(RSA) の署名: 取引の本人性
ハッシュチェーン: 過去の改竄検出
Proof of Work: 改竄の値段
ログ構造KV の追記ログ: 台帳の形

設計の観点

検出と抑止を分けて考える: ハッシュチェーンは改竄を見つけるだけで、止めてはいない。止めるのは値段のほう
つまみは1つにする: 難易度という整数1つで、指数的に動く量を調整している
値段を数えられるようにする: 「改竄が割に合わない」は主張なので、試行回数を数える口を用意する
確定を度合いで扱う: 深さが値段になるので、「何ブロック待てば安全か」は 0/1 ではなく程度の話になる
捨てる計算に意味を持たせる: 外れた試行そのものが担保になっている。だから電力を使う
やり直しの範囲を構造で決める: 前のハッシュを含める設計が、そのまま「どこまで作り直すか」を決めている

対照と実例

	改竄を止める仕組み	値段の払い方	管理者
この章 / ビットコイン	Proof of Work	計算(電力)	いない
現在のイーサリアム	Proof of Stake	資産を預けて、不正なら没収	いない
Git	(無し)	払わない	リポジトリの持ち主
WAL の追記ログ	(無し)	払わない	1台のサーバ
公証・タイムスタンプ局	第三者の署名	手数料	いる

裏どり:

深さが安全性: Bitcoin whitepaper の第11節が、攻撃者が z ブロック追いつく確率を計算していて、z が増えるほど指数的に落ちる。取引所が確認を何回か待つのはこの計算に由来する
難易度は動的に調整される: ビットコインは 2016 ブロックごとに、平均10分に1ブロックへ戻るよう難易度を上げ下げする。この章は固定にしてある
Git はハッシュチェーンだが PoW は無い: 各コミットが親のハッシュを含むので改竄は検出できるが、履歴の書き換えは誰でもできる。止めているのは値段ではなく、リポジトリの権限になる
51%攻撃の意味: 全計算力の過半を握れば、正直な鎖より速く作り直せる。値段の議論が成り立つのは、攻撃者が少数派である間だけになる
Proof of Stake への移行: イーサリアムは2022年に PoW をやめた。担保を「使った電力」から「没収されうる預け金」に置き換えたもので、払い方を変えても、割に合わなくするという狙いは同じ

簡略化したこと

P2P・合意なし: 単一ノード。実物は「最長チェーンが正」で分散合意する
取引は文字列1つ: 実物は署名付き取引の集まりを merkle root で束ねる。アンチエントロピーで作った木と同じ形
難易度固定: 実物は掘る速さを見て自動で上下する
報酬・残高管理なし: マイニング報酬も UTXO も扱わない
試行回数は運で揺れる: 1ブロックの実測は平均から大きく外れる。表の数字も平均で見ている
SHA-256 は標準ライブラリ: ハッシュ関数の中身は別の章

参考資料

Bitcoin whitepaper (Nakamoto, 2008) — 原典。9ページ。第11節が深さと確率の計算
naivechain — 200行の実装
実装: crypto/blockchain

ブロックチェーン ​

この章で作るもの ​

① 前のハッシュを含む ​

② 作り直しを高くつかせる ​

③ 値段は掛け算になる ​

動かす ​

追記ログとしての側面 ​

設計の観点 ​

対照と実例 ​

簡略化したこと ​

参考資料 ​