ブルームフィルタ

SPVウォレットを実現したブルームフィルタとは

ブルームフィルタ（Bloom Filter）とは

ブルームフィルタとはデータを活用した通貨のことです。暗号理論によって、取引の安全性を確保しています。世界への送金手数料を安くすることや取引のスピードを速くすること、非中央集権、そして、世界中で同じ基準で取引ができることなどを目的に作られました。

集合の中に自分が探している項目が存在しているとあらかじめ知っていれば、その項目の存在をわざわざ検証することはありません。しかし検証が必要な場合は、値もしくは値を元にした他のソースを使って検証することは可能です。そして低確率で誤検出が許されるなら、目的の項目を検出することが可能になります。これがブルームフィルタの概念です。

もう少し詳しく説明すると、ブルームフィルタとは、ある要素が集合の中に含まれているかどうかを、確率を使って判定する方法です。これは偽陽性といい、膨大に存在するデータの中から必要とするデータが存在することを判定することができるが、不要なデータも必要なデータの1つとして拾ってしまう可能性があることを指します。またこのブルームフィルタは効率的に空間消費を行うので処理速度が非常に早いという特徴があります。

ブルームフィルタはメモリの空間消費が少ないので、効率的にデータが存在するかどうかを判断することができるというメリットがあります。

たとえば、SPV（Simplified Payment Verification）はブロックチェーンのすべてのデータをダウンロードすることなく、取引の検証を行う方式としてビットコイン論文で紹介されていたものの、実装されるに至りませんでした。しかしブルームフィルタを用いることで技術を実現することが可能になりました。

ブルームフィルタの特徴と仕組み

ブルームフィルタは確率的データ構造の一種で、特定データが集合に属するかどうかを判断する際に用いられます。ブルームフィルタはBloom Filterと英語表記され、1970年にバートン・ブルーム（Burton H. Bloom）が考案したことからこの名前がつきました。

ブルームフィルタは偽陽性による誤検出という可能性はあるものの、偽陰性（実際には存在するのに見落としてしまうこと）はないデータ構造です。要素を集合に追加することは可能ですが、要素が追加されるほど偽陽性の可能性は高まります。

ブルームフィルタの大きな特徴としては、メモリの空間消費が少ないので、効率的にデータの存在判定が可能であることです。プロトコル拡張により、ブルームフィルタを使えば、SPVクライアントのように自分のアドレスに関連するトランザクションだけをダウンロードするような使い方が可能になります。

本来ビットコインアドレスが所有しているコイン量を知るためには、トランザクション情報すべてをブロックから取得しなければなりませんが、そのような方法を使うとSPVノードからリクエストされたフルノード側はSPVノード側のビットコインアドレスを特定できてしまいます。それを回避するために、どのアドレスをリクエストしているかを明らかにせずに、特定パターンのトランザクションをリクエストして検証することができます。

ブルームフィルタが使われるタイミング

ブルームフィルタは空間効率の良いチェックが行えることから、大量のデータを扱う時に用いられるインデックス方法の一つです。

フルノードの大量のデータをダウンロードすることなく、ブロックヘッダサイズだけを用いてトランザクション情報を取得することができます。SPVウォレットを利用する時はこのブルームフィルタを使って情報を取得しています。

ブルームフィルタはメモリ使用量が少なくて済むことからSPVノードでは使用されていますが、利用する場合には条件があります。これは偽陰性判定が許容されるような条件の時だけです。

ブルームフィルタを使用するメリット

・効率的なデータ判定
SPVノードはフルノードが保持するブロックチェーンの一部を参照することで、フルノードの持つ全ブロックチェーンの情報をダウンロードせずにトランザクションの検証が行えます。これは現在のSPVウォレットの最も一般的な形です。

空間効率の良いチェック判定により、効率的なデータ判定が実現可能になりました。

・メモリ消費が少ない
空間効率の良いチェック判定ができるので、メモリの空間消費が少なくて済みます。

・偽陰性による判定ミスがない
偽陰性はデータが実際にあるのに存在しないという判定を出すことですが、ブルームフィルタはこの偽陰性による判定ミスがない方法です。これはビットコインウォレットを扱う上では大切な要素になります。

ブルームフィルタのデメリット

・偽陽性判定によるデータ判定ミスがある
ブルームフィルタのデメリットとしては偽陽性により、データの誤判定の可能性があることです。これは集合の中に存在しないデータについて、存在するという判定をすることがあるということを表します。

ハッシュテーブルなどを使って実装するような種類のデータ型と比較すると、空間効率が良いというのがメリットですが、その代わりにある特定要素が入っているといったような判定（偽陽性）を一定の確率で行うこともあります。このような誤判定が許されない環境で使用するには、ブルームフィルタは向いていません。