最近、ブロック・チェーンが流行っていますね。もともとは、ビットコインのプラットフォームとして世の中に出てきたものですが、ビットコインのような仮想的な通貨の取引以外への応用を見据えて、ブロック・チェーンの基盤を提供するHyperledgerやEthereumなどのプロジェクトも立ち上がっています。しかし、ブロック・チェーンのビジネスへの応用について書かれた記事や、ブロック・チェーンの仕組みについて書かれた難解な記事はよく見かけますが、わかりやすい技術解説はあまり見ないように思います。そこで、今回はブロック・チェーンの合意形成アルゴリズム、特にビット・コインで用いられる採掘について調査し、まとめてみました。
ブロック・チェーンとは
ブロック・チェーンとは、P2Pのネットワークに参加するノードの間で合意形成を行う仕組みのことです。例えば、ビットコインのような仮想的な通貨の取引などのプラットフォームとして利用されます。
従来、デジタル資産の取引をネットワーク上で行うには、下の左の図のように、資産の渡し手と受取り手（クライアント）以外に、その取引を管理する第三者機関（サーバ）が必要でした。この第三者機関がいるおかげで、例えばAさんがBさんに100万ドル払ったあとに、Aさんがその取引を無かったことにするよう取引記録を書き換える、のような不正が行えないようになっていました。しかし、このような第三者機関がいると、第三者機関を導入・維持するコストの発生や、すべての取引が第三者機関を経由する必要となり、そこが取引のボトルネックとなる、などのデメリットが発生します。そこで、下の右の図のように、このような機関を導入しない、すなわちクライアント・サーバ型ではなくP2P型のネットワークで取引を行う仕組みとして、ブロック・チェーンが考案されました。
第三者機関を導入しない場合、ある取引が正当かどうかを判定するためには、ネットワークに参加するノードの間でその取引が正当であると合意を取る必要があります。そこで、ある取引を行ったノードは、その取引記録を周りのノードにブロードキャストします。その取引が正当であると判定されると、各ノードはその取引記録を保存します。では、「取引」とは一体何なのでしょうか？
ビット・コインの取引とは
現在の残高をS、取引をTx、取引後の残高をS'と表すとすると、ビットコインの取引は以下のように定義できます（参考文献）。
Apply(S, Tx) -> S' or Error
たとえば、AさんからBさんへお金を支払う場合に、Aさんの残高が支払額以上であればその取引は成功します。すなわち、
Apply({A: $50, B: $50}, "send $20 from A to B") -> {A: $30, B $70}
のように書くことができます。一方で、Aさんの残高が支払額以下であれば、取引は失敗です。
Apply({A: $50, B: $50}, "send $70 from A to B") -> Error
取引が成功すると、その記録を取引に関わったノードはネットワーク内の他のノードにブロードキャストします。このような取引記録がある程度貯まると、各ノードがそれらの正当性を検証し、正当性が認められるとそれらをまとめて「ブロック」を形成し、各ノードが保存します。この処理を繰返すことにより、複数のブロックが時系列に形成されるため、「ブロック・チェーン」と呼ばれています。取引記録の正当性は、例えば次のように検証します。
- 直前のブロックの残高を
S[0]とする。 - n個の取引記録について、順に
S[i+1]=Apply(S[i], Tx[i]), (i=0...n)を計算する。もし、残高が合わないなど取引記録に矛盾があれば、その取引は不正であるとする。 - 残高
S[n]をそのブロックに記録する。
ビットコインでは、ブロックが6つ形成された時点で、ひとつ目のブロックの取引の成立が認められます。例えば、AさんがBさんに20ドル払って、ある商品を買うとします。そして、AさんがBさんに20ドル払った記録が下の図のブロック①に記録されているとします。その取引はブロック⑥が追加された時点で成立し、BさんからAさんへ商品が発送されることになります。
また、ビットコインでは、一番長いチェーンが正当であるとみなします。すなわち、AさんがBさんに20ドル払って商品を受け取ったあと、AさんがBさんに20ドル払った、という記録をなかったことにしたいと思った場合、Aさんはブロック①の内容を書き換えたあと、その後の取引記録が辻褄が合うように、ブロック②...⑥の内容を書き換えて、元のチェーンの長さに追いつき、追い越す必要があります。もしブロックの内容が取引記録のテキストだけであれば、頑張ればすぐに元のチェーンに追いつくことができるような気がしますよね。そこで、ビットコインでは、採掘という仕組みにより、ブロックの内容の書き換えを非常に難しくしています。
採掘とは
採掘とは、ブロックの内容の書き換えを難しくする仕組みです。複数の取引記録がある程度貯まると、各ノードはその取引記録に乱数、および一個前のブロックのハッシュ値を追加し、ハッシュ関数への入力とします。ハッシュ関数の出力がある閾値以下となる乱数を見つけたノードは、それらの取引記録とその乱数、及び一個前のブロックのハッシュ値からなるブロックを形成し、チェーンに追加します。
ハッシュ関数とは、入力された値から出力される値を予測するのが難しい関数のことです。すなわち、ある値を入力した時に、出力される値がある閾値以下となるかどうかを予測することはできません。そこで、取引記録と乱数を入力し、出力が閾値以上となったら乱数に1を足してハッシュ関数に入力し直す、という作業を出力が閾値以下となるまで繰り返すことになります。この処理は、そのノードのCPUや電力を多く使う処理となり、何かしらの報酬がなければやる気が起きません。ビットコインでは、この処理を「採掘」と呼び、CPUや電力を使って条件を満たす乱数を見つけたノードに25ビットコインを与えます。このように、条件を満たす乱数を見つけたノードに報酬を与えることによって、多くのノードは不正など行わずに正当な取引記録をチェーンに追加しようとします。
上の図のブロック①の取引記録を書き換えようとすると、ハッシュ関数へ入力する値が変わるため、条件を満たす乱数も変わります。すなわち、条件を満たす乱数が見つかるまで採掘を実行し直す必要があります。当然、出力されるハッシュ値も元のブロックの結果とは異なります。また、各ブロックは一個前のブロックのハッシュ値を含むため、ブロック①の内容を書き換えると、以降のブロックについても採掘を実行し直す必要があります。不正なチェーンの長さが元のチェーンの長さに追いつくためには、元のチェーンにブロックを追加する正当なノードの数よりも、不正なチェーンに追加する不正なノードの数のほうが多くなければなりません。このようなことが起きないかぎり、ブロック・チェーンの正当性は守られます。
おわりに
以上が、ビットコインにおける採掘の仕組みでした。ブロック・チェーンの正当性を保証するために、CPUや電力をたくさん使ってハッシュ値を計算してくれたノードに対して報酬を与えていたのですね。なお、この採掘は、ビットコインにおける合意形成アルゴリズムであり、HyperledgerやEthereumなどのその他のブロック・チェーンでは、別のアルゴリズムが使われています。今後はビットコイン以外のブロック・チェーンについても調査していきたいと思っています。