分散システムは一般に、状態レプリケーターの原理 [1] を通じて一貫性を実現することがわかりました。基本的な考え方は、システム内のすべてのレプリカが同じステート マシンを実行するということです。すべてのレプリカが同じ初期状態で開始され、同じ初期状態に基づいて同じシーケンスで一連の操作を実行する限り、最終的にはすべての状態が収束します。つまり、システム全体が外部的には一貫性を示します。このグループの操作を同じ順序で決定するには、システムがコンセンサスに達する必要があります。さらに、すべての正直なノードが実行順序についてコンセンサスに達する必要があります。これは、有名な Byzantine Generals [2] 問題です。

分散システムは一般に、状態レプリケーターの原理 [1] を通じて一貫性を実現することがわかりました。基本的な考え方は、システム内のすべてのレプリカが同じステート マシンを実行するということです。すべてのレプリカが同じ初期状態で開始され、同じ初期状態に基づいて同じシーケンスで一連の操作を実行する限り、最終的にはすべての状態が収束します。つまり、システム全体が外部的には一貫性を示します。このグループの操作を同じ順序で決定するには、システムがコンセンサスに達する必要があります。さらに、すべての正直なノードが実行順序についてコンセンサスに達する必要があります。これは、有名な Byzantine Generals [2] 問題です。

ビザンチン コンセンサス アルゴリズムの理論上のセキュリティ保証。つまり、n>3f、n はノードの総数、f は悪意のあるノードの数です。ビザンチン コンセンサス アルゴリズムでは、次の 2 つの特性を保証する必要があります。

• セキュリティ: すべての正直なノードは、特定の時点でシステム状態が s であると信じています。

• アクティビティ: すべての正直なノードは最終的に をシステム状態として決定できます。

このうち、s は抽象的な概念であり、システム内には変数 S が存在し、この変数 S の値がシステムの状態であり、システム内のノードは S に関する一連の操作命令を受け取ることができます。特定の瞬間 (各ノードのクロックに誤差がないと仮定) S の値に関する合意、すべての正直なノードがセキュリティを満たすために変数 S=s を決定、すべての正直なノードは変数 S の値について決定を下す必要があり、活性を満たすために終了します。

これまで分散システムの研究において、ビザンチンコンセンサスは通信の複雑性を伴うことが多く、ネットワークの消費量が大きく、システム規模の拡大が容易ではありませんでした。たとえば、古典的な PBFT アルゴリズムでは、コンセンサスに達するまでに 3 つの段階を経る必要があります。PRE-PREPARE 段階では、マスター ノードが他のノードにリクエスト メッセージを送信します。他のノードがメッセージを検証した後、prepare メッセージを送信します。他のノードへのメッセージ。このステージでは n ^2 個のメッセージが生成されます。ビュー間の一貫性を確保するために、ノードは少なくともクォーラム準備メッセージを受信した後、他のノードにコミット メッセージを送信します。ノードが最終的にクォーラム以上のコミット メッセージを受信すると、最終的にリクエストを送信します。ただし、ネットワーク異常ノードがタイムアウトしてビュー切り替えが発生すると、o(n^3) の通信量が必要になります。

PBFT の各ステージの作業を理解することが HotStuff の基礎であり、PBFT の各ステージの目標は安全性と稼働性を確保することです。

ある時点でシステムがコマンド S'=S+1 を受信すると仮定すると、マスター ノードはこのコマンド S'=S+1 を非マスター ノードに送信します (これは事前準備メッセージです)。ビザンチン問題、正直なノードは、受信したメッセージが他の正直なノードと一致しているかどうかがわかりません (マスター ノードは一貫性のないメッセージを送信します)。ノードは、メッセージが自分自身で受信されたことを確認するために一度相互に通信する必要があります。他の正直なノードが一貫している (マスター ノードが一貫性​​のないメッセージを送信していないと判断する)、各ノードが準備メッセージを他のすべてのノードに送信し、クォーラム準備メッセージを受信して​​検証に合格する場合 (準備で指定された指示が正しいことを確認する)自分自身と一致している場合)、最初のラウンドの合意に達します (これは PREPARE 段階です)。この時点で、正直なノードが受信したメッセージは一貫しているように見えます。ただし、ここでの暗黙の条件は、コンセンサスに達したノードはそれを独自の観点からのみ見ているということです。つまり、クォーラムの一貫性のあるメッセージを受信して​​検証しました。ただし、他のノードがコンセンサスに達するために必ずしもクォーラム準備メッセージを受信するとは限りません。この時点で送信が行われ、ネットワーク障害が発生した場合、送信されたノードはコンセンサスに達したことを認識します。ネットワークが回復する限り、この命令は実行されます。システム全体で間違いなく受け入れられます。ただし、他のノードはネットワーク障害により合意に達していない可能性があり、待っても送信できるかどうかわかりません。システムを存続させるためにビューの切り替えが行われますが、このとき新しいマスターノードは S' または S に基づいて新しい命令を実行するかどうかを決定する必要があります。いくつかのノードが命令を提出し、別の命令 S''=S+2 が合意されて提出されたことが確認されない場合、システムは変数 S の値に不一致を生じます。したがって、現時点で提出する必要があるセキュリティ上の問題があります。

コンセンサスの別の段階が実行される場合、PREPARE コンセンサスに達した後、それぞれが別のコミット メッセージを送信し、各ノードは送信する前にクォーラム コミット メッセージの受け入れと検証を待機します。 COMMIT コンセンサスに達したノードはサブミット済みです。ネットワークが正常であればシステムは遅かれ早かれサブミットすることを知っていますが、COMMIT コンセンサスに達していない他のノードはサブミットを行っているかどうかわかりません。最終的には提出できる。ネットワーク障害が発生した後、新しいビューのマスター ノードが送信されたノードを見つけられない場合、依然として不整合が発生します。ここでの矛盾は、アクティビティのコンセンサスを継続するにはビューを切り替える必要があることです。セキュリティの観点から、新しいビューでコンセンサスを開始する前に S の値が一貫していることも確認する必要があり、送信された指示は新しいビューでも送信される必要があります。ビュー。 PBFTでは、ビュー切り替え時に自ノードのSの状態を証明するメッセージを他のノードに送信する、つまり、最新のSのPre-Prepareメッセージと、それに対応するQuorum prepareメッセージを送信する方法が用いられる。ビューが切り替わると、新しいマスターノードはコンセンサスの前に S'=S+1 を提出する必要があるかどうかを判断できます。

• S'=S+1 の PREPARE に関して合意に達したノードがない場合、S'=S+1 の送信は続行されません。

• S'=S+1 の PREPARE フェーズで合意に達したノードペアが存在する場合、競合する命令 S''=S+2 について合意に達してサブミットすることは不可能です。

このルールによれば、セキュリティとアクティビティは保証されますが、この方法によってもたらされる複雑さは o(n^3) です。したがって、このアルゴリズムは依然として大規模ネットワークでは使用できません。 ying Maofan らによって提案された HotStuff コンセンサス アルゴリズム [4] は、線形ビュー変更の特性を備えており、古典的な PBFT や BFT コンセンサスのボトルネックを解決し、マスター ノードの切り替えによって他のプロトコルやコストを増加させる必要がなく、システムは引き続き一貫した外部作業を実行できるため、コンセンサスプロセスの通信の複雑さが o(n) に軽減されます。

——HotStuff基本コンセプト——

hotstuff アルゴリズムを理解するには、コンセンサス プロセスに関連するいくつかの概念を導入する必要があります。

1) しきい値署名 [5] (しきい値署名): (k, n) しきい値署名スキームは、n メンバーで構成される署名グループを指し、すべてのメンバーが共通鍵を共有し、各メンバーが独自の秘密鍵を持ちます。 k 人のメンバーの署名が収集され、完全な署名が生成される限り、その署名は公開鍵によって検証できます。

2) 証明書 (クォーラム証明書、QC): マスター ノードが提案に対する少なくともクォーラム ノード ペアの投票メッセージ (署名付き) を受信した後、しきい値署名を使用して QC を合成します。この QC は完全なしきい値署名として理解できます。生成された署名は、提案に関して合意に達したことを意味します。

3) ビュー: ビューは合意の基本単位です. ビューは最大 1 回で合意に達することができ、単調増加します. 各ビューは徐々に回転して合意を進めます。

4) コンセンサス状態ツリー: 各コンセンサス ブロックはツリー ノードとみなすことができ、各ツリー ノードには対応する提案内容 (以前の操作指示) と対応する QC が含まれ、各ツリー ノードにはツリーを形成するための親ツリー ノード ハッシュが含まれます。構造を構築し、マスター ノードは最長のローカル ブランチに基づいて新しいツリー ノードを生成します。遅れているノードは、中間の欠落しているツリー ノードを、他のノードの最長のブランチにある最新のツリー ノードと同期させます。

—— HotStuff コンセンサスプロセス ——

文章

▲ Basic Hotstuff

基本的な HotStuff は、コンセンサスの基本的なプロセスです。このうちビューは単調増加的に連続的に切り替わる。各ビューには、提案、メッセージの収集と転送、および QC の生成を担当する固有のマスター ノードがあります。プロセス全体には、準備段階 (PREPARE)、提出前段階 (PRE-COMMIT)、提出段階 (COMMIT) の 4 つの段階が含まれます。意思決定ステージ (DECIDE) では、マスター ノードが特定のブランチをサブミット (コンセンサスに到達) し、PREPARE、PRE-COMMIT、COMMIT の 3 つのステージでクォーラム コンセンサス ノードから署名付きの投票メッセージを収集し、しきい値署名を使用して QC を合成します。 、それを他のノードにブロードキャストします。

しきい値署名と組み合わせることで、HotStuff はコンセンサス メッセージをマスター ノードにブロードキャストして処理、マージ、転送する以前の方法を変換し、通信の複雑さを o(n) に減らすことができます。達成するコミュニケーション PBFT コミュニケーションのラウンドのコンセンサス効果。

PBFTアルゴリズムと比較すると、事前準備においてマスターノードが他のノードにリクエストを送信した時点からコンセンサスが開始され、マスターノードはこのラウンドのコンセンサスの責任を果たしており、その後は他のノードと同じになります。コンセンサス プロセス全体には、ブロードキャスト提案フェーズ (PRE-PREPARE フェーズ) と 2 つのコンセンサス フェーズ (PREPARE フェーズ、COMMIT フェーズ) が含まれます。

準備段階:

マスターノード: 1) 受信したクォーラム New-View メッセージ (送信側の状態ツリーで最高の高さの prepareQC を含む) に従って、マスターノードは受信した prepareQC から最高の高さ QC を計算し、 highQC として記録されます。

２）このｈｉｇｈＱＣのノードが指すブランチに従って、ブロックをパックして新しいツリーノードを作成し、その親ノードはｈｉｇｈＱＣが指すノードである。

3) 生成されたプロポーザルを準備メッセージで他のスレーブ ノードに送信します。現在のプロポーザルには highQC が含まれています。

スレーブノード: 1) 準備メッセージを受信した後、QC での署名の有効性、現在のビューの提案であるかどうかなど、準備メッセージの情報を検証します。

2) prepare メッセージ内のノードが lockedQC のブランチ (つまり、子ノード) から拡張されているか、または prepare メッセージ内の highQC のビュー数が lockedQC のビュー数より大きいかどうか (前者はセキュリティ条件であり、後者は、ノードが遅れているときにタイムリーな同期を確保するためのアクティブな条件です)。

3) 投票準備メッセージを生成し、署名付きでマスター ノードに送信します。

プレコミット段階:

マスター ノードが現在の提案に対するクォーラム準備投票メッセージを受信すると、クォーラム部分署名を集約することで prepareQC が取得され、マスター ノードは集約された prepareQC を含むプリコミット メッセージをブロードキャストします。

スレーブ ノード: 他のノードはプレコミット メッセージを受信し、検証後にプレコミット投票メッセージをマスター ノードに送信します。

⚠️この時点では、マスター ノードによって送信された事前コミットの prepareQC は、準備メッセージの提案メッセージを示しており、すべてのノードが投票で合意に達することに成功していることに注意してください。この瞬間は、PREPARE 段階で到達した合意に似ています。 PBFTで。

コミットステージ:

マスターノード: コミット前の段階に似ています。 1) マスター ノードは、まずクォーラムのコミット前投票メッセージを収集し、次にこのステージのコミット前 QC を集約し、それをコミット メッセージで他のノードに送信します。 2) ローカルの lockedQC を pre-commitQC に設定します。

スレーブ ノード: コミット メッセージが受信されると、メッセージ検証に合格し、ローカルの lockedQC もコミット メッセージ内の pre-commitQC として更新され、署名され、コミット投票が生成されてマスター ノードに送信されます。

⚠️現時点では、マスター ノードによって送信されたコミット メッセージに添付される pre-commitQC は、PBFT の COMMIT フェーズのコンセンサスの第 2 ラウンドに似ていることに注意してください。PBFT のこのフェーズのコンセンサスは、PBFT の最初のフェーズのコンセンサスを示します。ノードペアがコンセンサスに達すること。つまり、少なくともクォーラムノードが PREPARE フェーズを完了していることを確認し、ビューの切り替えが発生したときに、十分な数のノードが提案に関して PREPARE コンセンサスに達していることを証明でき、提案内容には新しいビューで送信されます。

決定段階:

マスターノード: 1) クォーラムコミット投票メッセージが収集されると、commitQC が集約され、決定メッセージで他のノードに送信されます。

2) 他のノードが決定メッセージを受信すると、commitQC が指すプロポーザル内のトランザクションが実行されます。

3) 次に、ビュー番号 viewnumber を増やし、次のコンセンサスラウンドを開始し、prepareQC に従って New-View メッセージを構築します。

スレーブノード：メッセージを確認した後、決定メッセージ内のcommitQCが指すツリーノードのトランザクションを実行します。

nextView 割り込みステージ: コンセンサスの他のステージでタイムアウト イベントが発生した場合、新しいビューに対して新しいビュー メッセージを送信すると、新しいコンセンサスの次のラウンドが直接開始されます。

文章

▲ Chained HotStuff

Basic HotStuff の各ステージのプロセスは非常に類似していることがわかります。HotStuff の作成者は、Basic HotStuff のメッセージ タイプを簡素化し、Basic HotStuff の各ステージがパイプライン方式でトランザクションを処理できるようにするために、Chained HotStuff を提案しました。

Chained HotStuff のプロセスは次のとおりです。

図からわかるように、各段階でビューが切り替わるため、各提案には独自のビューがあります。ノードは、異なる提案に対して異なるビューにあります。PREPARE ステージの投票は、現在のビューのマスター ノードによって QC に合成され、次のビューのマスター ノードに転送されます。前のビューの PRE-COMMIT フェーズに進みます。各フェーズは同様の構造を持ち、ビュー v+1 の PREPARE フェーズはビュー v の PRE-COMMIT フェーズとみなすことができます。ビュー v+2 の PREPARE フェーズは、ビュー v+1 の PRE-COMMIT フェーズおよびビュー v の COMMIT フェーズとみなされます。 v1 の cmd1 は、ビュー v1、v2、v3 でそれぞれ PREPARE、PRE-COMMIT、COMMIT フェーズを実行し、v4 でコミットします。 cmd2など。各段階での cmd 提案の生成には、前の段階で投票された QC が伴います。 HotStuff の合理化バージョンの作業プロセスは次のとおりです。

マスターノード: 1) NEW-VIEW メッセージを待ち、独自の提案を送信します。

2) 他のノードが投票するのを待っています。

3) NEW-VIEW メッセージを次のマスター ノードに送信します。

スレーブノード: 1) マスターノードからの提案メッセージを待ちます。

2) 提案内の QC を確認し、ローカル highQC、lockedQC を更新し、投票を送信します。

3) NEW-VIEW メッセージを次のマスター ノードに送信します。

▲ Event-driven HotStuff

Chained HotStuff からイベント駆動型 HotStuff まで、元の論文ではプロトコル全体の安全性 (safety) とライブネス (liveness) が切り離されており、ライブネスは別個のペースメーカー モジュールになります。ペースメーカー モジュールは、Global Stability Time (GST) 後の稼働状態を保証します。次の 2 つの機能を提供します。

• 各ビューのプライマリ ノードを選択して確認します。

• マスターノードによる提案の生成を支援します。

言い換えれば、ビュー切り替えコストが非常に低いため、適切なノード回転メカニズムと提案生成戦略をペースメーカーで採用できます。

イベント駆動型 Hotstuff と他のバージョンの原理は依然として 3 段階の核心的な合意です. 違いはエンジニアリング実装の利便性だけです. 詳細については論文の疑似コードを参照してください [4]

副題

活動メカニズムの最適化

積極的なメカニズムがコンセンサスを継続的に前進させる鍵となります。オリジナルの HotStuff 論文では、ライブネス メカニズムはグローバルに一貫したタイムアウトを使用してビュー タイムアウトを決定していました。 NoxBFT では、ネットワーク環境の不安定性に対処するために、より柔軟なメカニズムを設計しました。

副題

トランザクションバッファプール

ブロックチェーンの応用では、トランザクションの損失を避けるために、クライアントのトランザクションをキャッシュするトランザクション キャッシュ プールを設計しました。コンセンサス モジュールは、パッケージ化するトランザクションをアクティブにプルします。トランザクション プールは、コンセンサス ワークロードを削減し、トランザクションの重複を排除することもできます。トランザクション コンテンツ ハッシュを通じてトランザクションを識別し、実行されたトランザクションをブルーム フィルターに書き込むことで、二重支払い攻撃を防ぎ、コンセンサス アルゴリズムの安定性を向上させます。

高速回復メカニズム

ネットワーク環境が不安定であると、コンセンサスノードがコンセンサスメッセージを失い、ノードが遅れてしまう可能性があります。オリジナルの HotStuff 論文では、著者はこの部分の具体的な実装を開発者に任せていました。遅れているコンセンサスノードの順序付け機能を復元するために、プロジェクトで利用可能な同期アルゴリズムを実装しました。これは 2 つのステップに分かれています。

1) ノードは大幅に遅れており、他のノードからブロックを直接プルして最新のチェックポイントに復元します。

2) チェックポイント後のコンセンサスの進行状況が遅れているため、最新の CommitQC が他のノードから取得され、コンセンサスの進行状況を迅速に復元します。

効率を向上させるために、異なるノードからブロックを並列にプルする仕組みを採用しており、並列度は柔軟に設定できます。並列にプルされたブロックは最初に永続化され、その後順序正しく実行され、同時に各ノードのプル効率のスコアが記録されるため、次回同期対象のノードを効率的に選択できます。プロセス全体が失われたすべてのトランザクションを最速の速度でプルできるため、プロセス全体の待ち時間が短縮されます。

集約署名

要約する

要約する

著者について

著者について

チェン・タイニン

参考文献

参考文献

[1] Schneider F B . The state machine approach: A tutorial[J]. Springer New York, 1990.

[2] Lamport L ,  Shostak R ,  Pease M . The Byzantine Generals Problem[J]. ACM Transactions on Programming Languages and Systems, 1982, 4(3).

[3] Castro M, Liskov B. Practical Byzantine fault tolerance[C]. OSDI.1999, 99(1999): 173-186.

[4] Yin M ,  Malkhi D ,  Reiter M K , et al. HotStuff: BFT Consensus in the Lens of Blockchain[J].  2018.

[5] Shoup V . Practical Threshold Signatures[C]// International Conference on Theory & Application of Cryptographic Techniques. Springer-Verlag, 2000.