Investor's wiki

Filtro Bloom

Filtro Bloom

Um filtro Bloom é uma estrutura de dados que pode ser usada para informar ao usuário se um determinado item faz parte de um conjunto. Embora não possa dizer com certeza se um elemento está no conjunto, pode dizer com certeza se o elemento não está.

Criados por Burton Howard Bloom em 1970, os filtros Bloom s√£o uma oferta atraente para uma variedade de aplica√ß√Ķes devido √† sua efici√™ncia no uso do espa√ßo. Em algumas criptomoedas (mais notavelmente Bitcoin), elas desempenham um papel integral na Verifica√ß√£o de Pagamento Simplificada, ou SPV.

Ao usar um cliente SPV, os usu√°rios podem interagir com a rede Bitcoin sem executar um n√≥ completo. Os n√≥s completos v√™m com certos requisitos computacionais e de armazenamento que os tornam dif√≠ceis de serem executados em dispositivos de baixa pot√™ncia, como smartphones. Os clientes SPV, por outro lado, simplesmente consultam n√≥s completos para obter informa√ß√Ķes relevantes para a(s) carteira(s) do usu√°rio.

A solu√ß√£o mais direta para retransmitir esses dados para o usu√°rio seria tornar os n√≥s completos cientes das chaves do cliente, de modo que apenas as transa√ß√Ķes pertinentes sejam enviadas a eles. Evidentemente, esta √© uma solu√ß√£o abaixo da m√©dia, pois a privacidade do cliente seria sacrificada. Por outro lado, baixar todas as transa√ß√Ķes apenas para descartar a maioria delas seria um desperd√≠cio de largura de banda. Insira os filtros Bloom.

Vamos ilustrar. Suponha que um cliente, Alice, tenha uma transação de alto valor que ela não quer que Bob, que executa um nó completo, esteja ciente. Ela constrói um filtro Bloom, que ilustraremos como uma grade 10x1:

Ela passa os dados da transa√ß√£o em que est√° interessada por meio de duas fun√ß√Ķes hash diferentes, que geram dois n√ļmeros entre 0 e 9. Vamos cham√°-los de 4 e 7. Ela envia o filtro para Bob.

Olhando para esta grade, voc√™ n√£o tem ideia de quais dados Alice passou para o filtro. Se voc√™ tivesse um conjunto no qual os dados estivessem contidos, voc√™ poderia fazer um hash e compar√°-lo com o filtro ‚Äď se houver uma correspond√™ncia, existe a possibilidade de que seja a informa√ß√£o que Alice solicitou.

Ao mesmo tempo, é provável que haja muitas entradas mapeadas para 4 e 7, de modo que Bob não pode determinar em qual parte dos dados Alice está interessada. Ele simplesmente retorna todas as correspondências e Alice as filtra do lado dela.

Isso √©, obviamente, uma simplifica√ß√£o grosseira, mas demonstra o conceito: os filtros Bloom ofuscam os verdadeiros interesses do cliente. N√£o √© um m√©todo perfeito (ainda h√° preocupa√ß√Ķes com sua privacidade), mas √© uma melhoria em rela√ß√£o a uma solicita√ß√£o n√£o blindada a um n√≥.