Mar 14, 2025

Right, and my point is that the block filter index for the whole chain is like 8GB

Which is one reason it's so fast

If you could build some kind of index like that, but for spends, it could massively reduce the amount of data needed to be scanned on the first pass

then if you hit a positive, you can check whether it's real or false. in my experience the false positive rate is configurable but can be very low, at the expense of a bit more computation. again, not sure if any of this is helpful, but i'm just throwing out ideas

That’s way too big.

You may not be aware but we already implement this, and support an index for it in the store.

ah.

yeah nvm i guess i did know that..

need to probably run a libbitcoin node at some point...

Why is 8GB too big?

doesn't that fit comfortably in ram?

is there a way to make an index of the index? haha

32GB RAM, 8GB is 1/4 of it.

Populating the compact filters requires a total ordering by block for filter combination. Also population of the block portion requires all prevouts populated. Keep in mind that a duplicate detection for points must run during milestone as well, this type of solution would kill milestone sync.

This is sorta like creating the massive address index, but actually more costly.

While it may be quick for a wallet, when reading the index, wallets don’t have 2.5 billion spends, and the cost to wallets doesn’t include the filter construction cost by the node/server.

The problem definition boils down to detecting (not preventing) duplicate points on tx insert to the store. It’s easily done, doing it while not thrashing by searching the point index is the challenge.

This problem reduces to detecting a duplicate upon insert within a single bucket’s conflict list. These lists are 0-14 elements long, with 6-14 being irrelevant due to small quantity of them. 0 and 1 element lists are trivial, so it’s the 2-5 range that is the real cost.

The 0-14 is probabilistic, and this expected outcome supported by a full scan of the table.

Hashmap heads are randomly accessed during read and write. So they must be memory resident or head paging becomes an issue. During a milestone run it’s all write, no table lookups. During validation we are reading all tables, but the design lints hashmap searching to a very limited amount. Neither block population nor prevout population search the massive point table. So validation in a 5k block window operates efficiently within the remaining 16GB, completing in 7.5 hrs without double spend checks.

But as soon as we add a constant paging through a 100GB table into the mix, it all goes sideways. Yet if we have detected all duplicates upon insert, there is no need to even access the table during confirmation.

We can get away with another 4GB of random access header (I tested with this), which pushes the total to 20GB. But 8GB would put us at 24GB, leaving only 8 for block/prevout population and validation table searches. Even if that was sufficient, building the table is likely a major cost, especially since the final stage requires a total ordering by block. So to confirm a block we would have to construct all prior filters in order, and that means even for all milestone blocks (filters are cumulative).

Finally, I’m not sure if filter construction actually detects double spends.

If not then that means also running every input in the block against the filter to detect the double spend.