Develop with pleasure!

福岡でCloudとかBlockchainとか。

マルチパーティ間のスクリプトのプライバシーを向上させるTaprootというコンセプト

先日、bitcoin-dev MLにGregory MaxwellがポストしていたTaprootというコンセプトが興味深かったので見てみる↓

[bitcoin-dev] Taproot: Privacy preserving switchable scripting

まだBitcoinにはデプロイされていないが、MASTというscriptPubkeyをマークル化するアプローチが提案されている↓

techmedia-think.hatenablog.com

techmedia-think.hatenablog.com

複数の条件でコインをアンロックできるscriptPubkeyがある場合(例えば、2-of-2の署名があればアンロックできる or 24時間経過したら1人の署名でアンロックできるなど)、通常のP2SHでは元の条件を全て含むredeem scriptを公開してどちらかの条件でアンロックする必要があるが、↑のMASTを利用すると実際にアンロックに使用する条件のみを公開するだけで良い。使用しない条件を公開する必要がないためプライバシーが少し向上し、ブロックチェーン上に記録される容量も削減できる。

ただ、MASTを使用してアンロックしていること自体は分かるので、公開されるのはアンロックに使用した条件のみだが、他に何らかの条件が存在したことは知られてしまう。

これを改善するのに、複数の条件が無い場合にもダミーのハッシュなんかを用意してMASTを構成するスクリプトを作り、別の条件があるかのように偽装するという方法も考えられる。ただこの場合ネックになるのが、複数の条件を必要としないケースに比べて32バイトほど余計にトランザクションスペースを消費する点だ。この余分な32バイトを使ってもプライバシーを考慮すべきかというトレードオフが発生する。

マルチシグ or 他の条件がアンロック条件となるスクリプトに対して、このトレードオフを発生することなくプライバシーの向上と容量のセーブの両方を実現するのがTaprootのコンセプトだ。

アリス(公開鍵A)とボブ(公開鍵B)がいて、以下のいずれかの条件でアンロック可能なコインがあるとする。

  • AとBに対応するアリスとボブそれぞれの秘密鍵による署名でアンロック可能
  • CSVでタイムロックされた時間を経過したらボブの秘密鍵による署名でアンロック可能

普通にscriptPubkeyを書くと以下のようなスクリプトになる。

OP_IF
  2 <A> <B> 2 OP_CHECKMULTISIG
OP_ELSE
  <ロック時間> OP_CSV OP_DROP <B> OP_CHECKSIG
OP_END
TaprootのscriptPubkey

Taprootのコンセプトでは、これを以下のようにしてある1つの公開鍵への支払いにする。
※ 前提としてSchnorrの集約特性を必要とする。

  1. まずAとBのマルチシグの部分について、AとBの公開鍵を集約した集約鍵C = A + Bを作る。(rogue key攻撃の懸念がある場合はMuSig*1を利用して集約鍵を作る。)
  2. タイムロックスクリプトS = <timeout> OP_CSV OP_DROP B OP_CHECKSIGVERIFYとする。
  3. CSから楕円曲線上の点P = C + H(C || S)Gを計算する。
    H()ハッシュ関数で、G楕円曲線のジェネレータ)
  4. scriptPubkey [Taprootのバージョン] [楕円曲線上の点P]宛てに支払いをする。
    (segwitのscriptPubkey [witness version] [witness program]みたいなイメージだと思う)

このscriptPubkeyにロックされた資金をアンロックする方法は当然2つあり、それぞれ以下のようにアンロックする。

アリスとボブのマルチシグを使ってアンロックする方法

P楕円曲線上の点=公開鍵で、この点はアリスとボブの公開鍵を集約して作った点CとH(C||S)をシークレットとして生成した点を加算した点なので、アリスとボブの秘密鍵にH(C||S)を加算して、Pに対して有効な署名を作成することができる。

タイムロックの条件を使ってアンロックする方法

マルチシグ以外でアンロックできる条件がもう1つのタイムロックされている条件で、この条件を使用するのに以下のような新しいコンセンサスルールを導入する。

Pを構成するアリスとボブの集約鍵Cともう1つの条件のスクリプトSを提供し、C + H(C||S) = Pが成立する場合、Sスクリプトのタイムロックの条件をクリアし、ボブの秘密鍵による署名があればコインをアンロックできるというものだ。

どちらの方法でアンロックするかの判定はwitness stackのアイテムの数で判断するのかな?

まとめ

Taprootでは、所謂マルチシグのアンロック条件とそれ以外のアンロック条件を持つスクリプトを組み合わせて1つの公開鍵にする。マルチシグの場合はマルチシグの参加者の署名があればその公開鍵に対する有効な署名を作ることができアンロックできる。もう1つのスクリプトの条件を使ってアンロックする場合は、マルチシグを構成する際の集約鍵とその元の条件のスクリプトを公開することで、スクリプトの条件を使ったアンロックを可能にする。

↑はアリスとボブのだったけど何人でも動作原理は同じで、Sにも任意のスクリプトをセット可能だ。

最初に説明したようにMASTのプライバシーをさらに向上させるのに、複数の条件がない場合でも条件があるように見せるようMASTを構成すると無駄なデータサイズが発生するが、Taprootの場合はロックに使用するのは公開鍵Pだけあれば良いのでこの問題が解消できる。

条件が課されたコントラクトを含むロックスクリプトを、オーバーヘッドの無い単純な公開鍵として表現するアイディアがおもしろいなー。

Schnorrベースのマルチシグネチャスキーム「MuSig」

先日、Gregory MaxwellとAndrew Poelstra、Yannick SeurinとPieter Wuilleらによって、Schnorr署名を使ったマルチシグスキームのホワイトペーパーが発表された↓

https://eprint.iacr.org/2018/068.pdf

これに関する記事をPeiter WuilleがBlockstreamのブログにポストしていたので↓

blockstream.com

まずは↑読んで理解した範囲でMuSigについて書いてみる↓

既存のマルチシグ

Bitcoinにおけるマルチシグはよくm-of-nのように記載されn個の公開鍵の内m個の公開鍵に対応する秘密鍵で署名された署名データがあればコインのロックを解除できるといったもので、以下のようなscriptPubkeyと、アンロックする際のscriptSigが用いられる。

scriptPubkey

2-of-3のマルチシグのscriptPubkey↓

2 <公開鍵1> <公開鍵2> <公開鍵3> 3 OP_CHECKMULTISIG
scriptSig

↑の2-of-3のscriptPubkeyにロックされたコインを使用する際に必要なscriptSig

0 <公開鍵1の秘密鍵による署名> <公開鍵3の秘密鍵による署名>

トランザクションにはn個分の公開鍵と、m個分の署名データが含まれm-of-nの個数が増えるほどこのデータサイズも増えることになる。

鍵と署名の集約

既存のマルチシグは署名にECDSAを採用しているが、MuSigではこの部分をSchnorr署名をベースにした仕組みでサイズの削減とプライバシーを向上させようとしている。MuSigは鍵の集約をサポートする新しいマルチシグの方式で、マルチシグを構成する複数の公開鍵を1つの鍵に集約することができる。既存のマルチシグのscriptPubkeyは複数の公開鍵への支払いとみなすことができるのに対し、MuSigでは集約された公開鍵への支払いとみなすことができる。署名検証時も集約された鍵があれば良いので、個々の公開鍵の値が何なのか検証者に知られることはなく、サイズの削減とプライバシーの向上が見込める。

マルチシグの仕組みをMuSigにすることで、

  • トランザクションの各インプットに複数セットしていた署名の数を1つに減らせる
  • すべての公開鍵を含むスクリプトを1つの集約された公開鍵に減らせる

といった既存のマルチシグへのメリットが考えられる。

またそれ以上に複数のインプットを持つトランザクションの署名を1つに集約するということも可能になる。前者のマルチシグが複数の署名者が同じメッセージ(sighash)に対して署名するのに対し、後者の場合は各署名者は異なるメッセージ(インプット毎にsighashは異なる)に署名することになる。

具体的にどういう署名方式なのか見てみよう。

表記

  •  {x,x_1,x_2,...}を公開鍵 {X,X_1,X_2,...}に対応する秘密鍵とする(ジェネレータGと合わせ、 {X_i = x_{i}G})。
  • 署名されているメッセージはm
  • H()は暗号学的ハッシュ関数

Schnorr署名

Schnorr署名の式は以下のように定義されている。

  • 署名は {(R, s) = (rG, r + H(X, R, m)x)}。rは署名者が選択したランダムなナンス。
  • 検証は {sG = R + H(X, R, m)X}が成立するか。

構成要素はECDSAよりシンプルだ。

※ 他のサイトのSchnorrの式みると {H(R, m)}でXが含まれてないんだけど、どういう違いから来てるのか? Xがあると(R, s)から公開鍵を復元することもできない気がする。

Schnorrベースのマルチシグ

Schnorrベースのマルチシグの署名と検証は以下のように行う。

  • Xを各署名者が持つ公開鍵=点 {X_i}の合計とする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを点 {R_i}の合計とする。
  • 各署名者は {s_i = r_i + H(X, R, m)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(X, R, m)X}が成立するか確認する。ここでXは個々の公開鍵の合計。

署名 {(R, s)}及び検証式 {sG = R + H(X, R, m)X}が↑のSchnorr署名の式を満たす形でマルチシグを構成しているのが分かる。

各署名者がの秘密鍵とナンスから {s_i}を加算して求めた点と、各署名者の公開鍵と {R_i}を加算して出来た点の検証になってるので、楕円曲線の準同型性を利用した仕組みみたいだなー。

rogue-key攻撃の問題

↑のSchnorrベースのマルチシグで問題になるのがrogue-key攻撃。例えばアリス(公開鍵 {X_A})とボブ(公開鍵 {X_B})がマルチシグを構成する場合、お互いに公開鍵を教える必要がある。例えばアリスが公開鍵を教えた後に、ボブがアリスの公開鍵を使って {X'_B = X_B - X_A}を計算して、 {X_B^{'}}を自分の公開鍵として教えることが考えられる。この場合鍵を集約すると {X_A + X'B = X_A + X_B - X_A = X_B}となり、ボブの公開鍵 {X_B}秘密鍵だけで署名ができてしまう。

この問題を回避する方法の1つは、アリスとボブの公開鍵に加えて、それぞれがその公開鍵に対応する秘密鍵を本当に所有しているという証明を最初にするというもの。ボブは {X'_B}秘密鍵を持っていないので証明できず不正を働けない。ただ必ずそういった証明を事前に行えるという保証をプロトコルレベルで保証するものではないので、こういった攻撃ができない仕組みが求められる。

Bellare-Nevenのマルチシグネチャ方式

rogue-key攻撃に対して安全なのがBellare-Nevenのマルチシグネチャで、以下の手順で署名の作成と検証を行う。

  •  {L = H(X_1,X_2,...)}とする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを {R_i}ポイントの合計とする。
  • 各署名者は {s_i = r_i + H(L, X_i, R, m)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(L, X_1, R, m)X_1 +H(L, X_2, R, m)X_2 + ... }が成立するか確認する。

さらに、各署名者は {R_i}を公開する前に、 {H(R_i)}を公開する事前のコミットメントラウンドを設けるケースもある。

検証式を見れば明らかだが、この方式だと↑の通常のSchnorrの式を満たさない。署名の {s_i}を計算する際に、公開鍵に乗算する {H(L, X_i, R, m)}に各公開鍵が含まれており、 {x_i}に乗算する値が署名毎に異なるため、 {sG = R + H(X, R, m)X}のような集約はできない。確かにrogue-key攻撃を防ぐことはできるが、反面、検証には各公開鍵が必要となり、鍵の集約特性が失われてしまう。

MuSig

rogue-key攻撃に対して安全でありつつ、鍵の集約特性を備えたマルチシグネチャ方式が、今回提案されたMuSigで、以下の手順で署名の作成と検証を行う。

  •  {L = H(X_1,X_2,...)}とする。
  •  {H(L, X_i)X_i}の合計をXとする。
  • 各署名者はランダムなナンス {r_i}を選択し、他の署名者と {R_i = r_{i}G}を共有する。
  • Rを {R_i}ポイントの合計とする。
  • 各署名者は {s_i = r_i + H(X, R, m)H(L, X_i)x_i}を計算する。
  • 最終的な署名データは(R, s)で、sは {s_i}の値の合計。
  • 検証は {sG = R + H(X, R, m)X}が成立するか確認する。

ポイントはSchnorrベースのマルチシグのXを、単純な各公開鍵の和でなく、全公開鍵をハッシュした要素に公開鍵を乗算した和にしている点だ。

BNと異なるのは、各署名作成時に署名毎に異なるハッシュ値 {H(L, X_i)}を持つものの、それに対応する点 {H(L, X_i)X_i}を加算してXを作り共有することで、鍵の集約を可能にしている。署名 {(R, s)}及び検証式 {sG = R + H(X, R, m)X}が標準のSchnorrの式と同じになりっており、集約特性があることが分かる。

また各 {s_i}の計算時に署名毎に異なる {H(L, X_i)}秘密鍵 {x_i}に掛けているため、標準的なSchnorrベースのマルチシグに比べてrogue-key攻撃への耐性がある。

というのがMuSigの仕組みみたい。

↑の式だと1つのメッセージへの多重署名なのでマルチシグの置き換えは可能だけど、トランザクションの署名を1つに集約する場合、メッセージはインプット毎に異なるため、 {H(X, R, m)}のmは署名毎に変わるからmを {H(L, X_i, m)}側に移動するのかな?この辺はホワイトペーパー見てみないと分からない。

これがどういう形でBitcoinに適用されるかは、多分またBIPとして出てくるだろう。

軽量クライアント向けの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が欲しい。

クライアントサイドでブロックのフィルタリングを行う軽量クライアント向けのプロトコル BIP-157

現在のSPVノードの実装は接続先のフルノードとのコネクションにBloom Filterをセットして自身に関連するトランザクションをフィルタリングするBIP-37↓の仕様をベースにしている。

techmedia-think.hatenablog.com

このプロトコルでは、フィルタがフルノード側に送られフルノードがそのフィルタを使ってSPVに関連するトランザクションをフィルタリングし、関連するトランザクションがあればSPVノードにmerkleblockメッセージと共に送信する仕組みになっている。このプロトコルには主に以下の2つの課題がある。

  • プライバシーの問題
    全データをダウンロードするフルノードと違い、フィルタにマッチしたデータを受け取るので、フルノードに自身が管理しているアドレスや残高が分かってしまうというプライバシーの問題がある。フィルタに自身と関係のない条件を加えることで正確な情報をぼかすことはできるが、依然として課題は残る。
  • 悪意あるノードによるデータの省略
    フィルタにマッチしたデータについてはフルノードから通知されるが、悪意あるフルノードは合致するデータがあっても通知しない可能性がある。このため軽量クライアントでは信頼できるフルノードとの接続が必要で、常時複数のノードと接続し漏れがないか検証する必要がある。

これらの課題はいずれもフィルタリング処理を接続先のフルノードに依存しているために発生する。これをクライアントサイド側で行うことでこの課題を解決しようというのが↓のBIP-157の提案。

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

正確には↑のBIPにはブロックをフィルタリングする流れと、それを実現する新しいP2Pメッセージが定義されており、フィルタ生成の仕様は別のBIP-158に定義されている。

今回は前者のBIP-157の内容について見てみる。

概要

このBIPでは、現在利用可能なオプションを改善するBitcoinの軽量クライアントプロトコルについて説明する。現在使用されているBIP-37で定義された標準の軽量クライアントのプロトコルは、クライアントのセキュリティを弱め、フルノードによるDoS攻撃を可能にする欠陥がある。新しいプロトコルでは、軽量クライアントがフルノードからブロックのコンテンツの確率的なフィルタを取得し、フィルタに関連するデータがマッチする場合にブロックをダウンロードできるようにすることでこの問題を解決する。

新しいP2Pメッセージは、信頼できるソース(フルノード)に頼ることなく、軽量クライアントがブロックチェーンを安全に同期できるようにする。このBIPは、前のブロックのすべてのフィルタへのコミットメントとして機能し、無効なフィルタを提供している悪意あるピアもしくは障害のあるピアを効率的に検出するフィルタヘッダを定義する。結果、プロトコルは、少なくとも1つの正直なピアと接続された軽量クライアントが正しいブロックフィルタを識別できることを保証する。

動機

Bitcoinの軽量クライアントを使用すると、すべてのデータをダウンロードして検証することなく、ブロックチェーンから自分に関連するトランザクションを読み取ることができる。このようなアプリケーションは同時に、ピアへの信頼や帯域幅、ストレージ容量および計算量を最小化しようとする。軽量クライアントはすべてのブロックヘッダをダウンロードし、Proof of Workを検証し、一番長いProof of Workのチェーンを選択することでこれらを実現している。ブロックヘッダは80バイト固定で、平均10分毎に生成されるので、ブロックヘッダの同期に必要な帯域幅は最小限に抑えられる。その後軽量クライアントは、自身に関連するブロックチェーンデータのみをピアから直接ダウンロードし、それがヘッダーチェーンに包含されているか検証する。軽量クライアントは一番長いProof of Workのチェーンのすべてのブロックの有効性はチェックせず、セキュリティためのマイナーのインセンティブに頼っている。

BIP-37は現在Bitcoinで最も広く活用されている軽量クライアントの実行モードだ。BIP-37では、クライアントが監視したいBloom Filterをフルノードのピアに送信し、フィルタにマッチするトランザクションおよびブロック毎に通知を受け取る。クライアントは続いて、ピアに自身に関連するトランザクションとそのトランザクションがブロックに含まれていることのマークルプルーフ(これを使ってブロックヘッダに対して検証を行う)を要求する。Bloom Filterはクライアントのアドレスや未使用のアウトプットなどのデータとマッチする。偽陽性率とリモートピアへリークされる情報とのバランスを取るため、フィルタサイズは慎重に調整する必要がある。しかし利用可能なほとんどの実装では、ウォレットやその他のアプリケーションで実質的にプライバシーは0となっていることが示されている*1。さらに軽量クライアントに対して悪意あるフルノードは検出のリスクが殆ど無くクリティカルなデータを省略することができる。これは特定のオンチェーンイベントに応答する必要のあるアプリケーション(Lightning Networkクライアントなど)では受け入れられない。最後にBIP-37の軽量クライアントにサービスを提供する正直なノードは、悪意を持って作成されたBloom FilterによりI/OやCPUリソースを大量に消費し、DoS攻撃を発生させ、ノード運用者にこのプロトコルをサポートしないようすることが考えられる*2

このドキュメントに記述されている代替案はBIP-37の反対のアプローチとしてみることができる。クライアントがフルノードのピアにフィルタを送るのではなく、フルノードがクライアントに提供されるブロックデータに対して決定性フィルタを生成する。軽量クライアントは自身が監視しているデータとフィルタがマッチする場合、ブロック全体をダウンロードすることができる。フィルタは決定性なので、新しいブロックがチェーンに追加された際に一度だけ作成しディスクに格納すればいい。これによりフィルタ処理に必要な計算が最小限に抑えられ、BIP-37に対応するフルノードを脆弱にするI/Oの問題が排除される。クライアントは、フィルタリングされたブロックの完全性を検証するよりも簡単にピアから受信したフィルタの有効性を検証できるので、関連するすべてのトランザクションをより確実に確認することができる。最後にブロックはどのソース(フルノード)からでもダウンロードできるので、どのピアもクライアントが必要とする情報を得ることができずクライアントのプライバシーが向上する。極めてプライバシーが配慮された軽量クライアントでは、プライバシーを考慮した情報探索*3のような高度な技術を駆使してブロックを匿名でフェッチすることも選択可能だ。

定義

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

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

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

double-SHA256double-SHA256(x) = SHA256(SHA256(x))というSHA256の2回の呼び出しで定義されるハッシュ関数

仕様

フィルタタイプ

将来の拡張性とフィルタサイズ削減のため、どのデータがブロックフィルタに含まれているか決定するのとフィルタの構築/クエリの方法を定義する複数のフィルタタイプがある。このモデルでは、フルノードはサポートされるフィルタタイプ毎に1ブロックあたり1つのフィルタを生成する。

各タイプは1バイトのコードで識別され、フィルタのコンテンツとシリアライゼーションフォーマットを指定する。フルノードはservice bitsを使って特定のフィルタタイプのサポートを通知しても良い。初期のフィルタタイプはBIP-158で別々に定義され、1つのservice bitがそれらのシグナルサポートに割り当てられる。

フィルタヘッダ

この提案は、Bitcoinノードがブロックを同期するのに使用するヘッダファースト*4の仕組みからインスプレーションが浮かんだ。ブロックヘッダがブロック内のすべてのトランザクションに対するマークルコミットメントを持つのと同様に、ブロックフィルタへのコミットメントを持つフィルタヘッダを定義する。またブロックヘッダのようにフィルタヘッダは前のフィルタヘッダへのコミットメントを持つ。軽量クライアントはフィルタヘッダ自体をダウンロードする前に、現在のブロックチェーンのすべてのフィルタヘッダをダウンロードし、それを使ってフィルタの信頼性を検証する。複数のピア間でフィルタヘッダチェーンが異なる場合、クライアントはそれらが分岐するポイントを特定し、どちらのピアに欠陥があるか識別することができる。

ブロックフィルタの正規のハッシュは、シリアライズしたフィルタのdouble-SHA256で、フィルタヘッダはブロックフィルタ毎に導出される32バイトのハッシュだ。それらはフィルタハッシュと連結された前のフィルタヘッダのdouble-SHA256として計算されるジェネシスブロックの場合、計算に使用する前のフィルタヘッダは32バイトの0の配列となる。

新しいメッセージ

getcfilters

getcfiltersは特定の範囲のブロックに対して、特定のタイプのコンパクトフィルタを要求するのに使われる。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 ヘッダを要求するフィルタタイプ
StartHeight uint32 4 要求する範囲の最初のブロック高
StopHash [32]byte 32 要求する範囲の最後のブロックハッシュ
  1. ノードは接続先のピアがこのフィルタタイプをサポートするシグナルと出していない場合、getcfiltersを送信しない方が良い。サポートしていないフィルタタイプのgetcfiltersを受信した場合、ノードは応答を返さないほうが良い。
  2. StopHashは受信ピアによって受け入れられたブロックに入っているものでなければならない。これはピアが以前に、そのブロックもしくはその子孫が含まれるheadersもしくはinvメッセージを送信していた場合だ。不明なStopHashがセットされたgetcfiltersを受信したノードは応答しなくても良い。
  3. StopHashのブロック高はStartHeight以上でなければならず、またその差は厳密に1000未満でなければならない。
  4. メッセージを受信したノードは要求された範囲内の各ブロックについてブロック高順に1つのcfilterメッセージで応答しなければならない。
cfilter

cfiltergetcfiltersへの応答として送信されるメッセージで、要求された範囲内の各ブロックについて1つずつ送信される。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 返されるフィルタタイプのバイト識別子
BlockHash [32]byte 32 フィルタが返すBitcoinのブロックのブロックハッシュ
NumFilterBytes CompactSize 1-5 次のフィールドのフィルタのサイズを表す可変長整数
FilterBytes []byte NumFilterBytes このブロックのシリアライズされたコンパクトフィルタ
  1. FilterTypeはgetcfiltersで要求されたフィールドと一致する必要があり、BlockHashはStartHeight以上の高さを持ちStopHashの祖先のブロックでなければならない。
getcfheaders

getcfheadersはある範囲内のブロックに対して検証可能なフィルタヘッダを要求する際に使われる。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 ヘッダを要求するフィルタタイプ
StartHeight uint32 4 要求する範囲の最初のブロック高
StopHash [32]byte 32 要求する範囲の最後のブロックハッシュ
  1. ノードは接続先のピアがこのフィルタタイプをサポートするシグナルと出していない場合、getcfheadersを送信しない方が良い。サポートしていないフィルタタイプのgetcfheadersを受信した場合、ノードは応答を返さないほうが良い。
  2. StopHashは受信ピアによって受け入れられたブロックに入っているものでなければならない。これはピアが以前に、そのブロックもしくはその子孫が含まれるheadersもしくはinvメッセージを送信していた場合だ。不明なStopHashがセットされたgetcfheadersを受信したノードは応答しなくても良い。
  3. StopHashのブロック高はStartHeight以上でなければならず、またその差は厳密に2000未満でなければならない。
cfheaders

cfheadersgetcfheadersへの応答として送信されるメッセージで、複数のフィルタヘッダを含めるのではなく、レスポンスには1つのフィルタヘッダと後続のフィルタハッシュが含まれ、そこからヘッダを導出する。これはクライアントがヘッダ間のバインディングリンクを検証できるというメリットがある。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 ハッシュを要求するフィルタタイプ
StopHash [32]byte 32 要求された範囲の最後のブロックのハッシュ
PreviousFilterHeader [32]byte 32 要求された範囲の最初のブロックの前のフィルタヘッダ
FilterHashesLength CompactSize 1-3 次のフィールドのフィルタハッシュのvectorの長さ
FilterHashes [][32]byte FilterHashesLength * 32 要求された範囲内の各ブロックのフィルタハッシュ
  1. FilterTypeとStopHashはgetcfheadersのリクエストと一致する必要がある。
  2. FilterHashesLengthは2000より大きくてはならない。
  3. FilterHashesはStartHeightのブロック高から始まり、StopHashで終了するチェーンの各ブロック毎に1つのエントリーを持たなくてはならない。このエントリーは要求された範囲内のブロック毎の指定されたタイプのフィルタハッシュで、ブロック高の昇順でなければならない。
  4. PreviousFilterHeaderには要求された範囲内の最初のブロックの1つ前のフィルタヘッダをセットしなければならない。
getcfcheckpts

getcfcheckptsはブロックのある範囲に渡って均等に間隔を置いたフィルタヘッダを要求するのに使われる。クライアントは、以下のクライアント操作のセクションで説明されているように、getcfheadersのフィルタハッシュを使ってこれらのチェックポイントを繋ぐことができる。getcfcheckptsには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 要求されているヘッダのフィルタタイプ
StopHash [32]byte 32 ヘッダが要求されているチェーン内の最後のブロックのハッシュ
  1. ノードは接続先のピアがこのフィルタタイプをサポートするシグナルと出していない場合、getcfcheckptsを送信しない方が良い。サポートしていないフィルタタイプのgetcfcheckptsを受信した場合、ノードは応答を返さないほうが良い。
  2. StopHashは受信ピアによって受け入れられたブロックに入っているものでなければならない。これはピアが以前に、そのブロックもしくはその子孫が含まれるheadersもしくはinvメッセージを送信していた場合だ。不明なStopHashがセットされたgetcfcheckptsを受信したノードは応答しなくても良い。
cfcheckpts

cfcheckptsgetcfcheckptsへの応答として送信される。含まれるフィルタヘッダは要求されたチェーン上のすべてのフィルタヘッダのセットで、その高さは1000の正の倍数(1000間隔毎のフィルタヘッダ)。メッセージには以下のフィールドが含まれる。

フィールド名 データ型 バイトサイズ 定義
FilterType byte 1 要求されているヘッダのフィルタタイプ
StopHash [32]byte 32 ヘッダが要求されているチェーン内の最後のブロックのハッシュ
FilterHeadersLength CompactSize 1-3 次のフィールドのフィルタヘッダのvectorの長さ
FilterHeaders [][32]byte FilterHeadersLength * 32 1000間隔のフィルタヘッダのリスト
  1. FilterTypeとStopHashはgetcfcheckptsリクエストと一致する必要がある。
  2. FilterHeadersはジェネシスブロックからStopHashのブロックまでの間のブロック高が1000の倍数であるブロック毎に1つのエントリーを持たなくてはならない。そのエントリーはそのような各ブロックの与えられたタイプのフィルタヘッダで、ブロック高の昇順でセットされていなければならない。

ノード操作

ルノードは、このBIPをサポートし指定された任意のフィルタタイプを生成することができる。そのようなノードは、フィルタをブロックチェーンの追加インデックスとして扱う必要がある。メインチェーンに接続する新しいブロック毎に、ノードはサポートしているすべてのタイプのフィルタを生成し保存する必要がある。フィルタを保持しておらず、すでにブロックチェーンと同期済みのノードは、起動時にチェーンを再インデックスしジェネシスブロックから最新のブロックまでの各ブロックのフィルタを構築する必要がある。また、getcfcheckptsのリクエストにより多くのディスクへのランダムアクセスを引き起こさないようすべてのチェックポイントヘッダをメモリ上に保持する必要がある。

悪意あるピアが大きなブロックから派生した小さなフィルタを要求しDoS攻撃を実行する可能性があるため、要求に応じて動的にフィルタを生成しない方がいい。これはBIP-111に記載されているBIP-37対応ノードに対する攻撃と同じく、ノード上で計算とサービスを行うI/Oの問題が発生する。

ノードはブロックのすべてのフィルタを生成し保存した後であれば、ブロックをプルーニングしてもいい。

クライアント操作

このセクションではクライアントが最大のセキュリティをもってフィルタをダウンロードするための推奨事項を示す。

クライアントはまずブロックフィルタやフィルタヘッダをダウンロードする前に、標準のヘッダファーストの仕組みを利用してピアからすべてのブロックヘッダの同期をする必要がある。トラステッドチェックポイントを構成するクライアントは、最後のチェックポイントからヘッダの同期を開始するだけでいい。クライアントは接続先のピアのベストチェーンが既知の最長のProof of Workのチェーンよりも大幅に作業量が少ない場合、そのアウトバウンドピアとのコネクションは切断する必要がある。

クライアントのブロックヘッダが同期できたら、後でダウンロードする可能性のあるすべてのブロックとフィルタタイプのフィルタヘッダをダウンロードして検証する必要がある。クライアントはgetcfheadersメッセージをピアに送信し、各ブロックのフィルタヘッダを導出し格納する必要がある。クライアントは最初にgetcfcheckptsメッセージを送信することで、1,000ブロック間隔でヘッダをフェッチしてもいい。ヘッダチェックポイントを使うとクライアントは複数のピアからさまざまな間隔でフィルタヘッダを並行してダウンロードし、1000個のヘッダの各範囲をチェックポイントに対し検証することができる。

フィルタヘッダを提供する信頼できるピアに確実に接続しているか分からない場合、クライアントは各フィルタタイプをサポートする複数のアウトバウンドピアに接続し、不正なヘッダをダウンロードするリスクを軽減する必要がある。クライアントが任意のブロックやフィルタタイプについて異なるピアから競合するフィルタヘッダを受信した場合、調査しどちらに欠陥があるのか判断する必要がある。クライアントはgetcfheadersおよびgetcfcheckptsを使用して一致しなくなった最初のフィルタヘッダを特定する必要がある。クライアントはピアから完全なブロックをダウンロードし、正しいフィルタとフィルタヘッダを導出する必要がある。クライアントは計算したものと一致しないフィルタヘッダを送信したピアをBANする必要がある。

クライアントが必要なすべてのフィルタヘッダをダウンロード及び検証し、アウトバウンドピアが競合するヘッダを送信していなければ、クライアントは必要なブロックフィルタをダウンロードできる。クライアントはこの時点で最初に検証されたフィルタヘッダより前のフィルタヘッダについて埋め戻しても良い、ただし後でダウンロードを開始した場合のみ。クライアントは再起動後に新しいピアから受信したヘッダと比較するため、チェーン内のラスト100ブロック分()の検証済みフィルタヘッダを保持する必要がある。後で再スキャンが必要になった場合に、再ダウンロードを避けるためより多くのファイルヘッダを保存しておいてもいい。

希望する範囲内の最初のブロックから始めて、クライアントはフィルタをダウンロードすることができる。クライアントは、各フィルタが対応するフィルタヘッダと不正なフィルタを送信するBANピアにリンクするかテストする必要がある。クライアントは複数のフィルタを一度にダウンロードしスループットを上げることができるが、フィルタは順番にテストする必要がある。クライアントは、フィルタを要求する前にフィルタヘッダが空のフィルタのハッシュにコミットしているかどうかチェックすることで、不要な往復を避けても良い。

新しい有効なブロックヘッダを受信するたびに、クライアントはすべての適格なピアに対応するフィルタヘッダを要求する必要がある。2つのピアが競合するフィルタヘッダを送ってきた場合、クライアントは上記のようにそれらを調べ、無効なヘッダを送信するピアをBANする必要がある。

クライアントがP2Pネットワークから全ブロックをフェッチする場合、アウトバウンドピアから無作為にダウンロードし、トランザクションの交差分析によるプライバシーの損失を軽減する必要がある。このBIPをサポートしていないピアからブロックをダウンロードできることに注意する。

論拠

フィルタヘッダとチェックポイントメッセージは、競合する情報を送信しているピアに接続されている場合、クライアントがブロックの正しいフィルタを識別するのに役立つ。別の解決方法はBitcoinのブロックにブロックフィルタを導出するためのコミットメントを含める方法で、この場合軽量クライアントはブロックヘッダといくつかの追加のwitness dataを使って信頼性を検証できる。しかしこれはBitcoinのコンセンサスルールをネットワーク全体で変更する必要がありるため、このドキュメントでは純粋にP2Pレイヤのみで解決する方法を提案している。

現在のチェーンの長さと成長率と、2つのチェックポイント間のcfheadersからcfcheckptsメッセージのサイズが大幅に大きくならないよう考慮し、チェックポイント間の間隔を1000ブロックとした。また1000は少なくとも10進数で考える我々にとっては良い番号だ。

互換性

この軽量クライアントのモードは、現在の展開されているノードと互換性はなく、新しいP2Pメッセージのサポートが必要となる。この提案のノード実装は、現在のP2Pネットワークルールと互換性はない(つまりフルノードのネットワーク・トポロジーには影響しない)。軽量クライアントはこのBIPに基づくプロトコルを既存のBIP-37の代替として採用することができる。このBIPの採用により、BIP-37のネットワークサポートが低下する可能性がある。

参照実装

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

所感

  • フィルタにマッチした際にそのブロック全部ダウンロードするので、今までよりダウンロードするデータサイズは増える。これは悪意あるフルノードへの対応やプライバシー問題とのトレードオフかな。あとブロックサイズが大きいほどこの負担は増えるので、ビッグブロックのチェーンの軽量クライアントでこれを採用するのは、その部分がネックになりそう。
  • 参照実装のプロダクトみる感じだとbtcdとLightning Networkのクライアントであるneutrinoなので、Coreに実装されるのはまだ先か?
  • 軽量クライアント向けの改善は以前roasbeefがhttps://github.com/Roasbeef/bips/blob/master/gcs_light_client.mediawikiを提案していたが、BIP-157とBIP158に置き換えるみたい。
  • 互換性の部分にこれが採用されることによるBIP-37のネットワークサポートへの影響について記載されているが、競合となる機能リリースする際はこういった影響の視点も重要ね。

BIP-158へ続く。

techmedia-think.hatenablog.com

どうしてECDSA署名から公開鍵が復元できるのか?

ECDSAの署名からどうして公開鍵が取得できるの?という聞かれて何でだろうねって話になったので調べてみた。

署名から公開鍵のセットを復元

Rubyではecdsaのgemを使えば以下のように署名と署名対象のメッセージから公開鍵を取得できる。(署名対象のメッセージはどうせなのでBitcoinで使用されているのと同じトランザクションのsighashを使用。そのためbitcoinrbのgemも利用している)

実行すると↓のように2つの公開鍵が抽出できる。

0259f6658325c4e3ca6fb38f657ffcbf4b1c45ef4f0c1dd86d5f6c0cebb0e09520
03a9255e098f4075e9ebfaf7859f459095667879db33e977fc8c91029afa8a2490

↑のコード上の署名はこの内の0259f6658325c4e3ca6fb38f657ffcbf4b1c45ef4f0c1dd86d5f6c0cebb0e09520に対応する秘密鍵で行ったもの。

署名とメッセージから公開鍵を復元する際の計算

ecdsaのgemで署名とメッセージから公開鍵を計算しているのがrecovery_public_key.rbの↓の部分。

module ECDSA
...

  def self.recover_public_key(group, digest, signature)
    return enum_for(:recover_public_key, group, digest, signature) if !block_given?

    digest = normalize_digest(digest, group.bit_length)

    each_possible_temporary_public_key(group, digest, signature) do |point|
      yield calculate_public_key(group, digest, signature, point)
    end

    nil
  end

  private

  def self.each_possible_temporary_public_key(group, digest, signature)
    signature.r.step(group.field.prime - 1, group.order) do |x|
      group.solve_for_y(x).each do |y|
        point = group.new_point [x, y]
        yield point if point.multiply_by_scalar(group.order).infinity?
      end
    end
  end

  def self.calculate_public_key(group, digest, signature, temporary_public_key)
    point_field = PrimeField.new(group.order)

    # public key = (tempPubKey * s - G * e) / r
    rs = temporary_public_key.multiply_by_scalar(signature.s)
    ge = group.generator.multiply_by_scalar(digest)
    r_inv = point_field.inverse(signature.r)

    rs.add_to_point(ge.negate).multiply_by_scalar(r_inv)
  end

end

ここでは以下の計算をしている。

  1. 署名データ(r, s)r楕円曲線のx座標として、y座標を計算する。
    secp256k1の楕円曲線多項式はy2 = x3 + 7なので、rの値をxに入れればyを計算できる。楕円曲線の平面曲線はx軸に対して対称なのでyの取りうる値はx軸を対称に2つある(↑のrecover_public_keyを呼んで2つの公開鍵が返ってきたのはこのため)。ここで計算した2つの点について2以降の計算をして2つの公開鍵を導出する。
  2. rと1で計算したyから[r, y]となる楕円曲線上の点を計算する。
  3. 2で計算した点に(r, s)sを掛けた点rsを計算する。
  4. secp256k1のグループGの生成点にメッセージを掛けた点geを計算する。
  5. 3で計算した点rsに4で計算した点geを減算して出来た点に {r^{-1}}を掛けた点を計算する。

5で計算した点が復元した公開鍵になる。

もう少し簡略化してみよう。署名データを(r, s)、1でrを使って計算した2つの点をRとR'とし、メッセージのハッシュ値e、secp256k1の楕円曲線の生成点をGとした場合、算出している公開鍵は以下の2つだ。

 {\displaystyle \frac{sR - eG}{r}}および {\displaystyle \frac{sR' - eG}{r}}

補足

↑の1の計算についてコメントもらったので追記。

1でrをx座標として2つのRとR'を計算すると書いたが、楕円曲線のペーパーには、このx = r + jnでx座標を求めるようになっている。ここでj {j \in \{0, 1, ...., h\}}の集合でhは各楕円曲線毎に定義されており、secp256k1の場合h = 1だ。つまりx座標の候補はrr + nの2つになる(nはグループの位数)。r + nがグループの剰余系の素数を超えないようになってるので、実際にその範囲内のr + nが候補に上がるのは、r剰余系の素数 - 1 - n以下の場合。最初の復元コードの出力結果が2つの公開鍵だったのはr + nがこの範囲外で、rのみの計算となったため。

なぜこれが公開鍵になるのか?

という疑問が当然わくが、これはECDSAの署名生成と署名検証時のロジックからそれっぽい理由が分かる↓(数学的にはもっとちゃんとした解説があると思う)

秘密鍵p、その公開鍵をQ = pGとし、メッセージのハッシュ値eへのECDSAの署名データ(r, s)は以下のようにして計算される。

  1. 最初にランダムな値kを選択する。
  2. kを使って楕円曲線上の点=kG = (x, y)を計算し、そのx座標をrとする。
  3.  {s = k^{-1}(e + r*p) \bmod n}を計算する。
  4. 算出した(r, s)が署名データとなる。

そしてその署名データが正しいかどうかは以下のようにして判定される。

 {\displaystyle R = (e/s)G + (r/s)Q}

となる点Rを計算し、Rのx座標がrと同じであれば署名は正しい。

この検証に使用した式を公開鍵Qを求めるように展開すると

 {\displaystyle R = \frac{eG + rQ}{s}}
 {\displaystyle sR = eG + rQ}
 {\displaystyle sR - eG = rQ}
 {\displaystyle \frac{sR - eG}{r} = Q}

署名が正しい場合Rのx座標はrと等しいということを思い出そう。公開鍵の復元に使用したRR'のx座標はいずれもrで、公開鍵による検証の際に使用した楕円曲線上の点と合致する。

このことから(r, s)およびそのメッセージeから計算した {\displaystyle \frac{sR - eG}{r}}および {\displaystyle \frac{sR' - eG}{r}}が公開鍵と言える。