著者: Wang Yongge 教授、有名な中国の暗号学者、ノースカロライナ大学シャーロット校 (UNC、シャーロット) のコンピューター サイエンスの終身教授、ハイデルベルク大学の博士号、そして Sperax の主任科学者。
文章
Lamport, Leslie. "The part-time parliament." ACM Transactions on Computer Systems (TOCS) 16.2 (1998): 133-169.
コンセンサスプロトコルの設計は常に非常に困難なテーマです。チューリング賞受賞者のランポート氏は、1989 年に古代ギリシャのパクソス島でアマチュア議員のグループを利用して、分散コンピューティング用に設計したパクソス コンセンサス プロトコルを説明する法律を制定しました。 Lamport は論文を ACM TOCS に投稿しました。おそらくこのジャーナルの編集者はその記事の重要性を理解していなかったので、出版には決して同意しませんでした。 Paxos コンセンサス プロトコルが学界で広く議論され、産業界で広く使用されるようになるまで、1998 年にこのジャーナルは次の記事を掲載しました。
ランポート氏は、これは彼の論文の中で出版までに 2 番目に長い待ち時間だったと冗談を言った。これまでのところ、Paxos コンセンサス プロトコルはほぼすべての分散システムで使用されています。たとえば、Google の Bigtable は、Chubby ロック サービス システムを使用して、各ノードでのデータの一貫性を確保しています。 Chubby ロック サービスは Paxos プロトコルに基づいています。さらに、Microsoft、IBM、Amazon のクラウド サービス システムはすべて、システムの一貫性を提供するために Paxos プロトコルを使用しています。大まかに言えば、Paxos プロトコルは一連の ROUND で構成されます。 ROUND は 0 から始まり、合意に達するまで行われます。各 ROUND は次の 4 つのステップで構成されます。
1. マスター ノードはシリアル番号を生成し、それをすべてのノードにブロードキャストします。皆さんもこのシリアルナンバーの活動に参加していただければ幸いです
2. 各ノードは、参加した投票のシリアル番号と投票した投票の情報をマスター ノードに送信します。
3. 2 番目のステップでほとんどの応答を受信した後、マスター ノードは SAFETY に違反しない値 v を選択します。この値をすべてのノードにブロードキャストします v
4. 各ノードは、3 番目のステップでマスター ノードから値 v を受信した後、v に投票し、その投票をすべてのノードにブロードキャストします。
Paxos プロトコルは実装が難しいため、スタンフォード大学の研究者は 2014 年にモジュール式で実装が簡単な Paxos プロトコルを提案し、それを Raft プロトコルと名付けました。 Paxos/Raft プロトコルは、より穏やかな脅威モデルで動作します。言い換えれば、このプロトコルは、非同期ネットワークにおける非ビザンチン エラーに対してのみ堅牢です。非ビザンチン脅威モデルでは、障害のあるノードは受動的ミス (作業の停止など) のみを起こすことができ、積極的な攻撃攻撃を開始することはできません。 n 個のノードを持つシステムが許容できる非ビザンチン障害ノードの最大数は (n-1)/2 です。 Paxos/Raft プロトコルは、この最大数のフォールト トレラント ノードを達成します。
Paxos/Raft プロトコルはビザンチン エラーに対して堅牢ではないため、オープン ネットワーク システム (ブロックチェーン システムなど) では使用できません。ビザンチン エラーは、嘘をつく、メッセージを偽造する、共謀する攻撃、選択的 DoS 攻撃を開始するなど、積極的に攻撃的なエラーです。以前の記事で、分散型ブロックチェーン システムはオープン ネットワーク システムに基づいているため、ビザンチン脅威モデルを使用する必要があると述べました。
市場のブロックチェーンで最も広く使用されているビザンチン協定は、チューリング賞受賞者のバーバラ・リスコフ氏とその教え子カストロ氏が設計した実用的なビザンチンフォールトトレラントシステムPBFT（実用的BFT）です。 PBFT は、アライアンス チェーン (Hyperledger sawtooth や Qulian Technology の Hyperchain など) および多くのパブリック チェーンで広く使用されています。 PBFT は、Paxos プロトコルのビザンチン バージョンとみなすことができます。主な違いは、PBFT ではビザンチン エラーを防ぐために Paxos プロトコルに検証ステップが追加されていることです。そのセキュリティを分析する前に、まずそのプロトコルの正式な説明を行います。
PBFT プロトコルでは、n=3t+1 個のノード P1、...、Pn があると仮定します。そのうち、最大でも t 個のノードが攻撃者によって制御されます。 PBFT では、すべてのノードが共同で状態を維持し、一貫したアクションを実行する必要があります。 PBFT プロトコルは、一連のビューを通じて実行されます。各ビューには、メイン ノード (リーダー) と呼ばれるノードがあります。 PBFT システムは、最初にビュー (v=0) から開始し、次にビュー置換プロトコルを通じてビュー v=1、v=2、…などに進みます。マスター ノードが正常に動作できないとシステムが判断した場合にのみ、ビュー置換プロトコルが開始され、次のビューが開始されます。すべてのノードが各ビューのマスター ノードを知っていると仮定します。クライアントが現在のビューのマスター ノードにタスクを送信するたびに、PBFT プロトコルは、シーケンス番号の割り当て (事前準備)、相互対話 (準備)、およびシーケンス番号の確認 (コミット) という 3 つの通信フェーズを実行します。シリアル番号割り当て (事前準備) フェーズでは、各タスクにシリアル番号が割り当てられ、相互対話 (準備) フェーズとシリアル番号確認 (コミット) フェーズでは、すべてのタスクにグローバルな順序付けが行われます。現在ビュー v にいて、プライマリ ノードが Pi であるとします。その後、合意全体のプロセスは次のようになります。
1. クライアントはタスク要求 m を送信して、マスター ノードのサービス操作をアクティブにします。
2. マスター ノード Pi はタスク要求 m を受信した後、3 フェーズ プロトコルを開始します。
m,
a. シーケンス番号割り当て (事前準備) フェーズ: マスター ノードは、タスク要求 m に対して一意のシーケンス番号 seq を選択します。次に、マスター ノードは次のメッセージをすべてのノードにブロードキャストします。
ここで、H はハッシュ関数です。ノード Pj は、以下の条件が満たされる場合に上記のメッセージを受け入れます。
i. デジタル署名 SIGNATURE は有効です
ii. Pj は、同じ v、seq を持つ別のタスク要求をまだ受け入れていません。
iii. シリアル番号の配列が妥当な範囲内であること
b. 相互対話 (準備) フェーズ: ノード Pj がマスター ノードからのブロードキャスト メッセージを受け入れると、Pj は相互対話 (準備) フェーズに入り、次のメッセージをすべてのノードにブロードキャストします。
Pj の準備が完了すると、Pj は次の確認メッセージをすべてのノードにブロードキャストします。
ノードが 2t+1 確認メッセージを受信すると、ノードはタスク要求 m に含まれるタスクを実行し、結果をクライアントに直接送信します。
3. クライアントは異なるノードからの応答を待ちます。t+1 個の応答が同じであれば、その応答は操作の結果です。
Yongge Wang. Byzantine Fault Tolerance in Partially Connected Asynchronous Networks
最近、次の記事で PBFT のセキュリティを分析しました。
この記事の分析では、PBFT コンセンサス プロトコルは非同期ネットワークでは安全ではないと結論付けられています。この記事では、非同期ネットワークにおける PBFT プロトコルに対して私たちが設計した攻撃手法を簡単に紹介します。説明を簡単にするために、システムには n=3+1=4 つのノード P1、P2、P3、P4 があると仮定します。このうち、ノード P1 は攻撃者によって制御されています。また、ビュー v のプライマリ ノードが P1 であると仮定します。私たちの攻撃は v の視点で展開されます。
、ＳＩＧＮＡＴＵＲＥ」をＰ１、Ｐ２、Ｐ３に送信する。しかし、P4まではいきません。
ノード P1、P2、P3 の準備ができています。 P4 は最大 2 つのインタラクティブ メッセージを受信しており、配列を準備するには少なくとも 2+1=3 個のメッセージが必要であるため、P4 では配列の準備ができていません。
, SIGNATURE」がすべてのノードに送信されます。もちろん、可能であれば、攻撃者は、ノード P4 がノード P2 および P3 からブロードキャスト メッセージを受信するのを防ぐために DoS 攻撃を開始する可能性があります (この DoS 攻撃は、私たちの攻撃にとってそれほど重要ではありません)。この時点で、ノード P1 と P2 はタスク m に対する 3 つの確認メッセージを受信しています。ノード P3 および P4 は、タスク m について最大 2 つの確認メッセージを受信します。したがって、ノード P2 はタスク要求 m に含まれるタスクを実行し、結果をクライアントに直接送信します。ただし、P1、P3、P4 はこのタスクを実行しません。そのため、クライアントは十分な応答を受信できません。
上記の攻撃を実行した後、ノード P1 はビュー v のメッセージに応答しなくなります。したがって、システムはビュー置換プロトコルを開始して、次のビュー v+1 に入ります。ビュー v +1 に入った後、正直なノード P2、P3、P4 の内部データ状態は異なります。そのため、システムは調整不能な状態になります。
PBFT プロトコルでは、一部のノードが特定のメッセージを受信できない問題 (上記の攻撃シナリオなど) を解決するために、PBFT プロトコルは CHECKPOINT ステータス更新プロセスを設計しました。特に、100 個のタスクが実行されるごとに、各ノード Pj は現在のステータス メッセージをすべてのノードにブロードキャストします。
ノード Pi が上記の 2t+1 状態更新メッセージを受信し、その状態が state である場合、ノード Pi は現在の状態を上記のメッセージ内の状態 state に置き換えます。上記の攻撃では、不正なノード P1 が状態更新メッセージを発行しない場合、P2 によって発行される状態更新メッセージは、P3 および P4 によって発行される状態更新メッセージとは異なります。ノードのステータスを更新するには少なくとも 2+1=3 個の同一のステータス更新メッセージが必要であるため、P2 のステータスを P3 および P4 のステータスに更新することはできません。したがって、システムは常に調整されていない状態になります。
後の図では、不正なノード P1 は、正直なノード P3 および P4 と協力して、クライアントからの別のタスク要求を共同で実行できます。そのため、各ノードの状態は回復不可能なバラバラの状態になってしまいます。
前回の記事で、インターネットベースのブロックチェーン技術では DoS 攻撃が仕掛けられやすいと述べました。インターネットは非同期ネットワークであるため、次のモデルを使用してそのネットワーク通信を記述します。
Global Stabilization Time (GST) があり、その前にメッセージが失われる (DoS 攻撃など) か、順序が変更される可能性があります。 GST の後、ネットワークは同期ネットワークになります。しかし、GST がいつ始まるかは誰にもわかりません。
