BIP158: Compact Block Filters – Trezor Blog


Bitcoin Core 0.19, released in November 2019, contains an exciting addition called Compact Block Filters (BIP158), which are a replacement for Bloom Filters (BIP37) disabled in the same release.

These filters provide a space-efficient and fast way for testing whether an element is a member of a set. In this particular use-case, to tell whether a particular block somehow affects an address (more precisely an output script). Although the check may produce false positives (saying the block does affect the address when it does not), the chances are minimal (1 in 784931). Still, the check will never produce a false negative (saying the block does not affect the address when it does). This makes it ideal for filtering out the vast majority of blocks we want to process without the need to download them first. Compact Block Filters use Golomb-coded sets (GCS), which have an advantage over Bloom filters by providing the same false-positive rate with much less size.

To enable this new feature, you need to add the blockfilterindex=1 option into your bitcoin.conf file and restart the daemon. Doing so will build a “blockfilter” index, which takes around 5 GiB of disk space and 1 hour to create. Once enabled, you’ll be able to use a new RPC method called getblockfilter.

How do these filters work practically? Let’s have a look at block #926485 on the Bitcoin testnet:

$ bitcoin-cli -testnet getblockhash 926485000000000000015d6077a411a8f5cc95caf775ccf11c54e27df75ce58d187313

The hash of the block is 000000000000015d6077a411a8f5cc95caf775ccf11c54e27df75ce58d187313. Let’s have a look at its filter (the getblockfilter call needs block hash as its argument, not the block height):

$ bitcoin-cli -testnet getblockfilter 000000000000015d6077a411a8f5cc95caf775ccf11c54e27df75ce58d187313{ "filter": "09027acea61b6cc3fb33f5d52f7d088a6b2f75d234e89ca800",
"header": "546c574a0472144bcaf9b6aeabf26372ad87c7af7d1ee0dbfae5e099abeae49c" }

The call returns two values — “filter” and “header.” In our experiments, we’ll be using just the “filter” field. The “header” field described in BIP157 is there to verify the chain of filter values.

Let’s rewrite the bitcoin-cli commands above to Javascript:

const Client = require('bitcoin-core');const rpc = new Client({ network: 'testnet' });rpc.command('getblockhash', 926485).then((hash) => {
console.log(hash);
rpc.command('getblockfilter', hash).then((filter) => {
console.log(filter);
});
});

Running this via node will produce the more-or-less the same output:

000000000000015d6077a411a8f5cc95caf775ccf11c54e27df75ce58d187313{
filter: '09027acea61b6cc3fb33f5d52f7d088a6b2f75d234e89ca800',
header: '546c574a0472144bcaf9b6aeabf26372ad87c7af7d1ee0dbfae5e099abeae49c'
}

We now know that09027acea61b6cc3fb33f5d52f7d088a6b2f75d234e89ca800 is a Golomb-coded set (GCS) constructed for block #926485, but how do we use it?

First, we create a Golomb-coded set filter (GCSFilter) and initialize it with the filter value from above. Value P is set to 19 as defined in BIP158.

const GCSFilter = require('golomb');const block_filter = Buffer.from("09027acea61b6cc3fb33f5d52f7d088a6b2f75d234e89ca800", "hex");const P = 19;const filter = GCSFilter.fromNBytes(P, block_filter);

Next, we need to construct a key, which we set to lower 128 bits of the block hash.

const block_hash = Buffer.from("000000000000015d6077a411a8f5cc95caf775ccf11c54e27df75ce58d187313", "hex");const key = block_hash.reverse().slice(0, 16);

Now, we are ready to do queries using the filter. Let’s prepare three scripts we want to check. The first and the second belong to the addresses modified via transactions within the block (mmEfi2cW9Vizeau3E6zzmRvbmzJXNrmW9Z and my2hmDuD9XjmtQWFu9HyyNAsE5WGSDBKpQ). The third one is a made-up value.

const script1 = Buffer.from("76a9143ebc40e411ed3c76f86711507ab952300890397288ac", "hex");  // mmEfi2cW9Vizeau3E6zzmRvbmzJXNrmW9Z
const script2 = Buffer.from("76a914c01a7ca16b47be50cbdbc60724f701d52d75156688ac", "hex"); // my2hmDuD9XjmtQWFu9HyyNAsE5WGSDBKpQ
const script3 = Buffer.from("76a914000000000000000000000000000000000000000088ac", "hex"); // made-up

Finally, we can use either filter.match() function to check an individual value or filter.matchAny() for a list (the function returns true if any of the provided values match).

console.log(filter.match(key, script1));
console.log(filter.match(key, script2));
console.log(filter.match(key, script3));
console.log(filter.matchAny(key, [script1, script3]));

When we run this code, we’ll get the following result. That was easy, right?

true
true
false
true



Source link

Comments (No)

Leave a Reply