Bloom filters in Ethereum

Background

Bloom filters are compact data structures for probabilistic representation of a set in order to support membership queries (i.e. queries that ask: “Is element X in set Y?”).

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions, generating a uniform random distribution. Typically, k is a constant, much smaller than m, which is proportional to the number of elements to be added; the precise choice of k and the constant of proportionality of m are determined by the intended false positive rate of the filter.

To add an element, feed it to each of the k hash functions to get k array positions. Set the bits at all these positions to 1.

To query for an element (test whether it is in the set), feed it to each of the k hash functions to get k array positions. If any of the bits at these positions is 0, the element is definitely not in the set – if it were, then all the bits would have been set to 1 when it was inserted. If all are 1, then either the element is in the set, or the bits have by chance been set to 1 during the insertion of other elements, resulting in a false positive. In a simple Bloom filter, there is no way to distinguish between the two cases, but more advanced techniques can address this problem

Pros:

• space efficient

Cons:

• can’t store an associated object
• deletions are not allowed
• small false positive probability

Applications:

• weak password dictionary
• cache sharing
• query filtering and routing
• blockchain (logs)

Ethereum bloom filter function

Here’s excerpt from the yellow paper:

If you didn’t understand anything, no worries, I will try to describe its implementation in the next section.

Elixir implementation

  @spec bloom(integer(), binary()) :: integer()
  def bloom(data, number \\ 0) do
    bits =
      data
      |> sha3_hash            \\ (1)
      |> bit_numbers          \\ (2)

    number |> add_bits(bits)  \\ (3)
  end

The bloom/2 method accepts 2 aguments:

• data - binary. a new object to add to the bloom filter
• number - integer. the bloom filter. default value is zero (for new filter)

Bloom filter generation can be divided into three parts:

• calculate sha3 hash of an input data (1)
• get three bit indices from this hash (2)
• set these indices to one in the filter (3)

  @spec bit_numbers(binary()) :: [integer()]
  defp bit_numbers(hash) do
    {result, _} =
      1..3
      |> Enum.reduce({[], hash}, fn(_, acc) ->
        {bits, <<head::integer-size(16), tail::bitstring>>} = acc
        new_bit = head &&& 2047

        {[new_bit|bits], tail}
      end)

    result
  end

The bit_numbers/1 method gets indices from the low order 11-bits of the first three double-bytes of the SHA3 hash.

  @spec add_bits(integer(), [integer()]) :: integer()
  defp add_bits(bloom_number, bits) do
    bits
    |> Enum.reduce(bloom_number, fn(bit_number, bloom) ->
      bloom ||| (1 <<< bit_number)
    end)
  end

The last thing left to do is to define method to check if filter has an object:

  @spec contains?(integer(), binary()) :: boolean()
  def contains?(current_bloom, val)
      when is_integer(current_bloom) and
           is_binary(val) do
    temp_bloom = bloom(val)

    (temp_bloom &&& current_bloom) == temp_bloom
  end

Now we can use our Bloom filter:

iex(1)> filter = EthBloom.create("rock")
364236115780354413527177740824718248475191169123433179704674083584030171707548895141763338864017157468044931245187476551639917006481686358559826056819612140499456696964058447681377941080842953023782344796365486712958202642967905678562795813182653349819408730761190197772532753708011416878102770310284058867224260870159690230717337345574083724951534664321152788810106636281468311475567122070065682554961594780791945980493299780947753165983844578885074727735505366654109046841451940478976

iex(2)> new_filter = EthBloom.add(filter, "blues")
364236115780354413527177740824718248475191169123433179704674083584030171707548895141763338864017157468044931245187476551639917008583551526575664755314165081912131926893248480084782472542419712838325886207711387518315201817289948316059274529230320334129359156724892064138319603709966466517388006639868069257972765204989827007471817298541374196685568760261999794300328280707725224364790299899128819784076530509337252429855458993811873518002173094917629136344228828519818452981281942732800

iex(3)> EthBloom.contains?(new_filter, "punk")
false

iex(4)> EthBloom.contains?(new_filter, "rock")
true

iex(5)> EthBloom.contains?(new_filter, "blues")
true

Described code has a GitHub repository - https://github.com/ayrat555/eth_bloom

See also

• https://ethereum.github.io/yellowpaper/paper.pdf
• https://en.m.wikipedia.org/wiki/Bloom_filter
• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/riKfa/bloom-filters-the-basics