[Bitcoin] ブルームフィルター

軽量クライアントがフルノードに伝えるトランザクション
フルノードはブルームフィルターを介してトランザクションを取り扱い、通過するトランザクションに関しmerkleblockコマンドを送信する

アイテムがどの入れ物に入るかを判断するプロセス

from helper import hash256
bit_field_size=10
bit_field = [0] * bit_field_size
h = hash256(b'hello world')
bit = int.from_bytes(h, 'big') % bit_field_size
bit_field[bit] = 1
print(bit_field)

複数

from helper import hash256
bit_field_size=10
bit_field = [0] * bit_field_size
for item in (b'hello world', b'goodbye'):
	h = hash256(item)
	bit = int.from_bytes(h, 'big') % bit_field_size
	bit_field[bit] = 1
print(bit_field)

### 複数ハッシュ関数を使用するブルームフィルター

from helper import hash256, hash160
bit_field_size=10
bit_field = [0] * bit_field_size
for item in (b'hello world', b'goodbye'):
	for hash_function in (hash256, hash160):
		h = hash_function(item)
		bit = int.from_bytes(h, 'big') % bit_field_size
		bit_field[bit] = 1
print(bit_field)

### BIP0037ブルームフィルター
murmur3と呼ばれるハッシュ関数を使用する

from helper import murmur3
from bloomfilter import BIP37_CONSTANT
field_size = 2
num_functions = 2
tweak = 42
bit_field_size = field_size * 8
bit_field = [0] * bit_field_size
for phrase in (b'hello world', b'goodbye'):
	for i in range(num_functions):
		seed = i * BIP37_CONSTANT + tweak
		h = murmur3(phrase, seed=seed)
		bit = h % bit_field_size
		bit_field[bit] = 1
print(bit_field)

[0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0]

from bloomfilter import BloomFilter, BIP37_CONSTANT
from helper import bit_field_to_bytes, murmur3
field_size = 10
function_count = 5
tweak = 99
items = (b'Hello World', b'Goodbye!')
bit_field_size = field_size * 8
bit_field = [0] * bit_field_size
for item in items:
	for i in range(function_count):
		seed = i * BIP37_CONSTANT + tweak
		h = murmur3(item, seed=seed)
		bit = h % bit_field_size
		bit_field[bit] = 1
print(bit_field_to_bytes(bit_field).hex())

### ブルームフィルターの読み込み

	def filterload(self, flag=1):
		payload = encode_varint(self.size)
		payload += self.filter_bytes()
		payload += int_to_little_endian(self.function_count, 4)
		payload += int_to_little_endian(self.tweak, 4)
		payload += int_to_little_endian(flag, 1)
		return GenericMessage(b'filterload', payload)

class GetDataMessage:
	command = b'getdata'

	def __init__(self):
		self.data = []

	def add_data(self, data_type, identifier):
		self.data.append((data_type, identifier))

	def serialize(self):
		result = encode_varint(len(self.data))
		for data_type, identifier in self.data:
			result += int_to_little_endian(data_type, 4)
			result += identifier[::-1]
		return result

from bloomfilter import BloomFilter
from helper import decode_base58
from merkleblock import MerkleBlock
from network import FILTERED_BLOCK_DATA_TYPE, GetHeadersMessage, GetDataMessage, HeadersMessage, SimpleNode
from tx import Tx
last_block_hex = '00000000000538d5c2246336644f9a4956551afb44ba47278759ec55\
ea912e19'
address = 'mwJn1YPMq7y5F8J3LkC5Hxg9PHyZ5K4cFv'
h160 = decode_base58(address)
node = SimpleNode('testnet.programmingbitcoin.com', testnet=True, logging=False)
bf = BloomFilter(size=30, function_count=5, tweak=90210)
bf.add(h160)
node.handshake()
node.send(bf.filterload())
start_block = bytes.fromhex(last_block_hex)
getheaders = GetHeadersMessage(start_block=start_block)
node.send(getheaders)
headers = node.wait_for(HeadersMessage)
getdata = GetDataMessage()
for b in headers.blocks:
	if not b.check_pow():
		raise RuntimeError('proof of work is invalid')
	getdata.add_data(FILTERED_BLOCK_DATA_TYPE, b.hash())
node.send(getdata)
found = False
while not found:
	message = node.wait_for(MerkleBlock, Tx)
	if message.command == b'merkleblock':
		if not message.is_valid():
			raise RuntimeError('invalid merkle proof')
		else:
			for i, tx_out in enumerate(message.tx_outs):
				if tx_out.script_pubkey.address(testnet=True) == address:
					print('found: {}:{}'.format(message.id(), i))
					found = True
					break