BLOOM FILTER
Structure de données probabiliste utilisée pour tester si un élément fait partie d’un ensemble. Les Bloom Filters permettent de vérifier rapidement l’appartenance sans tester l’ensemble des données. Ils sont particulièrement utiles dans les contextes où l’espace et la vitesse sont critiques, mais où un taux d’erreur faible et contrôlé est acceptable. En effet, les Bloom Filters ne produisent pas de faux négatifs, mais ils produisent une certaine quantité de faux positifs. Lorsqu’un élément est ajouté au filtre, plusieurs fonctions de hachage génèrent des positions dans un tableau de bits. Pour vérifier l’appartenance, les mêmes fonctions de hachage sont utilisées. Si tous les bits correspondants sont définis, l’élément est probablement dans l’ensemble, mais avec un risque de faux positifs. Les filtres de Bloom sont largement utilisés dans le domaine des bases de données et des réseaux. On sait notamment que Google les utilise pour son système de stockage distribué pour données structurées BigTable. Dans le protocole Bitcoin, on les utilise notamment pour les portefeuilles SPV selon le BIP-0037.
Lorsque l’on parle spécifiquement de l’utilisation des Bloom Filters dans le cadre des transactions Bitcoin, on retrouve parfois le terme de « Transaction Bloom Filtering ».