From 25ee74dd11401ce2bfb0b24c4ce70578c5b99e51 Mon Sep 17 00:00:00 2001 From: Sebastian Falbesoner Date: Wed, 19 Oct 2022 18:57:09 +0200 Subject: test: add SipHash implementation for generic data in Python We will need this in the next commit to calculate ranged hashes of scriptPubKeys as defined in BIP158. --- test/functional/test_framework/siphash.py | 56 ++++++++++++++++--------------- 1 file changed, 29 insertions(+), 27 deletions(-) (limited to 'test') diff --git a/test/functional/test_framework/siphash.py b/test/functional/test_framework/siphash.py index 85836845d4..5ad245cf1b 100644 --- a/test/functional/test_framework/siphash.py +++ b/test/functional/test_framework/siphash.py @@ -1,15 +1,17 @@ #!/usr/bin/env python3 -# Copyright (c) 2016-2018 The Bitcoin Core developers +# Copyright (c) 2016-2022 The Bitcoin Core developers # Distributed under the MIT software license, see the accompanying # file COPYING or http://www.opensource.org/licenses/mit-license.php. -"""Specialized SipHash-2-4 implementations. +"""SipHash-2-4 implementation. -This implements SipHash-2-4 for 256-bit integers. +This implements SipHash-2-4. For convenience, an interface taking 256-bit +integers is provided in addition to the one accepting generic data. """ def rotl64(n, b): return n >> (64 - b) | (n & ((1 << (64 - b)) - 1)) << b + def siphash_round(v0, v1, v2, v3): v0 = (v0 + v1) & ((1 << 64) - 1) v1 = rotl64(v1, 13) @@ -27,37 +29,37 @@ def siphash_round(v0, v1, v2, v3): v2 = rotl64(v2, 32) return (v0, v1, v2, v3) -def siphash256(k0, k1, h): - n0 = h & ((1 << 64) - 1) - n1 = (h >> 64) & ((1 << 64) - 1) - n2 = (h >> 128) & ((1 << 64) - 1) - n3 = (h >> 192) & ((1 << 64) - 1) + +def siphash(k0, k1, data): + assert(type(data) == bytes) v0 = 0x736f6d6570736575 ^ k0 v1 = 0x646f72616e646f6d ^ k1 v2 = 0x6c7967656e657261 ^ k0 - v3 = 0x7465646279746573 ^ k1 ^ n0 - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0 ^= n0 - v3 ^= n1 - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0 ^= n1 - v3 ^= n2 + v3 = 0x7465646279746573 ^ k1 + c = 0 + t = 0 + for d in data: + t |= d << (8 * (c % 8)) + c = (c + 1) & 0xff + if (c & 7) == 0: + v3 ^= t + v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) + v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) + v0 ^= t + t = 0 + t = t | (c << 56) + v3 ^= t v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0 ^= n2 - v3 ^= n3 - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0 ^= n3 - v3 ^= 0x2000000000000000 - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) - v0 ^= 0x2000000000000000 - v2 ^= 0xFF + v0 ^= t + v2 ^= 0xff v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) v0, v1, v2, v3 = siphash_round(v0, v1, v2, v3) return v0 ^ v1 ^ v2 ^ v3 + + +def siphash256(k0, k1, num): + assert(type(num) == int) + return siphash(k0, k1, num.to_bytes(32, 'little')) -- cgit v1.2.3 From 3bca6cd61a8cd677023f18c146f2a6534829b1c7 Mon Sep 17 00:00:00 2001 From: Sebastian Falbesoner Date: Wed, 19 Oct 2022 19:12:43 +0200 Subject: test: add compact block filter (BIP158) helper routines By now, we add one helper for calculating ranged hashes and another one for finding relevant scriptPubKeys given a block. --- test/functional/test_framework/blockfilter.py | 49 +++++++++++++++++++++++++++ 1 file changed, 49 insertions(+) create mode 100644 test/functional/test_framework/blockfilter.py (limited to 'test') diff --git a/test/functional/test_framework/blockfilter.py b/test/functional/test_framework/blockfilter.py new file mode 100644 index 0000000000..a30e37ea5b --- /dev/null +++ b/test/functional/test_framework/blockfilter.py @@ -0,0 +1,49 @@ +#!/usr/bin/env python3 +# Copyright (c) 2022 The Bitcoin Core developers +# Distributed under the MIT software license, see the accompanying +# file COPYING or http://www.opensource.org/licenses/mit-license.php. +"""Helper routines relevant for compact block filters (BIP158). +""" +from .siphash import siphash + + +def bip158_basic_element_hash(script_pub_key, N, block_hash): + """ Calculates the ranged hash of a filter element as defined in BIP158: + + 'The first step in the filter construction is hashing the variable-sized + raw items in the set to the range [0, F), where F = N * M.' + + 'The items are first passed through the pseudorandom function SipHash, which takes a + 128-bit key k and a variable-sized byte vector and produces a uniformly random 64-bit + output. Implementations of this BIP MUST use the SipHash parameters c = 2 and d = 4.' + + 'The parameter k MUST be set to the first 16 bytes of the hash (in standard + little-endian representation) of the block for which the filter is constructed. This + ensures the key is deterministic while still varying from block to block.' + """ + M = 784931 + block_hash_bytes = bytes.fromhex(block_hash)[::-1] + k0 = int.from_bytes(block_hash_bytes[0:8], 'little') + k1 = int.from_bytes(block_hash_bytes[8:16], 'little') + return (siphash(k0, k1, script_pub_key) * (N * M)) >> 64 + + +def bip158_relevant_scriptpubkeys(node, block_hash): + """ Determines the basic filter relvant scriptPubKeys as defined in BIP158: + + 'A basic filter MUST contain exactly the following items for each transaction in a block: + - The previous output script (the script being spent) for each input, except for + the coinbase transaction. + - The scriptPubKey of each output, aside from all OP_RETURN output scripts.' + """ + spks = set() + for tx in node.getblock(blockhash=block_hash, verbosity=3)['tx']: + # gather prevout scripts + for i in tx['vin']: + if 'prevout' in i: + spks.add(bytes.fromhex(i['prevout']['scriptPubKey']['hex'])) + # gather output scripts + for o in tx['vout']: + if o['scriptPubKey']['type'] != 'nulldata': + spks.add(bytes.fromhex(o['scriptPubKey']['hex'])) + return spks -- cgit v1.2.3 From fa54d3011ed0cbb7bcdc76548423ba41f0042832 Mon Sep 17 00:00:00 2001 From: Sebastian Falbesoner Date: Wed, 19 Oct 2022 19:22:28 +0200 Subject: test: check for false-positives in rpc_scanblocks.py --- test/functional/rpc_scanblocks.py | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) (limited to 'test') diff --git a/test/functional/rpc_scanblocks.py b/test/functional/rpc_scanblocks.py index 39f091fd1a..68c84b17a2 100755 --- a/test/functional/rpc_scanblocks.py +++ b/test/functional/rpc_scanblocks.py @@ -3,6 +3,10 @@ # Distributed under the MIT software license, see the accompanying # file COPYING or http://www.opensource.org/licenses/mit-license.php. """Test the scanblocks RPC call.""" +from test_framework.blockfilter import ( + bip158_basic_element_hash, + bip158_relevant_scriptpubkeys, +) from test_framework.messages import COIN from test_framework.test_framework import BitcoinTestFramework from test_framework.util import ( @@ -71,6 +75,28 @@ class ScanblocksTest(BitcoinTestFramework): assert(blockhash in node.scanblocks( "start", [{"desc": f"pkh({parent_key}/*)", "range": [0, 100]}], height)['relevant_blocks']) + # check that false-positives are included in the result now; note that + # finding a false-positive at runtime would take too long, hence we simply + # use a pre-calculated one that collides with the regtest genesis block's + # coinbase output and verify that their BIP158 ranged hashes match + genesis_blockhash = node.getblockhash(0) + genesis_spks = bip158_relevant_scriptpubkeys(node, genesis_blockhash) + assert_equal(len(genesis_spks), 1) + genesis_coinbase_spk = list(genesis_spks)[0] + false_positive_spk = bytes.fromhex("001400000000000000000000000000000000000cadcb") + + genesis_coinbase_hash = bip158_basic_element_hash(genesis_coinbase_spk, 1, genesis_blockhash) + false_positive_hash = bip158_basic_element_hash(false_positive_spk, 1, genesis_blockhash) + assert_equal(genesis_coinbase_hash, false_positive_hash) + + assert(genesis_blockhash in node.scanblocks( + "start", [{"desc": f"raw({genesis_coinbase_spk.hex()})"}], 0, 0)['relevant_blocks']) + assert(genesis_blockhash in node.scanblocks( + "start", [{"desc": f"raw({false_positive_spk.hex()})"}], 0, 0)['relevant_blocks']) + + # TODO: after an "accurate" mode for scanblocks is implemented (e.g. PR #26325) + # check here that it filters out the false-positive + # test node with disabled blockfilterindex assert_raises_rpc_error(-1, "Index is not enabled for filtertype basic", self.nodes[1].scanblocks, "start", [f"addr({addr_1})"]) -- cgit v1.2.3