Blockchain
概要
分散システムにおけるブロックチェーン (blockchain) とは、ビザンチン障害耐性をもつ分散合意アルゴリズムを使ったステートマシンレプリケーション (SRM) として機能する Peer-to-Peer ネットワークである。特に、合意によって生成された命令シーケンスは暗号技術を使用してリンクされた不変のブロックのリストとして分散共有される (データ構造の文脈ではこのブロックのリストをブロックチェーンと呼ぶ)。暗号通貨やトレーサビリティの用途では改ざん不可能な取引や譲渡のログであることから分散型台帳技術 (distributed ledger technology; DLT) とも呼ばれる。
一度記録されたされたブロックを変更するには、それより後のすべてのブロックを遡及的に書き換える必要があり、その操作は P2P ネットワークでブロックを共有している多数のノードの合意なしに行うことができないことから、改ざんに対して比較的安全な技術と認識されている。このためブロックチェーンは高い分散性を備えた分散コンピューティングシステムの一例として、2 者間の取引を効率的に検証可能かつ恒久的な方法で記録できるオープンで分散した台帳技術と考えられている。
ブロックチェーンは Bitcoin
の取引を行うために考案された分散ネットワーク技術である。この発明により Bitcoin は集権機関や中央サーバを必要とせずに二重支出問題を解決した最初の暗号通貨となった。
現在、ブロックチェーンという言葉は ISO-22739:2020 の Vocabulary で次のように定義されている。歴史的に Bitcoin のインパクトから Bitcoin のブロックチェーンを前提とする人も少なくないが、proof-of-work や P2P のオープンネットワークであることは必ずしもブロックチェーンに必要な要件ではない点に注意。
blockchain: distributed ledger with confirmed blocks organized in an append-only, sequential chain using cryptographic links. Blockchains are designed to be tamper resistant and to create final, definitive and immutable ledger records.
Table of Contents
データ構造
データ構造としてのブロックチェーンはブロックと呼ばれるデータの単純な片方向リスト構造である。各ブロックは前のブロックのハッシュ値とタイムスタンプ、トランザクションと呼ばれる処理単位、およびトランザクションのハッシュ値 (通常、Merkle Tree ハッシュルートとして) を含んでおり、P2P ネットワーク上で共有され複数のノードによって検証される。
トランザクション
ブロックチェーンの目的は直列に並べられた比較的小さなデータを格納することである。特に暗号通貨やトークンのような金融取引を目的としたブロックチェーンではデータは処理命令であり、ブロックに含む最小単位の操作命令をトランザクション (transaction) と呼ぶ。トランザクションがどのような内容のデータかはそれを解釈するブロックチェーン上のアプリケーションに依存する。
トランザクションの操作はアトミックかつ決定論的であり、全てのトランザクションを最初から順序通りに適用すれば誰でも任意の時点の状態を復元することができる。ただしトランザクションは粒度が高く、それ自身を転送や検証の単位とするには処理コストが高いためブロック (block) と呼ばれる単位に集約して流通する。
一般にブロックチェーンはアカウントモデル (account model) と UTXO モデル (unspent transaction output model) に分類され、それぞれトランザクションの処理命令の表し方が違っている。
- アカウントモデル
-
ステートマシンの考え方に基づいたモデルで、各ノードの状態データベースはユーザごとの口座残高を管理している。アカウントモデルのトランザクションは「口座 A から口座 B に量 X を送金」といった命令を表す。
- UTXO モデル
-
現実の小切手を使った取引に似たモデルで、各ノードは小切手に相当する UTXO と呼ばれるデータ単位を管理する。このデータ単位は過去の取引での出力 (transaction output) のうちまだ支払いに使用されていない (unspent) ものであることから UTXO (unspent transaction output) と呼ばれている。
UTXO は個別の ID を持ち額面の分割や統合はできない。送金処理ではいくつかの UTXO を合算して支払い済みとし、新たに送金 UTXO とおつり UTXO が発行される。
例えば上の図では A から B に 100CU を送金する手続きを示している。A に発行済みで未使用の 58CU, 32CU, 28CU の額面を持つ 3 つの UTXO を消費して B への送金に充てる。結果としてこの取引は B に 100CU と A に 18CU の UTXO を新たに発行する。
アカウントモデルのトランザクションの内容はアプリケーションに強く依存するためブロックチェーンのレイヤーで並列実行する事は困難だが、UTXO モデルのトランザクションは依存関係が明確であるため DAG を解析して容易に並列実行することができる。
多くのブロックチェーンはステートマシンの設計と親和性の良いアカウントモデルを採用しているが、Bitcoin が UTXO モデルであったことや、送金の暗号化やアカウント残高の秘匿を目的に UTXO モデルを使用しているブロックチェーンもある。
ブロック
ブロックは複数のトランザクション (データ単位) に加えてメタ情報として直前のブロックのハッシュ値を保持するデータ構造である。したがって、あるトランザクションの書き換えを試みた場合、そのブロックのハッシュ値が変わることからそれより後に連結されている全てのブロックを遡及的に書き換える必要がある。さらに Proof of Work 型のブロックチェーンではブロックごとに nonce を再計算 (再マイニング) する必要があるためチェーン化されたブロックの書き換えは現実的ではない。
例えば Bitcoin のブロックチェーンでは、ブロックの全トランザクションから Merkle Tree Root ハッシュ値を算出し、さらにタイムスタンプやこのブロックの nonce、次の nonce 算出の目標値と共にヘッダに保存される。これらの一つでも改ざんされればすぐに検出することができる。直前のブロックのハッシュ値は \({\rm SHA256}({\rm SHA256}({\rm header}))\) によって算出される。
Merkle Tree
ブロックチェーンの種類によってハッシュ関数等の違いはあるものの、ツリーの値のいずれも変更されていないことを検証するためにマークルツリールートが使用されている。また、light node と呼ばれる一部のユーザ情報のみに限定したノードでは、ブロックの中の必要なトランザクションとそれを検証するためのマークルツリー状のハッシュ値のみを保存することでデータ量を軽減している。
コンセンサスメカニズム
整合性のあるブロックチェーンを生成するためにノード間で合意に至るプロセスはコンセンサス (consensus) と呼ばれる。Proof of Work, Proof of Stake, pBFT などはコンセンサスアルゴリズムである。ブロックチェーンネットワークは多数の参加者が同じコンセンサスを採用していなければならない。
分散型アプリケーション
dApp (decentralized application; 分散型アプリケーション) は P2P ネットワークを利用して機能するアプリケーション。ブロックチェーンに限らず BitTorrent アプリなどにも該当する用語である。ブロックチェーン界隈においては「暗号化された分散技術を使用するコンセンサスメカニズムを持ったトークンを扱うオープンソースのアプリケーション」との定義があるが、この単語が使われている状況を鑑みて解釈の幅は持った方が良い。このページではブロックチェーンネットワークに参加するアプリを前提とする。
バックエンドの集中サーバを利用するアプリケーションとは対照的に dApp は分散型 P2P ネットワークをバックエンドとして利用する。あるいは、自分自身がネットワークに参加して計算資源を提供する。ネットワークに参加するモチベーションとして何らかの報酬が考慮されていることがある。
スマートコントラクト
スマートコントラクト (smart contract) はブロックチェーンネットワーク上に格納された小さなプログラムによって表される、トランザクションの取引条件の正当性を検証するためのルールである。取引を確定する際の第三者による検証コストを排除し、履行の検証を自動的に実行することを目的としている。データに対する役割としては RDB 上の CHECK やその他の制約に相当する。
スマートコントラクトはトランザクションを検証するノード上で実行されるため、パブリックブロックチェーンでは無限ループや時間のかかる処理を不可能にするために一般的にチューリング完全ではない仕様となる。例えば Ethereum の Solidity という言語にはループや goto 命令、再帰命令が存在しない。また実行ステップ数に応じてインセンティブを得られるように Gas という概念を導入している。コントラクトの実行ごとに一定量の Gas を用意し、ステップごとに Gas を消費し、Gas が 0 になった時点で強制的に処理を中断してトランザクションは失敗する。EVM (Ethereum Virtual Machine) で動作する。
取引ルールを明確化しブロックチェーンネットワーク上の各ノードが共有することで、第三者による不当な拒否や不正取引の履行を防ぐことができる。また取引がどのようなコントラクトによって履行されたかも監査記録として明確である。従ってスマートコントラクトは完全に冪等 (idempotent) でなければならない。
ウォレット
暗号資産取引を目的としたブロックチェーンにおいて、ウォレット (wallet) とはユーザがブロックチェーン上に保有している資産を特定し送金などの取引の始点・終点を表す概念上のオブジェクトである。根本の実体はおおむねユーザが取引に使用する鍵を指している。ウォレットはブロックチェーン上でアドレス (address) と呼ばれる固定長の ASCII 文字表現によって識別される。一般にウォレットのアドレスはその公開鍵に基づいている。
ウォレットにただ一つの鍵ペアしか割り当てられていない場合、そのウォレットのアドレスは固定値となることから、そのアドレス上で行われた取引を追跡して口座の残高や取引先、どのような資産を所有しているかなどを知ることができる。加えて、そのアドレス上での取引が何時いくらの額面で誰に対して行われたかを実社会での活動と照合してアドレスの所有者を推測できる可能性がある。
このような非匿名性を緩和するために、取引ごと、取引目的ごと、あるいは取引先ごとに使い捨ての鍵 (アドレス) を使い、あえてそれらの資産を集約せずにしておくことで匿名性を高める方法が考案されている。ランダムウォレットおよび HD ウォレットは取引匿名化の目的で 1 つのウォレット (1 人のユーザ) が大量の鍵を使用する方法である。
ランダムウォレット
ランダムウォレット (random wallet) はアドレスの匿名性を向上させる目的で初期の Bitcoin クライアントに導入された方法である。これはユーザのウォレット (アカウント) を生成するときにランダムに 100 個の鍵ペアを生成しておき、取引を行うごとに異なる鍵を使用する。すべての鍵ペアを使い切ったら再び 100 個の鍵ペアを生成する。この動作により取引ごとに異なるアドレスとなり匿名性を向上させるが、ユーザは過去に使用したすべての秘密鍵を自分のウォレットに関連付けてバックアップし続けなければならない欠点がある。
HD ウォレット
ランダムウォレットに対して階層型決定性ウォレット (hierarchy deterministic wallet) または HD ウォレットでは、ウォレット生成時にランダムに生成された 1 つの固定長シード値に基づいて多数の鍵ペアを決定論的に生成する。この方法ではシードと階層構造上の位置を示すパスがあればどの鍵も比較的低コストで復元できる利点がある。
HD ウォレットは、階層の位置を示すパスを何らかの方法でアドレスに含める必要があるものの、ユーザのウォレットはシード値とどの位置まで鍵を発行したかの状態のみを保持すればよく、ランダムウォレットのように取引ごとにバックアップ量が線形増加することはない。
HD ウォレットはビットコイン向けに BIP32、BIP44 で仕様化され、その後にいくつかのブロックチェーンでも採用されている。Fig 3 は BIP32 による階層的な鍵生成を示している。
マスター鍵生成時の HMAC-SHA512 の key パラメータには 12 バイトの固定値 "Bitcoin seed" を使用し、それ以降は親のチェーンコードを使用する。data パラメータは、インデックスが \(i\ge 2^{31}\) の hardened child かそうでない normal child かで入力形式が異なる。ECDSA のような離散対数ベースのアルゴリズムでは秘密鍵から公開鍵が生成できる点にも注意。
HD ウォレットを使うとツリー構造の管理ドメインを構築することができる。例えばある階層の鍵ペアとチェーンコードを誰かに渡せば、それより下の鍵を復元して取引操作や監査を委譲することができるが、上層の鍵は復元できないことからその部分木以外の鍵は秘匿されたままである。他の応用例では、BIP44 のように階層の上位を「通貨」「アカウント」のように意味づけすることで、1 つの HD ウォレットから異なる暗号通貨ごとの複数のアカウントごとに鍵を用意することができる。
BIP39 は HD ウォレットのシードをシードフレーズ (seed phrase) またはシードリカバリーフレーズ (seed recovery phrase) と呼ばれる、人間が読める単語 (ニーモニック) の羅列に変換してウォレットのバックアップおよび復元を行う方法を示してる (当然ながらシードおよびシードフレーズは秘密鍵と同等に扱う必要がある)。
ブロックチェーン間の資産移動
サイドチェーン (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 よりも計算量やネットワーク負荷が少なく高速に機能し電力消費も少ない利点がある。
参加メンバーが交渉するによってガバナンスが適用できること。
脅威モデル
- シビル攻撃 (sybil attack)
- 過半数/BFT仮定の崩れ
- 2014 年に Stellar で起きた障害は意図しないフォークは BFT によるコンセンサスでビザンチン仮定が崩れたことに起因するものだった (Safety, liveness and fault tolerance—the consensus choices 参照)。