Blockchain: コンセンサス
概要
一般的な分散システムの文脈でのコンセンサスは、一貫性 (consistency) を達成するための役割選出 (リーダー選挙)、合意、同期、競合の解決や調整といったメカニズムを包括的に指した言葉である。しかし、ブロックチェーンに関する論文やブログではコンセンサスが内包するこれらのメカニズムを分解しないまま論議がなされており、中には選出メカニズムと合意メカニズムが同列で比較されているような間違いも起きている。
この背景には、Bitcoin の最初のバブル期である 2017 年前後に数多くの Proof-Compliant が乱造されたことがある。それらの多くは新規性のある権利の証明メカニズムというより、XXX-based (XXX に基づいて決める/信用する) を Proof of XXX と言い換えた、世間の注目と投資家の出資を集めるためのバズワードといった向きが強く、現在となっても不正確な分析を引き起こしている。
この記事ではブロックチェーンにおけるコンセンサスを分散システムの観点でより正しく分類し特徴を述べる。
Table of Contents
導入
| Blockchain | Election | Consistency | Finality | Byzantine | Participants |
|---|---|---|---|---|---|
| Bitcoin | PoW | The longest-branch wins | ✘ | ✔ | permissionless |
| Ethereum | PoS + PoW (difficulty-weighted PoW) | The heaviest-branch wins | ✘ | ✔ | permissionless |
| NEM | Round Robin + PoI | BFT | ✔ | ✔ | private |
| NEO | DPoS | dBFT | ✔ | ✔ | |
| EOS | DPoS | BFT | ✔ | ✔ | |
| TRON | DPoS | BFT | ✔ | ✔ | |
| Zilliqa | PoW | pBFT | ✔ | ✔ | |
| Ontology | Random Selection + PoS | BFT (VBFT) | ✔ | ✔ | |
| Algorand | VRF + PoS | BFT | ✔ | ✔ | |
| Polkadot (BABE) | PoS + PoW (difficulty-weighted PoW) | GRANDPA | ✔ | ✔ | |
| Polkadot (GRANDPA) | PoS | BFT | ✔ | ✔ | |
| Tendermint | Round Robin + PoS | Tendermint-BFT | ✔ | ✔ | private |
| Ostracon | Random Selection + PoS | Tendermint-BFT | ✔ | ✔ | private |
| Diem | PoS | DiemBFT (based on HotStuff) | ✔ | ✔ | private |
| Hyperledger Fabric (BFT) |
Round Robin | BFT-SMaRt | ✔ | ✔ | private |
| Hyperledger Fabric (Message Ordering) |
Static | Kafka | ✔ | ✘ | private |
| Hyperledger Fabric (Transaction) |
Raft | Raft | ✔ | ✘ | private |
| Ripple | ? | FBA | ✔ | ✔ | private |
| Stellar | ? | FBA (SCP) | ✔ | ✔ | private |
選出アルゴリズム
ブロックを生成する権利を持つノード (一般に Leader, Block Generator, Proposer などと呼ばれる役割) の選出方法。この記事では Proposer と呼ぶ。Proof of Work のように非決定論的な選出は PoS や BFT のような決定論的アルゴリズムと組み合わせることで決定論的な操作にすることができる。
静的な役割
システムに必要な役割を特定のノードまたはクラスタに固定的に割り当てているもの。これは非ブロックチェーンの分散システムと同様のもので、メカニズムではなくシステム設計の範疇である。例えば Hyperledger Fabric の一形態は Ordering Service として固定的な Kafka クラスタが存在する (Kafka クラスタ内で行われているリーダー選挙とは別の話)。また IOTA 1.0 で DAG を直列化するコーディネーターは固定的なサービスである。
ボトルネックになる選出メカニズムがないためもっとも高速だが、Byzantine 耐性や非中央集権化を諦めることになるため、信頼のできるノードで構成されたプライベートブロックチェーン向けである。
ラウンドロビン
ラウンドロビンは候補の中から決定性のある順序で役割を割り当てる選出メカニズム。加重ラウンドロビン (weighted round-robin) であっても単純な整数演算のみで決定するため高速である。具体的な実装では、Hyperledger Fabric (BFT-SMaRt) や ICON は固定数のノードの中からラウンドロビンで Proposer を決めているし、Tendermint は PoS と組み合わせて加重ラウンドロビンによって Proposer を決定する。
ラウンドロビンは決定性を持つため将来の役割がどのノードに割り当てられるかを誰でも知ることができる。この特性はパフォーマンスの改善に利用することができる。例えば ICON では通常 3 フェーズ必要な BFT の最後の commit フェーズと次の Proposer の prepare フェーズをオーバーラップすることで 1 フェーズ分の時間を短縮しているし、Tendermint の軽量クライアントが持つ skipping verification はいくつかの検証をスキップすることができる。
一方で、将来の選出の予測が容易であることから、Byzantine ノードが混在したケースでの共謀や標的型攻撃に対する耐性は低くなる。
ランダム選択
ランダム選択は公平な乱数を使用して候補の中から役割を割り当てる選出メカニズム。乱数はまたはそのシードは恣意的に選択されたものでないことが設計上保証されていたり、第三者によって検証できなければならない。現在のラウンドが終わった時点で次のラウンドの役割が決定することからラウンドロビンと比較して攻撃耐性は高くなっている。ただし、ラウンドロビンの決定論的な動作によってもたらされていたようなパフォーマンス改善策は適用できない。
具体的な実装例は Ontology と Ostracon で VRF に基づく乱数を使用して候補ノードの中から Proposer や Validator を割り当てている。
自己抽選
自己抽選型の選出は、自分が当選したことはすぐに分かるが他の参加者の誰が当選しているかを容易に知ることができない方法である。ブロックをブロードキャストするまで誰が当選者か分からない匿名性によって当選者が妨害を受ける危険性は少ないが、自分が選出されたことを証明するための何らかの方法が必要となる。
自己抽選型の選出メカニズムは他人に見えないように行うコイントスに似ている。例えば Proof of Work は極めて低い確率で表 (当選) の出るコインを表が出るまで短時間で繰り返しトスするのに似ている。また VRF 自己抽選や Sleepy コンセンサスは一定の確率で表の出るコインをラウンドごとにすべてのノードが 1 回トスするのに似ている。
自己抽選型の選出は確率論的な当選となるため、1 ラウンド (あるいは一定時間内) に誰も当選者が出なかったり複数の当選者が出ることがある (VRF 自己抽選で例えると 1/100 で表の出るコインを 100 人がトスしても現実には当選者がいなかったり 3 人が当選したりするだろう)。したがってこのメカニズムによる選出だけでは決定論的ではなく、状態を確定させるためにはさらなるメカニズムが必要となる。
Proof of Work
PoW は Nakamoto コンセンサスとも呼ばれる、もっとも世に知られているブロックチェーンのコンセンサスメカニズムである。この選出メカニズムは、あるターゲット値よりも小さいハッシュ値を生成するような nonce を探し当てたノードが役割を得る。自分自身で当選を引き当てることから自己抽選型と言える。このメカニズムは Bitcoin や Ethereum で使用されており、この高負荷の抽選処理は暗号通貨の "マイニング" として知られている。
当選のためには単純に計算力が必要であるため、少数のノードで大量のアカウントを作成するようなシビル攻撃 (Sybil attacks) 耐性を持つ。
VRF 自己抽選
P2P ネットワークに参加しているすべてのノードがある共通のシードに基づいて検証可能な乱数を生成し、その値が規定のしきい値を超えているかで各々が当選を判断する自己抽選型メカニズム。PoW で大量の CPU リソースを消費していたハッシュ計算を 1 回の VRF ハッシュ計算に置き換えているため、PoW と同等の非中央的な構造でありながら高速なブロック生成を行うことができる。このメカニズムは (多分特許付きで) Algorand が実装している。
一方で、PoW で複数の選出が起きるのと同様に VRF 自己抽選の選出数も正確ではない。これは確率 \(p\) で表が出るコインを \(N\) 回トスして表が出る回数に相当することから、統計的なモデルでは二項分布に従う。
Sleepy コンセンサス
VRF 自己抽選のメカニズムと似ているが、VRF の代わりに共通参照列 (CRS; common reference string) とハッシュ関数、ゼロ知識証明を使ってノードごとに生成された乱数が誠実に算出されたものである証明を行っている。
Proof of Stake
ノードが保有する暗号資産あるいはそれに類する掛け金を Stake とみなし、コンセンサスにおける選出されやすさや投票権、発言力としてそのノードの影響力を調整するメカニズム。PoW における計算コストの非効率さを解消するために Peercoin (2012) や Nxt (2013) で導入された。基本的に PoS 自体は選出や合意のメカニズムではなく、他のメカニズムに追加する重み付けのようなの特徴として利用される。
- 決定性の追加. ノードの参加が自由な public (permissionless) P2P ネットワークは非決定的である。ある瞬間のネットワークを構成するすべてのノードを把握することができないため、役割選出のための候補を特定することができない。しかし暗号通貨と同様に決定性を持つ Stake を導入することによって、選出に参加できる権利を持つノードをすべてのノードが決定論的に認識することができるようになる。
- 性能改善. PoW のような勝者総取りスキームの下では勝者のパフォーマンスに全体の性能が影響される。言い換えると、ノードごとの有利さに優劣を設定することで、全体的なパフォーマンスは最も有利なノードの選出時間となることが期待できる。Ethereum では大量の Stake を保有するノードの difficulty が下がるため PoW の時間が短縮され全体のパフォーマンスを改善している。
- 誠実な参加の促進. 多くの暗号通貨を保有することで多くの報酬が期待できるという設計は、暗号資産を保有しブロックチェーンネットワークへ参加する動機となる。P2P ネットワークでは参加ノードの多さは 51% 攻撃の耐性となる。また大きな Stake を保有している攻撃者が悪意的な行為を行って暗号通貨の社会的価値を毀損した場合、その攻撃者自身の資産価値も落ちて大きな損失を受けることになる。これらは結果的に運営の健全性に寄与する。
PoS は中央集権的で大量の資産保有者がさらに有利に資産を増やすという批判もある。また報酬目的の暗号資産保有者が増えたとしてもそれは取引や購買といった本来の流通ではなく、暗号資産の固定化や死蔵化に繋がり暗号通貨にマイナスに働く可能性がある (タンス預金で貨幣流通と経済が収縮する状況に似ている)。
Nothing at Stake 攻撃
Nothing at Stake は Stake の大口保有者が資産差し押さえの罰則を回避してフォークを発生させる PoS 固有の攻撃である。PoS では最大の Stake を保有しているノードは比較的容易に不正な動作を起こすことができるが、一方で、不正行為の処罰として (一般に) Stake の差し押さえを行うことでそれを抑止している。しかし、例えばある Stake の大口保有者 \(A\) がすべての Stake を B 銀行の自分の口座に出金する取引が完了した直後、まだ自分が大口保有者だった過去のブロックから別のブロックをフォークさせ、今度はすべての Stake を C さんのアドレスに送金する取引を成立させた場合、悪意的な二重支払い (double spending) を仕掛けるフォークを引き起こしたことは明らかだが、フォークしたどちらの枝も Stake は既に他者に譲渡されていることから資産差押えによる罰則を与えることが難しい。
Proof of Stake Time
PoSt は PoS の発展形で、Stake 保有量だけではなくその保有期間も加味する。短期間しか保有していないノードを過度に有利にしないことで、複数のノードで分散して保有していた Stake を特定のラウンドを狙って一つのノードに集中させ合意を乗っ取るような行為の抑止が期待できる (ただし流動性はより低下する)。
Peercoin は Stake 保有量と保有期間に由来する coin age と呼ばれるパラメータに基づいてブロック生成者を決定している。
Delegated Proof of Stake
DPoS は Stake 保有者の投票で選出されたノードがブロックを生成するメカニズム。PoS では大口の Stake 保有者がブロック生成者に選ばれやすくマイニング報酬を得る機会が偏る設計だったが、DPoS の Stake 保有者は参加者の中に投票して必要な役割を決定する。
Stake 保有者は 1 Stake を 1 票として参加者に投票を行う (保有 Stake の範囲内で複数の参加者に投票することも可能である)。ただし特定の参加者に連続して投票することはできない。投票に参加した Stake 保有者の総 Stake 量が全体の 50% 未満だった場合は無効選挙となる。
立会人 (witness) はトランザクションを検証しブロックを生成する役割を持つ。Stake 保有者は正直に行動することが期待できる参加者に投票し立会人を選出する。立会人の数は EOF で 21、BitShares では Lisk が 101、ARK が 51 である。立会人が悪意的な行動を行うと 1 分で Stake 保有者たちに通知され、Stake 保有者の投票によってその立会人は排除されて将来の報酬を得る機会を失う。
BitShares では 1 日ごとに投票を行い立会人を更新する。選出された立会人はラウンドごとにシャッフルされた順序で 2 秒に一つの速度でブロックを生成する。ブロックの検証はラウンドが終わるまでに各立会人に付き一回実行できる。
ラウンドごとにシャッフルされたブロック生成の順序は決定論的でありすべての参加者が知っている。したがって、立会人があるラウンドのブロックを生成するとき、新しいブロックをどのブロックに接続すべきかが分かっている。また、新しいブロックの前に何個のブロックが存在すべきかも明らかであることから、もしどこかのブロックでフォークが発生していたとしても、最も長い枝をすぐに選択して The Longest History Wins ルールで動作することができる。
代表者 (delegates) も同様に Stake 保有者の投票によって選出される。代表者の目的は DPoS ネットワークを改善するための、例えばブロックサイズ、生成間隔、立会人が受け取るトランザクション手数料といったパラメータ変更の提案である。ただし、ネットワークが大きくなるほど 51% 以上の Stake 保有者からパラメータ変更の賛同が得られるのは難しくなる。
Leased Proof of Stake
Stake 保有者が自分の Stake を Staking Node に貸し出し (リース) することで Staking Node の重みを増やして選出確率を上げるメカニズム。
様々な Proof-Compliant
Proof of XXX
一貫性アルゴリズム
または競合の解決または調整のためのアルゴリズム。
選択ルール
分散システムに対する一貫性モデルの中では該当するものはない。
Bitcoin の最長優先ルール
Ethereum の最重優先ルール
DAG
DAG (directed acyclic graph) または Tangle と呼ばれる。したがってクライアント中心の一貫性モデル
の中でも単調な書き込み一貫性 (monotonic write consistency) に相当する。
BFT プロトコル
BFT (Byzantine fault tolerance) はビザンチン故障プロセス (最大限悪意的に振る舞うプロセス) が一定数存在したとしても安全に強い一貫性を達成することのできる特性である。ブロックチェーンへの適用では検証フェーズにおいてブロックが正しいことを Validator 間で合意するために使用するケースが多く、それ以外では Ethereum 2 のように fork した枝を選択するための合意プロトコルとしても使用されている。一般に金融取引のような強い一貫性を必要とする要件では BFT を適用する必要がある。
一般に BFT はシステムが許容可能なビザンチン故障プロセス数の上限を定めるプロトコルとなるため、悪意のノード数を想定できない完全なオープンネットワーク向けのブロックチェーンには適さない。
pBFT
pBFT (practical Byzantine fault-tolerance) はビザンチン障害耐性を持つ非同期分散合意アルゴリズムとして最も古典的で十分に研究されたプロトコルである。ブロックチェーンでも BFT-SMaRt や Tendermint-BFT など多くの pBFT 派生プロトコルがある。
元々 pBFT はステートマシンレプリケーションを目的としているため、各ラウンドの終了ごとにすべての正常なプロセス (ここでは validator が同一の状態になることを保証し、その結果として強い一貫性をもたらしている。一方、ブロックチェーンは検証済みのブロック (トランザクション列) によって一貫性を保証する。Validator に期待されるゴールは安全性を保証する結果 (ブロックや署名) を出力することである。言い換えると、検証時に大量のメッセージ交換を経て Validator 間で状態同期することは必ずしも必要な動作ではない。
このように、pBFT に基づくブロックチェーンは必ずしも必要ではない状態同期を強いる設計になっていることが他の BFT プロトコルと比べて \(O(n^2)\) という非効率的な通信複雑性となる理由である。
DiemBFT / LibraBFT
DiemBFT (旧 LibraBFT) は Facebook が提唱するブロックチェーンおよびその暗号通貨 Diemで使用されている HotStuff-BFT 派生プロトコルである。このプロトコルは次のようにブロックを生成する。
- ラウンド \(r\) の Proposer \(P_r\) (DiemBFT ではリーダーと呼ぶ) は提案ブロック \(B_r\) をネットワーク全体にブロードキャストする。
- 次の Proposer \(P_{r+1}\) は \(B_r\) を受信すると次のブロック \(B_{r+1}\) の生成を開始する。
- \(V_{r,*}\) は \(B_r\) を検証し、検証結果を次の Proposer \(P_{r+1}\) に送信する (2 と 3 は並行して行われる)。
- \(P_{r+1}\) は定足数の検証結果を受信すると定足数証明書 QC (quorum certificate) を生成して次のブロック \(B_{r+1}\) に埋め込み提案ブロックを完成する (1 に戻る)。
この動作は各 Validator の検証結果を次の Proposer が確認することで pBFT における通信複雑性 \(O(n^2)\) を \(O(n)\) に効率化している。また検証と次のブロック生成が同時に進行するようにパイプライン化されているため全体的に高効率である。
Proposer \(P_{r}\) が故障した場合、同じラウンドの Validator \(V_{r,*}\) がタイムアウトを検知してタイムアウト証明書 TC を生成して次の Proposer \(P_{r+1}\) に送信する。また Validator \(V_{r,*}\) が故障した場合は次の Proposer \(P_{r+1}\) がタイムアウトを検知する (このとき \(P_{r+1}\) が TC を生成するか前の QC を使うのか確証がない)。いずれの場合も \(P_{r+1}\) は前のブロック \(B_r\) が正しく生成されなかったものとして、自分が観測している最も高いラウンドの QC のブロックに新しいブロック \(B_{r+1}\) を連結する。
この回復動作のため DiemBFT は攻撃やプロセスの故障によってフォークが発生する可能性がある。このため、連続した 2 つのラウンドのブロックに次のブロックが連結されたときに、その 2 つのラウンドの先頭のブロックまでが確定することを保証する設計になっている (v4 より前は連続する 3 ブロックが必要だった)。
各 Validator \(v_i\) は \(r'_i=0\) を初期値とする優先ラウンド (preferred round) という状態を持つ。\(v_i\) があるラウンド \(r\) のブロック \(B_r\) に投票したとき、その \(B_r\) の 2 つ前のブロック \(B_\gamma\) ラウンドが \(r' \gt \gamma\) であれば優先ラウンドを \(r':=\gamma\) で更新する。
Validator が投票できるラウンドには制約がある。
- すでに投票したラウンドより前のラウンドのブロックには投票できない。例えばラウンド \(r\) に投票した Validator は \(r+1\) 以降のラウンドにしか投票できない。
- 一つ前のブロックのラウンドが優先ラウンドより低いブロックには投票できない。
Federated Byzantine Agreement
FBA。Ripple によって開発され Stellar も適用している。システムレベルで合意するために参加者の完全リストを必要とせず、オープンなメンバーシップをサポートしている。PoW や PoS と比較して計算資源が少なくて済む。