Develop with pleasure!

福岡でCloudとかBlockchainとか。

軽量クライアント向けのCompact Block Filterを定義したBIP-158

techmedia-think.hatenablog.com

で使用するフィルタの仕様を定義したのがBIP-158↓

https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki

おおまかな仕組みとしては、

BIP-37では軽量クライアント側が自身に関連する公開鍵ハッシュやOutPointなんかをフルノードとのフィルタにセットしていたが、BIP-157,158では逆にフルノード側がブロック内の全トランザクションの全OutPointscriptPubkey内の全データ要素(公開鍵ハッシュなど)を抽出し、それらをゴロム・ライス符号で圧縮してフィルタを生成している。BIP-37が各クライアント毎にフィルタは異なるのに対し、BIP-157,158ではブロック毎にフィルタの中身が決まり、ブロックがチェーンに追加されたタイミングで一度それを生成し保存しておくだけで良い。

BIP-158で定義されている2つのフィルタの構造についてBIPを見てみよう↓

概要

このBIPはBIP-157の軽量クライアントプロトコルで使われるブロックデータのコンパクトなフィルタの構造について説明する。BIP-37のBloom Filterの代替として提案されたフィルタ構成は、圧縮にゴロム・ライス符号を使用することでフィルタサイズを最小限に抑えるようになっている。このドキュメントでは基本的なウォレットとより高度なスマートコントラクトを持つアプリケーションを可能にする、この構成に基づく2つのフィルタの初期タイプについて定義する。

動機

BIP-157はブロックのコンテンツの決定性フィルタに基づいて軽量クライアントプロトコルを定義する。フィルタは軽量クライアントが消費すると予想される帯域幅を最小限に抑えて、フィルタとブロックをダウンロードするように設計されている。このドキュメントでは、基本および拡張用の2つの初期フィルタタイプを定義し、高度なアプリケーションをサポートし、基本的なウォレットのフィルタサイズを縮小する。

定義

[]byteはバイトベクトルを表す。

[N]byteは長さNの固定のバイト列を表す。

CompactSizeはBitcoinのP2Pプロトコルで使われる符号なし整数のコンパクトなエンコード

Data pushesはBitcoinのスクリプトルールに従ってスタックにプッシュされたバイトベクトル。

Bit streamsは個々のbitの読み書き可能なストリーム。このドキュメントの疑似コードでは以下の関数が使われている。

  • new_bit_stream 新しい書き込み可能なBit streamをインスタンス化する。
  • new_bit_stream(vector) vectorからデータを読み込んで新しいBit streamをインスタンス化する。
  • write_bit(stream, b) ストリームの最後にbit bを追加する。
  • read_bit(stream) ストリームから次の利用可能なbitを読み込む
  • write_bits_big_endian(stream, n, k) 整数nk個の最下位bitをビッグエンディアンの順でストリームの最後に追加する。
  • read_bits_big_endian(stream, k) ストリームから次に利用可能なkbitを読み込み、それらをビッグエンディアン整数の最下位bitとして解釈する。

仕様

Golomb-coded set

各ブロックについて、ブロックに関連する項目のセット(例えば送信先のアドレスや使用されたoutpointなど)を含むコンパクトフィルタが導出される。このようなデータオブジェクトのセットはGolomb-coded set (GCS)と呼ばれる確率構造に圧縮される。この確率構造はセット内のアイテムであれば確率1でマッチし、セット内にないアイテムがマッチする確率はある整数パラメータPに対して {2^{-P}}である。

高レベルなGCSはN個のアイテムのセットから次のように構築される。

  1. すべてのアイテムを0 〜 N * 2Pの範囲の64 bitの整数にハッシュする。
  2. ハッシュ値を辞書順にソートする。
  3. 各値についてその前の値との差を計算する。
  4. 差を順番に書き込み、ゴロム・ライス符号で圧縮する。

以下のセクションではこの各ステップについて詳しく説明する。

データオブジェクトのハッシュ化

フィルタ構築の最初のステップは、セット内の可変サイズのアイテムを[0, F)の範囲内でハッシュ化する(FはN * 2P)。ハッシュの出力に対するメンバーシップクエリを設定すると偽陽性率は {2^{-P}}になる。数の桁溢れを避けるため、アイテムの数Nは232より小さく、Pは32以下でなければならない。

アイテムはまず疑似乱数関数SipHashに渡される。疑似乱数関数SipHashは128-bitの鍵と可変サイズのバイト列を受け取り、均一にランダムな64-bitのアウトプットを生成する。このBIPの実装では、SipHashのパラメータはc = 2d = 4を使用しなければならない。

続いて64-bitのSipHashのアウトプットにFを掛けて、その結果の128-bitの上位64-bitを取ることで望ましい範囲にわたって一様にマッピングされる。このアルゴリズムは高価な除算演算を避けるため、モジュロ演算の削減に替わる高速なアルゴリズム*1。この削減を実装する際は、整数乗算の上位64-bitが切り捨てられないよう注意する必要がある。特定のアーキテクチャと高水準言語では、64-bitの乗算を4つの32-bitの乗算に分解し、その結果を再結合するコードが必要になる場合がある。

hash_to_range(item: []byte, F: uint64, k: [16]byte) -> uint64:
    return (siphash(k, item) * F) >> 64

hashed_set_construct(raw_items: [][]byte, P: uint, k: [16]byte) -> []uint64:
    let N = len(raw_items)
    let F = N << P

    let set_items = []

    for item in raw_items:
        let set_value = hash_to_range(item, F, k)
        set_items.append(set_value)

    return set_items
ゴロム・ライス符号

ハッシュされたセット内のアイテムを直接フィルタに書き込むのではなく、連続するアイテム間の差をソート順で書き込むことでより大きな圧縮効果がある。アイテムは一様に分布しているので、その差は幾何分布に似ていることが示されている*2。ゴロム・ライス符号*3は、幾何学的に分布した値を最適に圧縮する方法だ。

ゴロム・ライスでは、値は2Pを法とする商と剰余に分割され、別々にエンコードされる。商qは単身符号としてエンコードされ、qの文字列1つの後に0が1つ続く。余りrはP-bitのビッグエンディアンで表される。例えば以下はP=2を使った場合のゴロム・ライス符号だ。

n (q, r) c
0 (0, 0) 0 00
1 (0, 1) 0 01
2 (0, 2) 0 10
3 (0, 3) 0 11
4 (1, 0) 10 00
5 (1, 1) 10 01
6 (1, 2) 10 10
7 (1, 3) 10 11
8 (2, 0) 110 00
9 (2, 1) 110 01
golomb_encode(stream, x: uint64, P: uint):
    let q = x >> P

    while q > 0:
        write_bit(stream, 1)
        q--
    write_bit(stream, 0)

    write_bits_big_endian(stream, x, P)

golomb_decode(stream, P: uint) -> uint64:
    let q = 0
    while read_bit(stream) == 1:
        q++

    let r = read_bits_big_endian(stream, P)

    let x = (q << P) + r
    return x
セットの構成

GCSは以下の3つのパラメータから構成される。

  • L: N個の元のアイテムのベクトル
  • P: 偽陽性率を決定するパラメータ
  • k: SipHashのアウトプットをランダム化するのに使われる128-bitの鍵

結果はN * (P + 1)の最小サイズのバイト列である。

Lの元のアイテムは最初に上記で指定された64-bitの符号なし整数にハッシュされ、ソートされる。その連続した値間の差(以後deltasと記載する)はゴロム・ライス符号を使って順次bit streamにエンコードされる。最後にbit streamは最も近い境界バイトに0でパディングされアウトプットのバイト列にシリアライズされる。

construct_gcs(L: [][]byte, P: uint, k: [16]byte) -> []byte:
    let set_items = hashed_set_construct(L, P, k)

    set_items.sort()

    let output_stream = new_bit_stream()

    let last_value = 0
    for item in set_items:
        let delta = item - last_value
        golomb_encode(output_stream, delta, P)
        last_value = item

    return output_stream.bytes()
セットのクエリ/復元

圧縮されたGCS内にアイテムがあるかどうかメンバーシップを確認するには、エンコードされたdeltasからハッシュされたセットのメンバーを再構築する必要がある。これを行う手順は圧縮の逆で、deltasは1つずつデコードされ累積和に加算される。各中間和はオリジナルのセットのハッシュ値を表す。メンバーシップを照会されたアイテムはセット内のメンバーと同じ方法でハッシュされ、再構成された値と比較される。照会する際に圧縮解除されたセット全体をメモリ上に展開する必要はない。

gcs_match(key: [16]byte, compressed_set: []byte, target: []byte, P: uint, N: uint) -> bool:
    let F = N << P
    let target_hash = hash_to_range(target, F, k)

    stream = new_bit_stream(compressed_set)

    let last_value = 0

    loop N times:
        let delta = golomb_decode(stream, P)
        let set_item = last_value + delta

        if set_item == target_hash:
            return true

        // Since the values in the set are sorted, terminate the search once
        // the decoded value exceeds the target.
        if set_item > target_hash:
            break

        last_value = set_item

    return false

一部のアプリケーションでは単一のアイテムの照会でなく、あるセットが含まれているかのチェックが必要になるかもしれない。これには圧縮されたGCSのソート構造を利用することで、個々のアイテムを個別にチェックするよりはるかに効率的に実行できる。まず最初に照会するアイテムはすべてハッシュ及びソートされ、圧縮解除されたGCSのコンテンツと順次比較される。疑似コードについてはAppendix Bを参照。

ブロックフィルタ

このBIPでは2つの初期フィルタタイプを定義する。

  • Basic (0x00)
  • Extended (0x01)
コンテンツ

Basicフィルタは軽量クライアントが通常のBitcoinウォレットと同期するのに必要なものすべてを含むよう設計されている。Basicフィルタはブロック内の各トランザクション毎に以下のアイテムを正確に含まないといけない。

Extendedフィルタには、より高度なスマートコントラクトを持つアプリケーションを有効にするための追加データが含まれる。Extendedフィルタはコインベースを除くブロック内の各トランザクション毎に以下のアイテムを正確に含まないといけない。

  • 各インプットのwitness stack内の各アイテム(インプットがwitnessを持つ場合)
  • 各インプットのscriptSig内のデータプッシュ

どちらのフィルタタイプもP2SHスクリプト及びwitnessスクリプトを解釈して、そこからデータプッシュを抽出しないことに注意すること。必要に応じて今後のフィルタタイプがそれらを抽出するよう設計される可能性はある。

構成

BasicとExtendedフィルタタイプはどちらも以下のパラメータを持つゴロム・ライス符号のセットとして構成される。

パラメータPは必ず20に設定しなければならない。この値は、偽陽性のためダウンロードされる予想ブロック数とフィルタ自体のサイズの両方を考慮して、利用帯域幅を最小限に抑えるシミュレーションの結果選択された。このコードはパラメータ調整に使用されるデモと一緒にここにある。

パラメータkにはフィルタを構築するブロックのハッシュの先頭16バイトを設定しなければならない。これにより鍵に決定性がありながら、ブロックごとに変化することが保証される。

NはGCSをデコードするのに必要なので、シリアライズしたGCSの先頭に含める(CompactSizeで)。したがって完全にシリアライズしたフィルタは以下のようになる。

  • N: CompactSizeとしてエンコードされる
  • 圧縮されたフィルタ自体のバイト
シグナリング

このBIPは新しいservice bitsを割り当てる。

名称 service bit 内容
NODE_COMPACT_FILTERS 1 << 6 このservice bitsが有効なノードは、フィルタタイプ0x00および0x01についてBIP-157のすべてのメッセージに応答しなければならない。

互換性

このブロックフィルタの構成は、既存のソフトウェアと互換性は無く、新しいフィルタの実装が必要。

参照実装

Light client:https://github.com/lightninglabs/neutrino

Full-node indexing:https://github.com/Roasbeef/btcd/tree/segwit-cbf

Golomb-Rice Coded sets:https://github.com/Roasbeef/btcutil/tree/gcs/gcs

Appendix A: 代替案

ゴロム・ライスエンコードセットに決まるまでにはいくつかの代替セットエンコードが検討された。このAppendixのセクションでは、そのいくつかの選択肢と、選択しなかった根拠を列挙する。

Bloom filters

Bloom filtersはおそらくセットのメンバーシップをテストするための最もよく知られた確率的データ構造で、BIP-37でBitcoinに導入された。Bloom filterのサイズは同じ偽陽性率を持つGCSの予想サイズよりも大きく、これが採用しなかった理由だ。

暗号アキュムレータ

暗号アキュムレータ*4は、(他の操作の中で)一方向のメンバーシップテストを可能にする暗号データ構造だ。アキュムレータの1つのメリットは、アキュムレータに挿入されるデータの数に関係なく一定のサイズであることだ。しかし暗号アキュムレータの現在の構成では最初にtrusted setupが必要となる。さらに強RSA仮定に基づくアキュムレータはセットのアイテムを関連グループ内のプライムの代理人マッピングする必要がある。

行列ベースの確率的集合データ構造

Bloom filterに比べて空間的に効率が良いmatrix solverベースのデータ構造が存在する*5。たがGCSベースのフィルタは実装の複雑さがはるかに低く、分かりやすいためGCSベースのフィルタを選択した。

Appendix B:疑似コード

複数の要素にマッチするゴロム・ライスセット

gcs_match_any(key: [16]byte, compressed_set: []byte, targets: [][]byte, P: uint, N: uint) -> bool:
    let F = N << P

    // Map targets to the same range as the set hashes.
    let target_hashes = []
    for target in targets:
        let target_hash = hash_to_range(target, F, k)
        target_hashes.append(target_hash)

    // Sort targets so matching can be checked in linear time.
    target_hashes.sort()

    stream = new_bit_stream(compressed_set)

    let value = 0
    let target_idx = 0
    let target_val = target_hashes[target_idx]

    loop N times:
        let delta = golomb_decode(stream, P)
        value += delta

        inner loop:
            if target_val == value:
                return true

            // Move on to the next set value.
            else if target_val > value:
                break inner loop

            // Move on to the next target value.
            else if target_val < value:
                target_idx++

                // If there are no targets left, then there are no matches.
                if target_idx == len(targets):
                    break outer loop

                target_val = target_hashes[target_idx]

    return false

Appendix C:Test Vectors

まだ無い。

所感

  • P2SHやP2WSHのredeem scriptにプッシュされているアイテムはこのBIPのフィルタでは対象外なのはちょっと意外。
  • 偽陽性のパラメータはBIP-37は推奨値があるがBIP-158では固定されている(全チェーンで共通のフィルタになるので固定になるのはまぁ当然)。
  • ゴロム・ライス符号含めて理解するのには実装してみた方が早いかも。そのためにも検証用にTest Vectorsが欲しい。