論文翻訳: DiemBFT v4: State Machine Replication in the Diem Blockchain

Abstract

本報告では Diem のコアコンセンサスアルゴリズムである DiemBFT と名付けられた第 4 バージョンについて述べる。DiemBFT は設定可能な Validator 集合の間でトランザクションの順序と確定に関する合意を形成するという責任を持っている。本報告の主な目的は、旧バージョンのレイテンシーを改善するということである。我々は、以前のバージョンのビュー同期プロトコルでは故障したリーダーが存在する場合に 2 次関数的な数のメッセージを必要することを認識している。DiemBFT はこの設計上の選択を受け入れ、故障したリーダーの 2 次的なビュー変更を採用することで、通常は 3 ステップとなるブロックのコミットを 2 ステップで行えるようにした。さらに DiemBFT はリーダーレピュテーション機構 (leader reputation mechanism) を搭載し、Crash Fault 時のリーダー活用 (leader utilization) を実現するとともに、コミットされたブロックがすべてビザンチンリーダーによって提案されていないことを検証することができる。リーダー活用によってクラッシュしたリーダーが選出されないことが保証されるため不必要な遅延を防ぐことができる。最後に、DiemBFT は "安全分離" (safety isolation) 保証を定式化している。DiemBFT は、参加者の正しい動作を定数メモリフットプリントの "tcb"-able モジュールにカプセル化し、参加者への攻撃面を減らす安全なハードウェアエンクレーブ内で実行できるようにします。

Table of Contents

1. Abstract
2. 1 導入
3. 2 問題定義
   1. 2.1 システムモデル
   2. 2.2 技術的背景
4. 3 DiemBFT プロトコル
   1. 3.1 Main モジュール
   2. 3.2 Ledger モジュール
   3. 3.3 Block-tree モジュール
   4. 3.4 Safety モジュール
   5. 3.5 Pacemaker モジュール
   6. 3.6 MemPool 抽象モジュール
   7. 3.7 LeaderElection モジュール
5. 4 正しさの証明
   1. 4.1 合意
   2. 4.2 Liveness
   3. 4.3 Optimistic Time Bounds
   4. 4.4 Chain Quality
   5. 4.5 Leader Utilization
6. Acknowledgements
7. References
8. 翻訳抄

1 導入

インターネットとモバイルブロードバンドの出現により、世界中の何十億という人々がつながり、知識へのアクセス、自由なコミュニケーション、より安価で便利な幅広いサービスを利用できるようになった。またこの接続性により、より多くの人々が金融エコシステムにアクセスできるようになった。しかしこのような進歩にもかかわらず、金融サービスを最も必要とする人たちのアクセスはまだ限られている。

ブロックチェーンや暗号通貨は、コンピュータサイエンス、暗号技術、経済学の最新の進歩が金融インフラにイノベーションを起こす可能性を示しているが、既存のシステムはまだ主流にはなっていない。その次のステップとして、数十億人の人々に力を与えるシンプルなグローバル通貨と金融インフラを実現することを使命として我々は Diem Blockchain を設計した。

この新しいブロックチェーンの中核をなすのが本報告で取り上げる DiemBFT と呼ばれるコンセンサスプロトコルであり、これによりブロックチェーンの取引は順序付けられて確定する。トランザクション台帳の全 Validator ノード間の合意を促進するために Diem Blockchain は DiemBFT コンセンサスプロトコルを用いて BFT アプローチを採用している。

DiemBFT には設計上の重要な考慮事項がいくつか含まれている。

Permissioned & Open Network. DiemBFT のセキュリティは Validator ノード運営者の質に依存する。Proof-of-Work を用いて Validator committee を選出する先行研究 [14] と異なり、DiemBFT の Validator ノードは協会のメンバーまたは Diem Networks US が運営を代行することを認めた第三者機構によって運営されることになる。このモデルは permissioned と呼ばれ、参加する協会メンバーの質に基づいてネットワークのセキュリティを促進し、過剰な計算能力を浪費することなく持続可能にするアプローチである。

Classical BFT. DiemBFT は Lamport, Pease, Schostack が [15] で提唱した古典的な BFT アプローチをベースにしている。この分野での 40 年にわたる科学的進歩により、高いトランザクションスループットと低レイテンシー、そして他のブロックチェーンで使われている "proof of work" よりもエネルギー効率の高い合意形成アプローチが実現されている。

このアプローチで提供される主な保証は、ビザンチン故障に対する回復力、つまり個々の故障がシステム全体に波及することを防ぐことである。DiemBFT は、参加者の 3 分の 1 が正しい動作から逸脱しても故障が起きていないように見えるよう設計されている。これは、ノードのストレージでビットが反転するような無害なものから、秘密鍵を盗んでサーバを完全に危険にさらすものまで、あらゆる状況をカバーする。さらに、DiemBFT は無制限の通信遅延やネットワーク障害が発生した場合でも safety を維持する。これは、同期に依存した安全性の高いコンセンサスプロトコルは本質的に複雑でネットワークに対するサービス拒否攻撃 (DoS) に弱いという我々の信念を反映したものである。

このアプローチが DiemBFT に提供する第二の重要な保証は、明確に定義された Transaction Finality である。参加者は定足数の Validator からのトランザクション検証を以てトランザクションが完了したことを確信することができる。

Enhancements. DiemBFT は Nakamoto consensus [16] に基づくパブリックブロックチェーンと同様に、シンプルかつ堅牢な実装を可能にしている。注目すべきは、このプロトコルが単一の通信フェーズを中心に構成されており、簡素な安全性の議論と堅牢性を可能にしていることである。このように DiemBFT は Nakamoto コンセンサスに基づくパブリックブロックチェーンのシンプルさとモジュール性の間の橋渡しをしつつ、協会の集合的信頼性に基づいて信頼を構築している。

DiemBFT は 2 つのケースでリーダーを交代させる。まず通常の運用では DiemBFT は公平性と対称性を確保するために Validator 間でリーダーを交代させる。この場合、余計な通信は発生しない。しかし、素朴に (例えばラウンドロビンで) 実行した場合、故障したリーダーが選出され続けるため大きなレイテンシーのオーバーヘッドが発生する可能性がある。DiemBFT では、リーダー活性を実現する新しいリーダー選出機構を設計している。つまり、クラッシュしたリーダーがリーダーに選出される回数を制限する。リーダー選出機構は最後にコミットした状態を利用し、アクティブな検証者を追跡するレピュテーション機構を実装する。やっかいなのは最後にコミットした状態について合意することである。もし素朴に行えば、ビザンチン攻撃者は正直なパーティにリーダーに関する意見を対立させることができ、その結果 liveness または chain quality¹ 違反を引き起こす可能性がある。

2 つ目は、DiemBFT はリーダーが不良と判断されたときのリーダー変更である。旧バージョンでは HotStuff の線形ビュー機構を用いて故障したリーダーを交代していた。しかし旧バージョンではビュー同期にとにかく 2 次の通信が必要であるため、DiemBFT では 2 次ビュー変更機構を使うことで、一般的なケースで HotStuff のレイテンシーを短縮できるようにした。HotStuff の用語では、DiemBFT は 2-chain コミットルールを持っている。このため、DiemBFT はHotStuff (共通ケース実行) と PBFT [6] (故障リーダー実行) のハイブリッドとなっている。その結果、安定したネットワークでは HotStuff の線形コストとなり、不安定なネットワークではラウンドあたり 2 次コストから PBFT のような最悪ケースの 3 次コストとなる。ビュー同期に関して、DiemBFT は以前のバージョンで導入された time-out certificates に基づいて構築され、すべての正常な Validator がほぼ同じ速度でラウンドを進めることを保証するために、タイムアウトメッセージの Bracha broadcast [1] にインスパイアされたブースト機構を追加している²。

最後に、DiemBFT の Validator はローカルに少量 (定数) の情報を保存するだけで孤立した安全な safety モジュールの安全性を検証することができる。これにより、honest (誠実), compromised (危殆化(きたいか)), Byzantine の 3 種類の Validator をモデル化でき、敵対者が compromised Validator を制御してもその safety モジュールにアクセスできないようにすることが可能である。DiemBFT はビザンチンの割合が 1/3 以下であれば任意数の compromised Validator に対して安全性を保障する。

• ¹非ビザンチンのリーダーが提案したブロックの割合。
• ²2-chain の研究の一部は [11] に掲載されている。

2 問題定義

DiemBFT のゴールはプログラマブルなリソースのデータベースをフォールトトレランスで維持することである。このシステムは Validator が一連のトランザクションについて合意を形成し、複製されたデータベースに決定論的に順序づけられた適用を行う SMR エンジンを中核に設計されている。

DiemBFT は初期システムが \(n\) 個の Validator からなるネットワークシステムという古典的な設定で設計されている。初期システムの構成メンバーはシステム起動時に決定する。故障をモデル化するために、我々はネットワークの遅延と一部の Validator の挙動を制御しようとする攻撃者 (adversary) を定義する。そして安全な信頼できるホストを想定し、3 種類の Validator を定義する。

• Byzantine Validator - すべてのコードが攻撃者によって制御されている。
• Compromised Validator - 安全な信頼できるホスト以外のすべてのコードが敵対者によって制御されている。
• Honest Validator - 敵対者に制御されていない。

我々は Honest Validator と Compromised Validator をあわせて非ビザンチン (non-Byzantine) Validator と呼び、すべての Validator が危殆化するかもしれないが最大で \(f \lt n/3\) Byzantine Validator が存在すると仮定する。合意特性 (Agreement property) とは、Honest Validator が矛盾するチェーンプレフィクスを決してコミットしないことである。コミットされた情報は信頼されたハードウェアモジュールの外側に保存されるため、危殆化した Validator は局所的に何らかのコミットを行う可能性があることに注意。しかし Compromised Validator が Honest Validator に合意を破らせることはできない。

2.1 システムモデル

Network. DiemBFT で想定しているネットワークモデルは、部分同期と呼ばれる同期と非同期のハイブリッドモデルである。これは、ネットワークが一過性の非同期期間 (攻撃を受けている場合など) を経て、残りの時間は同期を維持するような実用的な設定をモデル化したものである。

Dwork ら [9] によって導入された部分同期設定に対する解決のアプローチは、safety (常時) と liveness (同期期間中) を分離するものである。DLS は、各ラウンドが特定のリーダーによって駆動される round-by-round パラダイムを導入した。同期期間中は Honest リーダーが現れるとすぐに進行が保証され、それまではタイムアウトによってラウンドが終了する。この DLS アプローチは、現在までのほとんどの実用的な BFT 研究と、Google Chubbie ロックサービス [3]、Yahoo の ZooKeeper [13]、etcd [19]、Google の Spanner [8]、Apache Cassandra [5] など、業界で最も成功した信頼性ソリューションの根底をなしている。

形式的には、部分同期モデルは同期ネットワークと同様に \(\Delta\) transmission bound と、GST (Global Stabilization Time) と呼ばれる特別なイベントを仮定している:

• GST は、ある未知の有限時間を経てやがて起きる。
• 時刻 \(t\) に送信されたすべてのメッセージは、時刻 \(\max\{t,GST\}+\Delta\) までに配信されなければならない。

我々は wire-protocol に関連するいくつかのタスクをカプセル化し、別の場所で説明される transport substrate にそれを委ねる。トランスポートは、メッセージをフォーマットし、ワイヤー上で送信するためにシリアライズし、メッセージを確実に配信し、配信されたメッセージによって参照されるデータ (特にブロックの祖先) を取得するために注意を払う。特に、疑似コードでメッセージが処理されるとき、そのフォーマットと署名が検証され、受信者がすべての祖先とメッセージのメタ情報によって参照されるほかのデータと同期していることを仮定する。

2.2 技術的背景

DiemBFT は Byzantine Fault Tolerance (BFT) を用いた部分同期モデルのレプリケーションプロトコル群 [9, 6, 12, 2, 4, 14, 17, 7] をベースにしている。これらの研究成果から得られた最先端の技術を取り入れ、プログラマブルなリソースの複製データベースを大規模にサポートする。

Round-by-round BFT solution. practical BFT レプリケーションの古典的なソリューションにはラウンド単位 (round by round) で動作するという共通の基本的なアプローチがある。各ラウンドでは、そのラウンドのリーダーを指定する固定マッピングが存在する (例えばラウンドを参加者数 \(n\) で余剰した値を取る)。リーダーの役割はそのラウンドに対する唯一の提案でネットワークに投入することである。

リーダーは Honest Validator がそのラウンドを諦めてタイムアウトする前にネットワークに自身の提案を投入すれば成功である。この場合、Honest Validator はそのラウンドのプロトコルフェーズに参加する。多くの古典的な practical BFT ソリューションはラウンドごとに 2 つのフェーズで動作し、決定ごとに 2 次の通信コストが発生する (例えば PBFT [6])。最初のフェーズでは Validator の定足数が一意の提案を承認 (certifies) し、定足数証明書 (quorum certificate) (QC) を形成する。第二フェーズでは承認された提案に対する定足数の投票がコミットを決定する。後のラウンドのリーダーは常に Validator の定足数が、自分たちが投票した中で最も高い QC を報告するのを待つ。もし Validator の定足数が、ラウンド \(r\) においてどの QC にも投票しなかったと報告した場合、これはラウンド \(r\) においてどの提案もコミットされなかったことを証明するものである。

一方で HotStuff は 3-フェーズの BFT レプリケーションプロトコルで、通常ケースでは線形の通信オーバーヘッドとなる。HotStuff ではラウンドの第一フェーズと第二フェーズは PBFT と同様だが、第二フェーズの結果はコミットの決定ではなく、証明の証明、つまり QC-of-QC となる。コミットの決定は QC-of-QC に対する定足数の票 (QC-of-QC-of-QC) を得た時点で到達する。

DiemBFT は線形 3-フェーズ HotStuff にインスパイアされているが、3 ステップの待ち時間コストを取り除いたものである。その代わり、リーダーが機能しているときは HotStuff の通信線形成を維持しつつ、2 ステップでコミットする能力を取り戻すために、ビューチェンジプロトコル中の 2 次コストを許容している。

Chaining. DiemBFT はブロックチェーンの BFT プロトコルで一般的になっているチェイニング (chaining) パラダイムを借用している。チェイニングアプローチではコミットのためのフェーズはラウンドに分散されている。より具体的には、すべてのフェーズはラウンドで進行し新しい提案を含んでいる。ラウンド \(k\) のリーダーはその提案の承認のためのフェーズを 1 つだけ駆動する。次のラウンドの \(k+1\) ではリーダーは再び承認のための単一のフェーズを駆動する。個のフェーズには複数の目的がある。\(k+1\) のリーダーは自身の \(k+1\) の提案を送信する。しかし \(k\) の提案の QC を背負う (piggyback) こともある。このように、ラウンド \(k+1\) での承認は \(k+1\) に対する QC と、\(k\) に対する QC-of-QC を生成する。その結果、2-フェーズプロトコルでは \((k+1)\) の提案が QC を獲得すると \(k\) の提案はコミットされることができる。

Round synchronization. 分散システムにおいて Validator はどの瞬間にも異なる状態にあり、異なるメッセージを受け取る可能性がある。PBFT ではラウンドの同期を取るために進捗が確認できるまでラウンドの期間を 2 倍にするという理論的な "結果性" (eventuality) の方法を示した。HotStuff ではラウンドを進める役割を PaceMaker という機能でカプセル化しているが、その実装は指定されていない。DiemBFT では、Validator があるラウンド (\(r\) とする) を放棄するとき、そのラウンドに入るための証明を載せたタイムアウトメッセージをブロードキャストする。これにより、すべての Honest Validator が送信遅延束縛 (transmission delay bound) \(\Delta\) 以内に \(r\) に到達する。タイムアウトメッセージが定足数から収集されるとタイムアウト証明 (timeout certificate) (TC) が形成される。また TC には \(2f+1\) 個のノードが認識している最も高いラウンドの QC に署名を含む。この署名は、新しく選ばれたリーダーよりも高いラウンドでリーダーがロックされているパーティがあったとしても、リーダーが安全にチェーンを延長できることの証明になる。GST の後、すべての Validator が互いに \(O(\Delta)\) 時間で TC を形成できるように Bracha [1] 式のメカニズムを使用してタイムアウトメッセージを転送する。

3 DiemBFT プロトコル

DiemBFT プロトコルのゴールはブロックを順番にコミットすることである。プロトコルはラウンドのパイプラインで動作する。各ラウンドではリーダーが新しいブロックを提案する。Validator は次のラウンドのリーダーに自分の票を送る。定足数の票が集まると、次のラウンドのリーダーは定足数証明書 (QC) を作成し次の提案にそれを埋め込む。Validator はタイムアウトによってラウンドを放棄することもできる。この場合、Validator は現在のラウンドのタイムアウト証明書 (TC) を形成または観測することにより、ビューチェンジのメカニズムを通じて次のラウンドに入る。実際、\(r+1\) ラウンドに入るには \(r\) ラウンドの QC または TC のいずれかを観測する必要がある。次のラウンドのリーダーは、現在知っているブロックツリーをどのように拡張するかという選択に直面する。DiemBFT では、リーダーは常に、直接の子を持つ最も承認された葉を拡張する。この利点は、ブロックツリーが均一な構造を持ち、すべてのノードがその直接の親に対して QC を持つことである。DiemBFT のチェイニングアプローチの結果として、DiemBFT のブロックツリーはラウンド番号にギャップのあるチェーンを含むことがある。

ラウンド数は明示的にブロックに含まれ、その結果コミットロジックはシンプルになる: 最後の子孫が認証されたラウンド番号を持つ連続した 2-chain が必要である。2 つのラウンドが途切れることなく終了すると、QC を形成した連続する 2 つのラウンドからなる "2-chain" の先頭がコミットされる。Figure 1 の図を参照。

新しくコミットされたブロックで終わる枝全体がコミットされるようになる。Figure 2 はコミットされていないフォークを含むブロックのツリーを示したものである。フォークは悪意のあるリーダーやメッセージの損失など様々な理由で発生する可能性がある。例えば図ではビザンチンリーダーが \(k\) のブロックでチェーンをフォークし、コミットされていないチェーンが放棄されたことを示している。\(k\) のブロックは左のフォークと同じ QC を親に使用する。描かれたシナリオでは \(k\) のブロックはコミットされ左のフォークが破棄される。後で説明するように、我々の safety ルールはコミットされた枝が決して破棄されないことを保証していることに注意。

DiemBFT は 2 つの要素からなる単純な投票ルールによって 1 つのフォークのみがコミットされることを保証している。第一に Validator は厳密に増加するラウンド数で投票を行う。第二に各ブロックは前ラウンドの QC または QT が含まれていなければならない。前ラウンドが TC だった場合、Validator は新リーダーの提案が拡張しても問題ないかどうかを確認する。このチェックは異なるノードのうち \(2f+1\) 個の highest_qc_round (Validator が投票したブロックに含まれている最も高い QC) を持つ TC を確認することで行われる。もし新提案がこれらの highest_qc_round のうち最も高いものを拡張した場合、これはより高いラウンドのものはコミットすらできないことの証明となる (さもなくば少なくとも一つはより高い highest_qc_round を報告したことになる)。Figure 3 のシナリオを考えてみよう。\(k+4\) の QC は \(k+3\) ラウンドからのブロックをコミットして形成されている。今後のラウンドでは \(k+3\) より低い QC を拡張できるような TC を形成することは不可能である。

我々は DiemBFT プロトコルの詳細な説明を行いデータ構造と実装モジュールを詳しく説明する。実装は以下のモジュールに分かれている。

• まず、メッセージやタイマーのイベントハンドラをディスパッチする接着剤となる Main モジュール (セクション 3.1)。
• フォーク可能な投機的台帳をローカルに保存する Ledger モジュール (セクション 3.2)。SMR サービスのための、より上位のロジック (実行系) に接続するためのインターフェースを提供する。
• 提案ブロックを生成する Block-tree モジュール (セクション 3.3)。これはコミットを保留しているブロックのツリーを、それに対する投票と QC で追跡する。
• コンセンサスの中核となる safety ルールを実装した Safety モジュール (セクション 3.4)。Safety: Private パートは秘密鍵を制御し、署名の生成と検証を処理する。最小限の状態を維持し、安全なハードウェアコンポーネントで保護することができる。
• Pacemaker モジュール (セクション 3.5) は liveness を維持しラウンドを進行する。Safety に "heartbeat" を提供する。
• 提案生成時にリーダーにトランザクションを提供する MemPool モジュール (セクション 3.6)。
• 最後に、ラウンドをリーダーに対応付けてビザンチン故障の下でチェーンの品質を維持しながら静的 Crush Fault の下で最適なリーダー活用を達成する LeaderElection モジュール (セクション 3.7)。

形式的な正しさの証明はセクション 4 に示す。

3.1 Main モジュール

DiemBFT の Main モジュールはイベント処理ループであり、適切なハンドラを呼び出してメッセージやイベントを処理する。取り扱うイベントは、提案メッセージ、投票メッセージ、リモートタイムアウト、ローカルタイムアウトである。

3.2 Ledger モジュール

最終的に、Diem Blockchain はプログラマブルなリソースのデータベースを保持し、それをコンセンサス DiemBFT コアが複製する。このデータベースは抽象的な台帳状態 (ledger state) を表現している。台帳状態を変化させるようなトランザクションを適用する永続的な台帳ストアと実行 VM 実装の詳細のほとんどは、DiemBFT の視点からは意図的に不透明で一般的なものにとどめている。特に Move トランザクション実行の詳細についてはこの原稿の範囲外である。

各 DiemBFT Validator のローカルにある Ledger モジュールは台帳ストアへの補助的なゲートウェイとして機能する。これは、最後にコミットされた状態を拡張した、ローカルで保留中の (分岐する可能性のある) 投機的な台帳状態を維持する。投機ツリーは 1 つの枝がコミットされるまで Validator のローカルメインメモリに保持される。これはコミット待ちのブロックから投機的な台帳状態へのマッピングを提供する。

Ledger.speculate(prev_block_id, block_id, txns) API は前のブロック状態に対してトランザクションのブロックを投機的に実行し、新しい台帳状態 ID を返す。投機的実行は台帳状態を複数の (競合する) フォークに分岐させ、投機的状態のツリーを形成することがある。最終的にはコンセンサスエンジンによって 1 つのブランチがコミットされる。Ledger.commit() API はコミットされた枝を永続的な台帳ストアにエクスポートする。ローカルでは、コミットされた状態の祖先からフォークした投機的な枝は破棄される。

Ledger が投機的実行をサポートするのは実行中の潜在的な非決定性を適切に処理するためであることを強調することは重要である。もし我々が実行レイヤーに渡すためだけに単純にトランザクションを順序付けるだけのシステムを構築しているのであれば、VM はコミットされたトランザクションのみを実行するため投機的状態のツリーを維持する必要はないだろう。しかしこのようなシステムでは (ハードウェアのバグなどによる) 非決定性を許容することができず、DiemBFT が気づくことなく Validator が発散してしまう。したがって DiemBFT はトランザクションの順序づけにとどまらず、トランザクションとその実行結果の両方を投票によって証明することを確認する。トランザクションのブロックに対して QC を形成するためには、少なくとも \(2f+1\) の Honest Validator が同じ状態に到達する必要がある。

DiemBFT は Ledger モジュールから上記の基本 API のみを必要とする。

3.3 Block-tree モジュール

Block-tree モジュールは Validator プロトコルの中核となる 2 つのコアデータ型、ブロックと票 (vote) で構成される。票から派生したもう一つのデータ型はブロックに対する票の集合で構成される定足数証明書 (QC; Quorum Certificate) で、これはブロックに対する票の集合からなる。タイムアウトとラウンドの進行にのみ関係する追加のデータ型は後述の Pacemaker モジュールで説明する。Block-tree モジュールはコミットメントを保留しているすべてのブロックと、それらが受け取った票のツリーを追跡するものである。

ブロック. コンセンサスプロトコルが台帳トランザクションの合意を形成するために使うコアデータ構造は Block である。各ブロックは提案された Ledger トランザクションと、コンセンサス決議を形成するために使用される追加情報が payload として含まれている。各ブロック b (既知のジェネシスブロック P₀ を除く) は b.qc を介して親に連結される。ここで b.qc は親ブロックに対する定足数の投票で構成される定足数証明書 (QC) である。このようにしてコミットメント待ちのブロックは P₀ をルートとする提案ブロックのツリーを形成する。

ブロック b に対する票情報 VoteInfo は決定論的な実行結果を保証するためにブロック id と推測される実行状態 exec_state_id の両方を含み必要がある。さらに、VoteInfo は b の親の ID とラウンドを保持する。この情報は便宜上保持されており、先祖を取得することなく単一のブロックからコミットメントを推測することができる。さらに、投票メッセージにはコミットされたと推測される元帳の状態である LedgerCommitInfo が含まれ、commit_state_id で識別される。あるブロックに対する QC の結果、その親ブロックがコミットされるとブロックに対する定足数の投票もまた、新たにコミットされた元帳の状態を証明する役割を果たす。

LedgerCommitInfo には 2 つの目的がある。一つ目は履歴の証明としてクライアントに提出できる commit_state_id が含まれている (実際の commit_state_id は台帳の履歴をカバーする Merkle ツリーのルートハッシュと考えてよい)。クライアントは、与えられた台帳状態が \(2f+1\) の参加者によって署名されていることを検証できる限りコンセンサスプロトコルの使用を意識する必要はない。二つ目は、LeaderCommitInfo が VoteInfo のハッシュを含んでいること。このハッシュはクライアントにとっては不透明でありコンセンサスの参加者によって使用される。したがって vote メッセージに署名する Validator は、潜在的な LedgerCommitInfo (コミットの証明として台帳に保存) と、投票したブロックに埋め込まれる QC (コンセンサスプロトコルの実行に使用) の両方を承認していることになる。ブロックの id には署名のダイジェストが含まれているため、コミットされた各ラウンドの Validator 集合は一意に決定されることに注意。

例としてラウンド \(k-1\) の親 b' を持つラウンド k の提案 b について考える。Validator が b に投票することを決定した場合、b の VoteInfo のハッシュと同様に b' の潜在的なコミットを含む LedgerCommitInfo に署名する。

Block-Tree モジュールはQC を作成していない票を pending_votes として追跡する。pending_block_tree は

Block-tree
  VoteInfo
    id, round;                // ブロックの ID とラウンド
    parent_id, parent_round;  // 親の ID とラウンド
    exec_state_id;            // 推定の実行状態

  // 直接投票する新たなコミット状態を推測
  LedgerCommitInfo
    commit_state_id;  // この投票が QC に集約されたときにコミットが発生しない場合は ⊥
    vote_info_hash;   // VoteMsg:vote のハッシュ

  VoteMsg
    vote_info;          // VoteInfo レコード
    ledger_commit_info; // 推定の台帳情報
    high_commit_qc;     // コミットされたブロックに同期する QC
    sender ← u;         // 構築されたときに自動で追加される
    signature ← signu(ledger_commit_info); // 構築されたときに自動で署名される

  // QC は複数の署名を持つ VoteMsg
  QC
    vote_info;
    ledger_commit_info;
    signatures;   // 署名の定足数
    author ← u;   // qc を生成した Validator
    author_signature ← signu(signatures);

  Block
    author;   // ブロックの作成者はビュー変更後の qc.author と同じではないかも知れない
    round;    // この提案が発生したラウンド
    payload ; // 提案されたトランザクション
    qc;       // 親ブロックの QC
    id;       // author, round, payload, qc.vote_info.id, qc.signatures の一意なダイジェスト

  parent_block_tree;  // コミットメントを保留しているブロックのツリー
  pending_votes;      // LedgerInfo ハッシュによってインデックスされたブロックごとに収集された投票数
  high_qc;            // 既知の最も高い QC
  high_commit_qc;     // コミット証明書となる最も高い QC

  Procedure process_qc(qc)
    if qc.ledger_commit_info.commit_state_id ≠ ⊥ then
      Ledger.commit(qc.vote_info.parent_id)
      pending_block_tree.prune(qc.vote_info.parent_id)  // parent_id は保留中の新しいルートとなる
      high_commit_qc ← maxround{qc,high_commit_qc}
    high_qc ← maxround{qc,high_qc}

  Procedure execute_and_insert(b)
    Ledger.speculate(b.qc.block_id, b.id, b.payload)
    pending_block_tree.add(b)

  Function process_vote(v)
    process_qc(v.high_commit_qc)
    vote_idx ← hash(v.leader_commit_info)
    pending_votes[vote_idx] ← pending_votes[vote_idx] ⋃ v.signature
    if |pendig_votes[vote_idx]| = 2f+1 then
      qc ← QC〈
        vote_info ← v.vote_info,
        state_id ← v.state_id,
        votes ← pending_votes[vote_idx]〉
      return qc
    return ⊥

  Function generate_block(txns, current_round)
    return Block〈
      author ← u,
      round ← current_round,
      payload ← txns,
      qc ← high_qc,
      id ← hash(author || round || payload || qc.vote_info.id || qc.signature)〉

3.4 Safety モジュール

DiemBFT では、連続する 2-チェーン、つまりブロックのラウンドが親ブロックのラウンドの直後であるようなときにコミットされた状態となる。これは commit_state_id_candidate 関数でチェックされる。

DiemBFT は Safety モジュールを信頼できるハードウェア上に配置できるように次の 2 つのカウンターのみを保持する: (i) highest_vote_round は最後に投票されたラウンドを保持し、(ii) highest_qc_round は Validator が投票したブロックに含まれる最高 QC のラウンドを保持する。

提案 (ブロック) b を受け取った Validator は、b.round が最後に投票したラウンドより大きい場合に限り投票する。さらに、Validator は投票安全性ロジックをカプセル化した safe_to_vote 術後を評価する。

Safety モジュールの完全なロジックは次の通り。最初に、安全モジュール内からのみアクセスできるプライベートメンバとインターフェースを説明する。

次に説明する安全モジュールの公開インターフェースは、他のモジュールによって 2 種類の投票 (VoteMsg と TimeoutMsg) を構築するために使用される。このように有効な投票は秘密鍵を持つ Safety モジュールによって準備され署名される。またこれらの関数の最初に有効な署名が呼び出され、投票を構成するために提供されたすべてのパラメータの整形性 (well-formedness) と署名をチェックすると仮定している (他の Validator の公開鍵を使用する)。システムの他の部分も整形式と署名をチェックするが (例えば何らかのメッセージを初めて受信したときなど)、侵害された Validator から保護するために Safety は独自の署名チェックのレイヤーを形成する必要がある。

安全性モジュールは外部依存を必要せず、純粋に提案とその QC によって運ばれたラウンドに基づいた潜在的なコミット情報と結合した票を生成するに注意。これは安全性を検証するのに役立つだけではなく、Safety モジュールを分離して TCB 内で実行できるようにもする。

3.5 Pacemaker モジュール

ラウンドの進行は Pacemaker とおバレルモジュールによって管理される。Pacemaker は投票数と時間を追跡する。"happy path" では各 Validator の Pacemaker モジュールがリーダー提案の QC を使用してラウンドを進める。"recovery path" では、Pacemaker はラウンドの進行欠如を観測し、タイムアウト証明書に基づいてラウンドを進める。

Pacemaker はローカルラウンドのタイムアウトが発生すると TimeoutMsg 通知をブロードキャストする。このメッセージは high_qc を含み、Safety モジュールによって署名されている。これは最高 QC のラウンドが high_qc のラウンドより高くないことを検証する。これはのちのリーダーが最後にコミットされたブロックより下でフォークできないことを保証するために重要である。さらに high_qc の情報はリーダーと遅いノードが最新情報を得るのに役に立つ。TimeoutMsg を送信したあと、Validator は自分の highest_vote_round を増やし、このラウンドでは絶対に投票しないようにする。

Validator がラウンド \(r\) に対する \(f+1\) 個のタイムアウトメッセージを受信した場合、まだタイムアウトしていなければラウンド \(r\) をタイムアウトさせる。\(2f+1\) 個のタイムアウトメッセージを受け取ったとき、Validator は TC を形成してラウンドを進めることができる。したがってある Validator が TC を形成したすると他のすべての誠実な Validator は 2 回のネットワーク遷移遅延の間に TC を作成するだろう。

• ^a保留中のタイムアウトを 1 ラウンド (現在のラウンド) のみ保存する必要がある - タイムアウトメッセージにはプロトコルに関連するラウンドに移行させる証明書が含まれているため、現在のラウンドも最高値となるだろう。

3.6 MemPool 抽象モジュール

ブロックにペイロードを投入するためのトランザクションを提供する MemPool モジュールを想定する。

3.7 LeaderElection モジュール

PBFT のような古典的なコンセンサスアルゴリズムでは、リーダーは (クラッシュまたはビザンチン) 故障があると疑われるまで安定的に維持される。しかしこれは誠実な Validator によって提案がコミットされること、つまりチェーン品質を保証する必要があるブロックチェーンプロトコルには適さない戦略である。一つの解決策はラウンドごとにリーダーを交代させてすべての誠実な Validator に等しく値を提案する機会を与えることである。しかしこの方法ではクラッシュした Validator が回復した証拠もなくリーダーに選ばれ続けることになる。

この問題を解決するために、我々はリーダーとして選出される資格を決定するときに評価に基づくリーダー選出機構 (reputation-based leader election mechanism) を提案する。これは以前のアクティブな参加を考慮する。しかしこのような機構を素朴に実行すると、敵対者は、リーダー選出を制御したり誠実な Validator がリーダーの身元について合意しないようにさせることができる。

DiemBFT では Validator がリーダーを決定するために 2 つの経路がある。もしあるせい実は Validator がラウンド \(r-2\) でコミットした QC の埋め込まれたラウンド \(r\) のブロックを取得した場合、そのそのコミット情報はラウンド \(r+1\) のリーダーを決定するリーダー評価スキームによって使用される。具体的には、リーダー評価スキームは QC 署名情報を使用してアクティブな Validator 集合を決定し、(チェーン品質のために) コミットしたブロックの exclude_size 最新リーダーを除外し、残った集合から決定論的にリーダーを選択する。そうでないケースでは、Validator が (ビザンチン挙動、クラッシュまたはメッセージ遅延などにより) ラウンド \(r\) でラウンド \(r-2\) をコミットしなかった場合、ラウンド \(r+1\) のリーダーを決定するためにラウンドロビン³を使うようにフォールバックする。これは異なるレプリカが同じ経路を辿らないかもしれず、次のリーダーで合意しないかもしれなことを意味している。しかし、後で示すようにこのような現象は GST よりあとに少数回発生するのみである。

リーダー選出の目的はクラッシュした Validator を検出してリーダー交代から除外することでコンセンサスの待ち時間に与える影響を軽減することである。形式的には、ビザンチン障害の存在しな実行に対して我々は次のことを要求する:

• \(t\)-リーダー活用: ビザンチン Validator が存在しないケースの実行を考える。このとき、GST のあとに誠実な Validator たちはリーダーに合意しないか、彼らのリーダーがクラッシュしているラウンドが最大 \(t\) 回存在する。

上記の特性はリーダーがクラッシュして失敗する可能性がより高いシナリオを最適化する。しかしプロトコルはビザンチン Validator を含む最悪ケースの敵対者に耐性を持たなければならない。このため、最悪の場合にビザンチン条件下で以下の性質が成立することを要求する。

• Liveness: GST よりあと、無限にブロックがコミットされる。
• \(t\)-チェーン品質: \(t\) 個のコミットされたブロックの任意のウィンドウにおいて、少なくとも 1 個は誠実なリーダーによって提案される。

上記の保証と応答性の協会をセクション 4.2 で証明する。

実際、我々は遅い Validator にもリーダーになる機会を与えたいような場合がある。これは、active_validators \(\cup\) last_authors に含まれていない Validator を、アクティブな Validator よりも相対的に低い重みでリーダーに選出することを考慮することで実現できる。これはリーダー活用とのトレードオフをもたらす。

• ³チェーン品質の観点から、すべての Validator はラウンドロビンで 2 回考慮されることに注意。

4 正しさの証明

4.1 合意

まずいくつかの放棄法を説明する。

• 我々はビザンチン (誠実な) Validator によって低がんされたブロックをビザンチン (誠実な) ブロックと呼ぶ。
• \(B.{\tt id} = {\tt QC}_B.{\tt ValidatorInfo}.{\tt id}\) であるようなクォーラム証明書 \({\tt QC}_B\) が存在する場合、ブロック \(B\) は認証された (certified) と言う。
• \(B_i \leftarrow {\tt QC}_i \leftarrow B_{i+1}\) とは、ブロック \(B_i\) がブロック \(B_{i+1}\) に含まれるクォーラム証明書 \({\tt QC}_i\) によって認証されることを意味する。また \(B \leftarrow {\tt QC}_B \leftarrow B'\) を用いて \({\tt QC}_B\) がブロック \(B\) を認証し、ブロック \(B'\) で拡張されることを表現する。
• \(B_i \leftarrow^* B_j\) はブロック \(B_j\) がブロック \(B_i\) を拡張することを意味する。つまり、\(B_i \leftarrow\) \({\tt QC}_i \leftarrow\) \(B_{i+1} \leftarrow\) \({\tt QC}_{i+1} \leftarrow\) \(\cdots\) \({\tt QC}_{j-1} \leftarrow B_j\) というシーケンスが存在する。

定義 1 (グローバルダイレクトコミット). \(B'.{\tt QC}\) が \(B\) を認証し (つまり \(B'.{\tt QC}={\tt QC}_B\))、Safety.\({\tt highest\_qc\_round} \leftarrow B.{\tt round}\) を設定するように、\(f+1\) 個の非ビザンチン Validator がそれぞれラウンド \(B.{\tt round}+1\) でブロック \(B'\) に対して Safety.\({\tt make\_vote}\) を呼び出している場合、ブロック \(B\) はグローバルにダイレクトコミットされている (globally direct-committed) と言う。

定義 2 (ローカルダイレクトコミット). 誠実な Validator は、\(B \leftarrow {\tt QC}_B \leftarrow B' \leftarrow {\tt QC}_{B'}\) と \(B'.{\tt round} = B.{\tt round} + 1\) を満たす \({\tt QC}_{B'}\) を観測したときにのみ、Ledger.commit(B.id) を呼ぶことによって台帳にブロック \(B\) をローカルダイレクトコミット (locally direct-commits) する。

4.2 Liveness

4.3 Optimistic Time Bounds

4.4 Chain Quality

4.5 Leader Utilization

Acknowledgements

We wish to thank Manuel Bravo, Gregory Chockler, Alexey Gotsman, Rachid Guerraoui, Kartik Nayak, Ling Ren and Maofan Yin for valuable feedback and discussions.

References

1. Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130–143, 1987.
2. Ethan Buchman, Jae Kwon, and Zarko Milosevic. The latest gossip on BFT consensus. https://arxiv.org/abs/1807.04938v2, 2018.
3. Michael Burrows. The chubby lock service for loosely-coupled distributed systems. In 7th Symposium on Operating Systems Design and Implementation (OSDI ’06), November 6-8, Seattle, WA, USA, pages 335–350, 2006.
4. Vitalik Buterin and Virgil Griffith. Casper, the friendly finality gadget. https://arxiv.org/abs/1710.09437, 2017.
5. Apache Cassandra. Apache cassandra. Website, https://planetcassandra.org/what-is-apache-cassandra.
6. Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In 3rd symposium on Operating Systems Design and Implementation (OSDI’99), volume 99, pages 173–186, 1999.
7. TH Hubert Chan, Rafael Pass, and Elaine Shi. Pala: A simple partially synchronous blockchain. https://eprint.iacr.org/2018/981, 2018.
8. James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, J. J. Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson C. Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. Spanner: Google’s globally distributed database. ACM Trans. Comput. Syst., 31(3):8:1–8:22, 2013.
9. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288–323, 1988.
10. etcd community. etcd. Website, https://etcd.io/.
11. Rati Gelashvili, Lefteris Kokoris-Kogias, Alberto Sonnino, Alexander Spiegelman, and Zhuolun Xiang. Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback. arXiv preprint arXiv:2106.10362, 2021.
12. Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K Re- iter, Dragos-Adrian Seredinschi, Orr Tamir, and Alin Tomescu. SBFT: a scalable decentralized trust infrastructure for blockchains. In DSN, 2019.
13. Patrick Hunt, Mahadev Konar, Flavio Paiva Junqueira, and Benjamin Reed. Zookeeper: Wait-free coordination for internet-scale systems. In 2010 USENIX Annual Technical Conference, Boston, MA, USA, June 23-25, 2010, 2010.
14. Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. Enhancing bitcoin security and performance with strong consistency via collective signing. In 25th {usenix} security symposium ({usenix} security 16), pages 279–296, 2016.
15. Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382–401, 1982.
16. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. http://bitcoin.org/bitcoin.pdf, 2008.
17. Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. Hotstuff: BFT consensus with linearity and responsiveness. In 38th ACM symposium on Principles of Distributed Computing (PODC’19), 2019.

翻訳抄

Diem Blockchain のコンセンサスアルゴリズム DiemBFT (旧名 LibraBFT) に関する 2021 年の論文。この v4 で 2 ラウンドで確定するように修正された。

1. The Diem Team. DiemBFT v4: State Machine Replication in the Diem Blockchain, 2021
2. David Wong. Real-Worl Cryptography. Chapter 12. A round in the DiemBFT protocol, 2021 Manning