ビットコインの技術 BloomFilter

2016年05月01日(編集2016年05月01日)
このエントリーをはてなブックマークに追加

この記事は、ビットコインで利用されているBloomFilter(ブルームフィルタ)について説明をします。コードを通して、仕様と実装方法を理解していきます。

javaはoracle jdk 1.8.0_77を利用します。

環境

  • Windows8.1
  • oracle jdk version 1.8.0_77
  • Eclipse version Luna Service Release 2 (4.4.2)

BloomFilter利用例

  • ビットコイン
  • Elasticsearch
  • Solr
  • Redis
  • Chrome Browser

内容

中級者向け

BloomFilter

BloomFilter(以下、ブルームフィルタ)は、ある要素が集合に含まれているかどうかに使われるデータ構造です。

ブルームフィルタイメージ図

ブルームフィルタは、非常に高速に動作し、確率的に判定できます。

ここでいう確率的とは、偽陽性(False Positive)による誤検出の可能性があるが、偽陰性(False Negative)はないということです。

かんたんにいい換えると、

「含まれない物を、含まれると言ってしまうかもしれないが、含まれるものを含まれないとは言わない」

ということです。

使用例

具体的なブルームフィルタの例をあげてみましょう。

「Java」「Tomcat」「Struts」「Spring」という4つの単語を集めた辞書のブルームフィルタを作成します。

ブルームフィルタ

上記のブルームフィルタで、単語「Tomcat」が存在するかどうかをチェックします。
すると、このブルームフィルタは、単語「Tomcat」が存在しているので、必ずデータを検出できます

ブルームフィルタは、偽陰性(含まれるものを含まれないと言ってしまうことはない)の特性を持つので、「Tomcat」という単語を検索して、データが検出できないことは絶対にありません

存在する単語を、存在しないと判定することはない

一方で、ブルームフィルタは、偽陽性(含まれない物を、含まれると言ってしまうかもしれない)の特性をもつので、辞書に含まれていない「android」という単語を検索しても、trueを返す可能性があります。

存在する単語を、存在すると判定することがある

アルゴリズムと実装

では、実際にコードを実装します。
実装しながら考え方をさらに深めましょう。

ブルームフィルタは、二つの構成要素から成り立っています。
その構成要素は、

  • 与えられた長さmのビット配列
  • k個のハッシュ関数

です。

ハッシュ関数とビット配列

初期値のコンストラクタには、ビット配列の数m、ハッシュ関数の数k、ハッシュ値の調整値tweakを指定します。

{project_folder}/src/main/java/{package}/BloomFilter.java
public class BloomFilter {

  private long[] bytes;
  private int k;
  private long tweak;
  
  public BloomFilter(int m, int k, long tweak) {
    this.bytes = new long[m];
    this.k = k;
    this.tweak = tweak;
  }
}
        

次にハッシュ関数を用意します。
ビットコインは、ハッシュ値の計算にMurmurHash3アルゴリズムを使用しています。
MurmurHashは、衝突困難性と一様性に優れ、計算コストがMD5等よりも優れたハッシュ関数です。現在は32bitや128bitを生成するversion3が利用されています。

MurmurHash3アルゴリズムを利用したハッシュ関数は、デフォルトのjavaでは用意されていません。なので、ソースコードから抜き出して使用します。

このMurmurHash3ハッシュ関数を用いて、データの登録メソッドaddを実装します。

{project_folder}/src/main/java/{package}/BloomFilter.java
  /**
   * ブルームフィルタにデータを追加
   * @param data
   */
  public void add(String data) {
    for(int i = 0; i < k; i++) {
      int hash_value = murmurHash3(tweak, i, data.getBytes());
      int adjust_hash_value =  Math.abs(hash_value) % (byteArray.length * 8);
      int idx = adjust_hash_value >> 3;
      int value = (1 << (7 & hash_value));
      byteArray[idx] = value;
    }
  }
        

1つのデータに対し、k回ハッシュ関数を呼び出し、ハッシュ値を取得します。

文字列をハッシュ関数で計算して、データを登録する

ビット配列インデックスの値は、0 → 1とフラグを立てるか、値を設定します。初期値が変更されたことを、検索時に判断できることが重要です。

ビットコインの場合は、

  • idx = hash_value >> 3
  • byteArray[idx] = (1 << (7 & hash_value))

としています。

最後に、設定した単語がBloomFilterに登録されているかをチェックするメソッドを実装します。

{project_folder}/src/main/java/{package}/BloomFilter.java
  /**
   * ブルームフィルタにデータがあればtrue, なければfalseを返す。
   * @param data
   */
  public boolean contain(String data) {
    for(int i = 0; i < k; i++) {
      int hash_value = murmurHash3(tweak, i, data.getBytes());
      int adjust_hash_value =  Math.abs(hash_value) % (byteArray.length * 8);
      int idx = adjust_hash_value >> 3;
      if (byteArray[idx] != 0) {
        return true;
      }
    }
    return false;
  }
        

登録処理を検索処理に変更しただけです。

if (byteArray[idx] != 0) {
  return true;
}
        

文字列から算出したハッシュの値を取得し、配列インデックスをチェックします。値が0(初期値)ならデータがないことになります。

実行

上記で実装したコードをMainクラスで実行します。

{project_folder}/src/main/java/{package}/App.java
public class App {

  public static void main(String [] args) {   
    int len = 1 << 10;
    int k = 3;
    long tweak = 100;
    BloomFilter bloomFilter =  new BloomFilter(len, k, tweak);
    bloomFilter.add("Java");
    bloomFilter.add("Tomcat");
    bloomFilter.add("Struts");
    bloomFilter.add("Struts");
    System.out.println("Tomcat is " +  bloomFilter.contain("Tomcat"));
    System.out.println("Android is " +  bloomFilter.contain("Android"));
  }
}
        

"Java", "Tomcat", "Struts", "Struts"をブルームフィルタに登録し、"Tomcat", "Android"を検索します。

terminal
Tomcat is true
Android is false
        

Tomcatがtrue(検出)、Androidがfalse(未検出)になりました。

まとめ

ブルームフィルタは、通常のWEBアプリやスマホアプリの作成で使う機会はまずないと思います。

ビットコインでブルームフィルタが利用されているのは、

  • 少ないデータの転送で、存在チェックのデータを送れる
  • 秘密は保たれたままアドレスの近さ判定ができる

という特性のためでしょう。(作者不明なので、なぜブルームフィルタを採用したのかはわかりません。)

機械学習、人工知能というビックデータが重要な役割を果たすようになって、今後、再び注目を浴びるデータ構造かもしれません。

関連記事

タグ検索で調べてみよう

ビットコイン