Heuristiques de regroupement et leurs limites · Leçon 1 sur 6
Ce qu’est le clustering et pourquoi il est important
9 min de lecture
Presque toute affirmation on-chain concernant « qui » repose sur une étape de clustering. Lorsqu’un analyste écrit qu’une plateforme d’échange a reçu 40 BTC, qu’un groupe de rançongiciel contrôle 300 adresses ou qu’un portefeuille est « exposé » à un service sanctionné, cette affirmation dépend d’une méthode qui a regroupé des adresses, ainsi que des erreurs de cette méthode. Comprendre ce que fait le clustering et comment ses erreurs se propagent constitue le fondement de toutes les autres leçons de ce module.
Adresses, clusters et entités
Les analystes travaillent à trois niveaux qu’il est facile de confondre :
| Niveau | Ce qu’il représente | Comment il est connu |
|---|---|---|
| Adresse (ou compte) | Un script de verrouillage ou un compte unique sur la chaîne | Directement à partir des données de la blockchain |
| Cluster | Un ensemble d’adresses qu’une méthode considère comme étant contrôlées par la même partie | Déduit à partir d’heuristiques |
| Entité | Le contrôleur dans le monde réel : un service, une organisation, un groupe ou une personne | Déduit à partir des étiquettes associées aux clusters |
Le clustering est la version blockchain de la résolution d’entités, le problème général consistant à déterminer quels enregistrements font référence à une même réalité sous-jacente. Les bases de données clients le font à partir des noms et des adresses postales ; les analystes de blockchain le font à partir des habitudes de dépense. Le résultat n’est pas un fait lu directement sur la chaîne, mais une déduction fondée sur des hypothèses concernant le comportement des portefeuilles et des personnes.
Notez le mot contrôlées. Au mieux, une heuristique peut montrer que les mêmes clés, ou le même logiciel agissant pour un opérateur, ont transféré les fonds. Une plateforme d’échange avec conservation contrôle les clés de millions de clients ; un cluster étiqueté « Plateforme d’échange X » représente donc le service, et non l’un de ses clients. Le contrôle n’est pas la même chose que la propriété, et ni l’un ni l’autre ne signifie l’identité.
Comment les clusters sont construits
Le clustering comporte deux étapes. D’abord, les heuristiques produisent des éléments de preuve de liaison : des paires d’adresses qui, selon une règle donnée, partagent un contrôleur. La règle des entrées communes relie toutes les entrées d’une transaction (voir la leçon L’heuristique de propriété des entrées communes) ; la détection de la monnaie rendue relie un expéditeur à sa sortie de monnaie rendue (voir Les heuristiques de détection de la monnaie rendue) ; les chaînes de comptes utilisent des liens comportementaux tels que des adresses de dépôt partagées (voir Les heuristiques des modèles à comptes). Ensuite, l’analyste calcule la fermeture transitive de ces liens : si A est lié à B et B à C, alors A, B et C forment un seul cluster, même si aucun élément de preuve ne relie directement A à C. En termes de graphes, les clusters sont les composantes connexes du graphe de preuves.
Un petit exemple. La transaction 4f3a…c21e dépense des pièces provenant des adresses a1 et a2 et, une semaine plus tard, la transaction 9b7d…e014 dépense des pièces provenant de a2 et a3. La règle des entrées communes produit deux liens, a1–a2 et a2–a3, et la fermeture transitive produit un seul cluster {a1, a2, a3}. Le lien entre a1 et a3 n’a jamais été observé ; il est hérité. Si l’une des transactions était en réalité une transaction collaborative avec deux propriétaires, tout le cluster serait erroné, et pas seulement un lien.
Il est recommandé de conserver les éléments de preuve, et pas seulement les clusters finaux :
-- Une ligne par élément de preuve de liaison, et non une ligne par cluster
CREATE TABLE cluster_evidence (
addr_a VARCHAR NOT NULL,
addr_b VARCHAR NOT NULL,
heuristic VARCHAR NOT NULL, -- p. ex. 'common_input', 'change_v3'
evidence_tx VARCHAR NOT NULL, -- txid ou hash de transaction
block_height BIGINT NOT NULL,
confidence DECIMAL(3,2) -- attribuée par l'analyste, de 0,00 à 1,00
);
-- Reconstruire les clusters à partir des éléments de preuve les plus solides uniquement
SELECT addr_a, addr_b
FROM cluster_evidence
WHERE heuristic = 'common_input'
AND confidence >= 0.90;La table indique quelle règle a créé chaque lien, quelle transaction le justifie, à quelle hauteur de bloc et avec quel niveau de confiance. Comme les clusters finaux sont dérivés de cette table, l’analyste peut les reconstruire avec un ensemble d’heuristiques plus strict ou plus souple, supprimer une transaction erronée et voir ce qui s’effondre, ou expliquer à un examinateur pourquoi deux adresses ont été réunies. L’étape finale, qui consiste à calculer les composantes connexes, est peu pratique en SQL standard (les CTE récursives fonctionnent, mais passent mal à l’échelle) ; la plupart des équipes exportent les arêtes retenues vers une bibliothèque de graphes ou une routine union-find.
Les clusters ne sont pas des entités
La correspondance entre les clusters et les entités du monde réel échoue dans les deux sens.
Une entité, plusieurs clusters. Une plateforme d’échange peut conserver des portefeuilles froids qui ne sont jamais utilisés conjointement avec ses portefeuilles chauds ; aucune heuristique ne les relie donc. Une personne peut utiliser trois applications de portefeuille sans lien entre elles. Sur les chaînes fondées sur des comptes, où il n’y a pas de dépense à entrées multiples, un opérateur unique apparaît souvent comme des dizaines d’adresses non connectées. Il s’agit de fusions insuffisantes.
Un cluster, plusieurs entités. Une transaction CoinJoin combine les entrées de plusieurs utilisateurs sans lien entre eux ; les traiter comme un seul propriétaire fusionne leurs portefeuilles. Un service de conservation regroupe les fonds de nombreux clients. Certains anciens portefeuilles Web permettaient aux utilisateurs d’importer des clés privées, ce qui a amené la règle des entrées communes à relier des adresses appartenant à des personnes différentes : Harrigan et Fretter (« L’efficacité déraisonnable du clustering d’adresses », 2016) ont exclu le plus grand cluster Bitcoin, composé de plus de 10 millions d’adresses appartenant à l’origine à Mt. Gox, précisément pour cette raison. Il s’agit de fusions excessives.
Les clusters évoluent également au fil du temps. De nouvelles transactions ne cessent d’apporter des éléments de preuve ; un cluster calculé au bloc 800 000 peut donc fusionner avec un autre au bloc 850 000. Chaque cluster est un instantané et devrait indiquer la hauteur de bloc à laquelle il a été calculé.
Faux positifs et faux négatifs
Deux types d’erreurs sont importants :
- Un lien faux positif relie des adresses qui ne sont pas contrôlées par la même partie.
- Un faux négatif est un lien qui existe en réalité, mais que la méthode n’a pas détecté.
Leurs conséquences diffèrent, tout comme leur coût pour les différents utilisateurs :
| Erreur | Conséquence typique | Qui en souffre le plus |
|---|---|---|
| Faux positif | Des adresses sans lien héritent d’une étiquette (activité illicite, sanction, plateforme d’échange) ; les volumes sont surestimés ; la mauvaise partie est tenue responsable | Le filtrage et la conformité, où une mauvaise étiquette peut entraîner le gel des fonds d’un client innocent |
| Faux négatif | Le tableau est incomplet ; l’exposition et les volumes sont sous-estimés ; les pistes s’éteignent | Les enquêtes, où un lien manqué fait perdre la piste |
Il n’existe pas d’ensemble d’heuristiques universellement « meilleur ». Une équipe de conformité qui bloque des transactions sur la base d’étiquettes de clusters devrait privilégier la précision ; un enquêteur qui génère des pistes peut accepter davantage de faux positifs, à condition que chaque piste soit vérifiée avant d’être intégrée à un rapport.
Comment les erreurs se propagent
Les erreurs de clustering ne sont pas proportionnelles au nombre de liens erronés. Comme les clusters sont des fermetures transitives, un seul lien erroné entre un cluster de 5 000 adresses et un autre de 40 000 adresses produit un cluster de 45 000 adresses, qui héritent toutes désormais de l’étiquette portée par l’un ou l’autre côté.
Les erreurs s’accumulent également avec la taille du cluster. Si chaque lien a indépendamment une probabilité p d’être erroné, un cluster constitué de n liens est exempt d’erreurs avec une probabilité de (1 − p)^n. Avec p = 0,001 et n = 1 000 liens, cette probabilité est de 0,999^1 000 ≈ 0,37 : il y a donc 63 % de chances que le cluster contienne au moins une fusion erronée. Les grands clusters sont donc plus susceptibles d’être contaminés, précisément là où les analystes ont tendance à placer le plus de confiance.
Les publications de recherche montrent à quelle vitesse cela se produit dans la pratique. Meiklejohn et al. (2013, « Une poignée de bitcoins ») ont indiqué qu’une version naïve de leur heuristique de monnaie rendue produisait un supercluster de 1,6 million de clés publiques contenant Mt. Gox, Instawallet, BitPay et Silk Road, des services sans lien qui n’avaient manifestement pas le même propriétaire. Ce n’est qu’après l’ajout de raffinements prudents que les clusters sont devenus utilisables. La leçon Évaluer la qualité des clusters revient sur ces superclusters.
Les erreurs se propagent ensuite en aval :
- Une heuristique crée un faux lien.
- Deux clusters fusionnent.
- Une étiquette présente d’un côté se propage à l’ensemble du cluster fusionné.
- Les statistiques de flux et les scores de risque calculés à partir des étiquettes des clusters changent.
- Un rapport énonce une conclusion que les éléments de preuve sous-jacents ne justifient pas.
Chaque étape semble raisonnable en soi, ce qui explique pourquoi l’erreur est difficile à repérer à la fin.
Bonnes pratiques
- Conservez les éléments de preuve. Enregistrez les liens avec leur heuristique, leur transaction et leur hauteur de bloc, comme dans la table ci-dessus.
- Versionnez la méthode. Nommez et datez l’ensemble d’heuristiques et les seuils utilisés pour chaque cluster que vous citez.
- Surveillez les hausses soudaines. Examinez tout cluster dont la taille augmente brusquement entre deux instantanés, ainsi que toute fusion entre deux clusters portant des étiquettes différentes.
- Employez des termes précis. Écrivez « adresses regroupées par l’heuristique des entrées communes, étiquetées comme appartenant au Service X sur la base d’un dépôt test » plutôt que « portefeuille du Service X ». La leçon Confiance, incertitude et formulation explique comment exprimer cela dans un rapport.
- Testez la sensibilité. Reprenez les principales conclusions sans l’heuristique la plus faible et indiquez si elles restent valables.
Points clés pour l’examen : la différence entre une adresse, un cluster et une entité ; le clustering comme résolution d’entités et comme fermeture transitive (composantes connexes) des éléments de preuve de liaison ; le contrôle par opposition à la propriété, en particulier pour les services de conservation ; les fusions insuffisantes et excessives et leurs causes typiques ; les définitions et les coûts différents des faux positifs et des faux négatifs ; pourquoi un seul faux lien peut fusionner des clusters entiers et propager des étiquettes ; le raisonnement fondé sur (1 − p)^n pour expliquer pourquoi les grands clusters sont plus susceptibles d’être contaminés ; la conservation des éléments de preuve avec l’heuristique, la transaction et la hauteur de bloc afin que les clusters puissent être reconstruits et audités.