Skip to content

Commit 0b28060

Browse files
petertoddpetertodd
committed
Implement CBloomFilter class
Currently missing IsRelevantAndUpdate(), but that isn't very useful unless you are a full node.
1 parent 417afe9 commit 0b28060

2 files changed

Lines changed: 170 additions & 0 deletions

File tree

‎bitcoin/bloom.py‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
2+
#
3+
# bloom.py
4+
#
5+
# Distributed under the MIT/X11 software license, see the accompanying
6+
# file COPYING or http://www.opensource.org/licenses/mit-license.php.
7+
#
8+
9+
import struct
10+
import math
11+
from bitcoin.serialize import *
12+
from bitcoin.coredefs import *
13+
from bitcoin.core import *
14+
from bitcoin.hash import MurmurHash3
15+
16+
class CBloomFilter(object):
17+
# 20,000 items with fp rate < 0.1% or 10,000 items and <0.0001%
18+
MAX_BLOOM_FILTER_SIZE = 36000
19+
MAX_HASH_FUNCS = 50
20+
21+
UPDATE_NONE = 0
22+
UPDATE_ALL = 1
23+
UPDATE_P2PUBKEY_ONLY = 2
24+
UPDATE_MASK = 3
25+
26+
def __init__(self, nElements, nFPRate, nTweak, nFlags):
27+
"""Create a new bloom filter
28+
29+
The filter will have a given false-positive rate when filled with the
30+
given number of elements.
31+
32+
Note that if the given parameters will result in a filter outside the
33+
bounds of the protocol limits, the filter created will be as close to
34+
the given parameters as possible within the protocol limits. This will
35+
apply if nFPRate is very low or nElements is unreasonably high.
36+
37+
nTweak is a constant which is added to the seed value passed to the
38+
hash function It should generally always be a random value (and is
39+
largely only exposed for unit testing)
40+
41+
nFlags should be one of the UPDATE_* enums (but not _MASK)
42+
"""
43+
LN2SQUARED = 0.4804530139182014246671025263266649717305529515945455
44+
LN2 = 0.6931471805599453094172321214581765680755001343602552
45+
self.vData = bytearray(int(min(-1 / LN2SQUARED * nElements * math.log(nFPRate), self.MAX_BLOOM_FILTER_SIZE * 8) / 8))
46+
self.nHashFuncs = int(min(len(self.vData) * 8 / nElements * LN2, self.MAX_HASH_FUNCS))
47+
self.nTweak = nTweak
48+
self.nFlags = nFlags
49+
50+
def bloom_hash(self, nHashNum, vDataToHash):
51+
return MurmurHash3(((nHashNum * 0xFBA4C795) + self.nTweak) & 0xFFFFFFFF, vDataToHash) % (len(self.vData) * 8)
52+
53+
__bit_mask = bytearray([0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80])
54+
def insert(self, elem):
55+
"""Insert an element in the filter.
56+
57+
elem may be a COutPoint or bytes
58+
"""
59+
if isinstance(elem, COutPoint):
60+
elem = elem.serialize()
61+
62+
if len(self.vData) == 1 and self.vData[0] == 0xff:
63+
return
64+
65+
for i in range(0, self.nHashFuncs):
66+
nIndex = self.bloom_hash(i, elem)
67+
# Sets bit nIndex of vData
68+
self.vData[nIndex >> 3] |= self.__bit_mask[7 & nIndex]
69+
70+
def contains(self, elem):
71+
"""Test if the filter contains an element
72+
73+
elem may be a COutPoint or bytes
74+
"""
75+
if isinstance(elem, COutPoint):
76+
elem = elem.serialize()
77+
78+
if len(self.vData) == 1 and self.vData[0] == 0xff:
79+
return True
80+
81+
for i in range(0, self.nHashFuncs):
82+
nIndex = self.bloom_hash(i, elem)
83+
if not (self.vData[nIndex >> 3] & self.__bit_mask[7 & nIndex]):
84+
return False
85+
return True
86+
87+
def IsWithinSizeConstraints(self):
88+
return len(self.vData) <= self.MAX_BLOOM_FILTER_SIZE and self.nHashFuncs <= self.MAX_HASH_FUNCS
89+
90+
def IsRelevantAndUpdate(tx, tx_hash):
91+
# Not useful for a client, so not implemented yet.
92+
raise NotImplementedError
93+
94+
__struct = struct.Struct("<IIB")
95+
def deserialize(self, f):
96+
self.vData = deser_string(f)
97+
(self.nHashFuncs,
98+
self.nTweak,
99+
self.nFlags) = self.__struct.unpack(f.read(self.__struct.size))
100+
101+
def serialize(self):
102+
r = ser_string(self.vData)
103+
return r + self.__struct.pack(self.nHashFuncs, self.nTweak, self.nFlags)

‎bitcoin/tests/test_bloom.py‎

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
# Distributed under the MIT/X11 software license, see the accompanying
2+
# file COPYING or http://www.opensource.org/licenses/mit-license.php.
3+
4+
from __future__ import print_function
5+
6+
import json
7+
import os
8+
import unittest
9+
10+
from binascii import unhexlify
11+
12+
from bitcoin.bloom import *
13+
14+
class Test_CBloomFilter(unittest.TestCase):
15+
def test_create_insert_serialize(self):
16+
filter = CBloomFilter(3, 0.01, 0, CBloomFilter.UPDATE_ALL)
17+
18+
def T(elem):
19+
"""Filter contains elem"""
20+
elem = unhexlify(elem)
21+
filter.insert(elem)
22+
self.assertTrue(filter.contains(elem))
23+
24+
def F(elem):
25+
"""Filter does not contain elem"""
26+
elem = unhexlify(elem)
27+
self.assertFalse(filter.contains(elem))
28+
29+
T('99108ad8ed9bb6274d3980bab5a85c048f0950c8')
30+
F('19108ad8ed9bb6274d3980bab5a85c048f0950c8')
31+
T('b5a2c786d9ef4658287ced5914b37a1b4aa32eee')
32+
T('b9300670b4c5366e95b2699e8b18bc75e5f729c5')
33+
34+
self.assertEqual(filter.serialize(), unhexlify('03614e9b050000000000000001'))
35+
36+
def test_create_insert_serialize_with_tweak(self):
37+
# Same test as bloom_create_insert_serialize, but we add a nTweak of 100
38+
filter = CBloomFilter(3, 0.01, 2147483649, CBloomFilter.UPDATE_ALL)
39+
40+
def T(elem):
41+
"""Filter contains elem"""
42+
elem = unhexlify(elem)
43+
filter.insert(elem)
44+
self.assertTrue(filter.contains(elem))
45+
46+
def F(elem):
47+
"""Filter does not contain elem"""
48+
elem = unhexlify(elem)
49+
self.assertFalse(filter.contains(elem))
50+
51+
T('99108ad8ed9bb6274d3980bab5a85c048f0950c8')
52+
F('19108ad8ed9bb6274d3980bab5a85c048f0950c8')
53+
T('b5a2c786d9ef4658287ced5914b37a1b4aa32eee')
54+
T('b9300670b4c5366e95b2699e8b18bc75e5f729c5')
55+
56+
self.assertEqual(filter.serialize(), unhexlify('03ce4299050000000100008001'))
57+
58+
def test_bloom_create_insert_key(self):
59+
filter = CBloomFilter(2, 0.001, 0, CBloomFilter.UPDATE_ALL)
60+
61+
pubkey = unhexlify('045B81F0017E2091E2EDCD5EECF10D5BDD120A5514CB3EE65B8447EC18BFC4575C6D5BF415E54E03B1067934A0F0BA76B01C6B9AB227142EE1D543764B69D901E0')
62+
pubkeyhash = ser_uint160(Hash160(pubkey))
63+
64+
filter.insert(pubkey)
65+
filter.insert(pubkeyhash)
66+
67+
self.assertEqual(filter.serialize(), unhexlify('038fc16b080000000000000001'))

0 commit comments

Comments
 (0)