Bitcoinの軽量クライアント向けに自身に関連するトランザクションを判別する仕組みとしては、Bloom Filterを利用するBIP-37がベースだが、軽量ノード側のプライバシーの改善とフルノードの負荷を軽減するためCompact Block Filterという新しい仕組みが提案されている↓
techmedia-think.hatenablog.com
Bitcoin Coreのmasterブランチにもマージされていたので、それをbitcoinrbにも移植してみた。
Compact Block Filterの仕組み
BIP-37のBloom Filterを利用したフィルタリングでは、各軽量クライアントがフルノードと接続する際に、クライアント毎にフィルタが作成されフルノードは接続されたクライアント毎に、トランザクションやブロックを伝播すべきかフィルタを通して検証していたが、Compact Block Filterは、各ブロック毎に生成されるようになる。そのため、そのブロックに自身に関連するトランザクションがあるかどうかは、各クライアントがブロック毎のフィルタをダウンロードし検証するようになり、フィルタを作成するエンティティとフィルタを使って検証するエンティティの関係が変わる。
フィルタの作成
Compact Block Filterでは上述の通り、ブロック毎にフィルタを作成する。BIP-158で定義されているフィルタタイプはBasic（フィルタタイプ=0x00）の１つのみで、このフィルタにはブロック内の以下のデータがセットされる。
なので、ブロック内の↑の全てのscriptPubkeyのペイロードをフィルタに登録する。
bitcoinrbではフィルタを作成する対象のブロックと、そのブロックの各インプットが参照するUTXOのscriptPubkeyのペイロードのセットを使って以下のようにフィルタを作成する。
# block はBitcoin::Block、prev_out_scriptsはUTXOのscriptPubkeyのバイナリの配列 block_filter = Bitcoin::BlockFilter.build_from_block(Bitcoin::BlockFilter::TYPE[:basic], block, prev_out_scripts)
実際に中身でやってることは、まず、blockとprev_out_scriptsから要素をピックアップする。
elements = [] block.transactions.each do |tx| elements += tx.outputs.select{|o|!o.script_pubkey.empty? && !o.script_pubkey.op_return?}.map{|o| o.script_pubkey.to_payload} end elements += prev_out_scripts.select{|s|!s.empty? && !s.op_return?}.map(&:to_payload) elements.uniq
OP_RETURN及び空のscriptPubkeyを除外し、重複するscriptPubkeyは除外する。
ここまでで要素の準備ができたので、続いて実際にフィルタを作成する。BIP-158ではBloom Filterに代わって、フィルタサイズを削減するためGolomb-coded set（GCS）が使われる。GCSの確率構造では、セット内に存在する要素を問い合わせた場合必ずマッチし、セット内に存在しない要素を問い合わせた場合にそれがマッチする確率は1/Mとなる。つまりBloom Filterと同様、偽陽性が存在する。この偽陽性率は整数のパラメータMで制御され、↑のBasicタイプのフィルタではM = 784931と設定されている。
↑のようにブロック内の要素をピックアップしたら、その要素を使って以下のステップでGCSを構成する。
1. 各要素をハッシュし整数にマッピングする
続いて各要素を、要素の数をN個とするとフィルタの偽陽性パラメータMと合わせた0〜N*Mの数値の範囲内にマッピングする。
まず最初に要素のバイナリのSipHash*1を使ってハッシュ値を計算する（使用するSipHashのパラメータはc = 2, d = 4）。BasicフィルタではSipHashの128 bitの鍵には、ブロックハッシュの先頭16バイトを使用する。これにより鍵はブロックごとに決定論的に導出され、かつブロック毎にランダムになる（先頭16バイトというのはビッグエンディアンでなので、リトルエンディアンとは違い0が続くのは先頭ではなく後方である）。
ruby ではsiphash gemを利用することで、SipHash-24のハッシュ値が得られる。
key = ブロックハッシュの先頭16バイト（バイナリ） element = フィルタに登録する要素のバイナリ hash = SipHash.digest(key, element)
SipHash#digestによりハッシュ値が整数で返ってくるので、この整数に F = M * N を乗算し、その上位64 bitを取得する。
(hash * f) >> 64
モジュロ演算は高価なので、結果がある範囲内に一様に分布しかつ高速に計算できるよう↑の計算が採用されている。
↑のように全要素を64 bitのハッシュ値に変換し、その結果を昇順にソートしたセットを用意する。
hashed_set = elements.map{|e| hash_to_range(e) }.sort
2. フィルタへの登録
↑までで、各要素をハッシュし、結果をソートした整数のセットが準備できた。
肝心なのはここからで、要素のハッシュをそのままフィルタに登録するととても巨大なフィルタになってしまうので、圧縮してフィルタに登録する。この時、圧縮に使われるのがゴロム・ライス符号だ。
現在、昇順にソートされた整数のセットを持っているので、この連続する整数の差分をフィルタに登録する。各整数値は↑の計算により一様に分布しているため、その差分は幾何分布に似るとされており、ゴロム・ライス符号はその幾何分布の値を最適に圧縮するための方法になる。ソートされた順番で連続する2つのアイテムの差分を算出し、その差分をゴロム・ライスでエンコードする（先頭の要素の差分は0との差）。ゴロム・ライス符号では、差分の値は2P*2を法とする商と剰余に分割され、別々にエンコードされ（商は単項としてエンコードされ、その後に１ bit0が続き、その後余りがP bitの値としてエンコードされる）、順次BitStreamに追記される。尚、値が幾何分布を形成するため、商は0もしくは１のケースが多い。
bit_writer = Bitcoin::BitStreamWriter.new last_value = 0 hashed_set.each do |v| delta = v - last_value # 連続する要素の差分がdelta golomb_rice_encode(bit_writer, p, delta) # deltaをゴロムライスでエンコード last_value = v end bit_writer.flush filter = bit_writer.stream ... def golomb_rice_encode(bit_writer, p, x) q = x >> p while q > 0 nbits = q <= 64 ? q : 64 bit_writer.write(-1, nbits) q -= nbits end bit_writer.write(0, 1) bit_writer.write(x, p) end
BitStreamは追記型のbit型のストリームで、指定bit分データをバッファに書き込み、書き込まれたデータが8 bitになったら、それをストリームに書き込むという、bit単位の書き込み/読み込みが可能なストリームである。 今回Rubyで実装したものが↓
https://github.com/chaintope/bitcoinrb/blob/master/lib/bitcoin/bit_stream.rb
※ Rubyの場合、整数は無限多倍長整数に自動拡張されていくので仕様でデータ長の制限がある場合は、そのデータ長に合うよう計算時に桁溢れの対応を逆に自前でする必要がある。
上記のように、ソート済みの要素のハッシュのセットの各差分を順次、ゴロム・ライス符号でエンコードしたデータをストリームに追記していく。全データ分エンコードしたら最後にBitStreamのバッファについて最も境界に近い値に0でパディングし、ストリームをビット列に変換する。こうやって出来たビット列の先頭に要素数をCompactSizeでエンコードしたデータを付加したデータがBasicタイプのフィルタデータになる。
フィルタの検索
↑でブロック毎のフィルタが作成され、ブロックチェーンとは別にこのフィルタデータがP2Pネットワークで配信されるので、軽量クライアントはそのフィルタをダウンロードし、自身に関連するトランザクションがそのブロックに含まれるか検証する必要がある。
クライアントはまずエンコードされたフィルタから、要素数とフィルタのペイロードをロードする。
n, payload = Bitcoin.unpack_var_int(エンコードされたフィルタのバイナリデータ) bit_reader = Bitcoin::BitStreamReader.new(payload)
nがフィルタに登録されている要素の数。
続いて、フィルタに検索をかけるデータを用意する。これは自身が持つUTXOのscriptPubkeyなどで、フィルタに登録した時と同様、SipHashを使って整数値に変換し、要素が複数ある場合は昇順にソートしておく。
あとは要素の数分n回、ゴロム・ライス符号でエンコードされたデータをデコードし、その差分を加算していき、検索対象のデータと一致するか順番に検証していく。一つでも一致するデータがあれば偽陽性率Mの下で、フィルタに合致するデータが存在したことになる。
hashes = 昇順にソートした要素の整数値の配列 size = hashes.size value = 0 hashes_index = 0 n.times do delta = golomb_rice_decode(bit_reader, p) value += delta loop do return false if hashes_index == size return true if hashes[hashes_index] == value break if hashes[hashes_index] > value hashes_index += 1 end end return false ... def golomb_rice_decode(bit_reader, p) q = 0 while bit_reader.read(1) == 1 q +=1 end r = bit_reader.read(p) (q << p) + r end
bitcoinrbでは、GCSFilter#match?,match_any?でそれぞれ上記の検索をしている。
フィルタに合致した場合、そのブロック内に自身に関係するトランザクションがある可能性が高いので、軽量クライアントは別途そのブロックをダウンロードし、対象のトランザクションを特定する必要がある。BIP-37のBloom Filterを利用した既存のフィルタではmerkeleblockメッセージの他txメッセージで関連するトランザクション情報をフルノードが送ってくれるが、BIP-157,158のCompact Block Filterでは軽量クライアントがフルブロックデータをダウンロードする必要がある。このため、BIP-37のプライバシーの課題は解消されるが、使用する帯域幅は増加するため、ビッグブロックを掲げるチェーンでは採用し辛いだろう。
Rubyでの実装
ほぼ↑で説明したけど、Bitcoin Coreから移植したRuby実装は主に以下のコンポーネントになる。
テストは
