布隆過濾器、SPV和比特幣

最新 05-28

布隆過濾器（Bloom Filter）是什麼？

布隆過濾器（Bloom Filter）是1970年由布隆提出的，它實際上是由一個很長的二進位向量和一系列隨意映射函數組成。

它是一種基於概率的數據結構，主要用來判斷某個元素是否在集合內，它具有運行速度快（時間效率），佔用內存小的優點（空間效率），但是有一定的誤識別率和刪除困難的問題。它能夠告訴你某個元素一定不在集合內或可能在集合內。

為什麼說可能在集合內而無法確定一定在集合內呢？而一定不在集合內為什麼又能則可以百分百確定呢？下面我們通過分析布隆過濾器的原理來解釋。

在軟體設計時，我們經常要判斷一個元素是否在一個集合中。如：網路爬蟲時，一個網址是否已經被訪問過、一個郵件地址是否在黑名單中、在文字處理軟體中某個英文單詞是否拼寫正確等。一個直接的方法是，將集合中的所有元素都存儲在計算機中（如保存在鏈表、樹、哈希表等數據結構）。當要判斷一個新元素的時候，直接跟集合中的已存儲元素對比即可判斷元素是否在集合中。但是，當隨著加入的數據量增加，我們需要存儲元素的空間就越來越大，而且檢索速度也會開始變慢。鏈表、樹、哈希表的數據結構檢索時間複雜度分別為：O(n)、O(logn)、O(n/k)。

舉個例子，像Gmail這種郵件服務提供商，要過濾垃圾郵件。如果採用上面說的方法，將垃圾郵件加入到哈希表中，那至少要加入數十億的垃圾郵件地址。沒存儲一個億的email地址，就需要1.6GB（將一個email地址轉換成一個8位元組的信息指紋並存入到哈希表中。由於哈希表的存儲效率一般只有50%（為什麼是50%，可以看這篇文章），所以實際存儲一個email地址需要16位元組，一個億的email地址就大概需要1.6GB的內存空間，如果存儲幾十億的email地址，就可能需要幾十上百的內存空間）。

所以傳統的存儲方法要求要大量的存儲空間。而採用布隆過濾器，它只需要哈希表的1/8或1/4的大小（也就是只需要200MB或400MB的空間）就可以解決問題。下面我們來看看布隆過濾器是怎麼做到的（原理）。

布隆過濾器是一個基於m位的比特向量（b1,b2…,bm），這些比特向量的初始值為0。同時還有一系列的哈希函數（h1,h2…,hk），這些哈希函數運算後的哈希值範圍在[1, m]內。

如下圖，就是x、y、z三個元素插入到布隆過濾器中，並判斷w值是否在集合中的示意圖。

上圖中，m=18，k=3，h1、h2和h3是三個哈希函數將輸入值分別映射成比特向量上的某個位置上。

插入x值（對應紅線），則將經過h1、h2和h3三個哈希函數映射到的比特向量上的值改為1。

y（對應綠線）和z（對應藍線）值也一樣操作。

如果要查找x、y、z，通過布隆過濾器可以找到對應的比特向量都為1，我們只能確定想x、y、z可能在集合中。這裡我們我上圖中，可以發現，x和z在h2哈希函數映射後映射到的是同一個比特向量位置（第6個），同時y和z在經過h3映射後也是同一個比特向量位置（第12個）。也就是說，當我們通過布隆過濾器判斷一個元素是否在集合中時，即使對應的比特向量位置全為1，也可能是其他元素映射後導致的。如果要查找w值，經過哈希映射後，可以發現有一個比特向量上的值不為1，那就可以判斷，w值一定不在集合中。

所以布隆過濾器只能判斷一個元素可能在集合中。而且插入的數據越多，誤報的概率也越大。具體關於誤報概率的分析可以參考wiki文章：Probability of false positive。

也就是說，誤報率跟數據集的容量大小n、哈希行數個數k和總比特數m相關。而當布隆過濾器的空間使用率為50%的時候，其誤報率是最小，具體數學證明我就不展開，可以看看這篇文章的數學分析過程：《布隆過濾器詳解》。

相比於哈希表、鏈表等數據結構，其空間和時間的優勢明顯。而且布隆過濾器的插入、查詢時間都是常數O(k)，也就是說每次想要插入或查詢一個元素是否在集合中時，只需要使用k個哈希函數對元素求值，並將對應的比特位標記或檢查對應的比特位即可。

一般情況下，無法從布隆過濾器中刪除元素。因為在刪除元素之前，我們需要確認一個元素是否在集合中，而我們知道布隆過濾器只能給出可能在集合中或者一定不在集合中的回復，而無法給出是否一定在集合中的回復。

在實際應用中，我們要設計一個布隆過濾器，只需要確定數據集的容量大小n和誤報率P這兩個參數。

輸出：

比特幣中布隆過濾器是在BIP-0037中提到。下面我們通過「比特幣錢包如何知道有多少錢」的問題來介紹布隆過濾器在比特幣中的應用。這個問題其實就是「比特幣錢包如何知道有多少UTXO」

備註：UTXO的概念可以閱讀《比特幣交易原理分析》。

在《Merkle樹和SPV機制》文章中，我們提到過比特幣網路中主要有兩種節點類型：

全節點：存放所有區塊數據和交易

SPV節點：只存放區塊頭（Block Header）

我們假設，比特幣錢包最開始值存儲了私鑰，沒有任何其他數據。那麼它要獲取跟自己地址相關的UTXO，只能向比特幣網路中相鄰的全節點詢問，詢問的方式有3中：

方法一：下載完整的區塊鏈賬本，自己查找

這種方法很簡單，也能隱藏用戶的隱私（全節點無法知道SPV節點關聯的錢包的地址）。但是在手機端是不現實的，每次用戶需要下載上百G的區塊鏈數據，才能知道自己錢包有多少錢，雖然保護了用戶隱私，但是浪費了存儲空間和帶寬。所以這種方法不行，而這也是為什麼有SPV的概念存在，中本聰也是考慮到移動支付的場景的。

方法二：直接告訴全節點自己錢包的所有地址，全節點返回所有跟錢包地址相關的UTXO

這種方法直接等於是泄露了用戶隱私，其他全節點就知道SPV節點所關聯的錢包地址。但是好處是所要下載的數據少了很多，也更精確了。

方法三：告訴全節點部分自己錢包的地址信息，全節點返回可能相關的UTXO

這種方法實際上就是採用布隆過濾器的方法隱藏用戶隱私，從而做到即保護用戶隱私，又節省存儲空間和帶寬。在前面的章節，我們知道布隆過濾器的兩個特點：只能告訴你某個元素可能存在集合中以及某個元素一定不存在集合中。這裡可以簡單理解Bloom Filter就是一個過濾器，用來過濾不屬於錢包的UTXO。

錢包節點（SPV節點）會以布隆過濾器的形式告訴相鄰全節點自己地址信息，那麼根據布隆過濾器的特性，會有兩種結果：

沒有通過布隆過濾器過濾出來的UTXO，就【一定】不屬於錢包地址

通過布隆過濾器過濾出來的UTXO，【可能】屬於錢包地址

這種方法雖然在一定程度上保護用戶隱私，節省了存儲空間和帶寬，但是根據布隆過濾器的特點，我們知道，隨著錢包交易的UTXO越多，布隆過濾器誤報率會越高，也就是相鄰全節點返回正確的UTXO概率越低。