Develop with pleasure!

福岡でCloudとかBlockchainとか。

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

Bitcoin BIP

techmedia-think.hatenablog.com

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

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

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

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

BIP-158で定義されている２つのフィルタの構造について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) 整数nのk個の最下位bitをビッグエンディアンの順でストリームの最後に追加する。
  • read_bits_big_endian(stream, k) ストリームから次に利用可能なkbitを読み込み、それらをビッグエンディアン整数の最下位bitとして解釈する。

仕様

Golomb-coded set

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

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

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

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

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

フィルタ構築の最初のステップは、セット内の可変サイズのアイテムを[0, F)の範囲内でハッシュ化する（ここでFはF = N * M）。通常Mは2Pに設定される。しかし両方のパラメータを個別に選択できる場合は、より最適な値を選択することができる。ハッシュの出力に対するメンバーシップクエリを設定すると偽陽性率はMになる。数の桁溢れを避けるため、アイテムの数Nは232未満、Mは232未満でなければならない。

アイテムはまず疑似乱数関数SipHashに渡される。疑似乱数関数SipHashは128-bitの鍵と可変サイズのバイト列を受け取り、均一にランダムな64-bitのアウトプットを生成する。このBIPの実装では、SipHashのパラメータはc = 2とd = 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, k: [16]byte, M: uint) -> []uint64:
    let N = len(raw_items)
    let F = N * M

    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は以下の４つのパラメータから構成される。

  • L: N個の元のアイテムのベクトル
  • P: ゴロム・ライス符号のbitパラメータ
  • M: ターゲット偽陽性率
  • 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, M: uint) -> []byte:
    let set_items = hashed_set_construct(L, k, M)

    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は１つずつデコードされ累積和に加算される。各中間和はオリジナルのセットのハッシュ値を表す。メンバーシップを照会されたアイテムはセット内のメンバーと同じ方法でハッシュされ、再構成された値と比較される。照会する際に圧縮解除されたセット全体をメモリ上に展開する必要はない。

gcs_match(key: [16]byte, compressed_set: []byte, target: []byte, P: uint, N: uint, M: uint) -> bool:
    let F = N * M
    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では１つの初期フィルタタイプを定義する。

  • Basic (0x00)
    • M = 784931
    • P = 19
コンテンツ

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

nil項目はフィルタ要素の最終セットに含まれてはならない。

我々は将来ソフトフォークを介して、フィルタを容易にコミットできるよう全てのOP_RETRUNアウトプットを除外する。現在のwitness commitmentと同様、将来のコミットメントの領域になる可能性があるのが、コインベーストランザクションの追加のOP_RETURNアウトプットだ。全てのOP_RETURNアウトプットを除外することで、コミットメントとコミットされるアイテムの循環依存性を回避する。

構成

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

パラメータPは必ず19に設定し、パラメータMは784931に設定しなければならない。PとMを個別に設定できる場合、>M=1.497137 * 2Pと設定することが最適に近いことが分析で分かった。

実証分析によると、これらのパラメータは偽陽性によりダウンロードされる予想ブロック数とフィルタ自体のサイズの両方を考慮し、使用帯域幅を最小に抑えるために選択されている。

パラメータ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は、（他の操作の中で）一方向のメンバーシップテストを可能にする暗号データ構造だ。アキュムレータの１つのメリットは、アキュムレータに挿入されるデータの数に関係なく一定のサイズであることだ。しかし暗号アキュムレータの現在の構成では最初に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, M: uint) -> bool:
    let F = N * M

    // 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

P値が１９の５つのテストブロックのTest Vectorがここに公開されている。１〜３２のPの値についてこれらのTest Vectorを生成するコードはこちら。

所感

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

*1: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/

*2:https://en.wikipedia.org/wiki/Geometric_distribution

*3:https://en.wikipedia.org/wiki/Golomb_coding#Rice_coding

*4:https://en.wikipedia.org/wiki/Accumulator_(cryptography)

*5:https://arxiv.org/pdf/0804.1845.pdf