🍶ブロックチェーン技術でも用いられている確率的データ構造 - ブルームフィルタ

ブルームフィルタとは

探索アルゴリズムのために用いられる確率的データ構造ある。
特定の要素が集合に含まれているかどうかを調べるために使われる。

• 長所
  ハッシュテーブルなどと比較してメモリの使用効率が優れている。
  探索の際の計算量も優れており集合への検索、追加ともにO(1)で行われる。

• 短所
  確率的データ構造であり偽陽性による誤検出の可能性がある。(偽陰性はない)
  [例] [a, b, c]という集合があるとき、aの存在を検索するときは誤ってfalseを返すことはないが、dの存在を検索するときは誤ってtrueを返す可能性もある。

Bloom filter - SlideShareは直感的でわかりやすい。

データ構造

ブルームフィルタはビット配列Bで表される。
mビットの領域、k個のハッシュ関数を用意する。

• 要素の追加
  追加する要素をk個のハッシュ関数に通して0~m-1の範囲の値を得る。
  値をビット配列に対する添字とみなし、対応するビットを立てる(1にするなど)。

• 要素の検索
  対象の値に対してk個のハッシュ関数に通して0~m-1の範囲の値を得る。
  それぞれが示すビットが全て立っているかで判定する。

具体例で考えてみる。
["beer", "sake", "gin"]の集合がある。
この集合に対するブルームフィルタをまず作成する。
m=8, k=2のブルームフィルタを考える。
それぞれのハッシュ値は以下である。

	ハッシュ値1	ハッシュ値2
beer	1	5
sake	2	6
gin	3	7
whisky	1	7

初期のブルームフィルタ

index	0	1	2	3	4	5	6	7
ビット	0	0	0	0	0	0	0	0

例えば、beerを追加したブルームフィルタ

index	0	1	2	3	4	5	6	7
ビット	0	1	0	0	0	1	0	0

sakeとginも追加したブルームフィルタ

index	0	1	2	3	4	5	6	7
ビット	0	1	1	1	0	1	1	1

🍺🍻ブルームフィルタ完成🍶🍸

sakeが含まれているか検索してみる。
ハッシュ値は2,6なので、indexが2,6のところをみると1になっていて集合にsakeが含まれているのがわかる。

whiskyが含まれているか検索してみる。
ハッシュ値は1,7なので、indexが1,7のところをみると1になっていて集合にwhiskyが含まれているということになる。
しかし、これは誤りである。偽陽性である。

実装

Rubyで実装した。
Rubyで文字列で一意にきまるハッシュ値を取得するにあるように、Objectのhashメソッドを使うと実行の度にハッシュ値が変わるので注意。
擬似コードの代わり書くだけなら、hashメソッドでも十分だとおもうが一応sha256を用いた。

require 'digest/sha2'

class BloomFilter
  def initialize(m, k)
    @bits = Array.new(m, 0)
    @m = m
    @k = k
  end

  def add(elem)
    # ビットを立てる
    @k.times do |i|
      hash_value = Digest::SHA256.hexdigest(elem + i.to_s).to_i(16) % @m
      @bits[hash_value] = 1
    end
  end

  def include?(elem)
    # ビットが全て立っているか調べる
    @k.times do |i|
      hash_value = Digest::SHA256.hexdigest(elem + i.to_s).to_i(16) % @m
      return false if @bits[hash_value] == 0
    end
    true
  end
end

# ブルームフィルタの作成
bf = BloomFilter.new(8, 2)
bf.add('beer')
bf.add('sake')
bf.add('gin')

# ブルームフィルタに含まれているか判定
p bf.include?('beer')
p bf.include?('sake')
p bf.include?('gin')
p bf.include?('whisky')

# 出力
true
true
true
true

whiskyは含まれていないはずだが、含まれることになってしまっている。
パラメータm,kの選び方によって、偽陽性の割合は変わってくる。
ブルームフィルタの計算量空間量と、偽陽性の割合のトレードオフである。

bitcoinでは、実際にm=36000,k=50が用いられているようだ。
https://github.com/bitcoin/bitcoin/blob/db3cb5c5a686279b220cac13c17b367aa0e4af99/src/bloom.h#L16-L18

どのようにブロックチェーン技術に用いられてるか

ブルームフィルタは、P2Pネットワーク上のSPVノードが受け取るトランザクション(およびそれらを含んでいるブロック)をフィルタリングするために使われる。
SPVノードは、自分のウォレットにあるビットコインアドレスのみにマッチするフィルタを作成する。
ピアにブルームフィルタを送る。
ブルームフィルタにマッチしたトランザクションのみがSPVノードに送られる。

自分がどのアドレスに対するトランザクションを探しているか明らかにすることなく、特定のパターンに適合するトランザクションを確認できる。
正確性とプライバシーのバランスを取ることができる！

SPVノードとは
ビットコインのブロックチェーンネットワーク上にはフルブロックチェーンノードと呼ばれるブロックチェーンの情報を全て持っているノードや、自ノードに関する簡単な情報を持っているSPVノードなどさまざまな種類のノードが存在する。SPVは、ブロックチェーンを持たずウォレットなどの情報のみを持つノードである。

参考

http://kakts-tec.hatenablog.com/entry/2017/06/21/004248
https://qiita.com/saka1_p/items/da8f2216d864b0659b8a