bloom filterの全体像。ハッシュ化した値をインデックス番号にして、bloom_filterの値を更新する。
bloom filterにハッシュ値が入っているかどうか確認することで、bloom filterに登録されているかを判定する。
bloom_filter = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
def hash_a(val):
return hash_val
def hash_b(val):
return hash_val
val = "hello world"
a_hashed = hash_a(val) # 1
b_hashed = hash_b(val) # 4
bloom_filter[a_hashed] = 1
bloom_filter[b_hashed] = 1
[0, 1, 0, 0, 4, 0, 0, 0, 0, 0]
bloom_filter[a_hashed]
bloom_filter[b_hashed]
import functools
class BloomFilter:
def __init__(self, filter_size):
self.filter_size = filter_size
self.bloom_filter = [0 for _ in range(filter_size)]
def set_v(self, val):
indexes = self.n_hash(val)
for index in indexes:
self.bloom_filter[index] = 1
def n_hash(self, val):
hashed = abs(hash(val))
d_lst = [int(n) for n in str(hashed)]
return [
self._hash_common(lambda acc, d: acc + d, d_lst),
self._hash_common(lambda acc, d: acc + 3 * d, d_lst),
]
def _hash_common(self, func, d_lst):
execed = abs(functools.reduce(func, d_lst, 0))
while execed >= self.filter_size:
execed = execed / self.filter_size
return int(execed)
def exist_v(self, val):
indexes = self.n_hash(val)
for index in indexes:
if self.bloom_filter[index] == 0:
return False
return True
bf = BloomFilter(10)
print(bf.bloom_filter)
bf.set_v(3)
print(bf.bloom_filter)
print(bf.exist_v(3))
print(bf.exist_v(10))
$ python3 bloom_filter.py
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0, 0, 0, 0, 1]
True
False
BTCではSPVがScriptPubKeyをbloomfilterにセットして、リモートノードがマッチングアルゴリズムで判定する。
-> リモートノード側では、トランザクションごとに、ScriptPubKey, Outpointがマッチするかを判定して、マッチする場合はブルームフィルタを更新している。
なるほど、直接pubkeyのデータをやり取りしない分、安全性が向上するということね。これをRustでやりたい。
文字列を数値に変換するには、文字列を数値として持っておいて、それを変換でしょうか。
static ASCII_LOWER: [char; 26] = [
'a', 'b', 'c', 'd', 'e',
'f', 'g', 'h', 'i', 'j',
'k', 'l', 'm', 'n', 'o',
'p', 'q', 'r', 's', 't',
'u', 'v', 'w', 'x', 'y',
'z',
];