Bloom filter

Définition cryptographique

Un bloom filter est une structure de données probabiliste inventée par Burton Howard Bloom en 1970. Elle teste l'appartenance d'un élément à un ensemble avec faux positifs autorisés mais pas de faux négatifs. Concrètement, on hashe k fois l'élément, on positionne k bits dans un tableau, et on interroge ce tableau plus tard. C'est très compact et très rapide, idéal pour pré-filtrer des données massives.

Usage Bitcoin via BIP-37

Le BIP-37, proposé par Matt Corallo en 2012, applique ce mécanisme aux clients SPV. Le client génère un bloom filter à partir des adresses et clés qu'il surveille, l'envoie à un full node, puis demande les transactions qui « matchent ». Le full node répond uniquement avec les transactions concernées et leurs merkle branches, permettant la vérification SPV. C'est l'architecture historique de Bitcoin Wallet (Android), Multibit et de nombreux wallets mobiles 2013-2018.

Pourquoi c'est abandonné

| Problème | Détail | |----------|--------| | Fuite de confidentialité | Le full node peut souvent déduire les adresses du client (peu d'utilisateurs partagent le même filtre) | | DoS | Un client peut demander des filtres très coûteux à appliquer côté serveur | | Manque d'intégrité | Le client doit faire confiance au serveur pour ne pas omettre des transactions | | Coût pour les nœuds | Activer le filtrage à la demande pèse en CPU et bande passante |

En 2016, Jonas Schnelli et Eric Lombrozo proposent les Compact Block Filters (BIP-157/158) où c'est le serveur qui publie un filtre par bloc et où le client le télécharge et le teste localement. Bitcoin Core a désactivé peerbloomfilters par défaut en 0.19 (2019).

Successeurs

Neutrino, implémenté par Lightning Labs dans LND et neutrino library, remplace les bloom filters. Tous les wallets mobiles modernes (Phoenix, Mutiny, Aqua, Breez) utilisent cette approche, beaucoup plus respectueuse de la confidentialité, même si elle reste plus coûteuse en bande passante côté client.

À retenir

Le bloom filter a été l'outil incontournable des wallets légers de la première décennie, mais ses faiblesses de confidentialité l'ont rendu obsolète. Le savoir reste utile : beaucoup d'attaques de désanonymisation publiées (Gervais 2014) reposent sur l'exploitation des filtres exposés par les anciens wallets.