布隆過濾器(Bloom Filter)，可以不用知道一個(gè)塊里的所有交易數(shù)據(jù)，而只用下載很少的數(shù)據(jù)，就能知道一個(gè)交易是否在一個(gè)塊里(如果在塊里，那么一定告訴你在塊里，如果不在塊里，有很小概率告訴你在塊里). 算法的設(shè)計(jì)的還是很妙的，值得去學(xué)習(xí)一下這種概率型算法思維。

原理：

Step1 :

假設(shè)一個(gè)塊有n個(gè)交易，那么做一個(gè)m=2*n長度的bit array，這里稱為A

用一個(gè)hash函數(shù)把交易映射到A的響應(yīng)位置x=hash[transaction], 并設(shè)置A[x]=1。并不處理沖突的情況。

那么查交易的時(shí)候，如果交易在塊里的話A[hash[transation]]一定為1，

如果不在塊里的話，A[hash[transaction]]為1的概率<=1/2 (因?yàn)锳的長度m=2*n)。

現(xiàn)在這個(gè)算法的問題是1/2的誤報(bào)概率太大了。

Step2:?

做多個(gè)bit array, A1, A2 ... Ak.?

先看兩個(gè)bit array的情況： 用個(gè)兩個(gè)不同的hash函數(shù)來填充A1,A2.

對一筆不在塊里的交易，A1,A2相對應(yīng)位置都為1的概率是1/2*1/2= 1/4，優(yōu)化了很多

假設(shè)用10個(gè)bit array, 那么誤報(bào)的概率為(1/2)^10 = 1/1024,是一個(gè)非常小的數(shù)字。

也就是說為了達(dá)到p的誤報(bào)率，就用log2(1/p)個(gè)bit array就可以了

通過記錄這些很少的hash數(shù)據(jù)，比特幣的輕錢包可以快速定位交易在哪個(gè)塊里。