#1.前提
ビットコインにおいて
SPVノードはブロックヘッダと自分に関係のあるノードの情報しかもたない。
そのため全てのブロックやトランザクションについて検証することができない
初期のSPVノードは全トランザクションをダウンロード後に自分に関係のないものを捨てていたので効率が悪かった。
→同期に時間がかるため
これを解決するためにダウンロードする時点で、自分に関係のあるトランザクションのみを入手するようなフィルターを
かけることにした。これがブルームフィルター
BTC以降の技術ではなく、1970年に Burton H. Bloom が考案したもの
#2.ブルームフィルタ
図1:ブルームフィルタを用いたブロックの受信
filterload:リモートノードとのコネクションにブルームフィルタをセットする
filteradd:データ要素を現在のブルームフィルタにセットする
filterclear:ブルームフィルタを除去する
フィルタリングはScript PubKeyやScriptSigにプッシュする個別の要素に対して行われる
<詳細>
データの有無を効率的に判断するアルゴリズム。
ブルームフィルタはn個のビット列とk個のハッシュ関数で構成される
ex:10このビット列,２個のハッシュ関数の場合
最初はこんなかんじー
図:2ブルームフィルタの初期状態
次に、要素Aを追加してみる
結果的に、出力された数字のビットを１に変換する(この場合は3と9)
図3:要素Aを追加したブルームフィルタ
同じように要素Bを追加する
図4:要素Bを追加したブルームフィルタ
このように、要素をハッシュにかけて出力された値をインデックスとしてビット列を走査し、そのビットの値全てが1であれば
要素が登録されている(可能性がある)と判断できる。
ん？？可能性がある？
そりゃそうだ。要素Aと同じ出力をもつ要素Cが存在する場合も考えられる
この場合は実際に登録されていないにも関わらずデータが含まれている(可能性がある)と判定するため偽陽性の誤検出の可能性がある。(可能性、可能性くどいので詳しくはgbec動画で)
ちなみに、ハッシュを通してフィルタをかけている以上、一度追加したデータの削除はできない。
<フィルタに用いるマッチングアルゴリズム>
自分に関係のあるトランザクションを検出するマッチングアルゴリズム。
5ステップの途中で一つでもマッチすれば、以降のアルゴリズムは無視される。
1.トランザクションのハッシュを計算し、テストする。
2.トランザクションの各アウトプットについてScriptPubkeyの各要素(ScriptPubKey全体ではなく、ScriptPubKey内のハッシュや鍵などの要素)
3.トランザクションの各インプットについて、シリアライズされたOutPointをテストする
4.トランザクションの各インプットについて、そのScriptSig内の各要素(ScriptSig内には基本的にデータしかない)をテストする
5.上記のいずれにも合致しない場合はマッチしないと判断する