Bloom Filter

What is a Bloom Filter?

A data structure called a bloom filter can be used to show the user if a specific item is a part of a set or not. Although it cannot be guaranteed whether a given element is part of the set, it can be certain that it is not.

Due to their effective use of space, Bloom filters, which Burton Howard Bloom developed in 1970, are desirable for various applications. For example, they are essential to Simplified Payment Verification, or SPV, in several cryptocurrencies (most notably Bitcoin).

Users can communicate with the Bitcoin network without running a complete node by utilizing an SPV client. Due to their specific storage and processing needs, full nodes are cumbersome to run on low-powered devices such as smartphones. While SPV clients merely ask full nodes for information about the users' wallets.

An Example of a Bloom Filter

Let's use an example. Let's say that Jane, a client, has a significant transaction that she doesn't want John, a full node operator, to be aware of. So she creates a 10x1 grid-based Bloom filter, which we'll use as an example.

She runs two distinct hash algorithms on the transaction data she is interested in, and they return two values between 0 and 9. They'll be known as 4 and 7. John receives the filter from her.

By looking at this grid, you do not understand what information Jane has given the filter. If you had a set containing the data, you could hash it and match it with the filter; if there was a match, there's a chance it was the data Jane asked for.

John cannot ascertain the portion of the data Jane is interested in since there are likely to be numerous inputs that will map to 4 and 7. Therefore, all of the matches are returned by him, and Jane filters them on her part.