🌊

EthereumのBloom Filterの仕組み

2023/03/08に公開

ブロックチェーン

この記事は株式会社Gincoのテックブログとして書いています。

GincoでSenior Software Engineerをしている内村です。今回はEthereumで使用されているBloom Filterという仕組みについて深掘りします。

Bloom Filterとは

Bloom Filterとは、Filterという名の通りデータのフィルタリングに使用される手法のことです。

以下、Wikipediaより引用。

1970年に Burton H. Bloom が考案した空間効率の良い確率的データ構造であり、あるデータが集合の要素である（集合に含まれている）かどうかの判定に使われる。ただし判定は正確ではなくて、含まれていないのに含まれていると誤って判定すること偽陽性（false positive）の可能性がある。しかし含まれているものを含まれていないと誤判定すること偽陰性（false negative）はない。

つまり、以下の特徴を備えているデータ構造です。

データが集合の中に存在するかを判定する
空間効率の良い確率的データ構造である
偽陽性の可能性はあるが、偽陰性の可能性はない

これらの特徴を活かして、Bloom Filterは主にStorageへのアクセスを行う前にデータが存在するか否かを判定し、無駄なクエリを減らす用途で使用されます。

構築方法

Bloom Filterはバイナリで構成されています。以下は長さ18bitsのBloom Filterに３つの要素を追加する例が表されています。

wikipedia

要素を新たに追加する際は、追加する要素のハッシュ値からFilterのどのbitを反転するか決定し、フラグを立てる(0->1に反転)
要素がFilterに登録されているか判定する際には、追加する時と同様に判定する要素のハッシュ値からFilterのフラグの位置を特定し、Filter上で全てのフラグが既に1だった場合、Filterにその要素が含まれていると判定する
要素を追加する際に既存のFilterでフラグが1になっていた場合、1のままにする

上の図では、1つの要素につき3つのbitsが反転されているので、3つのハッシュ関数を使用していると考えられます。

より具体的にBloom Filterの動きを確認したい方には、以下のサイトがおすすめです。UIを通じてBloom Filterの作成・検証を試すことができます。

空間効率

Bloom Filterは、ハッシュテーブルなどで生データをメモリに保持して判定をするよりも少ないメモリ消費量でデータの有無が判定できます。以下はKey-Value Storeでの利用例で、Storageの前段にBloom Filterを置くことでStorageへのアクセスを減らし、パフォーマンスを向上させています。

wikipedia

実際のユースケースとして、Google Bigtable, Postgres, Cassandra等のプロジェクトでもBloom Filterが使用されているようです。以下の動画では、NoSQLで採用されることの多いLSM-Treeの実装でBloom Filterがどのように利用されるかが解説されています。

また、Bloom Filterはグループに含まれる生データのハッシュ値からFilterを構築するため、基本的にFilter自体に生データの情報はなく、第三者に共有しても問題がないという特徴があります。ただし、セキュリティは使用するハッシュ関数の原像計算困難性に依存します。

計算量

空間効率に加えて、計算量に関しても優れた点があります。例えば単純に要素数をNとしたときその中に任意の値が含まれるかを判定するナイーブなアルゴリズムの計算量がO(N)なのに対し、Bloom Filterを使用した場合は、内部で使用するハッシュ関数の個数をkとしてO(k)の計算量で判定することができます。

偽陽性率

Bloom Filterは確率的データ構造であるため、判定結果は偽陽性である(値がグループに含まれると判定されたが実は含まれない)可能性があります。偽陽性は登録されていない要素のハッシュ値に対してもフラグが有効になっているときに発生します。

Bloom Filterの偽陽性率を左右するパラメータは、以下の３つです。

Filterの構築に使用するハッシュ関数の数: k
Filterのサイズ(bits): m
Filterに登録する要素の数: n

Bloom Filters - the mathより、これら３つのパラメータを使用して、偽陽性率(p)は以下の式で求められます。見た目の通り、Filterのサイズ(m)が大きくなると偽陽性率は下がり、Filterに登録する要素の数(n)が増えると偽陽性率が上がることがわかります。

p=(1−e^{-\frac{kn}{m}})^k

加えて、mとnが与えられたときに、偽陽性率を最適化するハッシュ関数の数は以下の式で求められます。

k={\frac{m}{n}}ln 2

なんとなく各パラメータの関係が掴めたかと思いますが、より視覚的に理解したい方は、以下のリンクからGeoGebraでkとmのパラメータを変化させたときに偽陽性率がどのように変化するかを確認できます。ぜひ試してみてください。
https://www.geogebra.org/m/yq8zfgdz

GeoGebra

Blockchainでの使用例

Bitcoin

BitcoinではSPV(Simplified Payment Verification)ノードで使用されています。SPVノードとは、フルノードとは対照的にBitcoinの全てのBlockをダウンロードすることなく利用できる軽量ノードのことで、自分のウォレット(アドレス)に関係のあるBlockのみをダウンロードすることで軽量化を実現しています。この「自分のアドレスが含まれるBlockのみを探す」作業でBloom Filterが使用されています。

BitcoinのSPVノードのBloom Filterに関しては以下の動画で詳しく解説されています。

Ethereum

Ethereumでも、Bitcoinと同様にコントラクトのアドレスやEventのTopicに関連するBlockやTransactionのみをフィルタリングする際にBloom Filterが利用されています。例えば、Ethereumノードで提供されているjson rpcのeth_getLogsやeth_newFilterでは内部でBloom Filterを用いたトランザクションのフィルタリングが行われています。具体的にどのようなFilterが使用されているかは、BlockやTransaction ReceiptのlogsBloomフィールドを参照することで確認できます。

例えば、Ethereum MainnetのTx#0xa6af05e2859ff158cf78adba1bd48e14185641129f9e08ef7f60a820b71f9459のreceiptをrpcを通じて取得すると、以下のlogsBloomが設定されていることがわかります。

0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000001000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000001000001400000000000000080200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000200800000000000000000000000000000000000000000000000000000000

{
  "id": 1,
  "result": {
    ...
    "logsBloom": "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000001000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000001000001400000000000000080200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000200800000000000000000000000000000000000000000000000000000000",
    "transactionHash": "0xa6af05e2859ff158cf78adba1bd48e14185641129f9e08ef7f60a820b71f9459",
    ...
  },
  "jsonrpc": "2.0"
}

以降では、このlogsBloomがどのように計算され、Geth内部で利用されているのかを深掘っていきます。

LogsBloomの生成ロジック

Yellow PaperとGeth

EthereumのYellow PaperとGethの実装を照らし合わせて、どのようにLogsBloomが生成されているかを確認します。

以下がEthereum Yellow PaperのうちBloom Filterを生成する関数について述べられている箇所です。

Ethereum Yellow Paper

where M3:2048 is a specialised Bloom filter that sets three bits out of 2048と書かれている通り、EthereumのBloom Filterは長さ(m)が2048bitsで、ハッシュ関数の数(k)は3つであることがわかります。

加えて、以下がGethでの該当実装箇所になります。

ReceiptのLogsBloomを構築する

Gethの実装内容を確認するにあたって、0xa6af05e2859ff158cf78adba1bd48e14185641129f9e08ef7f60a820b71f9459のlogデータを使用してLogsBloomを再現します。

Etherscanより取得した以下の値を実際に使用します。

	hex
contract address	0x7a013b21bf13f50fdb9871b3016fd78432f0f742
topics[0]	0x17307eab39ab6107e8899845ad3d59bd9653f200f220920489ca2b5937696c31
topics[1]	0x00000000000000000000000045a0cff92e02397006e882b88ed860edef8c3683
topics[2]	0x0000000000000000000000001e0049783f008a0085193e00003d00cd54003c71

1. 任意の値の256-byteハッシュを生成する

sha := hasherPool.Get().(crypto.KeccakState)
sha.Reset()
sha.Write(data)
sha.Read(hashbuf)
hasherPool.Put(sha)

bloomValuesで受け取った任意のdata []byteをkeccak256に通してハッシュ値をhashbuf []byteにて受け取っています。

また、Yellow Paperでfirst three pairs of bytes in a Keccak-256 hash of the byte sequenceのように述べられている通りkeccak256のfirst three pairs of bytes = 先頭6bytesを抜き出します。

結果として、logの値のkeccak256ハッシュの先頭の6bytesが以下になります。ハッシュ値は16進数表記で、1文字で4bits、2文字で1byteになるため6bytesは12文字になっています。

	keccak256(first 6bytes)
contract address	62d0b119357c
topics[0]	08ed60e3ecf9
topics[1]	a28f83b41285
topics[2]	f2e8b5bdbace

2. ハッシュ値から反転するbitを計算する

// The actual bits to flip
v1 := byte(1 << (hashbuf[1] & 0x7))
v2 := byte(1 << (hashbuf[3] & 0x7))
v3 := byte(1 << (hashbuf[5] & 0x7))

ここでは2048bitsのフィルターのうち、どのbitを反転するかを決定します。

例えば、logのcontract addressのhashbufを考えると、62d0b119357cのbytesの配列なので中身はhex表記で[62,d0,b1,19,35,7c]で、binary表記では、[01100010,11010000,10110001,00011001,00110101,01111100]です。

つまり、以下の処理を分解すると、

v1 := byte(1 << (hashbuf[1] & 0x7))

hashbuf[1] = 11010000
0x7 = 00000111
- 0x7はbinaryで00000111
11010000 & 00000111 = 00000000 = 0
- hashbuf[1]と0x7のANDをとる
00000001 << 00000000 = 00000001 = v1
- 1を3の結果分シフトする

となり、Filterの00000001を反転させるという結果になります。
logの値それぞれに対する結果は以下になります。

	v1	v2	v3
contract address	00000001	00000010	00010000
topics[0]	00100000	00001000	00000010
topics[1]	10000000	00010000	00100000
topics[2]	00000001	00100000	01000000

3. ハッシュ値から反転するbyteのindexを計算する

// The indices for the bytes to OR in
i1 := BloomByteLength - uint((binary.BigEndian.Uint16(hashbuf)&0x7ff)>>3) - 1
i2 := BloomByteLength - uint((binary.BigEndian.Uint16(hashbuf[2:])&0x7ff)>>3) - 1
i3 := BloomByteLength - uint((binary.BigEndian.Uint16(hashbuf[4:])&0x7ff)>>3) - 1

ここでは先ほど求めたbitsをBloom Filterのどの位置のbyteの反転に利用するかを決定します。

先ほどと同様に、contract addressのハッシュ値の処理の場合を考えて以下の処理を分解します。

i1 := BloomByteLength - uint((binary.BigEndian.Uint16(hashbuf)&0x7ff)>>3) - 1

binary.BigEndian.Uint16(hashbuf) = 0110001011010000
- contract addressのkeccakハッシュの先頭6bytesはbinary表記では、[01100010,11010000,10110001,00011001,00110101,01111100]だったので、Uint16 = 先頭2bytesの処理を考える
0x7ff = 0000011111111111
- 0x7ff = 10進数で2047、2進数で0000011111111111
0110001011010000 & 0000011111111111 = 0000001011010000
- 0000011111111111でANDをとる
0000001011010000 >> 3 = 0000001011010 = 90
- 11bitsの値を3bitsシフトして8bitsの値に変換している
- Bloom Filterは256bytesなので、8bits(最大256通り)のindexを取得している

結果、反転するbyte indexとbitsの対応表は以下になります。

	i1	v1	i2	v2	i3	v3
contract address	165	00000001	220	00000010	80	00010000
topics[0]	226	00100000	227	00001000	96	00000010
topics[1]	174	10000000	137	00010000	175	00100000
topics[2]	162	00000001	72	00100000	166	01000000

4. 算出したindexを反転させる

func (b *Bloom) add(d []byte, buf []byte) {
	i1, v1, i2, v2, i3, v3 := bloomValues(d, buf)
	b[i1] |= v1
	b[i2] |= v2
	b[i3] |= v3
}

*Bloomは256bytes長のbytes[]配列です。その配列のそれぞれの計算したindexにある値に対してORをとることでフラグを有効にしています。

contract address、topics[0]、topics[1]、topics[2]の値をFilterに登録し、Hexに変換することで、Transaction Receiptと同じ値を構築することができます。

以下がgolangでの検証コードになります。対応表にまとめた値を256bytesのFilterに反映することで、rpcから取得したLogsBloomの値と同じ値を算出することができました。

検証コード(golang)

package main

import (
	"fmt"
	"strconv"

	"github.com/ethereum/go-ethereum/common/hexutil"
)

func main() {
	bloomValues := []struct {
		name string
		i1   int
		v1   string
		i2   int
		v2   string
		i3   int
		v3   string
	}{
		{
			name: "contract address",
			i1:   165,
			v1:   "00000001",
			i2:   220,
			v2:   "00000010",
			i3:   80,
			v3:   "00010000",
		},
		{
			name: "topic[0]",
			i1:   226,
			v1:   "00100000",
			i2:   227,
			v2:   "00001000",
			i3:   96,
			v3:   "00000010",
		},
		{
			name: "topic[1]",
			i1:   174,
			v1:   "10000000",
			i2:   137,
			v2:   "00010000",
			i3:   175,
			v3:   "00100000",
		},
		{
			name: "topic[2]",
			i1:   162,
			v1:   "00000001",
			i2:   72,
			v2:   "00100000",
			i3:   166,
			v3:   "01000000",
		},
	}

	var bloom [256]byte
	for _, bv := range bloomValues {
		fmt.Println(bv.name)

		v1, _ := strconv.ParseUint(bv.v1, 2, 8)
		bloom[bv.i1] |= byte(v1)

		v2, _ := strconv.ParseUint(bv.v2, 2, 8)
		bloom[bv.i2] |= byte(v2)

		v3, _ := strconv.ParseUint(bv.v3, 2, 8)
		bloom[bv.i3] |= byte(v3)

		hex, _ := hexutil.Bytes(bloom[:]).MarshalText()
		fmt.Printf("current bloom: %s\n\n", hex)
	}
	
	// rpcから取得したreceiptのlogsBloom
	const logsBloom = "0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000001000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000001000001400000000000000080200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000200800000000000000000000000000000000000000000000000000000000"
	hex, _ := hexutil.Bytes(bloom[:]).MarshalText()
	fmt.Println("result:", string(hex) == logsBloom)
}

▶ go run ./main.go
contract address
current bloom: 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000000000000000000000000000000000000000000000000000000000000

topic[0]
current bloom: 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000200800000000000000000000000000000000000000000000000000000000

topic[1]
current bloom: 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000000001000000000000000080200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000200800000000000000000000000000000000000000000000000000000000

topic[2]
current bloom: 0x00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000000001000000000000000000000000000000002000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000001000001400000000000000080200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000020000000000200800000000000000000000000000000000000000000000000000000000

result: true

まとめ

Ethereumで使用されるBloom Filterの仕組みと、Geth内部でのLogsBloomの構築方法について深掘りしました。

いままで何となくデータのフィルタリングに使ってるんだな、という理解でしたが、Yellow Paperとソースコードから理解することでより具体的にBloom Filterの仕組みと利点を理解することができました。社内のサービスでも、Bloom Filterを用いてデータアクセスを減らすことができる場面は多そうなので、活用していきたいと思います。

最後に、Gincoでは、一緒にブロックチェーンの未来を開発する仲間を絶賛募集しています！
Gincoでブロックチェーンを学びたい方、ウォレットについて詳しくなりたい方は以下のリンクからぜひご応募ください。お待ちしております。
株式会社Ginco の求人一覧

EthereumのBloom Filterの仕組み

Bloom Filterとは

構築方法

空間効率

計算量

偽陽性率

Blockchainでの使用例

Bitcoin

Ethereum

LogsBloomの生成ロジック

Yellow PaperとGeth

ReceiptのLogsBloomを構築する

1. 任意の値の256-byteハッシュを生成する

2. ハッシュ値から反転するbitを計算する

3. ハッシュ値から反転するbyteのindexを計算する

4. 算出したindexを反転させる

まとめ

参考文献

Discussion