Valutare la qualità dei cluster

Un cluster è un’ipotesi sul controllo, e le ipotesi vanno verificate. Gli analisti che non sanno valutare la qualità dei propri cluster non possono dire quanto sia affidabile un risultato basato su di essi. Questa lezione spiega come si misura la qualità dei cluster, cosa ha rilevato la letteratura di ricerca sui tassi di errore delle euristiche, come individuare il collasso dei cluster e come dimostrare che una conclusione resta valida anche con ragionevoli variazioni di metodo.

Verità di riferimento e relativi bias

Per valutare i cluster serve una verità di riferimento: indirizzi il cui controllore è noto indipendentemente dalle euristiche sottoposte a verifica. Le vere verità di riferimento sono rare e ogni fonte presenta bias:

Nick (2015, una tesi magistrale sulla de-anonimizzazione di Bitcoin) è un raro esempio basato su dati trapelati: una falla di privacy nei filtri Bloom dei wallet leggeri ha esposto gli insiemi di indirizzi di wallet reali e l’euristica degli input comuni ha individuato più del 69% degli indirizzi al loro interno. Möser e Narayanan (2022, «Resurrecting Address Clustering in Bitcoin») hanno usato etichette rivelate dal comportamento: 35,26 milioni di transazioni il cui resto è stato in seguito individuato tramite la regola degli input comuni. Nessuno dei due studi costituisce un campione casuale di tutti gli utenti, ed entrambi sono legati al periodo in cui sono stati condotti. Considerate ogni tasso di errore pubblicato come «misurato su questa verità di riferimento, in questo momento».

Precisione e richiamo per i cluster

La precisione indica quanta parte di ciò che il metodo ha raggruppato appartiene davvero allo stesso insieme; il richiamo indica quanta parte di ciò che appartiene allo stesso insieme è stata individuata dal metodo. Per i cluster si usano comunemente due metodi di conteggio.

Esempio svolto. L’entità E controlla 10 indirizzi e l’entità F ne controlla 4. Il metodo ha prodotto il cluster C, che contiene 8 indirizzi di E e tutti e 4 quelli di F (una fusione errata), mentre gli altri 2 indirizzi di E si trovano in un cluster separato.

• A livello di indirizzo (C considerato come cluster di E): precisione = 8 ÷ 12 = 0,67; richiamo = 8 ÷ 10 = 0,80.
• A coppie: C contiene 12 × 11 ÷ 2 = 66 coppie di indirizzi. Le coppie corrette sono E–E (8 × 7 ÷ 2 = 28) più F–F (4 × 3 ÷ 2 = 6), per un totale di 34. La precisione a coppie è 34 ÷ 66 = 0,52. Nella realtà, le coppie vere sono 45 per E più 6 per F, quindi 51; il richiamo a coppie è 34 ÷ 51 = 0,67.

Il conteggio a coppie penalizza maggiormente le fusioni errate, perché una fusione crea molte coppie sbagliate in una volta sola; questo rispecchia il danno che le fusioni arrecano all’analisi. Specificate sempre quale metodo di conteggio è stato usato per ottenere un valore.

-- Precisione e richiamo a livello di indirizzo per ogni cluster rispetto alla verità di riferimento
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;

Per ogni cluster, la query conta quanti dei suoi indirizzi inclusi nella verità di riferimento appartengono a ciascuna entità, seleziona l’entità dominante e divide l’intersezione per gli indirizzi del cluster con etichetta (precisione) e per la dimensione nota dell’entità (richiamo). Gli indirizzi privi di verità di riferimento vengono ignorati, scelta corretta: sono sconosciuti, non corretti. Moltiplicare per 1,0 evita la divisione intera nei motori che troncano il risultato.

Verifiche che non richiedono una verità di riferimento

La maggior parte delle indagini reali non dispone di una verità di riferimento per le entità coinvolte. Le verifiche di coerenza interna possono comunque rivelare problemi:

• Coerenza delle impronte. Gli indirizzi controllati da un unico wallet tendono ad avere in comune il tipo di script, la versione della transazione, le abitudini relative al locktime e lo stile delle commissioni. Un cluster le cui transazioni di spesa mostrano molte impronte non correlate probabilmente fonde più wallet. Kappos et al. (2022, «How to Peel a Million: Validating and Expanding Bitcoin Clusters») hanno usato caratteristiche di questo tipo, calcolate sull’intero cluster, per separare i cluster contaminati da CoinJoin da quelli puliti.
• Coerenza temporale. Se gli indirizzi di un cluster sono stati attivi in periodi molto distanti, senza alcun collegamento tra i periodi se non una singola transazione, è opportuno esaminare quella transazione.
• Coerenza comportamentale. Un cluster che in una parte si comporta come un exchange (migliaia di depositi e trasferimenti aggregati) e in un’altra come un singolo utente (pochi pagamenti manuali) potrebbe contenere due entità unite da un solo collegamento.
• Distribuzione delle dimensioni. Un aumento improvviso della dimensione dei cluster più grandi dopo una modifica del metodo indica probabilmente nuovi collegamenti errati, non nuove informazioni.

Nessuno di questi elementi dimostra che un cluster sia corretto, ma ciascuno può mostrare che probabilmente è sbagliato.

Cosa mostrano le ricerche sui tassi di errore

Ne seguono quattro conclusioni. I tassi di errore dipendono molto dal metodo di misurazione: la stessa euristica del resto ottiene lo 0,17% nel test di falsificazione degli autori e il 51,64% rispetto a cluster verificati in modo indipendente, nove anni dopo. Le euristiche invecchiano al cambiare del software dei wallet e delle abitudini degli utenti. Combinare più segnali è meglio che usare una singola regola. Infine, le euristiche per il modello account sono ancora in gran parte prive di convalida.

Collasso dei cluster

Il collasso dei cluster si verifica quando collegamenti errati fondono entità non correlate in un supercluster. La letteratura offre diversi esempi:

• L’euristica ingenua del resto di Meiklejohn et al. ha prodotto un cluster di 1,6 milioni di chiavi che comprendeva Mt. Gox, Instawallet, BitPay e Silk Road.
• Möser e Narayanan hanno rilevato che l’unione ingenua basata sul loro classificatore del resto produceva un cluster di 223,9 milioni di indirizzi, che assorbiva 113 dei 273 cluster etichettati in modo indipendente. I vincoli basati sul comportamento di spesa previsto hanno impedito 413.608 fusioni; il cluster più grande rimasto conteneva 40,5 milioni di indirizzi e si sono comunque fuse sette coppie di cluster etichettati.
• Harrigan e Fretter (2016, «The Unreasonable Effectiveness of Address Clustering») hanno escluso del tutto il cluster di Mt. Gox perché una funzione di importazione delle chiavi rendeva inaffidabile la regola degli input comuni in quel caso.

Segnali di allarme pratici:

1. Conflitti tra etichette: due exchange diversi, oppure un exchange e un mixer, finiscono nello stesso cluster.
2. Fusioni tra cluster grandi: Harrigan e Fretter hanno osservato che i cluster grandi raramente si fondono in modo naturale, quindi queste fusioni vanno esaminate.
3. Crescita improvvisa: un cluster che acquisisce in un’unica istantanea una quota consistente delle proprie dimensioni.
4. Singoli punti critici: una transazione è responsabile dell’unione di due componenti grandi; cercatela nella tabella delle evidenze ed esaminatela.

Analisi di sensibilità

L’analisi di sensibilità ripete un’analisi con metodi diversi ma ragionevoli e riferisce come cambia il risultato. Una progressione tipica:

In questo caso, i primi due valori sono molto vicini, mentre il terzo è quasi il triplo. Un rapporto accurato affermerebbe «almeno 120 BTC, e circa 141 BTC includendo i collegamenti del resto ad alta affidabilità» e considererebbe inaffidabili i 410 BTC, probabilmente gonfiati da una fusione. La ricerca mostra lo stesso effetto su vasta scala: Möser e Narayanan hanno rilevato che l’aggiunta del loro clustering del resto aumentava del 13,8% i flussi stimati dai mercati darknet agli exchange e riduceva di circa l’11,9% una stima della velocità di circolazione delle monete. Le scelte metodologiche modificano i valori principali.

Documentare le ipotesi

Ogni rapporto che si basa sui cluster dovrebbe riportare:

• l’insieme di euristiche, la relativa versione e le soglie (per esempio, il filtro CoinJoin e il punteggio minimo del resto);
• l’istantanea dei dati: chain, altezza del blocco e versione del nodo o del dataset;
• la verità di riferimento usata per valutare i cluster, le sue dimensioni e i bias noti;
• i tassi di errore misurati o citati, con la fonte e la data;
• i collassi noti esclusi e le fusioni esaminate;
• i risultati dell’analisi di sensibilità per ogni risultato chiave;
• le fonti e i livelli delle etichette (vedere la lezione Attribuzione ed etichettatura).

Questa documentazione consente a un revisore di riprodurre i cluster, contestare un collegamento specifico e capire quali conclusioni resterebbero valide se un’euristica si rivelasse errata. La lezione Redigere il rapporto analitico mostra dove inserire queste informazioni nel documento finale.

Focus sull'esame: fonti della verità di riferimento e relativi bias, inclusa la circolarità delle etichette dei fornitori; precisione e richiamo a livello di indirizzo e a coppie, e calcolo di entrambi a partire da un piccolo esempio; perché le metriche a coppie penalizzano le fusioni errate; cosa mostrano i dati della ricerca, soprattutto lo 0,17% contro il 51,64% per la stessa euristica del resto e perché anche un tasso di falsi positivi dello 0,06% può causare il collasso dei cluster su vasta scala; il collasso dei cluster e i relativi segnali di allarme; l’analisi di sensibilità e la comunicazione di un limite inferiore robusto; la documentazione di euristiche, soglie, istantanea, verità di riferimento e tassi di errore.