Develop with pleasure!

福岡でCloudとかBlockchainとか。

クライアントサイドでブロックのフィルタリングを行う軽量クライアント向けのプロトコル 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