O que são os Bloom Filters?

Um bloom filter (ou filtro de Bloom) é uma estrutura de dados probabilística que permite testar a pertença de um elemento a um conjunto de forma extremamente eficiente em termos de espaço e tempo. A grande sacada é que ele pode gerar falsos positivos (diz que o elemento está no conjunto quando não está), mas nunca falsos negativos.

Como funciona?

Um bloom filter consiste em um vetor de bits inicializado com zeros e em k funções hash independentes. Quando um elemento e é inserido:

1. Calcula‑se k valores de hash para e;
2. Cada hash indica uma posição no vetor de bits, que é então marcada como 1;

Para consultar se x está no conjunto, repete‑se o processo de hash e verifica‑se se todos os bits correspondentes são 1. Se algum for 0, x definitivamente não está no conjunto.

Vantagens principais

• Baixa memória: um filtro pode representar milhões de itens usando apenas alguns kilobytes.
• Velocidade: inserções e consultas são O(k), ou seja, constante.
• Facilidade de combinação: dois filtros podem ser unidos com operação OR, útil para agregação distribuída.

Limitações

• Taxa de falsos positivos que cresce com o número de itens inseridos.
• Impossibilidade de remoção de itens (a menos que se use variantes como Counting Bloom Filters).
• Não suporta recuperação de valores, apenas teste de pertença.

Aplicações em Blockchain

Na O futuro da arquitetura da blockchain, os bloom filters são essenciais para:

• SPV (Simplified Payment Verification) em Bitcoin: nós leves usam filtros para solicitar apenas transações relevantes.
• Filtros de eventos em Ethereum: logs de contratos inteligentes são indexados com bloom filters, permitindo buscas rápidas por tópicos.
• Redução de tráfego de rede: nós podem anunciar o que possuem sem enviar listas completas.

Exemplo prático em Python

from pybloom_live import BloomFilter
bf = BloomFilter(capacity=100000, error_rate=0.001)
bf.add('endereco_de_wallet')
print('endereco_de_wallet' in bf)  # True
print('outro_endereco' in bf)      # Possível False Positive

Quando usar?

Use bloom filters quando precisar de:

• Verificação rápida de pertença em grandes volumes de dados.
• Reduzir a quantidade de dados enviados entre nós (ex.: clientes leves).
• Construir sistemas de cache ou pré‑filtragem.

Recursos externos

Para aprofundar, consulte a página da Wikipedia sobre Bloom Filters e o artigo seminal de Bloom (1970).

Conclusão

Os bloom filters são uma ferramenta poderosa para lidar com grandes conjuntos de dados de forma eficiente. No ecossistema blockchain, eles permitem que nós leves operem com segurança e rapidez, mantendo a descentralização sem sobrecarregar a rede.

Se você quer entender mais sobre a arquitetura de blockchains modernas, leia também Blockchain Modular vs Monolítica.