BIP 158 緻密區塊過濾器詳解

作者：Elle Mouton

在本文中，我會簡要介紹比特幣輕客戶端的需要，以及為什麼“緻密區塊過濾器（compact block filters）” 比“布隆過濾器（Bloom filters）” 更好地滿足了這種需要。然後，我會深入解釋緻密區塊過濾器是怎麼工作的，並會附上在測試網上構造這樣的過濾器的逐步講解。

區塊過濾器的意義

比特幣輕客戶端（bitcoin light software）是一種軟件，其目標是不存儲比特幣區塊鏈但支持比特幣錢包。這意味著，它需要能夠向網絡廣播交易，但最重要的是，它必須能夠從鏈上找出跟本錢包相關的新交易。這樣的相關交易有兩種：給本錢包發送資金（為本錢包的一個地址創建了一個新的輸出）、花費本錢包所控制的其中一個UTXO。

布隆過濾器有什麼問題？

在BIP 158 出現以前，輕客戶端最常用的方法是由BIP 37 描述的布隆過濾器1。布隆過濾器的模式是，你找出自己感興趣的所有數據對象（比如，被花費的以及被創建的UTXO 的腳本公鑰）、將它們逐個多次哈希，然後將每個結果添加到一個叫做“布隆過濾器” 的位圖（bit map）中。這個過濾器代表了你感興趣的東西。然後，你將這個過濾器發送給一個你信任的比特幣節點，並要求他們給你發送所有跟這個過濾器相匹配的東西。

問題在於，這個過程並不是非常私密，因為，你還是向這個接收過濾器的比特幣節點洩露了一些信息。他們可以知曉你感興趣的交易以及你完全沒興趣的交易；他們還可以不給你發送跟過濾器相匹配的東西。所以，這對輕客戶端來說並不是理想的。但同時，它對向輕客戶端提供服務的比特幣節點來說也不理想。每次你發送一個過濾器，他們就必須從硬盤加載相關的區塊，然後確定是否有交易跟你的過濾器相匹配。只需要不停發送假的過濾器，你就可以轟炸他們—— 這本質上是一種DOS 攻擊。只需要非常少的能量就可以創建一個過濾器，但需要耗費很多能量，才能響應這樣的請求。

緻密區塊過濾器

OK，那麼我們需要的屬性有：

• 更強的隱私性
• 客戶端-服務端的負載更少不對稱性。即，服務端需要做的工作應該更少。
• 更少信任。輕客戶端不需要擔心服務端不返回相關的交易。

使用緻密區塊過濾器，服務端（全節點）將為每個區塊構造一個確定性的過濾器，包含這個區塊中的所有數據對象。這個過濾器只需計算一次，就可以永久保存下來。如果輕客戶端請求某一個區塊的過濾器，這裡是沒有不對稱性的—— 因為服務端不需要做比發起請求的客戶端更多的工作。輕客戶端也可以選擇多個信息源來下載完整的區塊，以確保它們是一致的；而且，輕客戶端總是可以下載完整的區塊，從而自己檢查服務端所提供的過濾器是不是正確的（與相關的區塊內容相匹配）。另一個好處是，這種方式更加隱私。輕客戶端不再需要給服務端發送自己想要的數據的指紋。這樣分析一個輕客戶端的活動也會變得更加困難。輕客戶端從服務端獲取這樣的過濾器之後，自己檢查過濾器中是否有自己想要的數據，如果有，輕客戶端就請求完整的區塊。還要指出的一點是，為了以這種方式服務輕客戶端，全節點需要持久保存這些過濾器，而輕客戶端可能也想要持久保存少數幾個過濾器，所以，保證過濾器盡可能輕量，是非常重要的（這也是為什麼它叫做“緻密區塊過濾器”）。

很好！現在我們要進入難得東西了。這樣的過濾器是怎麼創建的？它看起來是什麼樣子的？

我們的需求是？

• 我們想把特定對象的指紋放在過濾器中，這樣一來，當客戶端想要檢查一個區塊是否可能包含了跟自己相關的內容時，他們可以列舉所有的對象，並檢查一個過濾器是否與這些對象匹配。
• 我們希望這個過濾器盡可能小。
• 實質上，我們想要的是某種東西，它可以用一個遠遠小於區塊的體積，來總結一個區塊的某一些信息。

包含在過濾器中的基本信息有：每一筆交易的輸入的腳本公鑰（也就是每一個被花費的UTXO 的腳本公鑰），以及每一筆交易的每一個輸出的腳本公鑰。基本上就是這樣：

objects = {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}

輕客戶端下載這樣的過濾器，希望知道自己正在尋找的某個對像是否跟這個過濾器相匹配。他們只需取出自己感興趣的對象，然後運行相同的“哈希加轉換成數字” 函數，看看結果是否在這個過濾器中，就可以了。問題在哪裡呢？問題是過濾器中的數字已經佔據了這個空間內的一切可能性！這意味著，不管輕客戶端關心什麼樣的對象，產生的數字結果都一定會跟這個過濾器相匹配。換句話來說，這個過濾器的“假陽性率（false-positive rate）” 為1 （譯者註：這裡的“假陽性” 指區塊中可能不包含客戶端所關心的交易，但通過過濾器得到的結果卻是有）。這就不太好了。這也說明，在我們壓縮數據以生成過濾器的過程中，我們弄丟了太多信息。我們需要更高的假陽性率。那麼，假設我們希望假陽性率為5.那麼，我們可以讓區塊內的對象均勻匹配到[0, 50] 範圍內的數字：

這樣看起來就好一些了。如果我是一個客戶端，下載到了這樣的過濾器，要通過過濾器檢查一個我關心的對像是否在對應的區塊中，過濾器說有但區塊中並沒有（假陽性）的概率就下降到1/5 。很好，現在我們是將10 個對象映射成了0 到50 之間的數字。這個新的數字列表就是我們的過濾器。再說一遍，我們隨時可以停下來，但是，我們也可以進一步壓縮它們！

現在，我們有了一個有序的數字列表，這些數字均勻地分佈在[0, 50] 區間內。我們知道這個列表中有10 個數字。這意味著，我們可以推斷出，在這個有序數字列表內，相鄰兩個數字的差值 最有可能是5 。總的來說，如果我們有N 個對象，並希望假陽性率為M，那麼空間的大小應該是N * M 。也即這些數字的大小應該在0 到N * M 之間，但（排序之後）相鄰兩個數字檢查的插值大概率是M 。而M 存儲起來肯定比N * M 空間內的數字要小。所以，我們不必存儲每一個數字，我們可以存儲相鄰兩個數字的差值。在上面這個例子中，這意味著，我們不是存儲[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 的比特川，將餘數轉化為2 進制。在這里餘數為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]

而且，我們知道這個列表所表示的是相鄰兩數之間的差值，所以我們可以恢復最初的列表：

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

更加現實的例子

我們現在要嘗試為一個真實的比特幣testnet 區塊構造一個過濾器。我將使用區塊2101914 。我們看看它的過濾器長什麼樣：

$ 比特幣-cli getblockhash 2101914 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c $ 比特幣-cli getblockfilter 000000000000002c06f9afaf2b2b066d4f814ff60cfbc4df55840975a00e035c { “過濾器”：“5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df574378640 23833f2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5 b0b0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade 12fa2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270", “標頭”：“8d0cd8353342930209ac7027be150e679bbc7c65cc62bb8392968e43a6ea3bfe” }

好了親愛的，看看我們如何從區塊構造出這樣的過濾器吧。

這裡所用的完整代碼可以在這個github 庫中找到。我在這裡只會展示一些偽代碼片段。這段代碼的核心是一個名為constructFilter 的函數，比特幣客戶端可以用它來調用bitcoind 以及對應的區塊。這個函數看起來是這樣的：

func ConstructionFilter(bc *bitcoind.Bitcoind, block bitcoind.Block) ([]byte, error) { // 1 從區塊中收集我們想要添加到一個過濾器中的所有對象 // 2 將這些對象轉化為數字，並排序 // 3 取得排序後的數字列表中相鄰兩數的差值 // 4 使用Golomb-Rice 編碼來編碼這些差值 }

所以，第一步是從區塊中收集我們想要添加到過濾器中的所有對象。從BIP 出發，我們知道，這些對象包括所有被花費的腳本公鑰，以及每一個輸出的腳本公鑰。 BIP 還設定了一些額外的規則：我們會跳過coinbase 交易的輸入（因為它沒有輸入，這是沒有意義的），而且我們會通過所有OP_RETURN 輸出。我們也會刪除重複數據。如果有兩個相同的腳本公鑰，我們只會向過濾器添加一次。

// 我們希望向過濾器添加的對象的列表 // 包括所有被花費的腳本公鑰，以及每一個輸出的腳本公鑰 // 我們使用了“圖（map）”，這樣就去除了重複的腳本公鑰 對象 := make( 地圖 [string] 結構{}) // 便利區塊中的每一筆交易 對於 i, tx := 範圍塊.Tx { // 添加每一個輸出的腳本公鑰 // 到我們的對象列表中 對於 _, txOut := 範圍 tx.Vout { 公鑰 := txOut.PubKey 如果 len(公鑰) == 0 { 繼續 } // 如遇OP_RETURN (0x6a) 輸出，則跳過 如果斯普克 [0] == 0x6a { 繼續 } 物體 [skpStr] = 結構體{}{} } // 不添加coinbase 交易的輸入 如果我==0{ 繼續 } // 對每一個輸入，獲取其腳本公鑰 對於 _, txIn := 範圍 tx.Vin { prevTx, err := bc.GetRawTransaction(txIn.Txid) 如果錯誤！= nil { 返回零，錯誤 } PubKey := prevTx.Vout[txIn.Vout].PubKey 如果 len(公鑰) == 0 { 繼續 } 物體 [spkStr] = 結構體{}{} } }

OK，現在已經收集好了所有的對象。現在，我們定義變量N 為對像圖的長度。在這裡，N 為85 .

下一步則是將我們的對象轉換成在一個區間內均勻分佈的數字。再說一次，這個範圍取決於你想要多高的假陽性率。 BIP158 定義常量M 為784931 。這意味著，出現假陽性的概率為1/784931 。就像我們前面做的一樣，我們取假陽性率M 乘以N，得到所有數字的分佈範圍。這個範圍我們定義為F，即F = M * N 。在這裡，F = 66719135 。我不准備細說將對象映射為數字的函數（你可以在上面鏈接的github 庫中找到相關的細節）。你需要知道的僅僅是，它會取對象、常量F（定義了需要將對象映射到的範圍）以及一個鍵（區塊哈希值）作為輸入。一旦我們得出所有的數字，我們會用升序排列這個列表，然後創建一個叫做differences（差值） 的新列表，保存排好序的數字列表內相鄰兩個數字之間的差值。

數字 := make([]uint64, 0, N) // 遍歷所有對象，將它們轉化為在[0, F] 範圍內均勻分佈的數字 // 並將這些數字存儲為numbers 列表 for o := 範圍對象 { // 使用給定的鍵、最大數量 (F) 和對象字節 (o)， // 將對象轉換為 0 到 F 之間的數字。 v := 轉換為數字(b, F, 鍵) 數字 = 附加（數字，v） } // 給numbers 列表排序 sort.Slice(numbers, func(i, j int) bool { 返回數字 [i] < 數字 [j] }) // 將數字列表轉化為差值列表 差異 := make([]uint64, N) 對於 i, num := 範圍數字 { 如果我==0{ 差異 [i] = 數字 繼續 } 差異 [i] = num - 數字[i-1] }

很棒！這裡有張圖，展示了numbers 和differences 列表。

如你縮減，85 個數字均勻地分佈在整個空間中！所以differences 列表中的數值也非常小。

最後一步是用Golomb-Rice 編碼來編碼這個differences 列表。回憶一下前面的解釋，我們需要用最有可能的數值來除每個差值，然後編碼商和余數。在我們前面的例子中，我說最有可能的數值就是M，而餘數會在[0, M] 之間。但是，BIP158 並不是這麼做的，因為我們發現2，這並不是事實上能讓最終的過濾器體積最小化的參數。所以我們不使用M，而是定義一個新的常量P，並使用2 ^ P 作為Golomb-Rice 參數。 P 定義成19 。這意味著我們要將每一個差值除以2 ^ 19，以獲得商和余數，並且餘數會用19 比特編碼成二進制。

過濾器 := bstream.NewBStreamWriter(0) // 對於differences 列表中的每個數值，通過除以2 ^ P 來獲得商和余數。 對於 _, d := 範圍差異 { q := math.Floor(float64(d)/math.Exp2(float64(P))) r := d - uint64(math.Exp2(float64(P))*q) // 編碼商 對於我：= 0；我 < int(q);我++ { 過濾器.WriteBit(true) } 過濾器.WriteBit(假) 過濾器.WriteBits(r, P) }

很棒！現在我們可以輸出過濾器了，得到：

71d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df57437864023833f 2f 801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b0c 5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12fa2 e 61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270

除了開頭的兩個字節，其餘都跟我們在bitcoind 中得到的過濾器完全一樣！為什麼前面的2 字節會有區別呢？因為BIP 說N 的值需要在CompactSize 格式中編碼，並出現在過濾器的前面，這樣才能被接收者解碼。這是用下列辦法完成的：

fd := 過濾器.Bytes() 緩衝區字節.Buffer buffer.Grow(wire.IntSerializeSize(uint64(N)) + len(fd)) err = 線.WriteInt(&buffer, 0, uint64(N)) 如果錯誤！= nil { 返回零，錯誤 } _, err = buffer.Write(fd) 如果錯誤！= nil { 返回零，錯誤 }

如果我們現在再打印出過濾器，就會發現它跟bitcoind 的結果完全一樣：

5571d126b85aa79c9de56d55995aa292de0484b830680a735793a8c2260113148421279906f800c3b8c94ff37681fb1fd230482518c52df5743786402383 3f 2f801639692646ddcd7976ae4f2e2a1ef58c79b3aed6a705415255e362581692831374a5e5e70d5501cdc0a52095206a15cd2eb98ac980c22466e6945a65a5b0b 0c5b32aa1e0cda2545da2c4345e049b614fcad80b9dc9c903788163822f4361bbb8755b79c276b1cf7952148de1e5ee0a92f6d70c4f522aa6877558f62b34b56ade12 FA 2e61023abf3e570937bf379722bc1b0dc06ffa1c5835bb651b9346a270

成功！

不過，我個人的理解是，不需要把N 加入過濾器中。如果你知道P 的值，那你就能找出N 的值。來看看我們是否能用第一個過濾器輸出恢復初始的數字列表：

b := bstream.NewBStreamReader(過濾器) （ 數字 []uint64 prevNum uint64 ） 為了 { // 從字節串中讀取商。遇到的第一個0 表示商的結尾 // 再遇到0 之前，1 的數量就代表了商 q uint64 c, err := b.ReadBit() 如果錯誤！= nil { 返回錯誤 } 對於 c { q++ c, 錯誤 = b.ReadBit() if 錯誤.Is(err, io.EOF) { 休息 } 否則如果錯誤！= nil { 返回錯誤 } } // 隨後的P 個比特編碼了余數 r, err := b.ReadBits(P) if 錯誤.Is(err, io.EOF) { 休息 } 否則如果錯誤！= nil { 返回錯誤 } n := q*uint64(math.Exp2(float64(P))) + r num := n + 上一個Num 數字 = 附加（數字，num） 上一個編號 = 編號 } fmt.Println(數字)

上述操作會產生相同的數字列表，所以我們可以重構它而無需知曉N 。所以我不確認將N 加入過濾器的理由是什麼。如果你知道為什麼一定要加入N ，請告訴我！

感謝閱讀！