Blockchain Academy
We'll get together for networking with people interested in Blockchain including developers and anyone curious about Blockchain.

Bloom Filter

The Bloom filter is one of the data structure, a probabilistic data structure used to check whether an element belongs to a set. When a Bloom filter determines that an element belongs to a set, it is possible to generate a positive error that the element does not belong to the set, but on the contrary, it is judged that the element does not belong to the set, negative errors never occur. It is possible to add an element to a set, but it is not possible to remove an element from the set, and as the number of elements in the set increases, the probability of a positive error also increases.Despite being a stochastic data structure, it has characteristics that it can not be sure that there are no elements that are not present, and it is used in various fields because of its simple algorithm, its very small memory footprint, and so on. In Ethereum, this is one of the elements in the block header, and adds a log to the Bloom filter indexed when the transaction is executed. If you find a log for a particular transaction, it will search the block header and look for the log in the Bloom filter's indexed entry. You can save space by not storing the logs directly in blocks.

(Image Source : https://en.wikipedia.org/wiki/Bloom_filter)


A Bloom filter is a data structure that hashes values and then indexes them into arbitrary tables to see if all the corresponding values are 1. For example, when you put values from a set (x, y, z) into a Bloom filter, the elements in each set are mapped to Bloom filters with the following color arrows. If any element is included in the set, all values are 1, but since we include 0 when we assign the w element, we know that w does not belong to the set.