ブルームフィルター

ブルームフィルターは、特定のアイテムがセットの一部であるかどうかをユーザーに通知するために使用できるデータ構造です。要素がセットに含まれているかどうかを確実に判断することはできませんが、要素が含まれていないかどうかを確実に判断することはできます。

1970年にバートンハワードブルームによって作成されたブルームフィルターは、スペースの使用効率が高いため、さまざまなアプリケーションに魅力的な製品です。一部の暗号通貨（特にビットコイン）では、Simplified Payment Verification（SPV）で不可欠な役割を果たします。

SPVクライアントを使用する場合、ユーザーはフルノードを実行せずにビットコインネットワークと対話できます。フルノードには特定のストレージ要件と計算要件があり、スマートフォンなどの低電力デバイスで実行するには扱いにくいものになっています。一方、SPVクライアントは、ユーザーのウォレットに関連する情報をノード全体に照会するだけです。

このデータをユーザーに中継する最も簡単な解決策は、完全なノードにクライアントのキーを認識させ、適切なトランザクションのみがそれらに送信されるようにすることです。明らかに、これはクライアントのプライバシーが犠牲になるため、標準以下のソリューションです。一方、すべてのトランザクションをダウンロードしてそれらの大部分を破棄するだけでは、帯域幅の浪費になります。ブルームフィルターを入力します。

説明しましょう。クライアントのアリスが、フルノードを実行しているボブに気づかせたくない価値の高いトランザクションを持っているとします。彼女はブルームフィルターを作成します。これを10x1グリッドとして説明します。

彼女は、関心のあるトランザクションデータを2つの異なるハッシュ関数を介して渡します。ハッシュ関数は0から9までの2つの数値を出力します。それらを4と7と呼びましょう。彼女はフィルターをボブに送信します。

このグリッドを見ると、アリスがフィルターに渡したデータがわかりません。データが含まれているセットがある場合は、それをハッシュしてフィルターと比較できます。一致する場合は、アリスが要求した情報である可能性があります。

同時に、4と7にマップされる入力が多数ある可能性が高いため、ボブはデータのどの部分にアリスが関心を持っているかを判断できません。彼は単にすべての一致を返し、アリスは彼女の側でそれらをフィルタリングします。

もちろん、これは非常に単純化されていますが、概念を示しています。ブルームフィルターは、クライアントの真の利益を難読化します。これは完全な方法ではありませんが（プライバシーについてはまだ懸念があります）、ノードへのシールドされていない要求よりも改善されています。