Blockchain

  • このエントリーをはてなブックマークに追加

概要

分散システムにおけるブロックチェーン (blockchain) は、ビザンチン耐性のある分散合意アルゴリズムを使ったステートマシンレプリケーション (SRM) として機能する Peer-to-Peer ネットワークである。特に、合意によって生成された命令シーケンスは暗号技術を使用してリンクされた不変のブロックのリストとして分散共有される (データ構造の文脈ではこのブロックのリストをブロックチェーンと呼ぶ)。暗号通貨やトレーサビリティの用途では改ざん不可能な取引や譲渡のログであることから分散型台帳技術 (distributed ledger technology; DLT) とも呼ばれる。

一度記録されたされたブロックを変更するには、それより後のすべてのブロックを遡及的に書き換える必要があり、その操作は P2P ネットワークでブロックを共有している多数のノードの合意なしに行うことができないことから、改ざんに対して比較的安全な技術と認識されている。このためブロックチェーンは高い分散性を備えた分散コンピューティングシステムの一例として、2者間の取引を効率的に検証可能かつ恒久的な方法で記録できるオープンで分散した台帳技術と考えられている。

ブロックチェーンは Bitcoin の取引を行うために考案された分散ネットワーク技術である。この発明により Bitcoin は集権機関や中央サーバを必要とせずに二重支出問題を解決した最初の暗号通貨となった。

データ構造

データ構造としてのブロックチェーンは直前のブロックを参照する片方向リストである。各ブロックは前のブロックの暗号化ハッシュと、タイムスタンプ、複数のトランザクションおよびそのハッシュ値 (通常、Merkle Tree ハッシュルートとして) を含んでおり、P2P ネットワーク上で共有され複数のノードによって検証される。

トランザクション

ブロックは複数のデータ単位を含むことができる。特に、暗号通貨やトークンのような金融取引を目的としたブロックチェーンでは トランザクション (transaction) と呼ばれる最小単位の操作をデータ単位として扱う。

トランザクションの操作はアトミックであり、全てのトランザクションを最初から順序通りに適用すれば原則的に任意の時点の状態を復元することができる。トランザクションは粒度が高く、それ自身を転送や検証の単位とするには処理コストが高いためブロック (block) と呼ばれる単位に集約して流通する。

例えば Bitcoin のトランザクションは「A から B への送金」を表している。情報として送金元のアドレスと送金先のアドレス、金額、入出力の成立条件を示すスクリプトが含まれている。

ブロック

ブロックは複数のトランザクション (データ単位) に加えてメタ情報として直前のブロックのハッシュ値を保持するデータ構造である。したがって、仮にあるブロックのトランザクションを書き換えようとした場合、ブロックのハッシュ値が変わることからそのブロックの後に連結された全てのブロックを遡及的に書き換える必要がある。さらに Proof of Work 型のブロックチェーンではブロックごとに nonce を再計算 (再マイニング) する必要があるためチェーン化されたブロックの書き換えは現実的ではない。

Blockchain of Bitcoin
Fig 1 The blockchain of Bitcoin

例えば Bitcoin のブロックチェーンでは、ブロックの全トランザクションから Merkle Tree Root ハッシュ値を算出し、さらにタイムスタンプやこのブロックの nonce、次の nonce 算出の目標値と共にヘッダに保存される。これらの一つでも改ざんされればすぐに検出することができる。直前のブロックのハッシュ値は \({\rm SHA256}({\rm SHA256}({\rm header}))\) によって算出される。

Merkle Tree

ハッシュ値を再帰的にハッシュ化することで得られるツリー構造。発明者の名前をとってマークルツリー (Merkle tree) と呼ぶ。このルートのハッシュ値はすべてのノードのハッシュ特性を含んだ小さなサイズの値である。

ブロックチェーンの種類によってハッシュ関数等の違いはあるものの、ツリーの値のいずれも変更されていないことを検証するためにマークルツリールートが使用されている。また、light node と呼ばれる一部のユーザ情報のみに限定したノードでは、ブロックの中の必要なトランザクションとそれを検証するためのマークルツリー状のハッシュ値のみを保存することでデータ量を軽減している。

Merkle Tree
Fig.2 Merkle Tree

Fig.2 のような Merkle Tree を持つブロックがトランザクション C を含んでいるかを検証するには、

ハッシュ関数の特徴

  • 計算が速い。
  • 不可逆である。ハッシュ地の算出は簡単だが、ハッシュ値から元の値を復元することが現実的に不可能である。

コンセンサスメカニズム

整合性のあるブロックチェーンを生成するためにノード間で合意に至るプロセスはコンセンサス (consensus) と呼ばれる。Proof of Work, Proof of Stake, pBFT などはコンセンサスアルゴリズムである。ブロックチェーンネットワークは多数の参加者が同じコンセンサスを採用していなければならない。

選出アルゴリズム

ブロックを生成する権利を持つノード (一般に Leader, Block Generator, Proposer などと呼ばれる役割) の選出方法。この記事では Proposer と呼ぶ。

Proof of Work (PoW)
パブリックブロックチェーンにおいて最も有名で一般的な選出アルゴリズム。コンピュータの演算能力を利用して、最初にある条件を満たす "答え" を算出したノードが Proposer となる権利を得る。シビル攻撃 (Sybel attacks) 耐性を持つ。
Proof of Stake (PoS)
広義には暗号通貨の所有高によって新しいブロックの生成難度が低くなるメカニズム (。大量の通貨を保持すれば不正を行うことができるが、その不正によって所有通貨の信頼が既存され損失を被ることを阻止力としている。
Delegated Proof of Stake (DPoS)
PoS と似ているが、それぞれのノードが投票という意味で別のノードにトランザクションの検証を委譲できる stake を持っている。
Proof of Importance (PoI)
省電力と低電力環境での効果を狙って設計されたもの。信頼と重要性を確立するために、利害関係だけではなくトークンの使用と移動状況からトランザクションの重要度を算出する。
Proof of Elapsed Time (PoET)
各ノードには新しいブロックを生成するリーダーを選出するためのランダムなタイマーが与えられる。2016 年に Intel によって開発され Hyperleadger Swatooth で使用されている。
Proof of Burn (PoB)
ブロックチェーン上の資金を検証可能で保留にできないアドレスに送信することで「焼却」したとみなす。一般的には、あるブロックチェーンから別の種類のブロックチェーンに資金を移行するために使われている。
Proof of Activity (PoA)
ノードは認証局によって発行された ID や証明書を持ち、ネットワーク全体からランダムなノードが選択される。

コンセンサスという表現を使う場合は PoW のような finality のないメカニズムも含んでいる。PoW はどれだけ時間が経過しても 100% 結果が確定するわけではないため、コンセンサスメカニズムは必ずしも分散合意アルゴリズムではない。

分散型アプリケーション

dApp (decentralized application; 分散型アプリケーション) は P2P ネットワークを利用して機能するアプリケーション。ブロックチェーンに限らず BitTorrent アプリなどにも該当する用語である。ブロックチェーン界隈においては「暗号化された分散技術を使用するコンセンサスメカニズムを持ったトークンを扱うオープンソースのアプリケーション」との定義があるが、この単語が使われている状況を鑑みて解釈の幅は持った方が良い。このページではブロックチェーンネットワークに参加するアプリを前提とする。

バックエンドの集中サーバを利用するアプリケーションとは対照的に dApp は分散型 P2P ネットワークをバックエンドとして利用する。あるいは、自分自身がネットワークに参加して計算資源を提供する。ネットワークに参加するモチベーションとして何らかの報酬が考慮されていることがある。

スマートコントラクト

スマートコントラクト (smart contract) はブロックチェーンネットワーク上に格納された小さなプログラムによって表される、トランザクションの取引条件の正当性を検証するためのルールである。取引を確定する際の第三者による検証コストを排除し、履行の検証を自動的に実行することを目的としている。データに対する役割としては RDB 上の CHECK やその他の制約に相当する。

スマートコントラクトはトランザクションを検証するノード上で実行されるため、パブリックブロックチェーンでは無限ループや時間のかかる処理を不可能にするために一般的にチューリング完全ではない仕様となる。例えば Ethereum の Solidity という言語にはループや goto 命令、再帰命令が存在しない。また実行ステップ数に応じてインセンティブを得られるように Gas という概念を導入している。コントラクトの実行ごとに一定量の Gas を用意し、ステップごとに Gas を消費し、Gas が 0 になった時点で強制的に処理を中断してトランザクションは失敗する。EVM (Ethereum Virtual Machine) で動作する。

取引ルールを明確化しブロックチェーンネットワーク上の各ノードが共有することで、第三者による不当な拒否や不正取引の履行を防ぐことができる。また取引がどのようなコントラクトによって履行されたかも監査記録として明確である。従ってスマートコントラクトは完全に冪等 (idempotent) でなければならない。

ブロックチェーン間の資産移動

サイドチェーン (sidechain, pegged-sidechain) はあるブロックチェーン上のデジタル資産を別のブロックチェーンネットワークに移して運用し、必要に応じて元のブロックチェーンに戻すアーキテクチャ。既存のブロックチェーンのスケーラビリティを強化したり、運用を物理的に区分する、あるいは異なるブロックチェーン間での資産移動を行うことを目的としている。元のブロックチェーンはメインチェーンやプライマリチェーンと呼ばれる。

まず送信元ブロックチェーン上で送信資産をロックし、送信先ブロックチェーン上でトランザクションを作成する。このトランザクションに対して、送信元ブロックチェーン上で資産が正しくロックされていることを暗号的証明で提供する。

サイドチェーンに対応していないブロックチェーン設計でも、メインチェーン上の資産を存在しないアドレスに送金することで意図的に消失させ、サイドチェーン側で同額を発生させる方法で資産を移動させることができる (Proof of Burn と呼ばれる)。ただしこの方法はメインチェーン側に資産を戻すことはできず one-way peg と呼ばれる。

パフォーマンス

1 ブロックのサイズを \(S_b\)、トランザクションの平均サイズを \(\bar{S}_t\)、1ブロックを生成するまでの (設計により調整された) 時間を \(t_b\) としたとき、1秒あたりに処理できるトランザクション数 tps は以下のように概算することができる。\[ {\rm tps} = \frac{S_b}{\rm \bar{S}_t \times t_b} \]

Bitcoin におけるスループットは概ね 7[trx/sec] 程度である。これはブロックサイズが小さいことと、PoW によるブロックの生成時間が長すぎることに起因している。Ethereum のブロック生成時間はもっと短いがブロックはもっと小さいことから良くて 14[trx/sec] 程度である。Stellar, Bitshares, Waves などいくつかのブロックチェーンでは 1,000[trx/sec] を達成している。世界全体の VISA のピークトランザクション数 40,000[trx/sec] はブロックチェーンのパフォーマンスを考慮するうえでしばしば比較対象となる。

ブロックチェーンの分類

Public Blockchain

トランザクション生成や合意プロトコルの実行への参加に制限を設けていない運用を想定したブロックチェーンネットワーク。認可不要型 (permissionless) とも呼ばれる。

合意形成で負担するコストを上回る参加モチベーションを設計する必要があるため、一般的に何らかのインセンティブを設定している。また Proof of Work や Proof of Stake のようなコンセンサスアルゴリズムを使用して客観的な検証を行っている。Bitcoin や Ethereum はパブリックブロックチェーンを使った暗号通貨の実装である。

Private Blockchain

ネットワーク管理者から許可されない限り参加することができないブロックチェーンネットワーク。認可型 (permissioned) とも呼ばれる。ユーザが自由にトランザクションの履歴閲覧や新規発行することができない閉じたエコシステムとして機能する。トランザクション検証とブロック生成を行うノードへの参加のみに制限を持つタイプを semi-private blockchain と呼ぶこともある。

プライベートブロックチェーンは、ブロックチェーンの高い改ざん耐性に興味があるが、パブリックネットワークでの運用には向いていないシステムに適している。複数の組織 (意思決定機構) がお互いのトランザクションを安全に記録し、交換するために運営されるものを Consortium Blockchainと呼ぶ。

ブロックチェーンの読み込みはパブリックかユーザ自身のもののみだが、ブロック追加の権限は単一または認可された複数の組織のみが持っている。トランザクションの検証は少数のノードによって行われる。

暗号通貨の Ripple や NEM は運営組織の存在するプライベートブロックチェーン上で運営されている。

ブロック生成時間と目標値

Bitcoin では 10 分、Ethereum では 15 秒程度となるようにターゲットの難度が調整される。

Proof of Work では、マイニングに成功したノードはすぐさま次のブロックのマイニングを始めることができるが、他のノードは成功したブロックを受信するまで次のブロックのマイニングを行うことができない。Ethereum のようにマイニングの難度が低い (時間が短い) 設計ではマイニングに成功したノードが後のマイニングにおいても有利になり中央集権化する可能性がある。また複数のノードが同時に算出するケースが増え、チェーンの分岐が増えてトラフィックや処理量の増加をもたらす。

Ethereum の GHOST プロトコルはブロックの重さを定義しており、分岐が発生したときに最も重いブロックを採用するようになっている。重さは 6 世代前までの ommer ブロックとして定義される。ommer ブロックは、自分の親の親の子のうち自分の親を含まないブロック。採用されなかったがマイニングに成功したブロックに報酬が支払われることで中央集権化しづらくし、計算資源の無駄を軽減する。

Pros and cons

情報が高度に分散化されていることから一部の勢力によってプロトコルの変更を行う権限がない。

参加者のインセンティブによって運営することができる。国や銀行などとは独立したデジタル資産として使用できる。

匿名性。透明性。

一般的にプライベートブロックチェーンが採用するコンセンサスアルゴリズムはファイナリティ (finality; トランザクションが確定するタイミング) が存在している。これは、いくら時間が経っても取引が覆される可能性が 0 にはならない (つまり分散トランザクションではない) パブリックブロックチェーンに対する利点である。また分岐が発生せず PoW や PoS よりも計算量やネットワーク負荷が少なく高速に機能し電力消費も少ない利点がある。

参加メンバーが交渉するによってガバナンスが適用できること。

参考文献

  1. (2014) Enabling Blockchain Innovations with Pegged Sidechains