ブロックチェーンのファイナリティ考察 - Part I

Torao TAKAMI2022-10-07

Blockchain Engineering Team

この記事は LINE Blockchain Mainnet (LBM) のアーキテクチャを説明するシリーズの最初のパートであり、既存のブロックチェーン実装に立ち返って分散システムの観点での現在のブロックチェーンのアーキテクチャとファイナリティの実装要件を説明しています。このコンテキストは次の LBM のコンセンサス機構である Ostracon を理解するのに役立つでしょう。

現在の Ostracon の成果、特にゼロインタラクションでのリーダー選出や通信効率を向上した BFT に関する論議する機会を嬉しく思います。我々 Blockchain Engineering Team と LINE NEXT は現在と将来の Ostracon の分散合意実装に深く関与する VRF (Verifiable Random Function) や署名集約、仮想マシン化の研究を行っています。

ファイナリティに関する考察

2009 年に Bitcoin で最初のトランザクションが発生してから十数年間で様々なブロックチェーンアーキテクチャが生み出されました。当初こそ P2P ネットワークの分散性に注目が置かれていましたが、ポスト Ethereum 世代以降のブロックチェーン実装は分散化 (Decentralize) を重視するアーキテクチャとファイナリティを重視するアーキテクチャとで立場を明確にしています。これは分断耐性 (Partition Tolerance) を持つ分散データベースが可用性 (Availability) を選択するか整合性 (Consistency) を選択するかという CAP 定理の論議に通じています。ただ、現実の分散システム実装ではこれらは必ずしも競合する要素ではなく、整合性の一部を妥協して可用性を上げるような方針を取ることができるソフトウェアもあります。将来的なブロックチェーン実装でも分散化とファイナリティはその利用目的に応じて選択的に調整できるようになるかもしれません。

ブロックチェーンのファイナリティとは、過去のトランザクション実行結果が決して覆されない保証 ─ つまり強い整合性を持つことを意味します。そして、並行プログラミングや分散コンピューティングの実装における整合性と一貫性の方針はシステムの性能とデータの信頼性に直結する最も基本的で重要なテーマです。分散システムにおいて一貫性をもたらしているものは何でしょうか? ファイナリティを持つブロックチェーンと持たないブロックチェーンが存在するのはなぜでしょうか? このパートでは分散システムが一貫性を持つための条件について考えてみます。

ファイナリティの根源

RDBMS が実装している ACID 属性に基づくトランザクション処理 ─ この記事では「強い整合性」と表現します ─ は 1970 年代のメインフレームから現在まで金融を含む世界中のあらゆる情報産業を支え続けています。ここに新しいパラダイムが訪れたのは 2005 年頃のビッグデータでした。飛躍的に進化した計算能力と高速なネットワークによって蓄積された膨大なデータを処理する必要性から、よりスケーラビリティの高いデータベースの需要が高まり始めました。その結果、NoSQL トレンドの一部として「結果整合性」(または弱い整合性) と呼ばれる特性を持った分散データベースが相次いで開発されました。

近年のもう一つのパラダイムはブロックチェーンでした。Bitcoin や (The Merge 前の) Ethereum の実装する PoW (Proof of Work) は自立分散的な P2P ネットワークにリーダー選出、つまり整合性をもたらし、中央機関の存在しない P2P ネットワークであるも関わらず二重支払いの起きない電子的な通貨取引を可能にしました。

ただし、ここは注意深く表現する必要があります。PoW では、二重支払いのような矛盾した状態が発生することはありませんが、本質的に決定性アルゴリズムではないため、ある時点の観測結果が後の観測で変わる可能性があります。より正確には、ある整合性を持つ状態を過去の時点まで巻き戻して別の整合性を持つシナリオを再実行する可能性があります。つまり結果に対して整合性 (Consistency) を持つが一貫性 (Coherence) は持たないという性質です。一般にこの一貫性の欠如に対して「ファイナリティがない」と呼ばれています。

PoW のもたらす一貫性は時間の経過につれ急速に一つの結果に収束しますが、有限時間内に確定に至ることはありません。実際、PoW に基づくブロックチェーンでは短期的にフォーク (分岐) が発生してしばしば結果のロールバックとやり直しが観測されています。この記事ではファイナリティを持たないブロックチェーンの特徴を表す目的で、このような確率的に収束する特性を持つ整合性を「確率的整合性」と呼びます。

このような一貫性の欠落は、大局的にはシステムが有限状態とならないことを意味しています。

ビザンチン障害や任意障害を許容するパブリック P2P ネットワークは、参加している各ノードの状態はおろか、全体のノード数すらも正確には把握できません。つまり、パブリックブロックチェーンの扱うネットワークは本質的に有限状態ではないことを意味します。この点がプライベートネットワークを想定したシステム、つまり強い整合性を持つ HBase や結果整合性を持つ Cassandra といった分散データベースとの最も根本的な違いであり、PoW に基づいたブロックチェーンが確率的整合性となる根底の理由です。

しかしパブリックネットワークであっても何らかの前提を付け加えることで有限状態を作り出すことができます。さらにその有限状態からファイナリティという決定性のある状態を作り出すことができます。ここではその仕組について考えてみましょう。

ブロックチェーンとは何か?: 整合性の根源

同じ状態を持つ複数のノード上で、同じ (決定性のある) 処理を同じ順序で実行すると、結果的に全てのノードは同じ状態を共有しながら遷移します。これは分散システムでレプリカ (複製マシン) を作成する一般的な手段で SMR (ステートマシンレプリケーション) と呼ばれる方法です。SMR は複製によりシステムに可用性 (Availability) をもたらし、処理順序によりそれ自体が論理クロックとして機能することで整合性 (Consistency) をもたらします。分散システムでは全てのレプリカに同じ順序で (同時刻である必要はありません) で到達することが保証されているメッセージ配信を Atomic Broadcast と呼びます。

ブロックチェーンのアーキテクチャは、あるリーダー役が順序付けたトランザクションを全ての P2P ノードに Atomic Broadcast するという SMR の設計に基づいています。その本質は直列化されたトランザクションです。しかし、実際のトランザクションはとても粒度が高く、一つ一つを署名や配信するとシステム全体の大きなパフォーマンス低下をもたらします。このため現在のブロックチェーン実装では複数のトランザクションをブロックや DAG といった順序付けられたグラフ構造に束ねてバッチ化し署名して配信を行っています。

つまり、現実的なブロックチェーン実装で「ブロックを作る」とはネットワーク全体で共通した処理の順序を定義することと等価であり、ブロックチェーンそのものは直列化され順序付けられた処理そのものを表しています。そして、全てのレプリカ (フルノードに相当) がその順序で全ての処理を実行することでネットワーク全体のノードは同じ状態を共有します。

処理の順序付けは必ずしもブロックのようなリスト構造である必要はありません。DAG 型のブロックチェーンは一見して処理が直列化されていないように見えますが、DAG という構造はトポロジカルソートが可能という特徴を持っており、衝突のない処理順序を決定することができます。例えば、ワークフローエンジンやジョブスケジューラーのようなプロセス管理システムでは一般的に DAG を使ってタスクの依存関係を定義しています。

コンソーシアムチェーンである Hyperledger Fabric の初期のバージョンはネットワークに Message Ordering Service (Kafka のようなメッセージキュー) を導入して処理の直列化を行っていました。やや強引に思える解ですがシステム設計の観点では直感的で目的に適した解決方法と言えるでしょう。

全てのブロックチェーンは根底に二重支払いのような矛盾状態の排除を強く意識しています。したがってその設計には必ず「処理の直列化」が存在し矛盾のない状態を保証しています。では、処理の直列化によってブロックチェーンの整合性は確保できますが、一貫性 = ファイナリティの有無は何に起因しているのでしょうか?

強い整合性を持つ分散データベースはネットワーク上にリーダー (または Proposer, Master, Coodinator, Transaction Monitor と呼び名は様々ですが) と呼ばれる特別なノードが存在しています。このリーダーはネットワーク全体の処理の順序を決定し Atomic Broadcast を行う責任を持っています。この点はブロックチェーンも同じですが、根本的な違いとして PoW に基づくリーダー選出が決定性アルゴリズムではないという点が挙げられます。

リーダー選出アルゴリズム: 一貫性の根源

ブロックチェーンも一般的な分散システムの整合性メカニズムと同様にリーダー選出アルゴリズムと合意アルゴリズムのスキームで分類するとわかりやすくなります。例えば Bitcoin, Ethererum, Tendermint と LBM では、リーダー選挙と合意のメカニズムは以下のコアブロックに分離することができます。

いくつかの特徴的なブロックチェーンでのファイナリティについて考えてみましょう。Bitcoin や Ethereum が採用している (重み付き) PoW は特定のハッシュ値を引き当てたノードがリーダーとなる権利を得ます。ただし PoW は本質的に非決定性アルゴリズムです。それによって選出されたリーダーの構築するブロックもまた非決定的な性質を持ち、結果として PoW を採用するブロックチェーンには結果のロールバックと再実行の可能性、つまりファイナリティをもたない確率的整合性が顕在化します。加えて、膨大な計算能力を浪費する PoW はパフォーマンスやコストの観点でも大きく不利と考えられています。

PoW に対して、すべてのレプリカが共有する何らかの「保有量(Stake)」に基づいて判断する方針を PoS (Proof of Stake)と呼びます。保有量は決定状態であるため、それに基づくリーダー選出にも決定性があります。結果として PoS に基づくブロックチェーンはファイナリティを持つことができます。PoS は通信を必要とせずゼロインタラクションでリーダーを決定できるためパフォーマンスも理想的ですが、決定が予想可能であるためにリーダーノードへの攻撃の可能性があります。

PoS の派生型である DPoS は決定性のある承認者からの決定性のあるリーダーが選ばれるためファイナリティを持つことができます。しかし PoS と同様に承認者の予測が可能な上、パフォーマンスの観点でも提案者の投票のために少なくとも O(n) の通信コストが発生します。

PBFT のようにコンセンサスを形成するノードを限定したり、Kafka のような固定的な直列化機能を設置することで有限状態を作り出すことは非決定性に対する最もシンプルな解決方法です。このようなプライベートチェーンやコンソーシアムチェーンがファイナリティを実装できることは明らかです。

DAG 型のブロックチェーンには Coordinator という役割が存在しますが、それはトランザクションを定期的にチャンク化することを目的としており、この記事で示しているリーダーとは異なる役割です。DAG 型を説明するときにあまり言及されませんが、DAG 型では処理グラフのどのノードに新しい処理を連結するかをクライアントが決める必要があります。つまり DAG 型ブロックチェーンのクライアントはトランザクションの線型性 (linearity) を保証する責務を持ち、そのために一意性を管理する機構が必要であることを意味します。

このように比較すると、どのブロックチェーンも Atomic Broadcast、つまり処理の順序性を定めることで整合性を持つアプローチを取っていますが、そのリーダー選挙アルゴリズムに決定性があるかどうかがファイナリティを持つかどうかの分岐点と考えることができます (ただし、中には決定性のあるリーダー選出を行うにもかかわらず合意メカニズムでファイナリティを失っているものもあります)。ここで我々は様々なブロックチェーンの特徴を捉えるために論文やホワイトペーパーから根本の一貫性メカニズムを読み解いてカオスマップを作成しました。

LINE Blockchain の方針

整合性を譲歩した分散データベースは、些細な不整合は問題にならないが高スループットが求められるようなシステムに適用されています。しかし、人の生命や財産に関わるデータストアをこのようなデータベースに置き換えることはできません。暗号資産のプラットフォームとなるブロックチェーンも同様に、ハッカーであろうが国家諜報部であろうが、敵対勢力の大小に関わらず取引の改ざんが事実上不可能な「暗号学的困難さ」を伴うべきと考えています。

我々は LINE Blockchain をサービス指向ブロックチェーンと位置づけ、商取引やゲームといった様々なサービスを繋げるプラットフォームを構築しています。前述のように、ファイナリティを選択することは P2P ネットワークに有限状態を導入することと等価です。有限状態のような潜在する定量性を「特権性」と解釈されることもありますが、サービス指向ブロックチェーンのユースケースを想定したとき、やはりデータの整合性と一貫性は必須の要件となります。

では我々に必要なファイナリティはどのように実装すべきでしょうか? 言い換えれば、リーダー選出のための最良の決定性アルゴリズムは何でしょうか?