Brahms: 動的ネットワークでのランダムなノードサンプリング (2008)

Brahms: Byzantine Resilient Random Membership Sampling

Brahms ^[1] はノードが自由に参加と離脱を行うことのできる動的なネットワークで任意のノードをランダムにサンプリング (抽出) することのできる分散アルゴリズムです。

全体のスケッチとしては、Gossipping モジュールがネットワークに流通しているノード ID を収集し、そのノード ID で継続的に Sampler ベクトルを更新していると、Sampler ベクトルの状態がだんだん「ネットワークからランダムに選んだノード ID の集合」と同じものになってゆく、というものです。もしノードの参加や離脱のない安定したネットワークでれば、すべてのノードの ID がネットワークに浸透し切ったときに、すべてのノードの Sampler ベクトルはそれぞれネットワークからランダムサンプリングされたノード ID の集合と同じものになります (ノードごとにサンプル集合は異なります)。

P2P や大規模ネットワークのように他のすべてのノードを認識したりすべてのノードと接続するのが困難な環境では、代わりにネットワークの一部となるノードを選ぶ必要があります。このようなときに Brahm で偏りなくノードをサンプリングして接続先にしたり、処理を依頼したり、(Tor のような) トンネルにしたり、統計情報を収集することができます。さらに Brahms はネットワークにビザンチン故障ノード (悪意的に動作するノード) が含まれていても機能するという特徴を持っています。

システムモデル

Brahms は次のようなシステムを想定しています。

• すべてのノードは任意のタイミングでネットワークに参加/離脱する。
• ネットワーク上のすべてのノードはユニークな ID を持っている。
• 受信したメッセージの送信者のノード ID が正確に分かる。
  • ただし認証 (身元証明のための事前の公開鍵の交換や証明書の配付) は必要ない。
• 中間者はピア間で交換されるメッセージを改ざんできない。

サンプリングアルゴリズム

ノード ID は Brams の Gossip プロトコルによってネットワーク拡散されます。ノードは観測したノード ID で Sampler ベクトルを継続的に更新してノード ID のサンプルを維持します (ネットワークの任意のスナップショットに対するサンプリングではない点に注意)。ネットワークはノードの参加と離脱によって動的に変化するため Brahms が維持しているサンプルも時間と共に変化します。

min-wise independent permutations

Brahms のサンプリングは「ノード ID に基づいて一様にランダムな値を算出し、いままでに観測した中で最も小さな値を持つ ID を現在のサンプル値 $qq$ として保持する」という動作を行う Sampler と呼ばれるステートマシンによって行われます。単一の Sampler は単一の ID のみを保持します。したがって独立した $nn$ 個の Sampler を束ねた Sampler ベクトル $S\mathcal{S}$ を用意することで、最大 $nn$ 個のノード ID を一様にランダムにサンプリングすることができます。これは min-wise independent permutations^[2] と呼ばれるアルゴリズムに基づいています。

このサンプリングを Python のコードで表現すると Sampler の処理は次のようになります (後述で擬似コードも示しています)。ネットワークのすべてのノード ID に対して next() を呼び出した後、q はその中からランダムに選んだ 1 つを保持していることが分かると思います。

import hashlib
import secrets

class Sampler:
  def __init__(self):
    self.q = None
    self.salt = secrets.token_bytes(16)

  def h(self, id):
    return hashlib.sha256(id + self.salt).digest()

  def next(self, id):
    if self.q is None or self.h(id) < self.h(self.q):
      self.q = id

  def sample(self):
    return self.q

※ID の乱数化関数は「入力に対する出力(ハッシュ値)の分布が一様となることが保証されているハッシュ関数」のことです。経験的に SHA-256 や BLEAK2 のようなハッシュ関数がそのような動作になることを期待できますが、公式にそれがどの程度の品質なのかは分かりません。

乱数化関数

乱数化関数 $hh$ は入力された ID に対して一様にランダムな値を出力します。また $hh$ は冪等で同一の ID に対して同一の値を出力します。したがって、出力値を乱数として使用できることが保証されているようなハッシュ関数を適用できます (すべてのハッシュアルゴリズムがそれを保証している訳ではない点に注意)。

$hh$ は同じ ID に対してどのような値が出力されるかを Sampler ごとに (さらに初期化されるごとに) ランダムに変える必要があります。したがって実際は salt のようなハイパーパラメータを持たせたハッシュ関数と見なすことができます。

これは、ある数学的特徴を持ったハッシュ関数の集合からランダムに一つ選んだハッシュ関数を使うことと同じで、他の Sampler との衝突を最小限にすることができます (このような手法は Universal Hashing と呼ばれます)。論文ではこのような衝突は無視できる程度として議論の対象外としていますが、サンプルが少ないと衝突も十分起きるでしょう。

死活監視

各 Sampler が最小値として保持している $qq$ のノードがアクティブであることを確認するために、定期的に ping などの手段で死活監視を行います。もし $qq$ がすでにアクティブでないと判断すると、その Sampler は初期化され $q=⊥q=\perp$ (null の意味) と新しい乱数化関数 $hh$ で再開します。

ゴシッピングアルゴリズム

一般に Gossipping による情報伝達には push と pull が併用されます。push は自身の持つ情報を隣接するノードに拡散する動作です。ただし push だけでは中継するノードの故障によってネットワークの末端まで情報が到達しない可能性があるため、各ノードは定期的に任意のノードに pull 要求を出して自身の状態が最新かを確認します。

Brahms は Sampler ベクトル $S\mathcal{S}$ とは別に、そのノードが現在認識しているノード ID の最大 $mm$ 個の集合であるビュー $V\mathcal{V}$ を保持しています。このビュー $V\mathcal{V}$ は現在の隣接ノードと考えることもできます。初期状態では ($V=∅\mathcal{V}=\emptyset$ では誰とも通信できなくなってしまうため) 既知のノード ID 集合やスーパーピアなどから取得したノード ID 集合の $V0\mathcal{V}_0$ が設定されています。

Brahms の Gossipping 処理の流れは次のようになります。

1. $V\mathcal{V}$ に含まれているノード ID からランダムに $αm\alpha m$ 個を選択し push_request を送信する。
2. $V\mathcal{V}$ に含まれているノード ID からランダムに $βm\beta m$ 個を選択し pull_request を送信する。
3. 応答待ち。
4. 受信した push_request の送信者ノード ID の集合を $Vpush\mathcal{V}_{\rm push}$ とする。
5. 受信した pull_request の送信者ノード ID に対して $V\mathcal{V}$ を設定した pull_reply を送信する。
6. 受信した pull_reply に含まれているノード ID 集合の和集合を $Vpull\mathcal{V}_{\rm pull}$ とする (pull_request を送っていない相手からの pull_reply は無視する)。
7. $Vpush\mathcal{V}_{\rm push}$ に含まれるノード ID が $αm\alpha m$ 個以下であり、$Vpush\mathcal{V}_{\rm push}$ も $Vpull\mathcal{V}_{\rm pull}$ も空でなければ、次の集合の和集合を新しいビュー $V\mathcal{V}$ とする:
   • $Vpush\mathcal{V}_{\rm push}$ からランダムに選んだ $αm\alpha m$ 個のノード ID の集合。
   • $Vpull\mathcal{V}_{\rm pull}$ からランダムに選んだ $βm\beta m$ 個のノード ID の集合。
   • $S\mathcal{S}$ からランダムに選んだ $γm\gamma m$ 個の Sampler が持つノード ID の集合。
8. 新たに観測した $Vpush\mathcal{V}_{\rm push}$ と $Vpull\mathcal{V}_{\rm pull}$ で Sampler ベクトル $S\mathcal{S}$ を更新する。

$α\alpha$, $β\beta$, $γ\gamma$ はぞれぞれビューに対する push の影響力、pull の影響力、履歴の影響力を比率で示す 0～1 範囲の値です。$α,β,γ>0\alpha,\beta,\gamma\gt 0$ かつ $α+β+γ=1\alpha + \beta + \gamma = 1$ より、$V\mathcal{V}$ は最大でも $mm$ 個の ID で構成されます。

Brahms のノードが持つ状態とデータの流れ、それを実行する Sampling, Gossipping の擬似コードをまとめると次の図のようになります。

攻撃耐性

ビザンチン故障ノードが存在せず、クラッシュ障害のような良性障害のみを想定したネットワークでは Brahms は正しく機能します。十分に時間が経過して各 Sampler ベクトル $S\mathcal{S}$ がネットワーク上でアクティブなノード ID を収集すれば、$S\mathcal{S}$ はネットワークからランダムにサンプリングされたノード ID を保持する集合に収束します。

問題は悪意的な攻撃意思を持ったビザンチン故障ノードの存在するケースです。Brahms に対する攻撃者の目標はノードの Sampler ベクトル $S\mathcal{S}$ やビュー $V\mathcal{V}$ を故障ノードの ID で埋め尽くし (ポイズニング)、特定のノードをネットワークから分断させたり、ネットワーク全体の効率を低下させることです。

Push Flooding 攻撃

一般的な Gossipping での push flooding 攻撃は、大量の不正な情報を push で伝達してシステム全体をポイズニングします。こうなるとシステム上の正しい情報は pull でしか伝達されなくなり、システムで正しい情報の占める割合は指数関数的に減衰します。

一方、Brams の push_request は自身のノード ID のみを伝達できる制限された送信です。大量の故障ノード ID を push で拡散することができないため、push flooding のような手法での攻撃は難しくなります。

Balanced 攻撃

Balanced 攻撃は、悪意的なノードがネットワークの広域に push_request を送信して、すべてのノードのビューに悪意的なノードが含まれるように仕向けます。このような状況は、時間の経過と共にシステム全体に流通する故障 ID の比率がある固定値に収束します。そしてパラメータを調整すればこの固定値を 1 より小さくすることができます。したがって、このような Balanced 攻撃でネットワーク全体の効率を低下させることはできますが、ネットワークを分断したり特定のノードを孤立させることは… 調整次第です。

標的型攻撃

標的型攻撃はある 1 つの正常なノードに大量の攻撃ノードの push_request を集中させそのビュー $V\mathcal{V}$ を乗っ取ろうとします。しかし Brahms のアルゴリズムでは、多数の push_request でビュー $V\mathcal{V}$ をポイズニングされないように、1 ラウンドあたりで受信した push_request の数がその期待値 $αm\alpha m$ を超えていたらビュー $V\mathcal{V}$ を更新しないという動作をします。

Brahms の push は自身のノード ID しか伝達できないため、単一の攻撃者がこのブロック動作を利用してすべての正しいノードのビュー更新を阻害することは困難です。

しかし、ネットワークに攻撃者が多数 (例えば $mm$ の 10% 程度) 存在するケースでは、すべての正常なノードに push_request を送信し続けることで、このブロック機能でビューの更新を停止させることができそうです。この場合、pull によるノード ID の収集で Sampler ベクトル $S\mathcal{S}$ の更新は (効率は低下しますが) 進行します。しかし新規参加のノードが発見されず、時間と共に離脱ノードが増加してビュー $V\mathcal{V}$ や Sampler ベクトル $S\mathcal{S}$ が使い物にならなくなる可能性がありそうです。

攻撃がない場合はほとんどのラウンドでこのブロック動作は機能せず正しくビュー $V\mathcal{V}$ を更新します。

履歴のフィードバック

Brahms は標的型攻撃を緩和することはできても防ぐことはできません。標的型攻撃でビューに故障 ID を含むことに成功すると、その ID への pull によってさらに多くの故障 ID を増やすことになります。ビューがポイズニングされると正常なノードへの push が減少してシステム全体の更新が停滞します。

Brahms では、過去に観測され死活監視されている Sampler ベクトルに由来するノード ID を比率 $γ\gamma$ でビュー $V\mathcal{V}$ に編入させることにより、ビューが完全にポイズニングされノードが孤立することを難しくしています。

個人的な所感

プライベートネットワークへの適用: ノード数が概ね $NN$ の、ビザンチン故障を想定しない小～中規模ネットワークであっても、$n=m=Nn=m=N$ とした Brahms を適用すればノードの動的な参加と離脱をサポートする"ほぼ"全結合のネットワークを構成することができるんじゃないかな。

Sybil 攻撃耐性: 参加に制限のないオープンなネットワークでは 1 台の物理コンピュータを 1000 ノードに見せかけることは難しくない。Brahms はこのような Sybil 攻撃ですべての (あるいは一部の) 正常なノードのビュー更新を阻害させることができるように見える。追加の制約的な設計 (例えば承認参加制や push のためには proof-of-work が必要など) や "運用でカバー" できる何かがなければ P2P のような匿名のオープン環境への適用は難しいかなと想うところ。もちろん、良性の任意障害のみを想定するネットワークはその限りではない。

他の確率的データ構造と併用: 例えば Gossipping で収集したノード ID を Sampler ベクトルだけではなく HyperLogLog にも適用すると、ネットワークに接続しているノード数の概算値を得ることができます。HLL のような確率的データ構造は大規模データ処理でしばしば使われています。Gossipping をストリームデータ処理のデータソースとみなすと min-wise independent permutation や HyperLogLog のような確率的データ構造とは相性が良さそうな気がします。

脚注

1. BORTNIKOV, Edward, et al. Brahms: Byzantine resilient random membership sampling. In: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing. 2008. p. 145-154.

2. BRODER, Andrei Z., et al. Min-wise independent permutations. In: Proceedings of the thirtieth annual ACM symposium on Theory of computing. 1998. p. 327-336.