[ブロックチェーン] ブロックチェーンについて学んだこと

はじめまして、森田と申します。
2020年に入ってから、ブロックチェーンに興味を持ち、[堅牢なスマートコントラクト開発のためのブロックチェーン［技術］入門](https://gihyo.jp/book/2017/978-4-7741-9353-3)や[ブロックチェーンアプリケーション開発の教科書](https://book.mynavi.jp/ec/products/detail/id=87665)などの参考書で少しずつブロックチェーンについての勉強をはじめました。
そこで今回は、ブロックチェーンがなぜ注目されているのかについて学んだことを自分自身の備忘録も兼ねて、記述していきたいと思います。

# ブロックチェーンとは
ブロックチェーンとは、ビットコインと呼ばれる暗号通貨システムを支えるために開発された技術です。
ブロックチェーンは、特定の第三者を介さずに、ネットワークで分散型(Decentrized)の合意形成を可能にし、`すべての履歴を追跡可能にして透明性の高い取引を実現する技術`です。また、`データの改ざんが非常に困難`、`実質ゼロタイムダウンタイム`などの特徴もあります。

## ブロックチェーンの注目ポイント
ブロックチェーンは、インターネットの課題を解決しうる技術として注目されています。
現在インターネットを持ちうるシステムを構築する場合、大きく2種類の構成に分けることができる。
一つはクライアントサーバ方式で、もう一つはP2P方式です。
クライアントサーバ方式は、サービスを提供する`サーバ`とサービスを受ける`クライアント`が明確にその役割を分けている方式です。
P2P方式は、役割が明確に決められず、全てのノード(インターネットに接続したコンピュータ)が`サーバ`にも`クライアント`にもなり得る方式です。
　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/eb7f9ddb-2204-3ef1-2128-ec52d169f0fb.png" width=40% title="クライアントサーバ方式">　　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/aa426223-8fb3-50bc-c4bb-391c0396a8dc.png" width=45% title="P2P方式">

クライアントサーバ方式には、少数のサーバに多数のクライアントが接続するモデルとなっているため、サーバの処理能力の限界に達したり、サーバ側に何らかの障害が発生した場合に、サービスを利用することができなくなるという課題があります。この課題自体は、サーバを増強したり、複数の拠点にサーバを分散させることで、リスクを分散させることで解決することができますが、相応のコストがかかってしまいます。

### P2P方式の課題

一方、P2P方式では、特定のサーバに負荷が集中することがないため、一部のサーバで障害が発生しても、サービス全体が止まることはありません。また、サービスの利用者全員がサーバの機能を担うため、特定のサービス提供者が多額のコストを支払ってサービスを維持する必要もありません。つまり、P2P方式は、クライアントサーバ方式の課題を解決することが可能になっています。

しかし、P2P方式にも課題はあり、以下のような3つの課題があります。

    1. 悪意を持ったノードがサービス提供者となり得るため、データの改ざんの検知をするのが難しいこと
    2. 悪意を持ったノードがサービス提供者となり得るため、データの改ざんの拒否をするのが難しいこと
    3. 複数のノードが参加するP2Pネットワークで、全ノードが最新のタイムスタンプを参照するのが難しいこと
 
ブロックチェーンは、上記の3つのP2P方式の課題を解決し得る技術として、注目されています。
つまり、ブロックチェーンは、P2P方式でセキュアなサービスを実現するための技術であると言えます。

# P2P方式の課題をブロックチェーンで解決
ブロックチェーンは、時間が不可逆的であることと、1つの時間軸を全ノードが共有して、どの時間軸の中で前後関係(論理的タイムスタンプ)を定義できる物理的な時間の特徴を暗号学にもとづくデータ構造を用いて実装します。

## ハッシュチェーン
ブロックチェーンでは、暗号学的ハッシュ関数を用いて、あるデータが存在する前に別のデータが存在していたという前後関係を、論理的に否定できない形で定義しています。
暗号学的ハッシュ関数とは、任意のデータを引数に取り、ハッシュ化した値を戻り値として返す関数のことです。
ハッシュ値は、ハッシュ値から元のデータを推定することが、非常に困難であるという特徴を持っています。

　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/7c76cf62-690d-0b1b-83ec-330ac8451072.png" width=80% title="ハッシュチェーンの構造">

あるデータ`x0`に対して、暗号学的ハッシュ関数`h`を用いて得られたハッシュ値を`h(x0)`とします。
このとき、`h(x0)`から`x0`を求めることは困難であることが分かっているので、ハッシュ値`h(x0)`が存在しているということは、その前にデータ`x0`が存在していると言うことができます。
さらに、`h0 = h(x0)`として、`h(h0)`を計算したとすると、`h(h0)`が存在する前に`h0`が存在していたと言うことができます。
このように、同じデータに対して再帰的に暗号学的ハッシュ関数を適用する技術を`ハッシュチェーン`といいます。

次にハッシュチェーンを拡張して、ハッシュ関数への入力に任意のデータを埋め込んだ仕組みを示します。

　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/28cb497e-280c-5307-7dd2-2d50883099d3.png" width=75% title="拡張されたハッシュチェーンの構造">

拡張前のハッシュチェーンでは、あるデータ`x0`に対して、拡張後のハッシュチェーンでは、再帰的にハッシュ値を求める際に入力として任意のデータ`x0`、`x1`、`x2`、...を加えています。
この拡張により、`h3`を計算するためには前提として`h2`と`x3`が存在している必要があり、`h2`を計算するためには、`h1`と`x2`が存在している必要がある、という再帰的な関係が成り立ちます。
これにより、`x0` < `x1` < `x2` < ...とデータが存在する前後関係を、任意のデータに対して論理的に定義できます。

## ブロックチェーンのブロックのしくみ
ブロックチェーンでは、すべてのデータの前後関係を常に全ノードに共有するのではなく、複数のデータをまとめた`ブロック`単位で共有します。
このブロックの作成に利用されている技術が`マークルツリー`です。

### マークルツリー
マークルツリーは、木構造のハッシュチェーンで、ハッシュツリーとも呼ばれます。
マークルツリーは、二分木の木構造になっており、マークルツリーを作成するには、以下の処理を繰り返し行い、最終的に1つのハッシュ値が算出するまで続けます。

  - データの断片を2個のペアに分け、2つの断片を結合したデータのハッシュ値を計算します。
    - このとき、断片の数が奇数であれば、余った1つの断片に関しては自分と同じデータを複製して、その2つのデータに対するハッシュ値を計算します。  

最後の1つになったハッシュ値は、マークルルートもしくはトップハッシュと呼ばれます。

　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/ed535cfb-47fa-ae53-fef6-a424b4ef6fcf.png" width=75% title="マークルツリー">

マークルツリーを応用すると、巨大なデータを小さな断片に分割し、断片ごとのハッシュ値で`データの破損や改ざんの検証`が可能です。
マークルツリーを用いたデータの検証は、以下の手順を繰り返し、データの破損・改ざん箇所を特定します。
  1. まずはデータからマークルルートを計算し、元のマークルルートと比較します。
  2. もし、`マークルルートの値が異なっていた場合`は、マークルルートを計算するために用いた2つのハッシュ値を元のハッシュ値と比較します。
この操作を繰り返すことで、ハッシュ値が異なるデータの断片を効率的(`O(Logn)`)に発見でき、データを再受信する際も、破損データのみを再受信すればよいため、データの通信量的にも効率的です。 

このマークルツリーの構造を応用することで、ハッシュチェーンタイムスタンプをブロック単位でカウントアップすることができます。
これまで説明したマークルツリーは、1つのデータの断片を分割して、断片ごとのハッシュ値を計算していますが、この方法は、任意のデータリストに対しても適用可能です。
また、任意のデータリストにマークルツリーの構造を適用したものを`ブロック`と呼びます。

### マークルツリーによるブロックの生成
マークルツリーを用いてブロック単位でデータを埋め込む場合の例は、以下のようになります。

　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/ae47c31a-0195-d66f-d15a-d3c5cc7cad97.png" width=100% title="ブロックチェーンの最小構成">

ハッシュチェーンを用いた場合は、新しいデータが作成されるたびにハッシュチェーンのカウントがインクリメント(データの前後関係構築)されますが、マークルツリーを用いた場合は、複数のデータをブロックにまとめて、ブロック単位でカウントがインクリメントされます。つまり、ブロック単位でデータの前後関係が構築されます。
また、このブロックがチェーンのように繋がっていることから、このデータ構造は、`ブロックチェーン`と呼ばれています。

ブロック単位でインクリメントされたハッシュ値のカウントをタイムスタンプ(論理的タイムスタンプ)とみなして、以下に論理的時系列表を示します。

| データ | ブロック番号 | 論理的タイムスタンプ |
| :---: | :---: | :---: |
| x0 | 0 | 0 |
| x1 | 0 | 0 |
| x2 | 1 | 1 |
| x3 | 1 | 1 |
| x4 | 1 | 1 |
| x5 | 1 | 1 |
| x6 | 3 | 3 |

上記の表は、任意のデータ`x0`〜`x6`と、対応するブロック番号、ブロック番号と一致する論理的タイムスタンプを示しています。
この表から、同じタイムスタンプに複数のデータが紐づいていることがわかります。
つまり、タイムスタンプが`0`となっている`x0`と`x1`のデータは、`同時`に作成されたデータと解釈されます。
また、タイムスタンプが`2`となるデータが存在していませんが、これはタイムスタンプのインクリメントがブロックの作成と紐づいており、データの作成からは独立しているためです。つまり、データが作成されなくてもタイムスタンプは更新されるということです。

ここまでで、ブロック内にあるマークルツリーで`データの破損や改ざん`を検証し、ブロックとブロックをチェーンで繋ぐことで、ブロック間の前後関係を構築することで、P2P方式の1つ目の課題である`データの破損や改ざんの検知をするのが難しいこと`について対応することができます。

しかし、このブロックの概念を導入しただけでは、残り2つの課題に応えることができません。
つまり、残り2つの課題に応えるためには、`データを改ざんすることにメリットを感じさせない仕組み`を作ったり、`最新のブロックの情報が全ノードに行き渡るまで、次のブロックを作成しない仕組み`を作る必要があります。
これらの仕組みを完全にではないけれど、実用可能なレベルで実現した仕組みの一つが`Proof of Work`になります。
Proof of Workは、ブロックチェーンアプリケーションのひとつであるビットコインで採用されている仕組みになります。

## Proof of Workによる不正の防止
Proof of Workは、サービス提供者が作業量が膨大となる特定の作業をサービス利用者に要求し、その作業を完了した利用者のみがサービスを利用できる仕組みです。
Proof of Workには、作業は膨大だけれど、その作業結果が正しいかを検証する方法が比較的容易であるという特徴があります。
また、Proof of Workの仕組みは、善良なサービス利用者にとってはそれほど影響はなく、悪質なサービス利用者にとっては、大きなデメリットになるようになっています。
ブロックチェーン（ビットコイン）におけるProof of Workの作業は、暗号学的ハッシュ関数の出力が`ある値以下になる入力`を見つけることが作業になります。
例えば、出力が0〜99999の10万通り存在する暗号学的ハッシュ関数があるとします。
そして、ハッシュ関数の出力が99以下になる入力`x`を見つける作業が今回のProof of Workだとします。
出力から入力を逆算できないのが暗号学的ハッシュ関数の特徴であるため、入力を適当に変化させながら総当たりで`x`を見つけ出すしか方法がありません。
つまり、この作業は、`x`を見つけるために約10万回近く計算する可能性があるということになります。
このように`x`の値を見つけるには膨大な計算が必要ですが、`x`の値が見つかれば、検証は`xの値が99以下であること`をチェックするだけなので、1回の計算で済みます。

ビットコインで導入されているProof of Workの作業では、SHA-256と呼ばれる暗号学的ハッシュ関数を2回適用する、Double SHA-256を用いています。
この関数は出力として256ビットの値を返し、出力のパターン数は10の78乗通りという膨大な数になります。（なんて果てしないんだ、、、、）

　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/1288ff07-ef40-90dc-8637-6ff15c850af1.png" width=100% title="Proof of Work">

Proof of Workを導入する上で、ブロックチェーンでは、P2P方式を構成するすべてのノードで同じ作業を一斉に解く仕組みになっています。
ブロックチェーンにおけるブロックのハッシュ値が、ある値以下のハッシュ値になるブロックを一斉に探します。
ここで、ブロックのハッシュ値の上限となる値を`target`とします。
また、これまで説明したブロックチェーンにおけるブロックのハッシュ値の入力は、直前のブロックのハッシュ値と任意のデータのマークルルートでしたが、それに加えて`nonce`と呼ばれるワンタイムパスワードを加えます。
このワンタイムパスワードを何度も変更してブロックのハッシュ値を計算し、ハッシュ値が`target`以下になる`nonce`を見つけることが、ブロックチェーンにおけるProof of Workの作業になります。

つまり、ブロックチェーン上で、`データの破損や改ざん`を行うには、Proof of Workによる膨大な作業を何回も行わなければならず、これをするためには高価な計算機や膨大な電気代がかかってしまうため、悪質なサービス利用者にとってかなりのデメリットとなります。

そのため、Proof of Workを導入することで、P2P方式の2つ目の課題である`データの破損や改ざんの拒否をするのが難しいこと`に対して現実レベルで解決することができます。

最後に3つ目の課題について、
ビットコインなどのブロックチェーンアプリケーションでは、すべてのマイナーが一斉にマイニングを行い、平均して10分に1回Proof of Workの検証を行っています。
では、物理的な時間とは異なるハッシュチェーンに基づくタイムスタンプ(論理的タイムスタンプ)を導入しているブロックチェーンで`10分に1回`ブロックが生成されることと物理的な時間との同期をどのように実現しているのか、、、、、、
ビットコインの場合は、`ブロックタイムスタンプ`と`ネットワーク調整時刻`の2つの時刻を用いて、物理的な時刻とブロックチェーンの同期を行っています。

## ブロックタイムスタンプとネットワーク調整時刻
　　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/533822/61f5ae42-a122-a4e1-d1c7-dcd773b1961d.png" width=100% title="ブロックタイムスタンプとネットワーク調整時刻">

`ブロックタイムスタンプ`とは、ブロックに紐づくUNIXタイムスタンプです。
このブロックタイムスタンプも、ブロックのハッシュ値を計算する際の入力の中に含めます。
ブロックタイムスタンプは、UNIXタイムスタンプなので、ブロックを生成したマイナーが勝手に設定できてしまうため、以下の二つの制約があります。
  1. 過去11ブロックのブロックタイムスタンプの中央値より未来の値であること
  2. `ネットワーク調整時刻`より2時間以上未来の値でないこと

`ネットワーク調整時刻`とは、P2Pネットワークに接続している全てのノードが返すUNIXタイムスタンプの中央値です。

これらの定義から、ブロックタイムスタンプは、現実の時刻と同期できているわけではありません。
ブロックタイムスタンプは、現実の時刻と1~2時間ずれる可能性がありますし、前後関係にある2つのブロック間のタイムスタンプの順序が逆になっている可能性もあります。
それでも、俯瞰的に見ればブロックタイムスタンプと現実の時刻が緩やかに同期はできているため、実用していくうえで問題ないレベルとなります。
これで3つ目の課題も現実的なレベルで解決することができます。

# まとめ(感想)
今回は、インターネット利用サービスが抱える課題に対しての解決策として、ブロックチェーンが有効かもしれない理由について学び、それを記事にさせていただきました。

今回書いた内容については、ほぼすべて[堅牢なスマートコントラクト開発のためのブロックチェーン［技術］入門](https://gihyo.jp/book/2017/978-4-7741-9353-3)と[ブロックチェーンアプリケーション開発の教科書](https://book.mynavi.jp/ec/products/detail/id=87665)に記載されています。

それを自分なりの理解や解釈も踏まえて書かせていただいたので、間違っている箇所も大分あると思います。
しかし、記事を書くのは学んだことを体系的にまとめることができるので、大変良いアウトプット方法だなと思いましたので、これからも学んだことはどんどん記事にしていきたいと思います。

参考にさせてもらった二つの参考書は、本当にわかりやすく、何度も読み返したいと思えるほどでした。
今後も引き続きブロックチェーンの勉強を続けDAppの開発ができるようになっていきたいと思います。

次回は、スマートコントラクトについて学んだことを記事にしたいと思います。

# 参考資料
[堅牢なスマートコントラクト開発のためのブロックチェーン［技術］入門](https://gihyo.jp/book/2017/978-4-7741-9353-3)
[ブロックチェーンアプリケーション開発の教科書](https://book.mynavi.jp/ec/products/detail/id=87665)
[P2P（ピアツーピア）ネットワークの仕組みと強み・弱み](https://floc.jp/log/basic/1270/)