Heuristiques de détection de la monnaie rendue

La plupart des paiements Bitcoin restituent une partie de la valeur dépensée à l’expéditeur sous forme de monnaie rendue. L’identification de la sortie de monnaie rendue permet à un analyste de suivre les fonds restants de l’expéditeur, de reconstituer des chaînes de pelage et d’ajouter l’adresse de monnaie rendue au cluster de l’expéditeur. Toutefois, contrairement à la règle des entrées communes, la détection de la monnaie rendue reste toujours une estimation probabiliste, et les travaux de recherche montrent que des heuristiques de monnaie rendue mal choisies sont la principale cause de l’expansion incontrôlée des clusters.

Pourquoi la monnaie rendue existe

Un UTXO doit être dépensé intégralement. Un portefeuille qui détient une pièce de 0,09 BTC et souhaite payer 0,05 BTC dépense la pièce entière, envoie 0,05 BTC au destinataire et envoie le reste, déduction faite des frais, à une adresse qu’il contrôle. Voici une transaction de ce type, décodée et simplifiée :

{
  "txid": "b52d…0e7a", "version": 2, "locktime": 861203,
  "vin": [
    {"address": "bc1q…h8e2", "type": "p2wpkh", "value_btc": 0.09000000,
     "sequence": "0xfffffffd"}
  ],
  "vout": [
    {"n": 0, "address": "1Kx3…9vQe", "type": "p2pkh", "value_btc": 0.05000000},
    {"n": 1, "address": "bc1q…7k3f", "type": "p2wpkh", "value_btc": 0.03985860}
  ]
}

Les frais s’élèvent à 0,09000000 − 0,08985860 = 0,00014140 BTC (14 140 satoshis). Rien dans les données n’indique quelle sortie correspond au paiement. L’analyste doit le déduire, et plusieurs indices indépendants vont ici dans le même sens.

Les heuristiques classiques

L’idée de l’adresse nouvelle provient d’Androulaki et al. (2013, « Evaluating User Privacy in Bitcoin »), qui appelaient les sorties de monnaie rendue des « adresses fantômes », ainsi que de Meiklejohn et al. (2013, « A Fistful of Bitcoins »), dont l’heuristique 2 désigne une sortie comme monnaie rendue s’il s’agit de la seule adresse de sortie apparaissant pour la première fois, si la transaction n’est pas une transaction coinbase et si aucune sortie ne renvoie des fonds à une adresse d’entrée (pas de monnaie rendue vers une adresse d’entrée). Des travaux ultérieurs ont ajouté des conditions : Goldfeder et al. (2018, une étude des risques pour la confidentialité dans les paiements sur le Web) ont exclu les CoinJoin, et Ermilov et al. (2017, « Automatic Bitcoin Address Clustering ») ont exigé exactement deux sorties et une valeur significative au moins jusqu’à la quatrième décimale.

Dans l’exemple : la sortie 1 utilise une adresse nouvelle, correspond au type P2WPKH de l’entrée et présente un montant non rond, tandis que la sortie 0 correspond à un montant rond de 0,05 BTC envoyé à une adresse ancienne génération ayant déjà reçu des fonds. Tous les signaux concordent pour indiquer que la sortie 1 correspond à la monnaie rendue.

Les transactions ultérieures peuvent confirmer ou infirmer cette estimation. Si bc1q…7k3f est finalement dépensée avec d’autres pièces déjà présentes dans le cluster de l’expéditeur, la règle des entrées communes la relie alors de manière indépendante à ce cluster, et l’étiquette de monnaie rendue devient un élément de preuve solide plutôt qu’une déduction. Si, au contraire, elle est dépensée avec des pièces provenant d’un cluster connu de plateforme d’échange, la sortie 1 correspondait probablement au paiement, et l’étiquette doit être corrigée, de même que tous les liens établis à partir d’elle. Cette confirmation différée est précisément la méthode utilisée par Möser et Narayanan (2022) pour constituer leur vérité terrain, décrite ci-dessous ; c’est pourquoi les étiquettes de monnaie rendue doivent être réévaluées à mesure que la chaîne s’allonge, plutôt que figées au moment de leur attribution.

Empreintes des portefeuilles

Les logiciels de portefeuille laissent des traces cohérentes dans les champs dont la valeur n’est pas imposée par le consensus :

• Version. Les transactions utilisant des verrouillages temporels relatifs (BIP 68) doivent utiliser la version 2 ; de nombreux portefeuilles utilisent encore la version 1. Dans les données analysées par Möser et Narayanan (2022), environ 80 % des transactions utilisaient la version 1 ; la version 2 seule ne réduit donc que partiellement le champ des possibilités.
• Verrouillage temporel. Certains clients, notamment Bitcoin Core, définissent par défaut nLockTime à la hauteur courante de la chaîne pour décourager le fee sniping. Un verrouillage temporel proche de la hauteur de confirmation constitue une empreinte.
• Signalement du remplacement par frais. Une transaction signale qu’elle est remplaçable selon le BIP 125 lorsqu’une entrée présente une valeur nSequence inférieure à 0xfffffffe, comme dans l’exemple (0xfffffffd).
• Ordonnancement. Le BIP 69 définit un tri lexicographique facultatif des entrées et des sorties ; les portefeuilles qui l’appliquent produisent un schéma reconnaissable.
• Comportement relatif aux scripts et aux frais. Les types d’adresses, l’arrondi des taux de frais et les structures multisignatures diffèrent également selon les portefeuilles.

L’heuristique des empreintes compare la transaction qui dépense chaque sortie candidate à la transaction d’origine. Si la transaction d’origine utilisait la version 2, un verrouillage temporel défini à la hauteur du bloc et le signalement RBF, et que la sortie 1 est ultérieurement dépensée par une transaction présentant ces trois mêmes caractéristiques, tandis que la sortie 0 est dépensée par une transaction de version 1 avec un verrouillage temporel à 0, la sortie 1 correspond probablement à la monnaie rendue. Les empreintes sont des éléments de preuve liés à une période donnée : les paramètres par défaut changent d’une version à l’autre ; consignez donc la période à laquelle correspondent vos règles d’identification des empreintes.

Ce que dit la recherche sur la précision

Une même heuristique peut paraître excellente ou médiocre selon le moment et la manière dont elle est évaluée.

• Meiklejohn et al. (2013) considéraient la réutilisation ultérieure d’une adresse comme le signe d’un faux positif. Leur heuristique 2 naïve donnait 13 % de faux positifs et un supercluster de 1,6 million de clés ; après des améliorations (attente d’une semaine avant l’étiquetage, exemption des transactions de jeux de dés, exclusion de certains schémas d’adresses, examen manuel), ils ont estimé ce taux à 0,17 %.
• Kappos et al. (2022, « How to Peel a Million ») ont testé la même famille d’heuristiques sur des clusters vérifiés manuellement. Ils ont mesuré un taux de fausses découvertes de 51,64 % pour l’heuristique de Meiklejohn, de 64,19 % pour celle d’Androulaki et de 12,7 % pour l’heuristique plus stricte d’Ermilov, attribuant cet écart à l’évolution importante des usages de Bitcoin depuis 2013. Leur propre méthode, qui utilise le comportement passé du cluster en matière de monnaie rendue et ses schémas de dépense, a atteint 0,62 % et 0,02 % dans deux variantes.
• Möser et Narayanan (2022, « Resurrecting Address Clustering in Bitcoin ») ont constitué une vérité terrain à partir de monnaie rendue révélée ultérieurement par la réutilisation d’adresses. Les heuristiques prises individuellement présentaient de faibles taux de faux positifs, mais ne détectaient qu’une minorité des sorties de monnaie rendue : l’heuristique de monnaie rendue optimale en identifiait 30,6 % avec un taux de faux positifs de 2,6 %, et celle du type d’adresse 23,7 % avec un taux de 3,1 %. Un classificateur par forêt aléatoire combinant heuristiques et empreintes détectait environ 82 % de la monnaie rendue, avec un taux de faux positifs proche de 0,06 %.

Deux enseignements en découlent. Premièrement, les taux d’erreur sont liés à leur jeu de données et à leur période ; citez-les avec leur source, jamais comme des constantes. Deuxièmement, même un taux de faux positifs de 0,06 % est élevé lorsqu’il est appliqué à des centaines de millions de transactions : Möser et Narayanan ont constaté qu’une fusion naïve fondée sur les résultats de leur classificateur produisait un supercluster de 223,9 millions d’adresses, et ils ont dû ajouter des contraintes pour l’éviter (voir la leçon Évaluation de la qualité des clusters).

Attribution de scores et niveau de confiance

Une approche transparente attribue un score à chaque sortie candidate et n’accepte une étiquette de monnaie rendue que lorsqu’une sortie se détache nettement :

-- Attribuer un score de candidat à la monnaie rendue à chaque sortie des transactions à deux sorties
SELECT o.transaction_hash, o.output_index, o.address,
       (CASE WHEN o.script_type = s.input_script_type THEN 1 ELSE 0 END)
     + (CASE WHEN MOD(o.value, 100000) <> 0 THEN 1 ELSE 0 END)
     + (CASE WHEN f.first_seen_block = o.block_number THEN 1 ELSE 0 END)
       AS change_score
FROM outputs o
JOIN tx_summary s          ON s.transaction_hash = o.transaction_hash
JOIN address_first_seen f  ON f.address = o.address
WHERE s.output_count = 2
  AND s.single_input_type = TRUE;  -- ignorer les entrées de types différents

Chaque sortie obtient un point si son type de script correspond à celui des entrées, un point si sa valeur n’est pas ronde (pas un multiple de 100 000 satoshis, soit 0,001 BTC) et un point si elle apparaît pour la première fois dans ce bloc. Certains moteurs écrivent MOD(a, b) sous la forme a % b. La requête attribue un score aux deux sorties ; une étape en aval n’accepte la sortie 1 comme monnaie rendue que si, par exemple, elle obtient 3 points et que la sortie 0 en obtient 0 ou 1. Une égalité signifie « inconnu », et non un choix à pile ou face. La leçon Interrogation des données UTXO et des journaux et traces EVM construit le test du type d’entrée unique à partir des tables inputs et outputs ; les tables auxiliaires utilisées ici sont construites à partir de celles-ci de la même manière.

Cas d’échec à retenir

• Absence totale de monnaie rendue. Les méthodes de sélection des pièces telles que Branch and Bound de Bitcoin Core recherchent des ensembles d’entrées correspondant exactement au paiement, ce qui produit des transactions sans monnaie rendue. Une heuristique contrainte de choisir une sortie étiquettera alors le paiement comme monnaie rendue.
• Transferts à soi-même et consolidations, où toutes les sorties appartiennent à l’expéditeur.
• Paiements groupés comportant de nombreuses sorties, dont plusieurs semblent nouvelles.
• PayJoin et CoinJoin, conçus pour mettre ces règles en échec.
• Types d’adresses uniformes, qui suppriment le signal du type de script.

Les liens fondés sur la monnaie rendue doivent être consignés dans le tableau des éléments de preuve avec leur niveau de confiance et la note de A à D qu’il justifie sur l’échelle du cours (leçon 3.2), et les rapports doivent préciser si une conclusion dépend de ces liens.

Points clés pour l’examen : pourquoi les sorties de monnaie rendue existent ; les heuristiques de l’adresse nouvelle, du type de script, du montant rond et de la monnaie rendue optimale, ainsi que le cas d’échec de chacune ; les conditions de l’heuristique 2 de Meiklejohn et al. et le supercluster produit par sa version naïve ; les empreintes des portefeuilles (version et BIP 68, verrouillage temporel et protection contre le fee sniping, signalement RBF du BIP 125, ordonnancement du BIP 69) et pourquoi ces éléments de preuve sont liés à une période donnée ; le contraste entre 0,17 % (Meiklejohn, 2013) et 51,64 % (Kappos et al., 2022) pour une même heuristique ; pourquoi de faibles taux de faux positifs provoquent malgré tout un effondrement du regroupement à grande échelle ; l’attribution de scores aux sorties et le traitement des égalités comme des résultats inconnus ; les transactions sans monnaie rendue.