本文へ移動
Financial Context Wiki

ビザンチン耐障害性：安全性、ライブネス、クォーラム

ビザンチン耐障害性は、任意故障があっても分散プロトコルが安全性とライブネスを保つ条件を表す。プロトコル、ネットワークモデル、故障上限、クォーラム規則、重み、ファイナリティ、復旧経路を一体で評価する。

更新日

プロトコル分析の教育目的に限ります。BFT という名称やクォーラム閾値だけでは、安全性、ライブネス、正しい実行、分散性、ファイナリティ、資産の安全は証明されません。

直接の答え

ビザンチン耐障害性（BFT）とは、明示された故障モデルとネットワークモデルの下で、特定の分散プロトコルが持つ性質である。一部の参加者が停止し、メッセージを留保し、相手ごとに矛盾するメッセージを送り、その他の任意動作をしても、定められた保証を維持する。BFT は単一のアルゴリズムではなく、あらゆるネットワーク分断中に全サービスが利用可能であるという意味でもない。

保証は分けて考える。safety（安全性）は正直な参加者が相反する値を決定しないこと、liveness（ライブネス）は適格な入力が最終的に決定へ進めること、validity（妥当性）は決定可能な値を制約することを指す。通信や正直な投票力が足りないとき、安全性を守るため停止するプロトコルもある。正しい合意は、アプリケーションコード、取引妥当性規則、ブリッジ、鍵、ガバナンスの正しさまでは証明しない。

認証付き部分同期 BFT の一般的な一群では、n=3f+1 個のレプリカで最大 f 個のビザンチン故障に耐え、コミット証明書に q=2f+1 票を使う。「故障は三分の一未満」「クォーラムは三分の二超」という表現はこのモデルに由来する。同期プロトコル、乱択非同期プロトコル、クラッシュ耐障害プロトコル、Proof of Work チェーン、その他の BFT 構成では前提や閾値が異なり得る。

ステーク加重システムの閾値はプロトコルが定義する投票力を指し、必ずしもバリデータ数、アドレス数、人数、独立運営者数ではない。比率を当てはめる前に、正確なプロトコル版、重みのスナップショット、決定種別、ネットワーク前提、クォーラム比較（> か >=）、故障動作を明示する。

しきい値未満
25%
攻撃側比率
25%
しきい値までの余裕
8.4%

結果は教育用の概算です。明示されない限り、取引所ルール、税、遅延、オラクル動作、固有のプロトコル条件は含みません。

仕組み

  1. 何を決定するか定義する。 ノードが取引順序、ブロックのコミット、チェックポイントのファイナライズ、リーダー選出、状態遷移の受理、フォーク選択のどれを行うか確認する。これらは同じ決定ではない。
  2. システムと攻撃者モデルを示す。 メンバー資格、認証、権限変更、投票重み、適応的腐敗、鍵侵害、二重投票、クラッシュ、メッセージ損失、検閲、サービス妨害、故障の相関可能性を記録する。
  3. ネットワークモデルを示す。 同期、部分同期、非同期を区別する。部分同期では、未知の大域安定化時刻以後にのみ成立する保証と、タイムアウト調整方法を特定する。
  4. クォーラム規則を導く。 プロトコル固有の閾値、ロック、投票規則を使う。古典的な n=3f+1 では、二つの 2f+1 クォーラムは少なくとも f+1 レプリカで交差する。ビザンチンが最大 f なら交差部分に正直なレプリカが含まれる。
  5. 全フェーズと証明書を追跡する。 提案、投票、ロック、ビューまたはラウンド変更、コミット、フォーク選択、復旧を検証する。ノードが高さ、ラウンド、値、親、ドメイン、メンバー時期、先行証明書を検証して初めて、署名済み超多数に意味がある。
  6. 安全性とライブネスの証拠を分ける。 すべての関係時点で排除される競合決定を証明し、その後、通信と正直参加の前提が成立した際に進行が再開するか試す。タイムアウトはスケジューリング手段であり、無応答ノードが悪意を持つ証拠ではない。
  7. 実装と運用を検証する。 証明モデルに照らして、クライアント多様性、鍵保管、署名器フェイルオーバー、リプレイ防止、状態同期、証拠処理、メンバー変更、監視、アプリ確認方針、インシデント復旧を確認する。

FLP の結果は、完全非同期モデルでは、たとえ一つのプロセスがクラッシュする可能性しかなくても、決定的合意プロトコルが終了を保証できないことを示す。安全性が不可能だとも、分散合意が一切動作しないとも述べていない。部分同期、乱択、故障検出器、経済的前提、より弱い保証は、特定の不可能性条件を変える別々の方法である。

計算例

1. 等しい重みの四レプリカ

n=4、f=1、q=3 とする。任意の三票集合二つは少なくとも 3+3-4=2 レプリカで重なる。ビザンチンが最大一つなら、交差部分の少なくとも一つは正直である。正直ノードの規則が、関係する高さとラウンド履歴で競合値への投票を禁じるなら、競合する二つのコミット証明書は同時に成立しない。

二つのレプリカが停止すると残りは 2 票で、q=3 の証明書は作れない。これはライブネス障害であり、自動的に安全性障害になるわけではない。安全に設計されたプロトコルは、局所的に閾値を下げず待機する。

2. 等しい重みの七レプリカ

n=7、f=2、q=5 とする。二つのクォーラムは少なくとも 5+5-7=3=f+1 レプリカで重なる。ビザンチンは最大 2 なので交差部分に正直なレプリカがある。二つのビザンチンだけでは五票証明書を作れないが、三つが停止または棄権すると残りは 4 票となり、進行を止められる。

閾値計算は必要だが十分ではない。正直な実装が誤った高さの票を受理し、メンバー集合を使い回し、ロック規則に違反し、侵害された鍵で署名するなら、証明の前提は実システムと一致しない。

3. 加重投票力

バリデータの重みを 40、30、20、10、合計 100 とし、証明書は厳密に 2/3 超、ここでは最低 67 を要するとする。40+30=70 の連合は証明書を作れるが、30+20+10=60 は四者中三者でも作れない。重み 40 のバリデータが停止すれば残りは 60 で、ファイナリティが止まる。

最低 67 の集合二つは少なくとも 67+67-100=34 で重なる。従って競合証明書は、少なくとも 34 の重みが両集合に参加したか、別のプロトコル前提が破れたことを意味する。一部プロトコルでは三分の一をわずかに超える二重投票で安全性を壊し得るため、「攻撃には三分の二必要」は普遍的な最低条件ではない。

4. 部分同期とタイムアウト

四レプリカがラウンドごとに 1 s、2 s、4 s、8 s のタイムアウトを使うとする。未知の安定化時刻より前は、メッセージが毎回現在のタイムアウト後に到着し、決定なしにラウンド変更が続き得る。ネットワーク安定後の遅延が 3 s 未満なら、4 s 以降のラウンドで、他の前提も満たす限り、正直な提案者とクォーラムが通信し進行できる。

これは最終的な進行を説明する例で、普遍的なタイムアウト式ではない。短すぎれば不要なビュー変更が起き、長すぎれば復旧が遅れる。安全性は安定化前に正しい遅延上限を推測することに依存してはならない。

リスクと検証上の失敗

モデルと証明

  • プロトコル、版、決定、故障モデル、ネットワークモデル、メンバー規則、閾値を示さず「BFT」とだけ呼ぶ。
  • 異なる前提で証明されたプロトコルを含む全台帳に n=3f+1 や三分の一を適用する。
  • 安全性、ライブネス、妥当性、可用性、一貫性、ファイナリティ、フォーク選択、取引正当性を同義にする。
  • 決定的、完全非同期、終了保証という条件を残さず、FLP が合意全般を不可能にしたと主張する。
  • プロトコルがステーク、委任重み、委員会、エポック、別資源を数えるのにノードやアドレスを数える。
  • 「三分の二」を曖昧に丸め、実装が >、>=、整数重み、どの分母スナップショットを使うか無視する。
  • クォーラム寸法だけを確認し、交差、ロック、証明書、ビュー変更、再構成、状態移送を確認しない。
  • 証明なしに適応的腐敗、鍵盗難、相関故障、サービス妨害、長距離履歴までモデルが覆うと仮定する。

実装と運用

  • チェーン、ドメイン、高さ、ラウンド、値、親、メンバー時期、メッセージ種別に結び付かない署名を受理する。
  • 古い票や証明書をラウンド、高さ、フォーク、ネットワーク、アップグレード、バリデータ集合変更をまたいで再生する。
  • 二重署名、ロック後退、危険な署名器フェイルオーバー、二つの稼働レプリカによる同一バリデータ識別子共有を許す。
  • タイムアウトを悪意の証拠とみなし、ローカル時計だけで安全性に関わる判断をする。
  • 共通クライアント、クラウド、地域、ネットワーク、ハードウェア、鍵管理、運営者による相関故障を無視する。
  • スラッシングが故障防止、ライブネス回復、確定済みアプリ操作の取消し、全被害者の補償を行うと仮定する。
  • 通常運転だけを試し、分断、遅延・並べ替え、二重投票、提案者故障、再起動、メンバー変更を試さない。

アプリケーションとガバナンス

  • 決定的実行と状態遷移検証なしに、合意済みの値を有効なアプリ状態と扱う。
  • アプリが必要とする正確なファイナリティ条件より前に、入金反映、ブリッジ資産発行、取引決済を行う。
  • 鍵侵害、ソフトウェア障害、ガバナンス介入後の社会的不可逆性とプロトコルのファイナリティを同一視する。
  • 他の利用者向けブロックが確定し続けることを理由に、検閲と取り込み遅延を無視する。
  • BFT の名称や公称バリデータ数から、分散性、資産安全、トークン価値、法的強制力を推論する。

よくある誤解

  • BFT ならネットワークは決して停止しない。 多くの BFT は、過大な故障や分断時に安全性を守るため意図的にライブネスを犠牲にする。
  • 正直な参加者が 51% を超えれば常に十分である。 閾値はプロトコル次第で、古典的部分同期 BFT は通常、進行に関連投票力の三分の二超を要する。
  • 安全性を壊すには必ず三分の二が必要である。 三分の二なら単独で証明書を作れるが、一般的なクォーラムでは競合する超多数証明書が三分の一強の二重投票を示し得る。
  • バリデータアドレスを増やせば自動的に耐障害性が上がる。 共通所有、委任重み、クライアント、基盤、鍵、故障ドメインが独立故障能力を決める。
  • スラッシングが BFT の証明である。 一部 PoS の経済的対処にすぎず、安全性は規則と前提から生じ、罰則は外部結果を取り消さない。

関連トピック

出典

ナビゲーション

Wiki を検索...