A "Cuckoo Filter" is a nifty data structure invented a few years ago; read the paper for details.
Like a Bloom filter, you insert items and then can later ask "does this item exist in the filter?" You'll get either a definite "no" or "yes, probably" with some false-positive error rate. Cuckoo filters have two advantages over Bloom filters:
- They are more space efficient at false positive rates less than about 0.03.
- You can delete items from them without affecting the false positive rate at all.
It seems to me that an in-memory cuckoo filter could work really well to keep track of Bitcoin's "unspent transaction output set" (UTXO set), to make transaction (or block) validation as fast as possible using minimal memory or disk.
Recall that Bitcoin transactions (other than coinbase transactions that create new coins) have inputs that refer to unspent outputs. An input refers to a previous output by giving the transaction id (a 32-byte hash) co
