暗号資産初心者向けの記事です。本記事ではブルームフィルターについてわかりやすく解説していきます。
目次
はじめに
みなさん、こんにちは！
今回はビットコインでも使われているブルームフィルターについての解説していきたいと思います。「そもそもブルームフィルターってなんだろう？」という方も多いと思いますが、こちらの記事が少しでもお役に立てると幸いです。
それでは解説していきます！
ブルームフィルターとは
ブルームフィルターとは高速に動作を行い、それぞれの要素が集合に含まれるか否かを確率的に判定できるデータ構造のことです。
「確率的」というのは「本来であれば含まれない物を含まれると言う可能性はあるものの、含まれるものを含まれないと言う可能性はない」という特徴を持っています。
Simplified Payment Verificationはビットコイン論文で言及はされているものの、実際にはデータを部分的にダウンロードする方法というのは長年存在しなかったことがすでに明らかになっています。これまで効率的に SPV クライアントを実装する事は不可能でしたが、プロトコル拡張によりブルームフィルターを用いることで自分のビットコインアドレスに関連するトランザクションのみをダウンロードすることが可能になりました。
特徴
ブルームフィルターは上記でも述べたように確率的データ構造の1種となっており、特定データが集合に属するかどうかを判断する際に使われます。
ブルームフィルターはメモリの空間消費が多くないため、効率的にデータの存在判定が可能であることが大きな特徴です。プロトコル拡張により、ブルームフィルタを使えば、SPVクライアントのように自分のアドレスに関連するトランザクションだけをダウンロードするような使い方が可能になります。
長所と短所
次にブルームフィルターの長所と短所についてご紹介します。
- 動作が高速である
- ご検出の可能性がある
それでは1つひとつ見ていきましょう。
（長所）動作が高速である
非常に高速で要素の追加や探索が可能になっているのが大きな長所と言えます。また探索はハッシュ値を元に行うため、一定のプライバシーを守りながら行うことも可能になっています。
（短所）誤検出の可能性がある
短所としては確率的に誤検出する可能性があるという点です。さらにブルームフィルターではデータ削除ができません。なぜならk個のハッシュ関数によるハッシュ値を持つため、あるデータのハッシュ値が他のデータのハッシュ値と被る可能性があるのです。したがって、あるデータを削除すると他のデータに関する情報も削除してしまうことになるため、判定ができなくなってしまいます。
使用するメリット・デメリット
最後にブルームフィルターを使用するメリットとデメリットを解説して終わりにしたいと思います。
- 効率的なデータ判定
- 偽陰性による判定ミスがない
- 偽陽性判定によるデータ判定ミスがある
それでは詳しく解説していきます。
メリット
効率的なデータ判定
SPVノードはフルノードが保持するブロックチェーンの一部を参照することにより、フルノードの持つ全ブロックチェーンの情報をダウンロードせずにトランザクションの検証を可能にしています。これは現在のSPVウォレットの最も一般的な形であると言えます。
偽陰性による判定ミスがない
偽陰性はデータが実際にあるのに存在しないという判定を出すことを指しますが、ブルームフィルターはこの偽陰性による判定ミスがない方法となっています。これはビットコインウォレットを扱う上では大切な要素です。
デメリット
デメリットとしては偽陽性によるデータの誤判定があることです。これは集合の中に存在しないデータについて、存在するという判定をすることがあるということを表しています。
ハッシュテーブルなどを使って実装するような種類のデータ型と比較すると、空間効率が良いというのがメリットとなっていますが、その代わりにある特定要素が入っているといったような判定を一定の確率で行うこともあります。このような誤判定が許されない環境で使用するにはブルームフィルターは不向きです。
最後に
本記事ではブルームフィルターについて解説してきました。いかがでしたか？
なかなか聞きなれない言葉だったかもしれませんが、この記事がみなさんのお役に立てれば幸いです！
