背景
比特幣SPV節(jié)點(diǎn)因?yàn)椴痪哂腥湐?shù)據(jù)，所以無(wú)法對(duì)交易進(jìn)行驗(yàn)證梦裂。必須要從核心客戶端（具備全鏈數(shù)據(jù)的節(jié)點(diǎn)）下載特定的交易進(jìn)行選擇性驗(yàn)證似枕。這樣就產(chǎn)生了隱私風(fēng)險(xiǎn)。比如監(jiān)控網(wǎng)絡(luò)的第三方可以跟蹤某個(gè)SPV節(jié)點(diǎn)上的錢(qián)包所請(qǐng)求的全部交易信息年柠，并且利用這些交易信息可以把錢(qián)包用戶和比特幣地址關(guān)聯(lián)起來(lái)凿歼，從而會(huì)導(dǎo)致失去匿名信。
鑒于此冗恨，比特幣開(kāi)發(fā)人員添加了新功能--Bloom過(guò)濾器答憔，用以解決SPV隱私暴露風(fēng)險(xiǎn)問(wèn)題。Bloom過(guò)濾器通過(guò)一個(gè)采樣概率掀抹，運(yùn)行SPV節(jié)點(diǎn)只接收交易信息的子集虐拓，同時(shí)不會(huì)精確泄露哪些是他們感興趣的
Bloom過(guò)濾器
Bloom過(guò)濾器是一個(gè)允許用戶描述特定關(guān)鍵詞組合而不需要精確描述的基于概率的過(guò)濾方法。假如有個(gè)游客需要詢問(wèn)去某個(gè)特定地址的路線傲武，如果他向陌生人問(wèn)“聯(lián)運(yùn)街88號(hào)在哪里蓉驹？”，這樣他就會(huì)暴露自己的目的地揪利。Bloom過(guò)濾器則會(huì)這樣問(wèn)：“附近有帶聯(lián)字的街道嗎态兴？”這樣就暴露了很少的關(guān)鍵詞。會(huì)得到更多的結(jié)果（包含自己需要的）疟位，保護(hù)了自己的隱私瞻润。
1. SPV節(jié)點(diǎn)會(huì)初始化一個(gè)不匹配任何關(guān)鍵詞的空白Bloom過(guò)濾器。
2. SPV節(jié)點(diǎn)會(huì)創(chuàng)建一個(gè)包含錢(qián)包中所有地址信息的列表，并創(chuàng)建一個(gè)與每個(gè)地址相對(duì)應(yīng)的交易輸出相匹配的搜索模式绍撞。
3. SPV節(jié)點(diǎn)會(huì)將所有的搜索模式放入Bloom過(guò)濾器正勒。這樣只要關(guān)鍵詞出現(xiàn)在交易中就可以被過(guò)濾器識(shí)別出來(lái)。
4. 對(duì)等節(jié)點(diǎn)用收到的Bloom過(guò)濾器來(lái)匹配傳送至SPV節(jié)點(diǎn)的交易楚午。
Bloom過(guò)濾器采用一個(gè)可變的二進(jìn)制數(shù)組（N）和M個(gè)哈希函數(shù)組成昭齐。這些哈希函數(shù)的輸出區(qū)間是[1, N]，該值與二進(jìn)制數(shù)組對(duì)應(yīng)矾柜。且這些哈希函數(shù)必須為確定性函數(shù)（任何一個(gè)節(jié)點(diǎn)使用相同Bloom過(guò)濾器實(shí)現(xiàn)的哈希函數(shù)針對(duì)同樣的輸入最后輸出的結(jié)果是一致的）阱驾。通過(guò)調(diào)節(jié)N和M來(lái)改變Bloom過(guò)濾器的準(zhǔn)確性和私密性。
下面我們用一個(gè)16位的二進(jìn)制數(shù)組和3個(gè)哈希函數(shù)來(lái)演示Bloom過(guò)濾器應(yīng)用原理怪蔑。
Bloom過(guò)濾器數(shù)組中每個(gè)初始值都是0里覆。
將關(guān)鍵詞依次通過(guò)每個(gè)哈希函數(shù)（此例中是3個(gè)）運(yùn)算，輸出M個(gè)在1到N之間的數(shù)缆瓣。二進(jìn)制數(shù)組相應(yīng)的位就置為1喧枷，這就意味著B(niǎo)loom過(guò)濾器記錄下了某個(gè)關(guān)鍵詞
注意：
當(dāng)Bloom過(guò)濾器增加關(guān)鍵詞時(shí)，其中某個(gè)哈希函數(shù)的輸出值對(duì)應(yīng)的二進(jìn)制數(shù)組值可能已經(jīng)是1了弓坞，此時(shí)不改變二進(jìn)制數(shù)組值隧甚。也就是說(shuō)，隨著更多的關(guān)鍵詞指向某個(gè)二進(jìn)制數(shù)組值渡冻，Bloom過(guò)濾器隨著位1的增加而飽和戚扳，準(zhǔn)確性就降低了。準(zhǔn)確性依賴于關(guān)鍵字?jǐn)?shù)量族吻、二進(jìn)制數(shù)組大小和哈希函數(shù)數(shù)量帽借。更大的數(shù)組和更多的哈希函數(shù)會(huì)記錄更多的關(guān)鍵詞，會(huì)提高準(zhǔn)確性超歌；小的數(shù)組及有限的哈希函數(shù)只能記錄有限的關(guān)鍵詞從而降低準(zhǔn)確性砍艾。為了測(cè)試某個(gè)關(guān)鍵詞能否通過(guò)Bloom過(guò)濾器驗(yàn)證，首先將關(guān)鍵詞依次使用哈希函數(shù)運(yùn)算巍举，將運(yùn)算完成的結(jié)果與二進(jìn)制數(shù)組做比較脆荷。如果所有結(jié)果對(duì)應(yīng)的位在二進(jìn)制數(shù)組中都是1，那么這個(gè)關(guān)鍵詞可能在Bloom過(guò)濾器中被記錄了懊悯。如果所有結(jié)果對(duì)應(yīng)的位有一位在二進(jìn)制數(shù)組中為0简烘，那么這個(gè)關(guān)鍵詞肯定不在Bloom過(guò)濾器中被記錄。
