Évaluer la qualité des clusters

Un cluster est une hypothèse sur le contrôle, et les hypothèses doivent être mises à l’épreuve. Les analystes qui ne peuvent pas dire quelle est la qualité de leurs clusters ne peuvent pas dire dans quelle mesure il faut se fier aux conclusions qui en découlent. Cette leçon explique comment mesurer la qualité des clusters, ce que la littérature de recherche a établi au sujet des taux d’erreur des heuristiques, comment détecter l’effondrement des clusters et comment montrer qu’une conclusion résiste à des changements raisonnables de méthode.

Vérité terrain et biais

L’évaluation des clusters nécessite une vérité terrain : des adresses dont le contrôleur est connu indépendamment des heuristiques testées. Les vérités terrain réelles sont rares, et chaque source est biaisée :

Nick (2015, mémoire de maîtrise sur la désanonymisation dans Bitcoin) est un rare exemple fondé sur une fuite : une faille de confidentialité dans les filtres de Bloom des portefeuilles légers a exposé les ensembles d’adresses de portefeuilles réels, et l’heuristique d’entrée commune a permis de trouver plus de 69 % des adresses qu’ils contenaient. Möser et Narayanan (2022, « Resurrecting Address Clustering in Bitcoin ») ont utilisé des étiquettes révélées par le comportement, à savoir 35,26 millions de transactions dont les adresses de change ont ensuite été révélées par la règle d’entrée commune. Aucun des deux échantillons n’est aléatoire et représentatif de l’ensemble des utilisateurs, et tous deux correspondent à leur période respective. Considérez tout taux d’erreur publié comme « mesuré sur cette vérité terrain, à cette période ».

Précision et rappel pour les clusters

La précision mesure la part de ce que la méthode a regroupé qui appartient réellement au même ensemble ; le rappel mesure la part de ce qui appartient au même ensemble que la méthode a trouvée. Pour les clusters, deux méthodes de comptage sont courantes.

Exemple détaillé. L’entité E contrôle 10 adresses et l’entité F en contrôle 4. La méthode a produit le cluster C, qui contient 8 des adresses de E et les 4 adresses de F (une fusion erronée), tandis que les 2 autres adresses de E se trouvent dans un cluster distinct.

• Au niveau des adresses (C est considéré comme le cluster de E) : précision = 8 ÷ 12 = 0,67 ; rappel = 8 ÷ 10 = 0,80.
• Par paires : C contient 12 × 11 ÷ 2 = 66 paires d’adresses. Les paires correctes sont les paires E–E (8 × 7 ÷ 2 = 28) plus les paires F–F (4 × 3 ÷ 2 = 6), soit 34. La précision par paires = 34 ÷ 66 = 0,52. En réalité, il existe 45 paires pour E et 6 pour F, soit 51 ; le rappel par paires = 34 ÷ 51 = 0,67.

Le comptage par paires pénalise davantage les fusions erronées, car une fusion crée simultanément de nombreuses paires incorrectes, ce qui correspond aux dommages causés par ces fusions dans l’analyse. Indiquez toujours la méthode de comptage utilisée pour obtenir un chiffre.

-- Précision et rappel au niveau des adresses pour chaque cluster par rapport à la vérité terrain
WITH overlap AS (
  SELECT c.cluster_id, g.entity_id, COUNT(*) AS shared
  FROM clusters c
  JOIN ground_truth g ON g.address = c.address
  GROUP BY c.cluster_id, g.entity_id
),
ranked AS (
  SELECT o.*, SUM(shared) OVER (PARTITION BY cluster_id) AS labeled_in_cluster,
         ROW_NUMBER() OVER (PARTITION BY cluster_id ORDER BY shared DESC) AS rk
  FROM overlap o
),
entity_size AS (SELECT entity_id, COUNT(*) AS n FROM ground_truth GROUP BY entity_id)
SELECT r.cluster_id, r.entity_id,
       r.shared * 1.0 / r.labeled_in_cluster AS precision,
       r.shared * 1.0 / e.n                  AS recall
FROM ranked r
JOIN entity_size e ON e.entity_id = r.entity_id
WHERE r.rk = 1;

La requête compte, pour chaque cluster, le nombre de ses adresses appartenant à chaque entité selon la vérité terrain, sélectionne l’entité dominante et divise le chevauchement par le nombre d’adresses étiquetées du cluster (précision), puis par la taille connue de l’entité (rappel). Les adresses sans vérité terrain sont ignorées, ce qui est le choix honnête : elles sont inconnues, et non correctes. La multiplication par 1.0 évite la division entière dans les moteurs qui tronquent le résultat.

Vérifications ne nécessitant pas de vérité terrain

La plupart des enquêtes réelles ne disposent d’aucune vérité terrain sur les entités concernées. Des vérifications de cohérence interne permettent néanmoins de révéler des problèmes :

• Cohérence des empreintes. Les adresses contrôlées par un même portefeuille ont tendance à partager un type de script, une version de transaction, des habitudes de verrouillage temporel et un style de frais. Un cluster dont les transactions dépensant des fonds présentent de nombreuses empreintes sans lien entre elles regroupe probablement plusieurs portefeuilles. Kappos et al. (2022, « How to Peel a Million: Validating and Expanding Bitcoin Clusters ») ont utilisé des caractéristiques de ce type, calculées à l’échelle du cluster, pour séparer les clusters contaminés par des CoinJoins des clusters sains.
• Cohérence temporelle. Si les adresses d’un cluster ont été actives à des périodes très éloignées, sans autre lien entre ces périodes qu’une seule transaction, il faut examiner cette transaction.
• Cohérence comportementale. Un cluster qui se comporte comme une plateforme d’échange dans une partie (des milliers de dépôts et de balayages) et comme un utilisateur individuel dans une autre (quelques paiements manuels) pourrait réunir deux entités reliées par un seul lien.
• Distribution des tailles. Une hausse soudaine de la taille des plus grands clusters après un changement de méthode indique de nouveaux faux liens plutôt que de nouvelles connaissances.

Aucune de ces vérifications ne prouve qu’un cluster est correct, mais chacune peut montrer qu’il est probablement erroné.

Ce que la recherche montre sur les taux d’erreur

Quatre conclusions s’en dégagent. Les taux d’erreur dépendent fortement de la manière dont ils sont mesurés : la même heuristique de change obtient un score de 0,17 % avec le test de falsification de ses auteurs et de 51,64 % sur des clusters vérifiés indépendamment, neuf ans plus tard. Les heuristiques vieillissent à mesure que les logiciels de portefeuille et les habitudes des utilisateurs évoluent. La combinaison de plusieurs signaux donne de meilleurs résultats qu’une règle unique. Enfin, les heuristiques pour les modèles à comptes restent largement non validées.

Effondrement des clusters

L’effondrement d’un cluster se produit lorsque de faux liens fusionnent des entités sans lien entre elles pour former un supercluster. La littérature en donne plusieurs exemples :

• L’heuristique naïve de changement de Meiklejohn et al. a produit un cluster de 1,6 million de clés contenant Mt. Gox, Instawallet, BitPay et Silk Road.
• Möser et Narayanan ont constaté que la fusion naïve fondée sur leur classificateur de change produisait un cluster de 223,9 millions d’adresses, qui absorbait 113 des 273 clusters étiquetés indépendamment. Des contraintes fondées sur le comportement de dépense prédit ont empêché 413 608 fusions ; le plus grand cluster restant comptait 40,5 millions d’adresses, et sept paires de clusters étiquetés ont tout de même fusionné.
• Harrigan et Fretter (2016, « The Unreasonable Effectiveness of Address Clustering ») ont entièrement exclu le cluster de Mt. Gox, car une fonctionnalité d’importation de clés rendait la règle d’entrée commune peu fiable dans ce cas.

Signes avant-coureurs pratiques :

1. Conflits d’étiquettes : deux plateformes d’échange différentes, ou une plateforme d’échange et un mélangeur, se retrouvent dans un même cluster.
2. Fusions entre grands clusters : Harrigan et Fretter ont observé que les grands clusters fusionnent rarement de façon naturelle ; ces fusions méritent donc un examen.
3. Croissance soudaine : un cluster qui gagne une grande part de sa taille en un seul instantané.
4. Points de défaillance uniques : une transaction est responsable de la jonction de deux composantes importantes ; recherchez-la dans le tableau des éléments probants et examinez-la.

Analyse de sensibilité

L’analyse de sensibilité consiste à reprendre une conclusion avec différentes méthodes raisonnables et à indiquer comment elle évolue. Voici un exemple de progression :

Ici, les deux premières lignes concordent de près, tandis que la troisième multiplie presque le chiffre par trois. Un rapport rigoureux indiquerait « au moins 120 BTC, et environ 141 BTC en incluant les liens de change à haut niveau de confiance », et considérerait les 410 BTC comme peu fiables, probablement gonflés par une fusion. La recherche montre le même effet à grande échelle : Möser et Narayanan ont constaté que l’ajout de leur méthode de clustering du change augmentait de 13,8 % les flux estimés des marchés du darknet vers les plateformes d’échange et diminuait d’environ 11,9 % une estimation de la vélocité des pièces. Les choix méthodologiques modifient les chiffres mis en avant.

Documentation des hypothèses

Tout rapport qui s’appuie sur des clusters devrait consigner :

• l’ensemble d’heuristiques, sa version et ses seuils (par exemple, le filtre CoinJoin et le seuil du score de change) ;
• l’instantané des données : chaîne, hauteur de bloc et version du nœud ou du jeu de données ;
• la vérité terrain utilisée pour évaluer les clusters, sa taille et ses biais connus ;
• les taux d’erreur mesurés ou cités, avec leur source et leur date ;
• les effondrements connus exclus et les fusions examinées ;
• les résultats de l’analyse de sensibilité pour chaque conclusion clé ;
• les sources et niveaux de fiabilité des étiquettes (voir la leçon Attribution et étiquetage).

Ce compte rendu permet à un examinateur de reproduire les clusters, de contester un lien précis et de voir quelles conclusions résisteraient à la découverte d’une erreur dans une heuristique. La leçon Rédaction du rapport d’analyse indique où intégrer ces éléments dans le document final.

Points clés pour l’examen : les sources de vérité terrain et leurs biais, notamment le raisonnement circulaire dans les étiquettes fournies par les prestataires ; la précision et le rappel au niveau des adresses par rapport aux paires, et le calcul de ces deux mesures à partir d’un petit exemple ; les raisons pour lesquelles les métriques par paires pénalisent les fausses fusions ; ce que montrent les chiffres de la recherche, surtout les taux de 0,17 % et de 51,64 % pour la même heuristique de change, et pourquoi même un taux de faux positifs de 0,06 % peut provoquer l’effondrement de clusters à grande échelle ; l’effondrement des clusters et ses signes avant-coureurs ; l’analyse de sensibilité et la présentation d’une borne inférieure robuste ; la documentation des heuristiques, des seuils, de l’instantané, de la vérité terrain et des taux d’erreur.