BIP 158 高密度ブロック フィルターの説明

エル・ムートン著

この記事では、ビットコインにおけるライト クライアントのニーズと、「コンパクト ブロック フィルター」が「ブルーム フィルター」よりもこのニーズに適している理由について簡単に説明します。次に、テストネット上でこのようなフィルターを構築する手順を段階的に説明しながら、密ブロック フィルターがどのように機能するかを詳しく説明します。

ブロックフィルターの意味

ビットコイン ライト クライアント (ビットコイン ライト ソフトウェア) は、ビットコイン ブロックチェーンを保存することを目的とするのではなく、ビットコイン ウォレットをサポートすることを目的としたソフトウェアです。これは、トランザクションをネットワークにブロードキャストできる必要があることを意味しますが、最も重要なのは、このウォレットに関連するチェーンから新しいトランザクションを見つけられる必要があることです。このような関連トランザクションには 2 つのタイプがあります。1 つはこのウォレットへの資金の送信 (このウォレットのアドレスに対する新しい出力の作成)、もう 1 つはこのウォレットによって制御される UTXO の 1 つを使用することです。

ブルームフィルターの何が問題なのでしょうか?

BIP 158 より前は、ライト クライアントに対する最も一般的なアプローチは、BIP 371 で説明されているブルーム フィルターでした。ブルーム フィルターのパターンは、関心のあるすべてのデータ オブジェクト (たとえば、使用され作成された UTXO のスクリプト公開キー) を取得し、それらを 1 つずつ複数回ハッシュし、各結果を In に追加するというものです。 「ブルームフィルター」と呼ばれるビットマップ。このフィルターは、あなたが興味を持っているものを表します。次に、このフィルターを信頼するビットコイン ノードに送信し、このフィルターに一致するものをすべて送信するように依頼します。

問題は、フィルターを受け入れるビットコイン ノードに依然として一部の情報が漏洩するため、このプロセスがあまりプライベートではないことです。彼らは、あなたが興味のある取引とまったく興味のない取引を知ることができますが、フィルターに一致するものをあなたに送信することもできません。したがって、ライトクライアントには理想的ではありません。しかし同時に、これはライトクライアントにサービスを提供するビットコインノードには理想的ではありません。フィルターを送信するたびに、フィルターは関連するブロックをディスクからロードし、フィルターに一致するトランザクションがあるかどうかを判断する必要があります。偽のフィルターを送信し続けるだけで、それらを爆撃することができます。これは本質的に DOS 攻撃です。フィルターを作るのにはほとんどエネルギーはかかりませんが、このような要求に応えるには多くのエネルギーが必要です。

密ブロックフィルター

OK、必要な属性は次のとおりです。

• プライバシーの強化
• クライアントとサーバーの負荷の非対称性が少なくなります。つまり、サーバー側で行う作業が少なくなるはずです。 ※信頼度が低くなります。ライトクライアントは、サーバーが関連トランザクションを返さないことを心配する必要はありません。

高密度ブロック フィルターを使用すると、サーバー (フル ノード) は、このブロック内のすべてのデータ オブジェクトを含むブロックごとに決定論的フィルターを構築します。このフィルターは一度計算するだけで済み、永久に保存されます。ライト クライアントが特定のブロックのフィルターを要求した場合、サーバーは要求元のクライアント以上の作業を行う必要がないため、ここには非対称性はありません。ライト クライアントは、複数の情報ソースを選択して完全なブロックをダウンロードし、それらが一貫していることを確認することもできます。さらに、ライト クライアントは常に完全なブロックをダウンロードして、サーバーによって提供されたフィルターが正しいかどうかを確認できます。コンテンツ）。もう 1 つの利点は、この方法によりプライベート性が高まることです。ライトクライアントは、必要なデータのフィンガープリントをサーバーに送信する必要がなくなりました。また、ライトクライアントのアクティビティを分析することも難しくなります。ライト クライアントはサーバーからそのようなフィルターを取得した後、フィルターに必要なデータが含まれているかどうかを確認し、含まれている場合は完全なブロックを要求します。また、この方法でライト クライアントにサービスを提供するには、フル ノードがこれらのフィルターを永続化する必要があり、ライト クライアントもいくつかのフィルターを永続化したい場合があるため、フィルターをできるだけ軽く保つ必要があることにも注意してください。量は非常に重要です (これが「密ブロック フィルター」と呼ばれる理由です)。

とても良い！ここからは珍しいものを紹介していきます。このようなフィルターはどのように作成されるのでしょうか?それはどのように見えますか？

私たちのニーズは何でしょうか？

• 特定のオブジェクトのフィンガープリントをフィルターに入れたいので、クライアントがブロックに自分に関連するものが含まれているかどうかを確認したいときに、すべてのオブジェクトを列挙し、フィルターがこれらのオブジェクトと一致するかどうかを確認できるようになります。
• このフィルターはできるだけ小さくしたいと考えています。
• 本質的に、ブロックよりもはるかに小さい体積でブロックの一部の情報を要約できるものが必要です。

フィルターに含まれる基本情報は、各トランザクションの各入力のスクリプト公開キー (つまり、使用された各 UTXO のスクリプト公開キー)、および各トランザクションの各出力のスクリプト公開キーです。基本的には次のとおりです。

object = {spk1, spk2, spk3, spk4, ..., spkN} // N 個のスクリプト公開鍵のリスト

技術的には、ここで終了します。このようなスクリプト公開キーのリストは、フィルターとしても機能します。これは、ライト クライアントが必要とする情報を含むブロックの圧縮バージョンです。このようなリストを使用すると、ライトクライアントはブロック内に目的のトランザクションがあるかどうかを 100% 確認できます。しかし、そのようなリストは非常に膨大です。したがって、次のステップは、このリストをできるだけコンパクトにすることです。ここからが興味深いことになります。

まず、各オブジェクトを特定の範囲内の数値に変換し、各オブジェクトの数値がこの範囲内で均等に分散されるようにすることができます。 10 個のオブジェクト (N = 10) があり、各オブジェクトを数値に変換する何らかの関数があるとします。範囲 [0, 10] を選択するとします (オブジェクトが 10 個あるため)。ここで、「ハッシュから数値へ」関数は各オブジェクトを入力として受け取り、それぞれサイズ [0, 10] の数値を生成します。数値はこの範囲全体に均等に分布しています。これは、並べ替え後、次のようなグラフになることを意味します (非常に理想的なケースです)。

まず第一に、これが素晴らしいのは、各オブジェクトのフィンガープリントのサイズが大幅に削減されたためです。これで、各オブジェクトは単なる数字になります。したがって、新しいフィルターは次のようになります。

数値 := {1,2,3,4,5,6,7,8,9,10}

ライトクライアントは、探しているオブジェクトがフィルターに一致するかどうかを知りたいと考えて、そのようなフィルターをダウンロードします。彼らは、興味のあるオブジェクトを取得し、同じ「ハッシュから数値へ」関数を実行して、結果がこのフィルター内にあるかどうかを確認するだけです。問題はどこだ？問題は、フィルター内の数値がその空間内のすべての可能性をすでに取り上げていることです。これは、ライト クライアントがどのようなオブジェクトを気にするかに関係なく、結果として得られる数値結果がこのフィルターと一致する必要があることを意味します。言い換えれば、このフィルターの「偽陽性率」は 1 です (翻訳者注: ここでの「偽陽性」とは、ブロックにフィルターによって得られた結果が「はい」を含まない可能性があることを意味します)。これはあまり良くありません。また、フィルターを生成するためにデータを圧縮する過程で、あまりにも多くの情報が失われたことも示しています。より高い偽陽性率が必要です。次に、偽陽性率を 5 にしたいとします。その後、ブロック内のオブジェクトを [0, 50] の範囲の数値に均等に一致させることができます。

その方が見栄えが良くなります。私がクライアントで、このようなフィルターをダウンロードした場合、関心のあるオブジェクトがフィルターを通じて対応するブロック内にあるかどうかを確認する必要があります。フィルターが「はい」と答えてもブロック内にない (偽陽性) 確率は、次のように減少します。 1/5。これで、10 個のオブジェクトが 0 ～ 50 の数値にマッピングされました。この新しい数値リストがフィルターです。繰り返しますが、いつでも停止できますが、さらに圧縮することもできます。

これで、[0, 50] の範囲に均等に分布した番号の順序付きリストが得られました。このリストには 10 個の数字があることがわかっています。つまり、この順序付けられた数値リスト内の 2 つの隣接する数値間の 差 は 5 である可能性が最も高いと推測できます。一般に、N 個のオブジェクトがあり、誤検知率を M にしたい場合、空間のサイズは N * M でなければなりません。つまり、これらの数値のサイズは 0 から N * M の間である必要がありますが、(ソート後の) チェックされる 2 つの隣接する数値の内挿確率は M です。また、M は N * M 空間の数値よりも小さく格納する必要があります。したがって、単一の数値をすべて保存する代わりに、隣接する 2 つの数値の差を保存できます。上記の例では、これは、フィルターとして [0, 5, 10, 15, 20, 25, 30, 35, 40, 45, 50] を保存する代わりに、[0, 5, 5, 5, 5] を保存することを意味します。 , 5, 5, 5, 5, 5]、そこから初期リストを再構築するのは簡単です。スケールダウンすると、数値 50 を保存すると、数値 5 を保存するよりも明らかに多くのスペースが必要になります。しかし、なぜそこで止まるのでしょうか？もう少し圧縮してみましょう！

次のステップは、「Golomb-Rice エンコーディング」を使用することです。このエンコード方法は、テーブル内の各数値が特定の数値に非常に近いリストを適切にエンコードできます。そして、私たちのリストはまさにそれです！リスト内の各数値は 5 に近い (または誤検知率 M に近い) 可能性が高いため、各数値の商を M で計算します (各数値を 5 で割って余りを無視します)。ほとんどの場合、0 (数値が 5 よりわずかに小さい場合) または 1 (数値が 5 よりわずかに大きい場合) になります。商が 2、3 などになる可能性もありますが、確率ははるかに小さくなります。素晴らしい！したがって、これを利用できます。小さい商をエンコードするにはできるだけ少ないビットを使用し、より多くのビットコインを使用して、より大きな商をエンコードしますが、可能性は低いです。次に、(リスト全体を正確に再構成できるようにしたいため) 残りもエンコードする必要があります。これは常に [0, M - 1] の範囲内になります (この場合は [0, 4])。エンコーダーには、次のマッピングを使用します。

上記のマッピングは理解しやすいです。桁 1 の数はエンコードする商を示し、0 は商エンコードの終了を示します。したがって、リスト内の各数値について、上記の表を使用して商をエンコードし、M-1 の最大値を表現できる bittruck を使用して余りをバイナリに変換できます。ここで、余りは 4 であり、必要なビットは 3 ビットだけです。この例で考えられる剰余とそのエンコーディングを示す表は次のとおりです。

したがって、理想的には、リスト [0, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5] は次のようにエンコードされます。

0000 10000 10000 10000 10000 10000 10000 10000 10000 10000

より現実的なケースに移る前に、このフィルターを使用して元のリストを復元できるかどうかを確認してみましょう。

今あるのは「0000100001000010000100001000010000100001000010000」です。私たちは Golomb-Rice コードを知っており、M が 5 であることを知っています (これは公知となり、このフィルタ構造を使用するすべての人に知られるため)。 M が 5 であることがわかっているので、残りをエンコードするには 3 ビットがあることがわかります。したがって、このフィルターを次の「商-剰余」配列リストに変換できます。

[(0, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), (1, 0), ( 1、0)、(1、0)]

商は M(5) で割ることによって得られることがわかっているので、次のように求めることができます。

[0、5、5、5、5、5、5、5、5、5]

また、このリストは隣接する 2 つの数値の差を表すことがわかっているため、元のリストを復元できます。

[0、5、10、15、20、25、30、35、40、45、50]

より現実的な例

ここで、実際のビットコイン テストネット ブロック用のフィルターを構築してみます。ブロック 2101914 を使用します。そのフィルターがどのようなものかを見てみましょう:

$ bitcoin-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ bitcoin-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { "フィルター": "5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df574378640238 33f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa2e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", "ヘッダー": "8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe" }

さて、ブロックからそのようなフィルターを構築する方法を見てみましょう。

ここで使用されている完全なコードは、この github リポジトリにあります。ここでは、いくつかの疑似コードのスニペットだけを示します。このコードの中心となるのは、constructFilter と呼ばれる関数です。この関数は、ビットコイン クライアントが bitcoind および対応するブロックを呼び出すために使用できます。関数は次のようになります。

funcconstructFilter(bc *bitcoind.Bitcoind, block bitcoind.Block) ([]byte, error) { // 1 は、フィルターに追加するブロックからすべてのオブジェクトを収集します // 2 これらのオブジェクトを数値に変換し、並べ替えます。 // 3 ソートされた数値リスト内の 2 つの隣接する数値の差を取得します // 4 これらの違いをエンコードするには Golomb-Rice エンコードを使用します }

したがって、最初のステップは、フィルターに追加するブロックからすべてのオブジェクトを収集することです。 BIP から始めて、これらのオブジェクトにはすべての使用済みスクリプト公開キーとすべての出力スクリプト公開キーが含まれることがわかっています。 BIP は追加のルールも設定します。コインベース トランザクションへの入力をスキップし (入力がないため意味がありません)、すべての OP_RETURN 出力を渡します。データの重複排除も行います。同一のスクリプト公開キーが 2 つある場合、それをフィルターに 1 回だけ追加します。

// フィルターに追加するオブジェクトのリスト // すべての使用済みスクリプト公開キーとすべての出力スクリプト公開キーを含めます // 重複したスクリプト公開キーを削除する「マップ」を使用します。 オブジェクト := make(マップ [string] 構造体{}) // ブロック内のすべてのトランザクションを促進します for i, tx := range block.Tx { // 各出力にスクリプト公開キーを追加します // オブジェクトのリストに追加します for _, txOut := range tx.Vout { PubKey := txOut.PubKey if len(PubKey) == 0 { 続く } // OP_RETURN (0x6a) が出力された場合はスキップ SPKの場合 [0] == 0x6a { 続く } オブジェクト [skpStr] = 構造体{}{} } // Coinbase トランザクションの入力を追加しません if i == 0 { 続く } // 入力ごとに、そのスクリプトの公開キーを取得します for _, txIn := range tx.Vin { prevTx、エラー := bc.GetRawTransaction(txIn.Txid) エラーの場合 != nil { nil を返す、エラー } PubKey := prevTx.Vout[txIn.Vout].PubKey if len(PubKey) == 0 { 続く } オブジェクト [spkStr] = 構造体{}{} } }

OK、これですべてのオブジェクトが収集されました。ここで、変数 N をオブジェクト グラフの長さになるように定義します。ここで、N は 85 です。

次のステップでは、オブジェクトを一定間隔で均一に分布する数値に変換します。繰り返しますが、範囲は、どの程度の偽陽性率を望むかによって異なります。 BIP158 では定数 M を 784931 と定義しています。これは、偽陽性の確率が 784931 分の 1 であることを意味します。前に行ったように、偽陽性率の M × N を取得し、すべての数値の分布範囲を取得します。この範囲を F、つまり F = M * N として定義します。ここで、F = 66719135 です。オブジェクトを数値にマッピングする関数の詳細については説明しません (詳細は、上にリンクされている github リポジトリで見つけることができます)。知っておく必要があるのは、入力としてオブジェクト、定数 F (オブジェクトをマップする必要があるスコープを定義する)、およびキー (ブロック ハッシュ) を受け取ることだけです。すべての数値を取得したら、リストを昇順に並べ替えて、並べ替えられた数値のリスト内の 2 つの隣接する数値の差を保持する差分と呼ばれる新しいリストを作成します。

数値 := make([]uint64, 0, N) // すべてのオブジェクトを反復処理し、範囲 [0, F] に均等に分布する数値に変換します。 // これらの数値を数値リストとして保存します for o := range オブジェクト { // 指定されたキー、最大数 (F)、およびオブジェクト バイト数 (o) を使用して、 // オブジェクトを 0 から F までの数値に変換します。 v := ConvertToNumber(b, F, key) 数値 = 追加(数値, v) } // 数値リストをソートします sort.Slice(numbers, func(i, j int) bool { 数値を返す [i] < 数字 [j] }) // 数値のリストを差分のリストに変換します 違い:= make([]uint64, N) for i, num := 範囲の数値 { if i == 0 { 違い [i] = 番号 続く } 違い [i] = num - 数値[i-1] }

素晴らしい！これは、番号と違いのリストを示した図です。

ズームアウトすると、85 の数字が空間全体に均等に分散されています。したがって、差分リストの値も非常に小さくなります。

最後のステップは、Golomb-Rice エンコーディングを使用して相違点のリストをエンコードすることです。前の説明を思い出してください。各差を最も可能性の高い値で除算し、商と余りをエンコードする必要があります。前の例では、最も可能性の高い値は M であり、残りは [0, M] の間にあると述べました。ただし、実際に最終的なフィルター サイズを最小化するパラメーターではない 2 が見つかったため、BIP158 ではこれが行われません。したがって、M を使用する代わりに、新しい定数 P を定義し、2^P を Golomb-Rice パラメーターとして使用します。 P は 19 として定義されます。これは、各差を 2^19 で割って商と余りを求め、余りは 19 ビットのバイナリでエンコードされることを意味します。

フィルター := bstream.NewBStreamWriter(0) // 差分リストの各値について、商と余りを 2^P で割って求めます。 for _, d := 範囲の違い { q := math.Floor(float64(d)/math.Exp2(float64(P))) r := d - uint64(math.Exp2(float64(P))*q) // エンコーダ 私にとって:= 0; i < int(q); i++ { フィルター.WriteBit(true) } フィルター.WriteBit(false) filter.WriteBits(r, P) }

素晴らしい！これで、フィルターを出力して、以下を取得できるようになりました。

71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f2f 8 01639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0c 5b3 2aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa2e 6102 3abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270

最初の 2 バイトを除いて、bitcoind で得たフィルターとまったく同じです。最初の 2 バイトに違いがあるのはなぜですか? BIP では、受信機がデコードできるように、N の値を CompactSize 形式でエンコードし、フィルターの前に表示する必要があると規定しているためです。これは次のように行われます。

fd := filter.Bytes() バッファ バイト.バッファ buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = Wire.WriteInt(&buffer, 0, uint64(N)) エラーの場合 != nil { nil を返す、エラー } _、エラー = バッファ.書き込み(fd) エラーの場合 != nil { nil を返す、エラー }

ここでフィルターを再度出力すると、それが bitcoind の結果とまったく同じであることがわかります。

5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2 f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b 0c5 b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa 2e61 023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270

成功！

ただし、私の個人的な理解では、フィルターに N を追加する必要はありません。 P の値がわかっていれば、N の値を見つけることができます。最初のフィルターの出力を使用して、元の数値リストを復元できるかどうかを見てみましょう。

b := bstream.NewBStreamReader(フィルター) ( 数値 []uint64 前の数値 uint64 ) ために { // バイト文字列から商を読み取ります。最初の 0 は商の終わりを示します // 0 に遭遇する前は 1 の数字が商を表します q uint64 c、エラー:= b.ReadBit() エラーの場合 != nil { エラーを返す } cの場合{ q++ c、エラー = b.ReadBit() if エラー.Is(err, io.EOF) { 壊す } else if err != nil { エラーを返す } } // 次の P ビットは残りをエンコードします r、エラー := b.ReadBits(P) if エラー.Is(err, io.EOF) { 壊す } else if err != nil { エラーを返す } n := q*uint64(math.Exp2(float64(P))) + r 番号 := n + 前の番号 数値 = 追加(数値, 数値) 前の番号 = 番号 } fmt.Println(数値)

上記の操作では同じ数値のリストが生成されるため、N を知らなくてもリストを再構築できます。したがって、フィルターに N を追加する理論的根拠がわかりません。なぜ N を含める必要があるのかご存知の場合は、教えてください。

読んでくれてありがとう！