Bitcoin

概要

Table of Contents

1. ブロックチェーン
2. コンセンサス
   1. Proof of Work
   2. The Longest History Wins ルール
   3. パフォーマンス
3. セキュリティ
   1. Sybil 攻撃
   2. DDoS 攻撃
   3. 51% 攻撃
   4. Eclipse 攻撃
4. 技術的な問題点
5. 参照

ブロックチェーン

Bitcoin ユーザの取引要求はトランザクションというデータとして Gossipping によって P2P ネットワークに拡散される。Proof of Work によって選出されたノードは有効なトランザクションを集めてブロックを生成する。このとき、新しいブロックは直前のブロックのハッシュ値を含める必要がある。

ターゲットが小さいほど nonce の特定には時間がかかる。ターゲットの難度は過去の難度と実際の nonce 特定にかかった時間から導出され、ブロックの生成が概ね 10 分となるように見積もられる。難度は 2016 ブロックごとに再設定される。

1. 前のブロックのハッシュ値
2. 新しく作成するブロックのトランザクションハッシュツリールートのハッシュ値
3. これから求めるハッシュ値のターゲット (目標値)

コンセンサス

コンセンサスとは一貫性 (consistency) を達成するための仕組みを意味する。

Proof of Work

Bitcoin ネットワークには任意のノードがいわゆる採掘者 (miner) として自由に参加しており、採掘者の中から Proof of Work に基づいてブロックを生成するノードを決定する。つまり Bitcoin の PoW は分散システムにおけるリーダー選挙を意味する。

各採掘者は Bitcoin ネットワークから新しいブロックを受信すると、そのブロックヘッダのハッシュ値と任意の nonce (number used once; ナンス) を連結したハッシュ値を計算する。この結果が現在の difficulty 以下となれば、その nonce は "当たり" である。\[ \begin{equation} {\rm sha256}({\rm sha256}({\it block\_header})\ ||\ {\it nonce}) \le {\it difficulty} \label{mining} \end{equation} \] Fig 1 に示すようにブロックヘッダには version, 直前のブロックヘッダのハッシュ値、トランザクションの Merkle ルートハッシュ、タイアムスタンプ、difficulty、nonce が含まれている。

当たりの nonce を探し当てた採掘者はネットワーク上のトランザクションのうちまだブロックチェーンに取り込まれていないものをまとめて新しいブロックを生成し P2P ネットワークに拡散する。ブロックを受信した各ノードは、その nonce が本当に条件 (\(\ref{mining}\)) を満たしているかを確認することで、その採掘者が正当な権利を得て作成したブロック化を検証することができる。

The Longest History Wins ルール

PoW によるリーダー選出は決定論的に唯一のノードを選択することができず、複数の採掘者がほぼ同時に条件 (\(\ref{mining}\)) を満たす nonce を発見する可能性がある。P2P ネットワークでは当選した採掘者がお互いを認識する手段がないため、それぞれの当選者が異なる "正しい" ブロックを生成し Bitcoin ネットワークに配布する。このように発生するブロックチェーンの分岐をフォーク (fork) と呼ぶ。Fig 2 では \(B_3\) を起点に \(B_4\) と \(B'_4\) がフォークし、\(B_4\) を起点に \(B_5\) と \(B''_5\) がフォークしている様子を表している。

Bitcoin ネットワークではブロックチェーンのフォークは最も長いものを優先するというルールがある。このような方針をここでは仮に (last writer wins にならい) The Longest History Wins ルールと呼ぶ。

フォークを検出した採掘者はこれから自分が作るブロックをどの枝に接続するか (どの枝に対する nonce を計算するか) を決めなければならない。nonce の計算には膨大な計算能力を必要とするため、一般には Bitcoin ネットワーク上で破棄される可能性が高い枝より採用される可能性が高い枝の方に計算リソースを投資する判断となるだろう。

例えば最新のブロックの状況が Fig 2 のように見えている採掘者は \(B'_5\) や \(B''_7\) よりも \(B_9\) に対する nonce 計算を行うのが最も合理的である。将来的に \(B'_5\) の枝が \(B_9\) の枝を追い越す可能性はゼロとは言えないが一般には分の悪い賭けである。

この The Longest History Wins ルールは、あるユーザが Bitcoin ネットワークに送信したトランザクションがブロックに取り込まれたように見えても後に覆される可能性があることを暗に意味している。51% 攻撃で後述するように、ある時点で本当に最長の枝であってたとしても、後の採掘者がどの枝にブロックを接続するかで将来的には最長の枝ではなくなっていることは否定できない。時間が経過し枝が成長するに連れてそのようなことが起きる (起こせる) 可能性は急速に減少するが、それでもゼロとなることはない。これが Bitcoin には一貫性 (consistency) またはファイナリティ (finality) がないと言われる理由である。

ただし、51% 攻撃や Eclipse 攻撃のような規模の攻撃が秘密裏に進行していなければ、慣例的に 6 ブロックが連結された (つまりおおむね 1 時間が経過した) ブロックの履歴が覆される可能性は無視できると認識されている。一方、ファストペイメントの方針を取るシステムでは安全性より高速性を優先して 1～2 ブロックの連結を確認した時点で、あるいはブロックの連結をまったく確認せずに取引が確定したとみなす。

パフォーマンス

Bitcoin のブロックのサイズは 1MB に制限されていることから、各ブロックには特定の数のトランザクションしか含むことができない。またその生成速度が 10 分に 1 つであることから、概算して Bitcoin は 7[TPS] (1 秒間に 7 トランザクション) の性能である。さらに (慣例的な) 確定を待つには 1 時間が経過しなければならない。これは Mastercard の秒間取引数 10,000[TPS] と比べて遥かに低いことから Bitcoin を現実の金融取引に適用するには難しいと考える向きもある。

Bitcoin ではネットワーク全体の計算性能が変動しても nonce の計算時間をおおむね 10 分とするために 2 週間ごとに difficulty の調整が行われる。正確に 10 分で 1 ブロック作成されるとすれば、2週間 = 20,160分の間に 2,016 ブロックが生成されているはずである。現在の difficulty を \(d\) とし、直近の 2,016 ブロックの生成にかかった実際の時間を \(t'\) [min] としたとき、新しい difficulty は式 (\(\ref{difficulty}\)) のように算出することができる。\[ \begin{equation} d' = d \times \frac{t'}{20160} \label{difficulty} \end{equation} \]

セキュリティ

Bitcoin のコンセンサスは P2P 向けにうまく対策されている設計である。51% 攻撃や Eclipse 攻撃

Sybil 攻撃

Sybil 攻撃は攻撃者が多数の ID (アドレス、アカウントの意味) を生成しネットワークを支配する攻撃である。Blockchain では攻撃者が大量の ID を保有したとしても PoW によって攻撃者の実際の計算能力以上の効果を期待できないことから Sybil 攻撃に対して耐性を持つ。

DDoS 攻撃

DDoS (distributed denial of service; 分散サービス拒否攻撃) は特定の負荷をかけることでサービス全体の機能を低下させたり停止させる攻撃である。Blockchain の場合はブロックの生成を妨害したり、空または無効なトランザクションを集めて無意味なブロックを生成する攻撃が該当する。

Bitcoin のケースでは、nonce を発見した採掘者がネットワーク上にブロックを配布するまで第三者はブロック生成者が誰なのかを知るすべがないという PoW の性質により、攻撃の対象となるブロック生成者をネットワークで特定することは困難である。

また、nonce の発見に膨大な計算時間が必要であることと、nonce 発見後は速やかにブロックを生成し配布しないブロックが採用されにくくなる the Longest History Wins ルールによって、多数の採掘者が競合するブロックを同時に流布することは困難である。

同様に、PoW の下では悪意を持った採掘者が連続して nonce を引き当てることは困難である。言い換えると、悪意を持った採掘者が当選したとしてもせいぜい 1 ブロック程度の一時的な影響にとどまる。加えてブロック生成者はなるべく手数料の高いトランザクションをなるべく多くブロックに詰め込むことで自身が得る手数料も多くなることから膨大な計算量を投資して無効なブロックを作成するモチベーションは低くなると期待される。このような設計により Bitcoin は DDoS 攻撃に対して耐性を持つ。

51% 攻撃

例えば Fig 2 において、採掘者たちが結託して (あるいは \(B_9\) の枝が見えないように中継者が細工して) Bitcon 採掘者全体の 51% 以上となる計算能力を \(B''_7\) の枝を伸ばすために投資したとする。すると \(B_9\) よりも \(B''_7\) の伸びが速くなり、いずれ \(B''_7\) の系譜が \(B_9\) の系譜より長くなって "正しい" 枝を乗っ取ることができる (履歴を書き換えることができる)。このような 51% 攻撃 (51% attack) は PoW に基づくコンセンサスで有効な攻撃手段の一つである。51% 攻撃を困難にするには特定の集団組織に偏らない多数の採掘者を参加させる必要がある。

Eclipse 攻撃

中継者が (故意か事故かにかかわらず) Bitcoin ネットワークを分断したり、流通するブロックをフィルタリングすると、その中継者を挟んだ双方のパーティションでブロックチェーンがフォークし異なる枝が成長することになる (あるいは一部の枝しか見えなくなる)。ある程度の時間が経過した後に分断を解消すると、どちらか片方のパーティションのトランザクション履歴が大規模に書き換え大きな混乱をもたらすことになる。このような Eclipse 攻撃 (eclipse attack) は PoW に基づくコンセンサスで有効な攻撃手段の一つである。Eclipse 攻撃を困難にするには各参加者がそれぞれ多数の到達経路を持つように他の多くのノードとランダムに接続する必要がある。

大規模な攻撃を考慮すると、国家が管理下に置いているネットワークを意図的に操作することによって、そのネットワークに依存している自国内または他国の採掘者に Eclipse をもたらす攻撃が可能である。小規模な攻撃になると、悪意のあるプロバイダが正しいブロックチェーンを意図的にフィルタリングし、代わりにフォークした"偽の" 取引履歴 (枝) をユーザに見せることができる。ユーザは偽の取引履歴から入金確認して商品を発送した後にプロバイダは "正しい" 枝に取引履歴を書き換えることで支払いをなかったことにするような攻撃ができる。

技術的な問題点

Bitcoin は "総計算能力の大多数が正しい (バグや不正や悪意がない)" ことを前提としてる。この前提が破れ、悪意のあるノード群が計算能力の大部分を占めた場合、過去の取引履歴を書き換えることが可能となる。

計算能力の無駄

PoW は計算資源を過剰に消費しており 2017 年時点で TOP500 の最も速いスパコンでも Bitcoin マイニング総計算力の 12.8% でしかない。

計算能力の局所化

一般のユーザはマイニングに参加しても電力コストと報酬の期待値が釣り合わなくなっており、マイニング専用に構築された大規模なマイニングプールに参加して報酬の配分を得るしかなくなっている。これは計算能力の局所化を招いており、2017 年時点の Bitcoin の総計算力はおおむね 5 つのマイニングプールで占められている。この状況では公正性を保証することが難しい。

トランザクション完了の曖昧さ (finality の欠落)

Bitcoin のブロックチェーンは必ずしも一意な結果とはならない。実際に、ブロックのシーケンス \(\{B_0,B_1,\ldots,B_i,B_{i+1}\}\) を保持しているノードに \(\{B_0,B_1,\ldots,B_i,B'_{i+1},B'_{i+2}\}\) が伝達された場合、よりチェーンの長い後者が採用されることから、観測者からはブロック \(B_{i+1}\) に含まれているトランザクションの処理結果が取り消されたように認識される。

この問題から、チェーンの最後のブロックに含まれているトランザクションを信用することはできず、ブロックチェーンが十分に長くなり結果が安定したことを確認する必要がある。

参照

1. Satoshi Nakamoto (2008) "Bitcoin: A Peer-to-Peer Electronic Cash System"