BIP-37 Connection Bloom filtering（訳）

Bitcoinのフルノードは、Blockchainの全情報を保持するため、そのデータ量は50GB以上になる。サーバ等であればまぁ問題になるようなレベルの量ではないけど、スマホやIoTデバイスといったリソースにはそれだけの量のデータを保存することはできない。そのためトランザクションデータはサーバに保持しつつサーバと適宜連携する方法もあるけど、これだとサーバが必要となりあまりP2Pのメリットが活きない。
そこで活用されるのがSPV（Simple Payment Verification）クライアントで、保持しているアドレスに関係するトランザクションのみを取得できる。

そのSPVを可能にするベースとなってるのがBIP-37になる。こちらの仕様をざっと意訳してみる。

概要

このBIPでは、ピアが送信するトランザクションデータの量を削減するためにP2P プロトコルへ新しい機能を追加する。ピアにはバージョンのハンドシェイクが完了した後に各コネクション毎にフィルタを設定するオプションがある。このフィルタはトランザクションから得られれるデータに対するBloom Filter *1として定義される。Bloom filterを利用することで、データ構造に対して対象となるデータが（存在することは証明できないが）存在しないことを証明することができる。

動機

Bitcoinが使用される限り、ブロックをダウンロードするために必要な帯域幅は増加し、ブロードキャストされるトランザクション量も増加する。SPV（simplified payment verification）を実装するクライアントは、接続しているブロックヘッダが正しいか確認するだけで、全てのブロックチェーンを検証しない。

（このBIPが書かれた）現在、SPVクライアントは、ブロードキャストされた全てのトランザクションとブロックの内容を全てダウンロードする必要があるが、自分のウォレットに関係ないほとんどのデータは捨てることになる。その結果、自分のウォレットに関係ないデータのために不要な帯域幅を使用し、メモリ使用量も増加し、同期プロセスが遅くなる。これらの問題はSPVモードを実装したAndroidの"Bitcoin Wallet"アプリにとって実際のユーザからの苦情につながっている。低スペックなスマートフォンでも実行できるよう、チェーンの同期を速くするために、無関係なトランザクションを廃棄したい。

設計原理

クライアントがリモートノードに鍵のリストをアップロードするための最も明確な方法について記載していく。以下の理由により少し複雑な方法を取る。

プライバシー
Bloom filterは確率的であるため、クライアントによって選ばれる偽陽性率によっってノードの精度と帯域幅の使用量はトレードオフになる。帯域幅への多くのアクセス権を持つノードは高い偽陽性率を持つように選択することもでき、そうするとリモートピアは正確にクライアントが関連したトランザクションについて知ることはできなくなる。非常に少ない帯域幅のノードはとても精密なフィルタを選択できウォレットに関連するトランザクションのみを取得できるが、リモートピアはIPアドレス等とトランザクションの関連付けをすることができるかもしれない。
Bloom filterはコンパクトでテストも高速にできる。これはDoS攻撃に対して最小限のリスクで満足ゆく性能特性をもたらす。

仕様

新しいメッセージ

プロトコルに３つの新しいメッセージを追加する。

filterload
コネクションにBloom filterをセットする
filteradd
新しいフィルタをセットするのではなく、与えられたデータ要素をコネクションの現在のフィルタに追加する
filterclear
現在のフィルタを削除し、BIP-37の前の状態に戻す

※ Bloom filterは追加専用のデータ構造である（データの削除には対応できない）性質上、filterremoveというコマンドが無い。ひとたび要素が追加されると最初からデータの再構築をすることなくデータを除去することはできない。

filterloadコマンドは以下のように定義される。

フィールドサイズ	定義	データタイプ	コメント
?	filter	uint8_t[]	フィルタ自体は単に任意のバイト単位のビットフィールドで、最大サイズは36,000バイト。
4	nHashFuncs	uint32_t	このフィルタで使用するハッシュ関数の数で、このフィールドに入力できる最大値は50。
4	nTweak	uint32_t	Bloom filterで使われるハッシュ関数のシード値に追加するランダム値。
1	nFlags	uint8_t	どのようにマッチしたデータを制御するかのフラグのセットでフィルタに追加される。

Bloom filterのアルゴリズムの説明と望ましい偽陽性率のためどのようにしてnHashFuncsとfilter sizeを選択するかについては後述。

filterloadコマンドを受信すると、リモートピアは速やかにトランザクションのブロードキャストを制限し、フィルタにマッチしたトランザクションのみアナウンスするようになる（マッチングアルゴリズムについては後述）。フラグでマッチングアルゴリズムの振る舞いをコントロールする。

filteradd コマンドは以下のように定義される。

フィールドサイズ	定義	データタイプ	コメント
?	data	uint8_t[]	現在のフィルタに追加するデータ要素

dataフィールドは520バイト以下である必要がある。

与えられたデータ要素がBloom filterに追加される。要素が追加されるフィルタは前のfilterloadコマンドで追加されたフィルタである。このコマンドは、ネットワーク接続中に新しい鍵やスクリプトがウォレットに追加された際に、各ピアに新しいフィルタを送信して再計算をすることを回避できるので便利。

filterclearコマンドは引数を持たない。

フィルタがセットされると、ノードは単純にマッチしないトランザクションのアナウンスをやめるのではなく、 filtered blocksとして扱う。 filtered blocksはmerkleblockメッセージとして定義され、その定義内容は↓

フィールドサイズ	定義	データタイプ	コメント
4	version	uint32_t	ブロックのバージョン情報
32	prev_block	char[32]	前のブロックのハッシュ値
32	merkle_root	char[32]	このブロックに関連する全てのトランザクションハッシュがあるマークルツリーのコレクションへの参照
4	timestamp	uint32_t	このブロックが作成された際のタイムスタンプ（2106年まで）
4	bits	uint32_t	このブロック作成時に計算されたブロック生成のdifficulty（難易度）
4	nonce	uint32_t	このブロックを生成するのに使われたnance。
4	total_transactions	uint32_t	ブロック内のトランザクションの数（フィルタにマッチしないトランザクションを含む）
?	hashes	uint256[]	深さ優先順のトランザクションハッシュのリスト（可変長整数のサイズのプレフィックスを含む）
?	flags	byte[]	フラグビット。1バイトに8ずつパックされた最初の最下位ビット（可変長整数のサイズのプレフィックスを含む）

部分的なマークルツリーのハッシュとフラグのフォーマットについては後述。

従って、merkleblockメッセージは、ブロックヘッダであり、フィルタにマッチしたトランザクションの識別情報を抽出しそのトランザクションデータが解決されたブロック内に存在することを証明するのに使われるマークルツリーの一部である。クライアントはリモートノードが実際のブロックには存在しない偽物のトランザクションを供給していないことを、このデータを使って確認することができる。ただそれでも省略による嘘（嘘を付くのではなく事実の重要な部分を伝えないことによる嘘）を付くことは可能。

既存メッセージの拡張

versionコマンドが新しいフィールドで拡張される。

フィールドサイズ	定義	データタイプ	コメント
1バイト	fRelay	bool	falseの場合は、ブロードキャストするトランザクションはフィルタコマンド（load,add,clear）を受信するまでアナウンスされない。 true及び未定義の場合プロトコルの動作に変化はない。

Bloom filterによるフィルタリングを行いたいSPVクライアントはバージョンメッセージ内のfRelayにfalseをセットし、自分のウォレットにフィルタをセットする。クライアントはバージョンハンドシェイクを終えフィルタが設定されるまでの間、わずかな時間でトラフィックが殺到するのを防ぐため、invメッセージ*2を停止することができる。

getdataコマンドは、inv サブメッセージで新しいタイプが使用できるよう拡張される。タイプフィールドはMSG_BLOCKではなくMSG_FILTERED_BLOCK (== 3)と定義することができる。コネクションにフィルタが設定されていない場合は filtered blocksへの要求は無視される。フィルタがセットされている場合は、要求があったブロックハッシュのためmerkleblockメッセージが返される。さらに、merkleblockメッセージにはトランザクションハッシュのリストしか含まれていないため、フィルタにマッチしたトランザクションはmerkleblockが送信された後に別個にtx メッセージを送信する。なお、現在（フルノードへリクエストする以外に）ブロックに既に登録済みのトランザクションをリクエストする方法はないため、フィルタにマッチした一連のトランザクションについてノードへリクエストする際はそのトランザクション情報をまだ受信していないもしくはアナウンスしていないというinvメッセージを送信する必要があり、フィルタに一致する任意の追加トランザクションも送信することができる。これによってクライアントは必要なトランザクション情報をノードから供給されている間は、アナウンスによって与えられたノードを覚えておく必要があり、invメッセージの数を制限できる。

フィルタのマッチングアルゴリズム

フィルタはデータの任意のピースに対してそのデータがクライアントによって挿入されたのかどうかテストすることができる。そのため、どのデータのピースが挿入されたものかテストされたものか疑問が生じる。

トランザクションがフィルタにマッチするかどうか判断するのに以下のアルゴリズムが使用される。１つマッチする部分があればその後のアルゴリズムは無視される。

トランザクション自体のハッシュをテストする
トランザクションの各出力に対して、出力スクリプト各データ要素をテストする。この際、出力スクリプトの各ハッシュと鍵が独立してテストされる。重要なのは、トランザクションのテスト中に出力がフィルタにマッチすると、ノードはシリアライズしたCOutPoint構造を挿入してフィルタを更新する必要がある。詳細については下記参照。
トランザクションの各入力に対して、シリアライズされたCOutPoint構造をテストする。
トランザクションの各入力に対して、入力スクリプトの各データ要素をテストする（入力スクリプトがデータ要素を含む場合のみ）。
上記条件にマッチしない場合は、マッチするものが無いと判定する。

このようにアドレス、鍵及び（P2SHの）スクリプトハッシュは全てフィルタに追加できる。また、入力または出力のいずれかでよく知られているデータ要素でマークされたトランザクションの集合に対してマッチさせることができる。（例えばスマートプロパティの様々なフォーマットを実現するような）

出力のテストは、自分のウォレット内で取引に使用される出力を（それがどのような種類であれ）見つけるためにある。一度コネクションにフィルタがセットされても、それは静的に固定されるものではなく、コネクションが生きている間は変更することができる。これは以下の競合状態を回避するためである。

クライアントが自分のウォレット内の鍵にマッチするフィルタを設定する。そしてブロックチェーンをダウンロードする。欠落しているチェーンの一部があればgetblocksを使ってリクエストされる。
最初のブロックが接続中のピアによってディスクから読み取られ、そこにはクライアントの鍵にお金を送るTX1が含まれている。これはフィルタに一致しているため、クライアントに送信される。
2つ目のブロックが接続中のピアによってディスクから読み取られ、そこにはTX1を使用するTX2が含まれている。しかしTX2にはクライアントの鍵のいずれも含まれていないためTX2はクライアントに送信されない。そのためクライアントは受け取ったお金が既に使わているのか知らない。

↑の2つ目のステップで発見したoutpointで自動的にBloom filterを更新することで、3つ目のステップのTX2をフィルタで一致し、ノードが1つ目のブロックと2つ目のブロックの処理をしている間に一時停止する時間がなくてもクライアントが関連するトランザクションを知ることができる。

フィルタのnFlagsフィールドは正確にノードの振る舞いの更新を制御するビットフィールドである。

BLOOM_UPDATE_NONE (0) はフィルタにマッチした際に、更新を適応しないことを意味する。
BLOOM_UPDATE_ALL (1)はフィルタがscriptPubKey内の任意のデータにマッチした際に、outpointをシリアライズしフィルタ内に挿入することを意味する。
BLOOM_UPDATE_P2PUBKEY_ONLY (2)はscriptPubKey内のデータ要素がマッチした場合のみoutpointがフィルタに挿入され、そのスクリプトは標準的なP2PKHかマルチシグの形式。

↑の区別は、偽陽性率の増加による急激な劣化を回避するのに有用。標準的な公開鍵への支払いのみ受信するウォレットであれば、フィルタの自動更新は必要無い（自身の出力のいずれかを使う任意のトランザクションは入力に予測可能なデータ要素をを保持しているため）。ウォレットがアドレスへの支払いを行う出力を受け取りP2PKHかマルチシグへの支払いの出力である場合、BLOOM_UPDATE_P2PUBKEY_ONLYが適切になる。それは明示的に鍵を指定する支払いへの正しい動作を保証しつつ、最も一般的な出力のためのフィルタの不要な拡大を回避する。

nFlags == 1またはnFlags == 2を指定した場合、チェーンをスキャンし続けるとフィルタの汚れが増えていくことを意味するため、クライアントは偽陽性率を監視し、定期的にフィルタをクリーンなものに更新する必要がある。

部分的なマークルブランチのフォーマット

マークルツリーはツリーのリーフノード*3としてアイテムのセットを配置する方法で、内部ノード*4はその子ノードのハッシュを連結したハッシュになる。ルートノードはマークルルートと呼ばれる。全てのBitcoinブロックにはブロックヘッダに、ブロックとトランザクションから形成されたツリーのマークルルートが含まれている。マークルブランチと呼ばれる内部ノードにいくつかの要素を提供することによって、オリジナルのブロックサイズよりもはるかに小さいデータで、あるトランザクションが実際にブロック内に存在していることを証明できる。

部分的なマークルツリーオブジェクトの構築手順

ルートからツリーを下に見ていき、検出した各ノードに対して、
- そのノードがリーフノード（トランザクション）に対応するノードかその親ノードかチェックする
  - そうである場合はフラグビットに”1”ビットを付加
  - それ以外は"0"ビットを付加
- そのノードが（非リーフな）内部ノードでリーフノードを含む親であるかチェックする。
  - そうであれば
    - そのノードの左の子ノードに降りて、深さ優先でそのサブツリーを処理する。
    - そのノードが右の子ノードを持つ場合はは同様に処理する。
  - そうでない場合はハッシュリストにこのノードのハッシュを付加する。

部分的なマークルツリーオブジェクトのパース手順

一部のブロックメッセージにいくつかのトランザクションが含まれているように、マークルツリーの形状も既知のものである。以下の方法でノードのハッシュを計算する。

まずフラグビットのリストからビットを読み
- ビットが0であったら
  - ハッシュリストからハッシュを読み、このノードのハッシュとして返す。
- ビットが1でリーフノードの場合は
  - ハッシュリストからハッシュを読み、マッチしたtxidとしてそれを保存しこのノードのハッシュとしてそれを返す。
- ビットが１で内部ノードの場合は
  - 左の子ツリーに降り、計算したハッシュをLとして保存する。
  - そのノードに右の子ツリーがある場合は
    - 右の子ツリーに降り、計算したハッシュをRとして保存する。
    - L == Rの場合、その部分的なマークルツリーオブジェクトは無効。
    - Hash(L || R)を返す。
  - 右の子ツリーが無い場合は、Hash(L || L)を返す。

部分的なマークルツリーオブジェクトは↓を満たした場合のみ有効である。

ハッシュリストの全てのハッシュが使用されている。
フラグビットリストの全てのフラグが使用されている。
計算したルートノードのハッシュがブロックヘッダのマークルルートと一致する。
ブロックヘッダが有効であり、Proof of workで獲得したものと一致する。
２つの子ノードにおいて、左と右のハッシュが同じ値では無いこと。

Bloom filterのフォーマット

Bloom filterはビットフィールドで、このビットはデータ要素を異なるハッシュ関数のセットに食わせることによって設定される。使用されるハッシュ関数の数は、フィルタのパラメータである。Bitcoinでは、Murmurハッシュ関数のバージョン３を使っている。異なるN個のハッシュ関数を取得するのには、単純に以下の式でMurmurアルゴリズムを初期化している。

nHashNum * 0xFBA4C795 + nTweak

フィルタが４つのハッシュ関数と0x00000005のtweak*5で初期化されている場合、２つ目の関数が必要とするh1は4221880218と等しい。

filterloadコマンドでフィルタをロードする際、２つのパラメータを選択することができる。１つはバイト単位のフィルタのサイズで、もう１つは使用するハッシュ関数の数。以下の式を使うことでパラメータを選択できる。

Nをセットに挿入したい要素の数とし、Pを偽陽性の確率（1.0だと全てにマッチし、ゼロだと何もマッチしない）とする。

フィルタのサイズSは

(-1 / pow(log(2), 2) * N * log(P)) / 8

の式で得られる。ただし最大サイズを越えないようにする必要がある。（filterloadの定義に記載している通りフィルタの最大サイズは36,000なので、フィルタに20,000個のアイテムがある場合は偽陽性率が0.1%未満、10,000アイテムの場合は0.0001%未満の偽陽性率となる。）

必要なハッシュ関数の数は↓で得られる。

S * 8 / N * log(2)

所感

SPVのクライアントを動作させるには別に専用のフルノードも必要なのか？とか思ってたけど、通常のフルノードと同様P2Pのノードとして動作しノード間のコネクションに対してBloom filterをセットして自分に必要なトランザクションの判定をしてると。
既にブロックに取り込まれているトランザクション情報の取得をするために、invメッセージをフェイクさせるのはちょっとトリッキーな感じ。
nFlagsの設定値の説明を見る限り、SPVでサポートしてるアドレスはP2PKHとマルチシグのみでP2SHはサポートされない？確かにウォレットでP2SHのredeem scriptが管理されない限りサポートできない気がする。
ざっくりとSPVノードがどういうふうにデータをピックアップしたのかは分かったけど、まだはっきり理解できてない部分もある。このへんはSPVノードを実際に実装してみると分かるのかなー。
Bitcoin Coreのgetblock RPCを実行するとブロックの情報として"merkleroot"の値が確認できる。

$ bitcoin-cli -testnet getblock 000000000073b2c49bc59e2406ef5a160333cc1a6331313ebb3f784364364781
{
    "hash" : "000000000073b2c49bc59e2406ef5a160333cc1a6331313ebb3f784364364781",
    "confirmations" : 1348,
    "size" : 77706,
    "height" : 683937,
    "version" : 4,
    "merkleroot" : "08cc4706f279e9485c112c43bb8d96d6afe47c117086a3db9dfdc458b3cebc80",
    "tx" : [
...

*1:データのハッシュ値のビット配列を食わせると各ビット値をORで比較して全ビット値が1であればそのデータを含む可能性があり１つでもビット値が異なるとそのデータを含まないことが証明される。データの有無を効率的に判断できるアルゴリズムでHBaseやCassandraなんかでも使われてる。Bloom filterの判定を0/1のビット判定でなくカウンタ形式に拡張したのがCounting Filterで、Bloom filterではデータの削除に対応できないけどCounting Filterではカウンタをデクリメントして削除に対応できる。

*2:invメッセージとは各ノードがデータを送信する前に、相手のノードがまだその情報を持っていないか確認するためのメッセージで、持っていない場合はその後getdataメッセージが送られデータ本体を送信する。

*3:子ノードを持たない末端のノード

*4:子要素を持つノード

*5:tweakは乱数

Develop with pleasure!

福岡でCloudとかBlockchainとか。