Bitcoinを支えるブルームフィルタ解説
~やるじゃん、ブルームフィルタ~
執筆者：望月 紀生（HashHubインターン：@mochiblock）
はじめに
ぼちぼち花粉症の方にとっては厳しい季節が近づいてきましたね。ちなみに自分は花粉症が治ったと自負しているのですが、誰も信じてくれません。悲しいです。稀に治るらしいですよ、本当に。
さて、今回の話はBitcoinでも使われているブルームフィルターについてのお話です。そもそもブルームフィルターってなんぞ？というところから、そのちょっと深掘りした内容まで解説していきます。
ブルームフィルターとは
一言で言えば「データ構造」です。じゃあどんなデータ構造なんですかと言うと、「確率的データ構造」です。じゃあ確率的とはなんですかというと、偽陽性による誤判定（もしくは誤検出）の可能性があるが、偽陰性による誤判定（もしくは誤検出）の可能性はないということです。
偽陽性を持つが偽陰性は持たない
偽陽性：本当は正しくないのに、正しいと判定してしまう
偽陰性：本当は正しいのに、正しくないと判定してしまう
文字だけを追うと少しややこしいですが、割と読んで字のごとくですね。なので偽陰性を持つが偽陽性を持たない＝正しくないものを正しいと判定してしまうかもしれないけど、正しいものを正しくないとは判定しないと、ということです。
例えば[Bitcoin, Bitcoin Cash, Ethereum, NEM]というブルームフィルタがあったとします。ここでBitcoinがあるかどうか調べると、これは入っているので必ず検出できます。必ずなので、Bitcoinなんてないよとなることはありません。では EOS があるか調べるとどうなるでしょう？これは検出されるかもしれないし、されないかもしれません。これは偽陰性を持つからです。
これにより、探索したいデータが存在しないという判定が出た場合、そのデータは絶対に存在しないことが保証されます。
アルゴリズム
ブルームフィルタで必要になるのはmビットのビット配列とk個のハッシュ関数です。初期段階のビット配列には全て0が入っています。ここに追加する要素をk個のハッシュ関数に通していきます。これから得られた各ハッシュ値の0~m-1ビットの範囲で取得し、対応するindexにビットを立てます。
逆に探索する際には、調べたい要素のk個のハッシュ値を取得し、それぞれが示すビットに全て立っているかを調べることでできます。
そのため、どうしてもビットが立つ部分が重なる可能性が出てきます。これが偽陰性につながります。なのでmが大きいほど偽陰性の確率は下がります。
長所
非常に高速(O(k))で要素の追加、探索が可能です。また探索はハッシュ値を元に行うため、一定のプライバシーを守りながら行うことができます。
短所
確率的に誤判定（誤検出）する可能性がある。またブルームフィルターではデータの削除はできません。なぜなら、k個のハッシュ関数によるハッシュ値を持つため、あるデータのハッシュ値が他のデータのハッシュ値と被る可能性があります。そのため、あるデータを削除すると他のデータに関する情報も削除してしまい、判定できなくなってしまうためです。
SPVノードで大活躍
SPVはSimplified Payment Verification の略で、自分にとって必要な情報のみをダウンロードするノードです。スマホでBitcoinをやり取りする場合、スマホにフルノードを立てるのは現実的ではないので、自分にとって必要な情報（自分だけのトランザクション履歴）のみを入れておきたいですね。そんな時にブルームフィルタが生きてきます。というのも、ブルームフィルタによって自分にとって必要な情報があるかをO(k)時間で調べることが可能だからです。
まとめ
超正確に調べられるわけじゃないけど、大雑把でいいから早く判定したい。さらにプライバシーもある程度保持したい、という場合に威力を発揮します。やるじゃん、ブルームフィルタ。
参考資料
お知らせ
■ブロックチェーンエンジニア集中講座開講中！
HashHubではブロックチェーンエンジニアを育成するための短期集中講座を開講しています。お申込み、詳細は下記のページをご覧ください。
ブロックチェーンエンジニア集中講座：https://www.blockchain-edu.jp/
■フレセッツ株式会社では仮想通貨の事業者向け BtoB ウォレットの開発をしていただけるエンジニアを募集しています！詳しくはこちら→https://fressets.com/career/
■HashHubでは入居者募集中です！
HashHubは、ブロックチェーン業界で働いている人のためのコワーキングスペースを運営しています。ご利用をご検討の方は、下記のWEBサイトからお問い合わせください。また、最新情報はTwitterで発信中です。
HashHub：https://hashhub.tokyo/
Twitter：https://twitter.com/HashHub_Tokyo
