GCS - GOLOMB-CODED SET
Structure de données probabiliste utilisée dans le BIP-0158 pour construire les compact block filters sur Bitcoin. Un GCS permet de tester l’appartenance d’un élément à un ensemble avec la garantie de trouver tout élément présent, mais avec une probabilité de faux positif de \(1/M\).
La construction d’un GCS se déroule en plusieurs étapes : les éléments bruts sont d’abord hachés avec SipHash vers des entiers de 64 bits répartis uniformément dans l’intervalle \([0, N \times M)\). Les valeurs obtenues sont triées, puis les différences entre valeurs consécutives sont encodées par codage de Golomb-Rice. Ce codage exploite la distribution géométrique naturelle des écarts pour obtenir une compression quasi optimale : chaque différence est décomposée en un quotient (encodé en unaire) et un reste (encodé sur \(P\) bits).
Comparé aux filtres de Bloom utilisés dans le BIP-0037, le GCS produit des filtres plus compacts pour un même taux de faux positifs. En contrepartie, le test d’appartenance nécessite de décompresser séquentiellement le filtre, ce qui empêche les requêtes en temps constant. Cette structure a été retenue pour les compact block filters avec les paramètres \(P = 19\) et \(M = 784\,931\).