Block chain/Bitcoin の技術的原理

ちょっと前からブロックチェーンが話題になっているが，webを検索してもビジネス向けの解説ばかりで技術的詳細に踏み込んだ解説が見当たらない．そのため本記事を執筆することにした．

本記事は Satoshi Nakamoto 氏によるオリジナルの論文を参考にして説明するためビットコインの話が出てくるが，ブロックチェーンはビットコインよりも一般的な話なので注意．

しかしビットコインの話を理解すればブロックチェーンもわかる．

1. トランザクション(取引)

電子コインは、コインの取引をするためのデータの構造である。そのため、コインの所有者の変更について、どのように実行されているかを説明する。

コインは、デジタル署名の連鎖(チェーン)という構造をしている。具体的には、ある所有者Aが所有者Bにコインを転送したいとする。そのとき、以下のような手順でデジタル署名の連鎖が生成される。

プロトコル1 : 所有者転送のプロトコル
所有者AがBにコインを転送することを考える。前提として、所有者Aは、前の取引(Aの公開鍵、前回の取引で生成されたハッシュ値、前のオーナーの署名)を保持しておく必要がある。

1. Aは前の取引とBの公開鍵からハッシュ値を生成する。
2. 生成されたハッシュ値にAの署名鍵で電子署名する。
3. 電子署名したデータを、所有者Aの署名としてコイン(取引)に追加する。
4. BはAの公開鍵を用いて署名が真正なものであることを確認することで、所有権が転送されたことを確認する。

以上のプロトコルを図解したものが図１である．

図1: 所有者転送のプロトコルの図

この方式の問題は、所有者Aが複数の対象にコインを転送しうるという点にある。この問題の解決として、従来は信頼できる中央サーバーを設けてすべての取引を監視することであった。

しかしながら、中央サーバーなしに十分な解決を与える分散台帳プロトコルが存在する。

2. タイムスタンプサーバー

まずタイムスタンプサーバーについて説明する。タイムスタンプサーバーは、アイテムの塊(ブロック)のハッシュ値を広く公開することで、それらのアイテムに「タイムスタンプが押された」ことを示す。このタイムスタンプは、あるタイムスタンプが押されたアイテムが実際に存在したことを、ハッシュ値で証明するものである。

プロトコル2 : タイムスタンプサーバーのプロトコル
タイムスタンプサーバーがいくつかのアイテム $i_1,i_2\cdots$ のブロック $b_1=\{i_1,i_2,\cdots\}$ にタイムスタンプを押すことを考える。前提として、サーバーは前に生成したハッシュ値を保持している必要がある。ハッシュ関数を $h$ とする．

1. サーバーは、前回のハッシュ値 $h_0$ と、ブロック $b_1$ 中のアイテムの値 $i_1,i_2\cdots$ からハッシュ値 $h_1 = h(h_0,i_1,i_2,\cdots)$ を生成する。
2. サーバーはハッシュ値$h_1$をタイムスタンプとして広報する。

以上のプロトコルを図解したものが図2である．

図2 : タイムスタンプサーバーのプロトコル

各タイムスタンプ(ハッシュ値)は前回のタイムスタンプ(ハッシュ値)を含み、連鎖= ブロックチェーン を形成する。この連鎖によって，ブロック $b_1$ が $b_2$ の前者であることを検証可能にする．

3. Proof of Work

分散型のタイムスタンプサーバーをP2P上で実装するために、Proof-of-Workというシステムを実装する。ここで注意したいのは、タイムスタンプサーバーという実体が一つ存在するのではなく、ネットワーク全体でタイムスタンプサーバーとしての役割を果たすという点である。

定義 : Proof of Work
Proof-of-Workとは、サービスの要求者に一部の作業を要求することで、サービスの濫用を防ぐアイデアである。

ビットコインにおいては、サービスの要求者は、タイムスタンプサーバーを構成するネットワークのノードである。
そのためProof-of-Workという概念は以下のように適用される。

定義3 : ビットコインのProof of Work
ビットコインのタイムスタンプサーバーはProof-of-Workを以下のように実装している。

1. タイムスタンプサーバーネットワークは、各ノードに対して、ブロック $b_1=\{i_1,i_2,\cdots\}$ と前回のハッシュ値 $h_0$ を与える。
2. 各ノードは、ブロックの各値 $\{i_1,i_2,\cdots\}$ とハッシュ値 $h_0$ に対して、以下を満たす $nonce$ という値を発見する。ここで $h$ はハッシュ関数。$zeros$ は自然数の値(これは外部から指定される)。$top_0$ はハッシュの計算結果に対して、一番最初から0が何個連続しているかを返す関数(例えば、$top_0(0001)=3$,$top_0(111001)=0$)。
   
   $$zeros=top_0(h(i_1,i_2,\cdots,h_0,nonce)).$$

このビットコインのProof-of-Workの仕組みは、CPUパワーによる多数決を実現する。(次のネットワークの項で実際に多数決になるための仕組みを示す。)

4. ネットワーク

タイムスタンプサーバーのネットワークは次のように駆動する。

プロトコル4 : 分散型タイムスタンプサーバー

1. タイムスタンプサーバーの全ノードに新しい取引が通知される。
2. 各ノードは取引をアイテムとしてブロックに収集する。
3. 各ノードはProof-of-Workを実行し、正しいハッシュ値を探す。
4. あるノードが正しいハッシュ値を発見すると、他のすべてのノードに通知する。
5. 他のノードたちは、ブロック内の全取引が真正であり、かつブロックがまだ使われていない場合に限りそれを受け入れる。
6. 受け入れたノードたちは与えられたハッシュを元に新しいブロックを生成し、チェーンをつなげる。

以上のプロトコルを図解したものが図3である．

図3 : 分散型タイムスタンプサーバーのプロトコル

ここで何らかの理由で分岐が生じたと仮定する。このとき、分岐した先が長い方を採用する。(この仕様で、CPUパワーによる多数決が実現する。)

また、すべての最新の取引が常に最新のブロックに記録されている必要はない。 というのも、十分多くのノードのブロックに取引が記録されれば、いずれかの時点で記録されるためである。

5. 取引の検証

取引を検証したいと考える者は、自身では検証することはできないが、 ネットワークの最長のチェーンのヘッダーを保持することで、 ネットワークがそれを受け入れたということを確認することはできる。

以下のようなアルゴリズムで検証される。

アルゴリズム5 : 取引の検証

1. 検証者はタイムスタンプサーバーのネットワークに、得たブロックのチェーンが最長と確信できるまでブロックを要求する。
2. 検証したい取引がチェーンに含まれていることを確認する。

このため、誠実なノードがタイムスタンプサーバーを支配している限り、この検証は正しい結果を返す。正しくないチェーンを送信する攻撃者に対しては、タイムスタンプサーバーのネットワークのノードが無効なブロックを検出したときに警告を発するなどの方法がある。この警告を受けたブロックを有するユーザー(検証者)は再度ブロックを取得し、不整合があるか確認するといった対応をする。

企業などが頻繁に取引をする場合、専属のタイムスタンプサーバーノードを作ることで迅速な認証とセキュリティを確保できる。

6. インセンティブ

タイムスタンプサーバーの各ノードが「マイナー」と呼ばれるのは、ビットコインのシステムにおいて、 ノードが作成したブロックの最初のトランザクション(取引)がそのブロックの生成者を所有者とするコインを生成する特殊なトランザクション(取引)であるためである。 それゆえにマイナーに参加するインセンティブが与えられる。

また、ブロックを生成したマイナーに取引の際の手数料を与えるというのもある。

また、システム全体より大きいCPUパワーを持つ攻撃者を想定することも可能であるが、 そのような攻撃者にも攻撃を実行するよりもマイニングをするほうが利益が上がるという経済的な判断を促すことも可能である。

7. ブロックのサイズ

ブロック$b$に取引の履歴$\{i_1,i_2,\cdots\}$が記録されていくため、ブロックのサイズは放置すると増大し続ける。今誰が持っているかのみが重要であるので、最新の取引以外の取引を記録する必要はない。そのため、古い取引は消去してもよい。しかし、考えなしに消去するとブロックのハッシュ値が変化してしまう。ここで、プロトコル2を改良し、取引をマークルツリーという構造で保存することによって、古い取引の情報を容易に消去できるようにすることができる。

アルゴリズム6 : タイムスタンプのアルゴリズム(改良版)
ブロック $b$ はルートハッシュ $r$ 、前のブロックのハッシュ $b_0$ 、 $nonce$ からハッシュを生成する。これらの3つの値はブロックのヘッダーと呼ばれる。

ここでルートハッシュ $r$ は次のように生成される。ここで $t_1,t_2,t_3\cdots t_n$ は取引のハッシュ。

このとき、$t_1,t_2,\cdots,t_{n-1}$ や $s_2,s_3$ などについては削除しても，$s_0,s_4$ を覚えておけばルートハッシュは変化しない。

8. 価値の分割

省略．気になるなら元論文に当たってください．

9. プライバシー

取引を行うとき公開鍵を使ってハッシュを生成するが、ここで公開鍵を匿名にしておくことで誰が誰に送信を行っているかがわからないためプライバシーを確保できる。

10. 攻撃者との競争

攻撃者との競争過程を計算した項目．気になるなら元論文見てください．

11. まとめ

11.1 サーバーの動作

サーバー側の動作は以下の通り．

1. ユーザーが生成した取引データを収集する．
2. 収集した取引データと過去のデータからブロックを作成する．
3. ブロックを広報して，ほかのサーバーに使ってもらう．

11.2 ユーザーの動作

ユーザの動作は以下の通り．

1. 取引先がコインを所有しているか，最長のチェーンをタイムスタンプサーバーに問い合わせる．
2. 持っていたら所有者転送のプロトコルで所有者を変え，またサーバーに取引を通知する．

12. 蛇足

画質が荒いのはZennがsvgアップロードできないせいです😡

調べると Mastering Bitcoin という本があるそうですね．気になる方はさらに調べるといいかもしれません．