布隆過濾器(Bloom Filter)均芽，可以不用知道一個塊里的所有交易數(shù)據(jù)丘逸，而只用下載很少的數(shù)據(jù)，就能知道一個交易是否在一個塊里(如果在塊里掀宋，那么一定告訴你在塊里深纲，如果不在塊里，有很小概率告訴你在塊里). 算法的設(shè)計的還是很妙的劲妙，值得去學習一下這種概率型算法思維湃鹊。
原理：
Step1 :
假設(shè)一個塊有n個交易，那么做一個m=2*n長度的bit array镣奋，這里稱為A
用一個hash函數(shù)把交易映射到A的響應(yīng)位置x=hash[transaction], 并設(shè)置A[x]=1币呵。并不處理沖突的情況。
那么查交易的時候侨颈，如果交易在塊里的話A[hash[transation]]一定為1余赢，
如果不在塊里的話，A[hash[transaction]]為1的概率<=1/2 (因為A的長度m=2*n)哈垢。
現(xiàn)在這個算法的問題是1/2的誤報概率太大了妻柒。
Step2:?
做多個bit array, A1, A2 ... Ak.?
先看兩個bit array的情況： 用個兩個不同的hash函數(shù)來填充A1,A2.
對一筆不在塊里的交易，A1,A2相對應(yīng)位置都為1的概率是1/2*1/2= 1/4耘分，優(yōu)化了很多
假設(shè)用10個bit array, 那么誤報的概率為(1/2)^10 = 1/1024,是一個非常小的數(shù)字举塔。
也就是說為了達到p的誤報率绑警，就用log2(1/p)個bit array就可以了
通過記錄這些很少的hash數(shù)據(jù)，比特幣的輕錢包可以快速定位交易在哪個塊里央渣。
