Categories

Counting Bloom filter

You are here:
< All Topics

A counting Bloom filter modifies the Bloom filter by replacing each bit of the Bloom filter bit vector with a 4 bit counter to enable deletions. Every time an item is inserted, the counters at the k indices determined by the hash function are incremented. An item is deleted from the filter by decrementing the counter at each of the k indices. The Bloom filter indicates that an item is included if the counters at the k indices for an item are all non-zero. The Bloom filter indicates that an item is not included if any of these counters are zero.

 

Counting Bloom filters do not offer any advantage over a list of SHA-256 hashes when used as secure commitments to sets. They require 4x as many bits as a plain Bloom filter and therefore to achieve log p = –128 they require more than 32 bytes per inserted item.

 

 

Above is a diagram for a counting Bloom filter with k = 3, where A, B, and C are inserted with hash functions h1, h2, and  h3. As opposed to the basic Bloom filter, a 4 bit counter is used instead of a single bit at each position.

Previous Bloom filter
Next Bloom filter with sparse merkle trees
Table of Contents