Heuristiques de détection de la monnaie rendue

La plupart des paiements Bitcoin renvoient une partie de la valeur dépensée à l’expéditeur sous forme de monnaie rendue. Identifier la sortie de monnaie rendue permet à un analyste de suivre les fonds restants de l’expéditeur, de reconstituer les chaînes de décapage 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 repose toujours sur une supposition probabiliste, et les travaux de recherche montrent que des heuristiques mal choisies sont la principale cause de la croissance incontrôlée des clusters.

Pourquoi la monnaie rendue existe

Un UTXO doit être dépensé en entier. Un portefeuille qui détient une pièce de 0,09 BTC et souhaite payer 0,05 BTC dépense la totalité de la pièce, envoie 0,05 BTC au destinataire et envoie le reste, moins les frais, à une adresse qu’il contrôle. Voici une telle transaction, 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 sont de 0,09000000 − 0,08985860 = 0,00014140 BTC (14 140 satoshis). Les données n’indiquent pas quelle sortie correspond au paiement. L’analyste doit le déduire, et plusieurs indices indépendants pointent ici dans la même direction.

Les heuristiques classiques

L’idée de la nouvelle adresse vient d’Androulaki et al. (2013, « Évaluation de la confidentialité des utilisateurs dans Bitcoin »), qui ont appelé les sorties de monnaie rendue des « adresses fantômes », et de Meiklejohn et al. (2013, « Une poignée de bitcoins »), dont l’heuristique 2 désigne une sortie comme monnaie rendue si son adresse est la seule adresse de sortie à apparaître pour la première fois, si la transaction n’est pas une transaction coinbase et si aucune sortie ne renvoie de fonds à une adresse d’entrée (pas de monnaie rendue à soi-même). Des travaux ultérieurs ont ajouté des conditions : Goldfeder et al. (2018, une étude des risques pour la confidentialité des paiements sur le Web) ont exclu les CoinJoin, et Ermilov et al. (2017, « Regroupement automatique des adresses Bitcoin ») ont exigé exactement deux sorties et une valeur significative jusqu’à la quatrième décimale.

Dans l’exemple, la sortie 1 correspond à une nouvelle adresse, son type P2WPKH correspond à celui de l’entrée et son montant n’est pas rond, tandis que la sortie 0 est un montant rond de 0,05 BTC envoyé à une adresse héritée qui a déjà reçu des fonds. Tous les indices concordent : la sortie 1 correspond à la monnaie rendue.

Les transactions ultérieures peuvent confirmer ou réfuter cette supposition. 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 établit désormais un lien indépendant, et l’étiquette de monnaie rendue devient un indice 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 était probablement le paiement après tout, et l’étiquette doit être inversée, de même que tous les liens établis à partir de celle-ci. C’est précisément ainsi que Möser et Narayanan (2022) ont constitué leur vérité terrain, décrite ci-dessous, et c’est pourquoi les étiquettes de monnaie rendue doivent être réévaluées à mesure que la chaîne s’allonge, plutôt que d’être considérées comme définitives dès leur attribution.

Empreintes de portefeuille

Les logiciels de portefeuille laissent des traces cohérentes dans les champs que le consensus ne fixe pas :

• Version. Les transactions utilisant des verrous temporels relatifs (BIP 68) doivent définir 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, si bien que la version 2 seule ne permet de restreindre que partiellement le champ.
• Locktime. Certains clients, notamment Bitcoin Core, définissent par défaut nLockTime sur la hauteur du bloc actuel afin de décourager le fee sniping. Un locktime proche de la hauteur de confirmation constitue une empreinte.
• Signalement du remplacement par les frais. Une transaction signale qu’elle est remplaçable selon BIP 125 lorsqu’une entrée a un nSequence inférieur à 0xfffffffe, comme dans l’exemple (0xfffffffd).
• Ordre. BIP 69 définit un tri lexicographique facultatif des entrées et des sorties ; les portefeuilles qui le suivent produisent un schéma reconnaissable.
• Comportement du script et des frais. Les types d’adresse, l’arrondi du taux de frais et la disposition des multisignatures diffèrent également selon les portefeuilles.

L’heuristique des empreintes compare à la transaction initiale la transaction qui dépense chaque sortie candidate. Si la transaction initiale avait la version 2, un locktime défini sur la hauteur du bloc et un signalement RBF, et que la sortie 1 est dépensée plus tard par une transaction présentant les mêmes trois caractéristiques, tandis que la sortie 0 est dépensée par une transaction de version 1 avec un locktime de 0, la sortie 1 correspond probablement à la monnaie rendue. Les empreintes constituent des indices datés : les paramètres par défaut changent entre les versions, alors indiquez la période que couvrent vos règles d’empreinte.

Ce que disent les recherches sur la précision

La même heuristique peut sembler excellente ou médiocre selon le moment et la manière dont elle est évaluée.

• Meiklejohn et al. (2013) ont considéré qu’une adresse réutilisée ultérieurement indiquait un faux positif. Leur heuristique 2 naïve a produit 13 % de faux positifs et un supercluster de 1,6 million de clés ; après plusieurs améliorations (attendre une semaine avant d’attribuer une étiquette, exempter les transactions de jeux de dés, exclure certains schémas d’adresses, effectuer une vérification manuelle), ils ont estimé le taux à 0,17 %.
• Kappos et al. (2022, « Comment décaper un million ») ont testé la même famille d’heuristiques par rapport à 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, et ont attribué cet écart à l’évolution de l’utilisation de Bitcoin depuis 2013. Leur propre méthode, qui utilise le comportement passé du cluster en matière de monnaie rendue et ses habitudes de dépense, a atteint 0,62 % et 0,02 % dans deux variantes.
• Möser et Narayanan (2022, « Ressusciter le regroupement d’adresses dans Bitcoin ») ont constitué une vérité terrain à partir de monnaies rendues révélées ultérieurement par la réutilisation d’adresses. Les heuristiques individuelles présentaient de faibles taux de faux positifs, mais ne détectaient qu’une minorité des sorties de monnaie rendue : la monnaie rendue optimale en identifiait 30,6 % avec un taux de faux positifs de 2,6 %, et le type d’adresse, 23,7 % avec un taux de 3,1 %. Un classificateur de forêt aléatoire combinant des heuristiques et des empreintes a détecté environ 82 % des monnaies rendues, avec un taux de faux positifs proche de 0,06 %.

Deux enseignements en découlent. Premièrement, les taux d’erreur dépendent de l’ensemble de données et de la période ; citez-les avec leur source, ne les présentez 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é que le regroupement fondé naïvement sur les résultats de leur classificateur produisait un supercluster de 223,9 millions d’adresses, et qu’ils avaient dû ajouter des contraintes pour l’éviter (voir la leçon Évaluer la qualité des clusters).

Notation et confiance

Une approche transparente attribue un score à chaque sortie candidate et ne retient l’étiquette de monnaie rendue que lorsqu’une sortie se démarque nettement :

-- Attribuer un score à chaque sortie de transactions à deux sorties comme candidate à la monnaie rendue
SELECT o.tx_id, o.output_index, o.address,
       (CASE WHEN o.script_type = s.input_script_type THEN 1 ELSE 0 END)
     + (CASE WHEN MOD(o.value_sat, 100000) <> 0 THEN 1 ELSE 0 END)
     + (CASE WHEN f.first_seen_block = o.block_height THEN 1 ELSE 0 END)
       AS change_score
FROM outputs o
JOIN tx_summary s          ON s.tx_id = o.tx_id
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 mixtes

Chaque sortie gagne un point si son type de script correspond à celui de l’entrée, 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 est vue 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 ultérieure n’accepte la sortie 1 comme monnaie rendue que si, par exemple, elle obtient un score de 3 et que la sortie 0 obtient un score de 0 ou 1. Une égalité signifie « inconnu », et non un choix à pile ou face. La leçon Interroger les données UTXO montre comment créer les tables auxiliaires.

Modes d’échec à retenir

• Aucune monnaie rendue. Les méthodes de sélection des pièces, comme Branch and Bound de Bitcoin Core, recherchent des ensembles d’entrées qui correspondent exactement au paiement et produisent ainsi des transactions sans monnaie rendue. Une heuristique contrainte de choisir une sortie désignera alors le paiement comme monnaie rendue.
• Transferts à soi-même et consolidations, où chaque sortie appartient à l’expéditeur.
• Paiements groupés, avec de nombreuses sorties, dont plusieurs semblent nouvelles.
• PayJoin et CoinJoin, conçus pour déjouer ces règles.
• Types d’adresse uniformes, qui éliminent l’indice fondé sur le type de script.

Les liens liés à la monnaie rendue doivent être accompagnés de leur niveau de confiance dans la table des éléments probants, et les rapports doivent indiquer si un constat dépend de ces liens.

Points clés pour l’examen : pourquoi les sorties de monnaie rendue existent ; les heuristiques fondées sur une nouvelle adresse, le type de script, le montant rond et la monnaie rendue optimale, ainsi que le mode d’échec de chacune ; les conditions de l’heuristique 2 de Meiklejohn et al. et son supercluster naïf ; les empreintes de portefeuille (version et BIP 68, locktime et lutte contre le fee sniping, signalement RBF de BIP 125, ordre de BIP 69) et pourquoi elles constituent des indices datés ; le contraste entre 0,17 % (Meiklejohn, 2013) et 51,64 % (Kappos et al., 2022) pour la même heuristique ; pourquoi de faibles taux de faux positifs entraînent malgré tout un effondrement à grande échelle ; l’attribution d’un score aux sorties et le fait de traiter les égalités comme des cas inconnus ; les transactions sans monnaie rendue.