BIP-158: 緊湊區塊過濾器

Basic Filter（類型 0x00）

包含：

• • 區塊中所有交易輸出的 scriptPubKey
• • 區塊中所有交易輸入花費的 scriptPubKey（不含 coinbase）

這足以讓錢包發現與自己地址相關的交易。

給定參數 P（2 的冪次），對數值 x 編碼：

1. 計算商 q = x / P
2. 計算餘數 r = x % P

3. 編碼 q：使用一元碼（q 個 1 後跟一個 0）
4. 編碼 r：使用 log2(P) 個位元

範例（P = 4, x = 11）：
• q = 11 / 4 = 2
• r = 11 % 4 = 3
• 編碼 = 110（一元碼）+ 11（2 位元）= 11011

構建過濾器的步驟：

1. 收集元素
   elements = [scriptPubKey1, scriptPubKey2, ...]

2. 計算哈希值（使用 SipHash）
   hashes = [SipHash(key, e) for e in elements]

   key = 前一個區塊哈希的前 16 bytes

3. 縮放到目標範圍
   F = N * M  // N = 元素數量，M = 假陽性參數
   scaled = [(h * F) >> 64 for h in hashes]

4. 排序並計算差值
   sorted = sort(scaled)
   deltas = [sorted[i] - sorted[i-1] for i in range(1, N)]

5. Golomb-Rice 編碼差值
   encoded = GolombRice_encode(deltas, P)

查詢過濾器的步驟：

1. 計算查詢元素的哈希和縮放值
   query_hash = SipHash(key, query_script)
   query_scaled = (query_hash * N * M) >> 64

2. 解碼過濾器，重建排序後的值集合
   values = decode_filter(filter_data)

3. 二分搜索
   return binary_search(values, query_scaled)

假陽性場景：
• 查詢返回 True，但區塊實際不包含該腳本
• 發生機率 ≈ 1/M ≈ 1/784931
• 每約 1200 個區塊會有一次假陽性