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 |
| Libra | PoS | LibraBFT (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
PoW はあるターゲット値よりも小さいハッシュ値を生成する nonce を探し当てたノードが役割を得る選出メカニズム。自分自身で当選を引き当てることから自己抽選型である。Bitcoin や Ethereum で使用されており暗号通貨のマイニングとして知られている。
シビル攻撃 (Sybil attacks) 耐性を持つ。複数のノードがほぼ同時に選出される可能性があることから決定論的ではない。
VRF 自己抽選
P2P ネットワークに参加しているすべてのノードがある共通のシードに基づいて検証可能な乱数を生成し、その値が規定のしきい値を超えているかで各々が当選を判断する自己抽選型メカニズム。PoW で大量の CPU リソースを消費していたハッシュ計算を 1 回の VRF ハッシュ計算に置き換えているため、PoW と同等の非中央的な構造でありながら高速なブロック生成を行うことができる。このメカニズムは (多分特許付きで) Algorand が実装している。
一方で、PoW で複数の選出が起きるのと同様に VRF 自己抽選の選出数も正確ではない。これは確率 \(p\) で表が出るコインを \(N\) 回トスして表が出る回数に相当することから、統計的なモデルでは二項分布に従う。
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 は 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 プロトコル
逐次一貫性
Federated Byzantine Agreement
FBA。Ripple によって開発され Stellar も適用している。システムレベルで合意するために参加者の完全リストを必要とせず、オープンなメンバーシップをサポートしている。PoW や PoS と比較して計算資源が少なくて済む。