Regroupement et heuristique de propriété commune des entrées

Presque toute affirmation sur « qui » agit sur la blockchain repose sur une étape de regroupement. Lorsqu’un rapport indique qu’une plateforme d'échange a reçu 40 BTC ou qu’un groupe de rançongiciel contrôle 300 adresses, cette affirmation dépend d’une méthode qui a regroupé des adresses, ainsi que des erreurs de cette méthode. Sur les blockchains UTXO, la plupart des liens au sein d’un groupe proviennent d’une seule règle : l’heuristique de propriété commune des entrées. Elle est généralement juste et, lorsqu’elle se trompe, elle fusionne des portefeuilles entiers. Cette leçon présente ce qu’est le regroupement, pourquoi cette règle fonctionne, quelles transactions la mettent en défaut et comment consigner les groupes pour qu’un réviseur puisse les décomposer lien par lien.

Adresses, groupes et entités

Trois niveaux sont faciles à confondre :

Le regroupement est la version blockchain de la résolution d’entités, le problème général de traitement des données qui consiste à déterminer quels enregistrements se rapportent à une même réalité sous-jacente. Le résultat n’est pas un fait lu dans la blockchain, mais une inférence fondée sur des hypothèses concernant le comportement des portefeuilles et des personnes. Qu’une transaction ait dépensé trois entrées est un fait enregistré ; qu’une seule partie ait contrôlé les trois est une conclusion heuristique, et le rapport doit distinguer les deux.

Notez le mot contrôlées. Une heuristique peut tout au plus montrer que les mêmes clés, ou le même logiciel agissant pour un opérateur unique, ont déplacé les fonds. Une plateforme d'échange dépositaire contrôle les clés de millions de clients ; un groupe étiqueté « Plateforme d'échange X » représente donc le service, et non l’un quelconque de ses clients. Le contrôle n’est pas la propriété, et aucun des deux n’est l’identité (leçon 4.5).

Comment les groupes sont construits

Le regroupement comporte deux étapes. D’abord, les heuristiques produisent des éléments probants de liaison : des paires d’adresses qui, selon une règle donnée, partagent un même contrôleur. La règle des entrées communes relie toutes les entrées d’une transaction ; la détection de la monnaie rendue relie un expéditeur à sa sortie de monnaie rendue (leçon 4.2) ; les blockchains à comptes utilisent des liens comportementaux tels que des adresses de dépôt partagées (leçon 4.3). 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 groupe, même si aucun élément probant ne relie directement A et C. En théorie des graphes, les groupes sont les composantes connexes du graphe des éléments probants.

Par exemple, la transaction 4f3a…c21e dépense des fonds provenant des adresses a1 et a2, et la transaction 9b7d…e014, une semaine plus tard, des fonds provenant de a2 et a3. La règle produit les liens a1–a2 et a2–a3 ; la fermeture produit un seul groupe {a1, a2, a3}. Le lien a1–a3 n’a jamais été observé ; il est hérité. Si l’une ou l’autre transaction était en réalité collaborative et impliquait deux propriétaires, c’est tout le groupe qui est erroné, et pas seulement un lien.

L’heuristique de propriété commune des entrées

La logique

Pour dépenser un UTXO, une transaction doit fournir un script de déverrouillage ou un témoin valide pour celui-ci, en pratique une signature produite avec la clé qui le contrôle ; trois entrées nécessitent donc des signatures pour trois unités de fonds. Dans un usage ordinaire, un portefeuille sélectionne des fonds dans son propre solde et signe toutes les entrées correspondantes. Ainsi, si plusieurs adresses apparaissent comme entrées d’une même transaction, l’explication la plus probable est qu’un seul portefeuille, et donc un seul contrôleur, détient toutes leurs clés.

L’idée est aussi ancienne que Bitcoin : la section consacrée à la confidentialité dans le livre blanc de 2008 avertit que les transactions à plusieurs entrées « révèlent nécessairement que leurs entrées appartenaient au même propriétaire ». Reid et Harrigan (2011) l’ont utilisée pour construire un réseau d’utilisateurs, et Meiklejohn et al. (2013, « Une poignée de bitcoins ») l’ont formulée comme leur heuristique 1 : si deux adresses ou plus sont des entrées de la même transaction, elles sont contrôlées par le même utilisateur. On l’appelle également heuristique de propriété commune des entrées (CIOH) ou heuristique des entrées multiples.

Un exemple détaillé

Une transaction décodée, simplifiée pour ne conserver que les champs utiles au regroupement (identifiants tronqués) :

{
  "txid": "7c1e…40ab",
  "vin": [
    {"prevout": "a91f…03:1", "address": "bc1q…k3f7", "value_btc": 0.0400},
    {"prevout": "e2c8…7d:0", "address": "bc1q…m9a2", "value_btc": 0.0250},
    {"prevout": "51b0…e9:4", "address": "bc1q…x0d1", "value_btc": 0.0180}
  ],
  "vout": [
    {"n": 0, "address": "bc1q…p2w8", "value_btc": 0.0700},
    {"n": 1, "address": "bc1q…r4t6", "value_btc": 0.0128}
  ]
}

Les trois entrées totalisent 0,0830 BTC et les sorties 0,0828 BTC ; les frais sont donc de 0,0002 BTC (20 000 satoshis). La règle des entrées communes relie bc1q…k3f7, bc1q…m9a2 et bc1q…x0d1. Elle ne dit rien des sorties : déterminer si bc1q…r4t6 est une sortie de monnaie rendue appartenant au même portefeuille relève d’une inférence distincte et beaucoup plus faible (leçon 4.2).

Si bc1q…m9a2 faisait déjà partie d’un groupe de 2 000 adresses et bc1q…x0d1 d’un groupe de 300 adresses, cette seule transaction les fusionne en un groupe de 2 301 adresses. C’est là toute la puissance de la règle, mais aussi son danger.

La règle est la plus solide lorsqu’elle s’applique aux services. Les plateformes d'échange dépositaires et les prestataires de traitement des paiements consolident périodiquement de nombreux petits dépôts en une seule sortie, au moyen d’une transaction de convergence qui peut dépenser les fonds de centaines d’adresses de dépôt à la fois. Chaque balayage relie toutes ces adresses au portefeuille du service, ce qui explique pourquoi les groupes de services atteignent des millions d’adresses et pourquoi un seul dépôt vérifié suffit souvent à les étiqueter (leçon 4.5). Un utilisateur qui fusionne une douzaine d’anciens UTXO pour réduire ses frais futurs révèle de la même manière qu’un seul portefeuille les détenait tous. Dans les deux cas, l’inférence est correcte tant que personne d’autre n’a fourni d’entrée.

Son efficacité

Meiklejohn et al. ont appliqué la règle à l’ensemble de la blockchain en 2013 et ont ramené 12 056 684 clés publiques à environ 5,58 millions de groupes. Nick (2015, mémoire de master) a obtenu de rares données de référence grâce à une fuite de confidentialité dans les filtres de Bloom des portefeuilles légers, qui révélait les ensembles d’adresses de portefeuilles réels ; la règle des entrées communes a identifié plus de 69 % des adresses de ces portefeuilles. Notez ce que mesure ce chiffre : le rappel (la proportion de chaque portefeuille retrouvée), et non la précision (la proportion de liens corrects). La règle est généralement considérée comme très précise pour les transactions ordinaires, mais cela repose sur une hypothèse concernant le comportement des portefeuilles, que les transactions ci-dessous contredisent (la leçon 4.4 traite de la mesure de la qualité des groupes).

Quand l’hypothèse échoue

CoinJoin. Plusieurs utilisateurs conviennent d’une transaction unique ; chacun fournit des entrées et ne signe que les siennes, et les sorties en comprennent généralement plusieurs de valeur identique afin que personne ne puisse déterminer quelle sortie appartient à qui. L’application de la règle des entrées communes fusionne les portefeuilles de tous les participants, ce qui est précisément le lien erroné que CoinJoin vise à provoquer (leçon 6.2).

PayJoin. Dans un PayJoin (BIP 78), le destinataire d’un paiement ajoute l’une de ses propres entrées à la transaction de l’expéditeur. Le résultat ressemble à un paiement ordinaire à deux entrées ; la règle relie donc les fonds de l’expéditeur et du destinataire, et le montant apparent du paiement est lui aussi faussé. Un PayJoin bien construit ne peut pas être distingué de manière fiable d’une transaction normale ; son existence impose donc un plafond à la solidité de tout lien pris isolément. Son adoption est restée faible, ce qui limite les dommages globaux sans toutefois exclure sa présence dans un cas particulier.

Autres transactions multipartites. Les ouvertures de canaux Lightning à financement bilatéral, certains protocoles de swap et de traitement par lots, ainsi que les transactions signées avec SIGHASH_ANYONECANPAY, qui permet à d’autres d’ajouter des entrées après la première signature (utilisé, par exemple, dans des contrats de type financement participatif), comportent tous des entrées provenant de plusieurs parties.

Contrôle partagé. Une adresse multisignature détenue conjointement par plusieurs personnes constitue un seul « propriétaire » au sens du script ; l’entité correcte est le dispositif conjoint, et non un signataire particulier.

Garde et importation de clés. Un service dépositaire dépense ensemble les dépôts de ses clients ; son groupe est donc correct pour le service, mais ne dit rien des clients. Les portefeuilles qui permettent aux utilisateurs d’importer ou de balayer des clés privées reçues d’autres personnes (portefeuilles papier, cartes-cadeaux) peuvent relier des fonds qui avaient des propriétaires différents. Harrigan et Fretter (« L’efficacité déraisonnable du regroupement d’adresses », 2016) ont exclu le plus grand groupe Bitcoin, soit plus de 10 millions d’adresses appartenant à l’origine à Mt. Gox, pour cette raison précise.

Les groupes ne sont pas des entités

La correspondance entre les groupes et les entités du monde réel échoue dans les deux sens.

• Une entité, plusieurs groupes (fusion insuffisante). Les portefeuilles froids d’une plateforme d'échange peuvent ne jamais être dépensés conjointement avec ses portefeuilles chauds ; une personne peut utiliser trois applications de portefeuille sans lien entre elles ; sur les blockchains à comptes, qui ne permettent pas les dépenses à plusieurs entrées, un opérateur apparaît souvent sous la forme de dizaines d’adresses non reliées.
• Un groupe, plusieurs entités (fusion excessive). Les CoinJoin, la mise en commun par les dépositaires et l’importation de clés, comme indiqué ci-dessus, réunissent des portefeuilles appartenant à différentes personnes.

Les groupes évoluent aussi au fil du temps : un groupe calculé au bloc 800 000 peut fusionner avec un autre d’ici le bloc 850 000. Chaque groupe est un instantané et doit être accompagné de la hauteur de bloc à laquelle il a été calculé.

Faux positifs, faux négatifs et propagation des erreurs

Un lien faux positif réunit des adresses qui ne sont pas contrôlées par la même partie ; un faux négatif est un lien réel que la méthode n’a pas détecté. Leurs coûts touchent des utilisateurs différents :

Aucun ensemble d’heuristiques n’est optimal pour tous : une équipe de conformité qui bloque des transactions sur la base des étiquettes de groupes doit 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 de figurer dans un rapport.

Les erreurs de regroupement ne sont pas proportionnelles au nombre de liens erronés. Comme les groupes sont des fermetures transitives, un seul lien erroné entre un groupe de 5 000 adresses et un groupe de 40 000 adresses produit un groupe de 45 000 adresses, et chaque adresse partage désormais toute étiquette portée par l’un ou l’autre côté. Les erreurs se cumulent également avec la taille. Si chaque lien a indépendamment une probabilité p d’être erroné, un groupe constitué à partir de n liens est exempt d’erreur avec une probabilité de (1 − p)^n. Avec p = 0,001 et n = 1 000 liens, cela donne 0,999^1 000 ≈ 0,37 : il existe donc une probabilité de 63 % que le groupe contienne au moins une fusion erronée. Les grands groupes sont par conséquent plus susceptibles d’être contaminés, alors que c’est précisément à eux que les analystes ont tendance à accorder le plus de confiance. Meiklejohn et al. ont constaté qu’une version naïve de leur heuristique de monnaie rendue produisait un supergroupe de 1,6 million de clés publiques contenant Mt. Gox, Instawallet, BitPay et Silk Road (la leçon 4.4 traite de ces supergroupes). En aval, l’étiquette issue de la fusion modifie les statistiques de flux et les scores de risque, et un rapport finit par énoncer une conclusion que les éléments probants ne justifient pas, au terme d’étapes qui semblaient toutes raisonnables.

Précautions et consignation des éléments probants

Filtrer et surveiller avant de relier

1. Excluez les CoinJoin probables. Le test le plus simple recherche plusieurs sorties de valeur exactement identique :

-- Signaler les CoinJoin potentiels pour ne pas relier leurs entrées
WITH same_value AS (
  SELECT transaction_hash, value, COUNT(*) AS n_equal
  FROM outputs
  GROUP BY transaction_hash, value
),
shape AS (
  SELECT t.hash AS transaction_hash, t.input_count,
         MAX(s.n_equal) AS max_equal_outputs
  FROM transactions t
  JOIN same_value s ON s.transaction_hash = t.hash
  GROUP BY t.hash, t.input_count
)
SELECT transaction_hash
FROM shape
WHERE input_count >= 2
  AND max_equal_outputs >= 3;  -- ajuster ce seuil et le documenter

La requête compte, pour chaque transaction, combien de sorties partagent chaque valeur, conserve le plus grand groupe ainsi obtenu et signale les transactions à plusieurs entrées comportant au moins trois sorties identiques. Le seuil relève de l’appréciation de l’analyste. Ce test repère aussi certains paiements par lots de plateformes d'échange dont les montants sont identiques ; les exclure ne fait perdre que quelques liens (un faux négatif), l’erreur la moins risquée. Il manque les modèles de CoinJoin qui évitent les sorties de même valeur : il s’agit donc d’un filtre, et non d’un détecteur ; les travaux de recherche sur le regroupement, comme ceux de Goldfeder et al. (2018), ajoutent une exclusion des CoinJoin pour la même raison.

1. Signalez les combinaisons d’entrées inhabituelles. Des entrées de types de scripts différents (par exemple, une entrée P2PKH historique à côté d’une entrée P2TR) sont peu courantes lorsqu’elles proviennent d’un seul logiciel de portefeuille et méritent un examen complémentaire.
2. Surveillez les fusions. Examinez tout lien susceptible de fusionner deux grands groupes, ou deux groupes portant des étiquettes différentes. Harrigan et Fretter ont observé que les grands groupes fusionnent rarement naturellement ; une telle fusion est donc un signal d’alerte. Examinez également tout groupe dont la taille augmente fortement entre deux instantanés.

Conservez les éléments probants, pas seulement les groupes

Stockez une ligne par élément probant de liaison :

-- Une ligne par élément probant de liaison, et non par groupe
CREATE TABLE cluster_evidence (
  addr_a        VARCHAR NOT NULL,
  addr_b        VARCHAR NOT NULL,
  heuristic     VARCHAR NOT NULL,  -- par ex. 'common_input', 'change_v3'
  evidence_tx   VARCHAR NOT NULL,  -- txid ou hachage de transaction
  block_height  BIGINT  NOT NULL,
  strength      VARCHAR            -- 'high', 'moderate' ou 'low' (voir le tableau ci-dessous)
);

-- Reconstruire les groupes à partir des seuls éléments probants les plus solides
SELECT addr_a, addr_b
FROM cluster_evidence
WHERE heuristic = 'common_input'
  AND strength = 'high';

Puisque les groupes 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 identifiée ultérieurement comme un CoinJoin ou un PayJoin et observer ce qui se dissocie, ou montrer à un réviseur pourquoi deux adresses ont été réunies. Le calcul des composantes connexes est peu commode en SQL simple (les CTE récursives fonctionnent, mais passent mal à l’échelle) ; la plupart des équipes exportent les arêtes sélectionnées vers une bibliothèque de graphes ou une routine union-find. La génération des paires d’entrée à grande échelle, avec la même exclusion des CoinJoin, est abordée dans la leçon 2.9 (les noms de colonnes utilisés ici suivent son schéma UTXO).

Solidité et présentation des résultats

Sur l’échelle A–D du cours (leçon 3.2), tout lien fondé sur les entrées communes est de niveau C, soit une heuristique unique, quelle que soit la ligne du tableau à laquelle il correspond ; le tableau classe la solidité des liens au sein de ce niveau et détermine lesquels peuvent transmettre des étiquettes (leçon 4.5). Le cours réserve le mot « confiance » au fondement d’un jugement présenté dans un rapport (leçon 9.2) ; les liens heuristiques sont donc évalués selon leur solidité. Nommez et datez l’ensemble d’heuristiques, les exclusions, les seuils et la hauteur de bloc de l’instantané sur lesquels repose chaque groupe que vous citez. Écrivez « adresses regroupées par l’heuristique des entrées communes, filtre CoinJoin activé, étiquetées comme Service X sur la base d’un dépôt de test » plutôt que « portefeuille du Service X » (la leçon 9.2 traite de la formulation des rapports). Enfin, testez la sensibilité : reproduisez les principaux résultats sans l’heuristique la plus faible et indiquez s’ils restent valables.

Points clés pour l'examen : la différence entre une adresse, un groupe et une entité, ainsi que le contrôle par opposition à la propriété pour les services dépositaires ; le regroupement comme résolution d’entités et comme fermeture transitive (composantes connexes) des éléments probants de liaison ; pourquoi des entrées dépensées conjointement impliquent un contrôleur commun et l’origine de la règle (livre blanc, heuristique 1 de Meiklejohn et al.) ; le rappel par opposition à la précision dans les éléments probants issus des filtres de Bloom (plus de 69 % des adresses des portefeuilles retrouvées) ; les exceptions (CoinJoin, PayJoin selon BIP 78, canaux à financement bilatéral, SIGHASH_ANYONECANPAY, multisignature, garde et importation de clés) ; les fusions insuffisantes et excessives ; les coûts différents des faux positifs et des faux négatifs ; pourquoi un seul lien erroné fusionne des groupes entiers et propage les étiquettes, et le raisonnement (1 − p)^n ; le filtrage des sorties de même valeur avec un seuil documenté ; le stockage des éléments probants avec l’heuristique, la transaction et la hauteur de bloc afin de pouvoir reconstruire les groupes.