Clustering ed euristica della titolarità comune degli input

Quasi ogni affermazione on-chain relativa a "chi" si basa su una fase di clustering. Quando un rapporto afferma che un exchange ha ricevuto 40 BTC o che un gruppo ransomware controlla 300 indirizzi, tale affermazione dipende da un metodo che ha raggruppato gli indirizzi e dagli errori di quel metodo. Nelle blockchain UTXO, la maggior parte dei collegamenti di qualsiasi cluster deriva da un'unica regola: l'euristica della titolarità comune degli input. Solitamente è corretta e, quando sbaglia, unisce interi portafogli. Questa lezione illustra che cos'è il clustering, perché la regola funziona, quali transazioni ne violano i presupposti e come registrare i cluster affinché un revisore possa scomporli collegamento per collegamento.

Indirizzi, cluster ed entità

È facile confondere tre livelli:

Il clustering è la versione blockchain della risoluzione delle entità, il problema generale, nell'ambito dei dati, di stabilire quali record si riferiscano alla stessa cosa sottostante. Il risultato non è un fatto letto dalla blockchain, ma un'inferenza fondata su presupposti relativi al comportamento dei portafogli e delle persone. Che una transazione abbia speso tre input è un fatto registrato; che un solo soggetto li controllasse tutti e tre è una conclusione euristica, e il rapporto deve mantenere distinti i due aspetti.

Si noti la parola controllati. Un'euristica può al massimo mostrare che le stesse chiavi, o lo stesso software che agisce per un unico operatore, hanno movimentato i fondi. Un exchange custodiale controlla le chiavi di milioni di clienti, quindi un cluster etichettato "Exchange X" rappresenta il servizio, non uno qualsiasi dei suoi clienti. Il controllo non è proprietà, e nessuno dei due coincide con l'identità (lezione 4.5).

Come vengono costruiti i cluster

Il clustering comprende due fasi. Nella prima, le euristiche producono evidenze di collegamento: coppie di indirizzi che, secondo una determinata regola, condividono un soggetto controllante. La regola degli input comuni collega tutti gli input di una transazione; il rilevamento del resto collega un mittente al relativo output di resto (lezione 4.2); le blockchain basate su account utilizzano collegamenti comportamentali, come gli indirizzi di deposito condivisi (lezione 4.3). Nella seconda, l'analista calcola la chiusura transitiva di tali collegamenti: se A è collegato a B e B a C, allora A, B e C formano un unico cluster, anche se nessuna singola evidenza collega A e C. In termini di grafi, i cluster sono le componenti connesse del grafo delle evidenze.

Ad esempio, la transazione 4f3a…c21e spende dagli indirizzi a1 e a2, e la transazione 9b7d…e014, una settimana dopo, da a2 e a3. La regola produce i collegamenti a1–a2 e a2–a3; la chiusura produce un unico cluster {a1, a2, a3}. Il collegamento a1–a3 non è mai stato osservato: è ereditato. Se una delle due transazioni fosse stata in realtà collaborativa, con due proprietari, sarebbe errato l'intero cluster, non soltanto un collegamento.

L'euristica della titolarità comune degli input

La logica

Per spendere un UTXO, una transazione deve fornire uno script di sblocco o un witness valido per esso, in pratica una firma prodotta dalla chiave che lo controlla; quindi tre input richiedono firme per tre monete. Nell'uso ordinario, un portafoglio seleziona monete dal proprio saldo e le firma tutte. Pertanto, se diversi indirizzi compaiono come input di un'unica transazione, la spiegazione più probabile è che un unico portafoglio, e quindi un unico soggetto controllante, detenga tutte le relative chiavi.

L'idea è antica quanto Bitcoin: la sezione sulla riservatezza del white paper del 2008 avverte che le transazioni con più input "rivelano necessariamente che i loro input appartenevano allo stesso proprietario". Reid e Harrigan (2011) l'hanno utilizzata per costruire una rete di utenti, e Meiklejohn et al. (2013, "Una manciata di bitcoin") l'hanno formulata come Euristica 1: se due o più indirizzi sono input della stessa transazione, sono controllati dallo stesso utente. È anche chiamata euristica della titolarità comune degli input (CIOH) o euristica degli input multipli.

Un esempio svolto

Una transazione decodificata, semplificata ai campi rilevanti per il clustering (identificativi troncati):

{
  "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}
  ]
}

I tre input ammontano complessivamente a 0,0830 BTC e gli output a 0,0828 BTC, quindi la commissione è di 0,0002 BTC (20.000 satoshi). La regola degli input comuni collega bc1q…k3f7, bc1q…m9a2 e bc1q…x0d1. Non dice nulla sugli output: stabilire se bc1q…r4t6 sia resto appartenente allo stesso portafoglio è un'inferenza distinta e molto più debole (lezione 4.2).

Se bc1q…m9a2 si trovava già in un cluster di 2.000 indirizzi e bc1q…x0d1 in un cluster di 300, questa singola transazione li unisce in un cluster di 2.301 indirizzi. Questa è la forza della regola e, al contempo, il suo pericolo.

La regola è particolarmente solida nel caso dei servizi. Gli exchange custodiali e i gestori di pagamenti consolidano periodicamente molti piccoli depositi in un unico output, con una transazione di aggregazione che può spendere da centinaia di indirizzi di deposito contemporaneamente. Ogni operazione di svuotamento collega tutti questi indirizzi al portafoglio del servizio: per questo i cluster dei servizi crescono fino a milioni di indirizzi e spesso un solo deposito verificato è sufficiente per etichettarli (lezione 4.5). Un utente che unisce una dozzina di vecchie monete per risparmiare sulle commissioni future rivela allo stesso modo che un unico portafoglio le deteneva tutte. Entrambi i casi sono corretti purché nessun altro abbia contribuito con un input.

Quanto funziona bene

Meiklejohn et al. hanno applicato la regola all'intera blockchain nel 2013, riducendo 12.056.684 chiavi pubbliche a circa 5,58 milioni di cluster. Nick (2015, tesi di laurea magistrale) ha ottenuto rari dati di riferimento certi da una fuga di informazioni riservate nei filtri di Bloom dei portafogli leggeri, che esponeva gli insiemi di indirizzi di portafogli reali; la regola degli input comuni ha identificato oltre il 69% degli indirizzi di quei portafogli. Si noti che cosa misura questa percentuale: il richiamo (quanta parte di ciascun portafoglio è stata individuata), non la precisione (quanti collegamenti erano corretti). La regola è generalmente considerata ad alta precisione per le transazioni ordinarie, ma si tratta di un presupposto sul comportamento dei portafogli, che le transazioni descritte di seguito violano (la lezione 4.4 tratta la misurazione della qualità dei cluster).

Quando il presupposto non è valido

CoinJoin. Più utenti concordano un'unica transazione; ciascuno contribuisce con input e firma soltanto i propri, e gli output ne includono tipicamente diversi di identico valore, in modo che nessuno possa stabilire a chi appartenga ciascun output. Applicare la regola degli input comuni unisce i portafogli di tutti i partecipanti: è proprio il falso collegamento che CoinJoin è progettato per indurre (lezione 6.2).

PayJoin. In un PayJoin (BIP 78), il destinatario di un pagamento aggiunge uno dei propri input alla transazione del mittente. Il risultato appare come un normale pagamento con due input, quindi la regola collega le monete del mittente e del destinatario, distorcendo anche l'importo apparente del pagamento. Un PayJoin ben costruito non può essere distinto in modo affidabile da una transazione normale, perciò la sua esistenza impone un limite alla forza di qualsiasi singolo collegamento. La sua adozione è stata limitata, il che riduce il danno complessivo ma non ne esclude la presenza in un caso specifico.

Altre transazioni con più partecipanti. Le aperture di canali Lightning finanziati da entrambe le parti, alcuni protocolli di scambio e di raggruppamento dei pagamenti e le transazioni firmate con SIGHASH_ANYONECANPAY, che consente ad altri di aggiungere input dopo la prima firma (utilizzato, ad esempio, nei contratti di tipo crowdfunding), presentano tutti input provenienti da più soggetti.

Controllo condiviso. Un indirizzo multifirma detenuto congiuntamente da più persone costituisce un unico "proprietario" dal punto di vista dello script; l'entità corretta è l'assetto congiunto, non un singolo firmatario.

Custodia e importazione delle chiavi. Un servizio custodiale spende insieme i depositi dei clienti, quindi il suo cluster è corretto per il servizio ma non dice nulla sui clienti. I portafogli che consentono agli utenti di importare o svuotare chiavi private ricevute da altri (portafogli cartacei, carte regalo) possono collegare monete che avevano proprietari diversi. Harrigan e Fretter ("L'irragionevole efficacia del clustering degli indirizzi", 2016) hanno escluso il più grande cluster Bitcoin, con oltre 10 milioni di indirizzi originariamente appartenenti a Mt. Gox, proprio per questo motivo.

I cluster non sono entità

La corrispondenza tra cluster ed entità del mondo reale viene meno in entrambe le direzioni.

• Un'entità, molti cluster (unificazione insufficiente). I portafogli offline di un exchange potrebbero non essere mai utilizzati per spendere insieme ai suoi portafogli online; una persona potrebbe usare tre applicazioni di portafoglio non correlate; nelle blockchain basate su account, prive di spese con più input, un operatore appare spesso come decine di indirizzi non collegati.
• Un cluster, molte entità (unificazione eccessiva). I CoinJoin, il raggruppamento custodiale dei fondi e l'importazione delle chiavi, come descritto sopra, uniscono portafogli appartenenti a persone diverse.

I cluster cambiano anche nel tempo: un cluster calcolato al blocco 800.000 può unirsi a un altro entro il blocco 850.000. Ogni cluster è un'istantanea e dovrebbe riportare l'altezza del blocco alla quale è stato calcolato.

Falsi positivi, falsi negativi e propagazione degli errori

Un collegamento falso positivo unisce indirizzi che non sono controllati dallo stesso soggetto; un falso negativo è un collegamento reale non rilevato dal metodo. I loro costi ricadono su utenti diversi:

Nessun insieme di euristiche è il migliore per tutti: un team di conformità normativa che blocca transazioni sulla base delle etichette dei cluster dovrebbe privilegiare la precisione; un investigatore che genera piste può accettare più falsi positivi, purché ogni pista sia verificata prima di essere inserita in un rapporto.

Gli errori di clustering non sono proporzionali al numero di collegamenti errati. Poiché i cluster sono chiusure transitive, un solo falso collegamento tra un cluster di 5.000 indirizzi e uno di 40.000 produce un cluster di 45.000, e ogni indirizzo condivide ora qualsiasi etichetta presente su uno dei due lati. Gli errori si accumulano anche con l'aumentare delle dimensioni. Se ogni collegamento ha, indipendentemente dagli altri, una probabilità p di essere errato, un cluster costruito a partire da n collegamenti è privo di errori con probabilità (1 − p)^n. Con p = 0,001 e n = 1.000 collegamenti, tale probabilità è 0,999^1.000 ≈ 0,37: una probabilità del 63% che il cluster contenga almeno un'unificazione errata. I cluster grandi hanno quindi maggiori probabilità di essere contaminati, proprio laddove gli analisti tendono a riporre maggiore fiducia. Meiklejohn et al. hanno rilevato che una versione ingenua della loro euristica del resto produceva un supercluster di 1,6 milioni di chiavi pubbliche contenente Mt. Gox, Instawallet, BitPay e Silk Road (la lezione 4.4 tratta questi supercluster). A valle, l'etichetta risultante dall'unificazione modifica le statistiche dei flussi e i punteggi di rischio, e un rapporto finisce per affermare una conclusione non supportata dalle evidenze, attraverso passaggi che, singolarmente, apparivano ragionevoli.

Misure di salvaguardia e registrazione delle evidenze

Filtrare e monitorare prima di collegare

1. Escludere i probabili CoinJoin. Il test più semplice cerca diversi output con esattamente lo stesso valore:

-- Segnalare i possibili CoinJoin per non collegarne gli input
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;  -- calibrare questa soglia e documentarla

La query conta, per ciascuna transazione, quanti output condividono ogni valore, conserva il gruppo più numeroso e segnala le transazioni con più input nelle quali almeno tre output sono identici. La soglia è una scelta discrezionale. Il test intercetta anche alcuni pagamenti raggruppati degli exchange con importi uguali; escluderli costa soltanto qualche collegamento (un falso negativo), l'errore più sicuro. Non rileva le varianti di CoinJoin che evitano output uguali, quindi è un filtro, non un rilevatore; per lo stesso motivo, anche gli studi sul clustering, come quello di Goldfeder et al. (2018), aggiungono un'esclusione dei CoinJoin.

1. Segnalare combinazioni insolite di input. Input con tipi di script diversi (ad esempio, un input P2PKH tradizionale accanto a un input P2TR) sono poco comuni per un software di portafoglio singolo e meritano un esame supplementare.
2. Monitorare le unificazioni. Esaminare qualsiasi collegamento che unirebbe due cluster grandi o due cluster con etichette diverse. Harrigan e Fretter hanno osservato che i cluster grandi si uniscono raramente in modo naturale, quindi una simile unificazione è un segnale di allarme. Esaminare anche qualsiasi cluster che cresca bruscamente tra un'istantanea e l'altra.

Conservare le evidenze, non soltanto i cluster

Memorizzare una riga per ciascuna evidenza di collegamento:

-- Una riga per ogni evidenza di collegamento, non una riga per cluster
CREATE TABLE cluster_evidence (
  addr_a        VARCHAR NOT NULL,
  addr_b        VARCHAR NOT NULL,
  heuristic     VARCHAR NOT NULL,  -- ad es. 'common_input', 'change_v3'
  evidence_tx   VARCHAR NOT NULL,  -- txid o hash della transazione
  block_height  BIGINT  NOT NULL,
  strength      VARCHAR            -- 'high', 'moderate' o 'low' (vedere la tabella seguente)
);

-- Ricostruire i cluster soltanto dalle evidenze più forti
SELECT addr_a, addr_b
FROM cluster_evidence
WHERE heuristic = 'common_input'
  AND strength = 'high';

Poiché i cluster derivano da questa tabella, l'analista può ricostruirli con un insieme di euristiche più rigoroso o più permissivo, rimuovere una transazione successivamente identificata come CoinJoin o PayJoin e vedere quali collegamenti vengono meno, oppure mostrare a un revisore perché due indirizzi siano finiti insieme. Calcolare le componenti connesse in SQL puro è poco agevole (le CTE ricorsive funzionano, ma scalano male); la maggior parte dei team esporta gli archi selezionati in una libreria per grafi o in una procedura union-find. La generazione su larga scala delle coppie di input, con la stessa esclusione dei CoinJoin, è trattata nella lezione 2.9 (i nomi delle colonne qui utilizzati seguono il relativo schema UTXO).

Forza e rendicontazione

Nella scala A–D del corso (lezione 3.2), ogni collegamento basato sugli input comuni è di grado C, una singola euristica, indipendentemente dalla riga in cui rientra qui; la tabella classifica la forza dei collegamenti all'interno di quel grado e stabilisce quali possano trasmettere etichette (lezione 4.5). Il corso riserva la parola "confidenza" al fondamento di un giudizio riportato (lezione 9.2), quindi i collegamenti euristici sono valutati in base alla forza. Indicare nome e data dell'insieme di euristiche, delle esclusioni, delle soglie e dell'altezza del blocco dell'istantanea alla base di ogni cluster citato. Scrivere "indirizzi raggruppati mediante l'euristica degli input comuni, con filtro CoinJoin attivo, etichettati come Servizio X sulla base di un deposito di prova" anziché "il portafoglio del Servizio X" (la lezione 9.2 tratta il linguaggio dei rapporti). Infine, verificare la sensibilità: ripetere le analisi dei risultati principali senza l'euristica più debole e indicare se restano validi.

Focus sull'esame: la differenza tra un indirizzo, un cluster e un'entità, e tra controllo e proprietà per i servizi custodiali; il clustering come risoluzione delle entità e come chiusura transitiva (componenti connesse) delle evidenze di collegamento; perché gli input spesi congiuntamente implicano un soggetto controllante comune e l'origine della regola (white paper, Euristica 1 di Meiklejohn et al.); richiamo e precisione nelle evidenze dei filtri di Bloom (oltre il 69% degli indirizzi dei portafogli individuati); le eccezioni (CoinJoin, PayJoin secondo BIP 78, canali finanziati da entrambe le parti, SIGHASH_ANYONECANPAY, multifirma, custodia e importazione delle chiavi); unificazione insufficiente ed eccessiva; i diversi costi dei falsi positivi e dei falsi negativi; perché un solo falso collegamento unisce interi cluster e propaga le etichette, e il ragionamento (1 − p)^n; filtraggio degli output di uguale valore con una soglia documentata; memorizzazione delle evidenze con euristica, transazione e altezza del blocco, affinché i cluster possano essere ricostruiti.