Clusterqualität bewerten

Ein Cluster ist eine Hypothese darüber, wer die Kontrolle ausübt, und Hypothesen müssen überprüft werden. Analysten, die nicht sagen können, wie gut ihre Cluster sind, können auch nicht sagen, wie sehr sie einem darauf basierenden Befund vertrauen sollten. In dieser Lektion geht es darum, wie die Qualität von Clustern gemessen wird, was die Forschungsliteratur über Fehlerraten heuristischer Verfahren herausgefunden hat, wie sich ein Clusterkollaps erkennen lässt und wie gezeigt werden kann, dass eine Schlussfolgerung auch bei angemessenen Änderungen der Methode Bestand hat.

Ground Truth und ihre Verzerrungen

Für die Bewertung von Clustern ist eine Ground Truth erforderlich: Adressen, deren kontrollierende Instanz unabhängig von den zu prüfenden Heuristiken bekannt ist. Echte Ground Truth ist selten, und jede Quelle ist verzerrt:

Nick (2015, eine Masterarbeit zur Deanonymisierung in Bitcoin) ist ein seltenes Beispiel auf Grundlage eines Datenlecks: Eine Datenschutzlücke in den Bloom-Filtern leichtgewichtiger Wallets legte die Adressmengen echter Wallets offen, und die Common-Input-Heuristik fand darin mehr als 69 % der Adressen. Möser und Narayanan (2022, „Resurrecting Address Clustering in Bitcoin“) verwendeten durch Verhalten offengelegte Kennzeichnungen: 35,26 Millionen Transaktionen, deren Wechselgeld später durch die Common-Input-Regel offengelegt wurde. Keines der beiden Beispiele ist eine Zufallsstichprobe aller Nutzer, und beide sind an ihren jeweiligen Zeitraum gebunden. Behandeln Sie jede veröffentlichte Fehlerrate als „auf Grundlage dieser Ground Truth zu diesem Zeitpunkt gemessen“.

Präzision und Trefferquote bei Clustern

Präzision fragt, wie viel von dem, was die Methode zusammengeführt hat, tatsächlich zusammengehört; Trefferquote fragt, wie viel von dem, was zusammengehört, die Methode gefunden hat. Bei Clustern gibt es zwei verbreitete Zählweisen.

Ein ausgearbeitetes Beispiel. Entität E kontrolliert 10 Adressen und Entität F 4. Die Methode erzeugte Cluster C mit 8 Adressen von E und allen 4 Adressen von F (eine falsche Zusammenführung), während die übrigen 2 Adressen von E in einem separaten Cluster liegen.

• Auf Adressebene (C wird als Cluster von E bewertet): Präzision = 8 ÷ 12 = 0,67; Trefferquote = 8 ÷ 10 = 0,80.
• Paarweise: C enthält 12 × 11 ÷ 2 = 66 Adresspaare. Die korrekten Paare sind E–E (8 × 7 ÷ 2 = 28) plus F–F (4 × 3 ÷ 2 = 6), also insgesamt 34. Die paarweise Präzision = 34 ÷ 66 = 0,52. In Wirklichkeit gibt es 45 echte Paare für E und 6 für F, also 51; die paarweise Trefferquote = 34 ÷ 51 = 0,67.

Die paarweise Zählung bestraft falsche Zusammenführungen stärker, weil eine Zusammenführung auf einmal viele falsche Paare erzeugt. Das entspricht dem Schaden, den Zusammenführungen für Analysen verursachen. Geben Sie immer an, welche Zählweise für eine Kennzahl verwendet wurde.

-- Präzision und Trefferquote auf Adressebene für jeden Cluster im Vergleich zur Ground Truth
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;

Die Abfrage zählt für jeden Cluster, wie viele seiner Ground-Truth-Adressen zu jeder Entität gehören, wählt die dominante Entität aus und teilt die Überschneidung durch die Anzahl der gekennzeichneten Adressen im Cluster (Präzision) und durch die bekannte Größe der Entität (Trefferquote). Adressen ohne Ground Truth werden ignoriert. Das ist die ehrliche Wahl: Sie sind unbekannt, nicht korrekt. Die Multiplikation mit 1.0 verhindert eine Ganzzahldivision in Engines, die abrunden.

Prüfungen ohne Ground Truth

Bei den meisten realen Untersuchungen gibt es keine Ground Truth für die beteiligten Entitäten. Prüfungen der internen Konsistenz können dennoch Probleme aufdecken:

• Konsistenz von Fingerprints. Adressen, die von einer Wallet kontrolliert werden, haben in der Regel denselben Skripttyp, dieselbe Transaktionsversion, ähnliche Locktime-Gewohnheiten und denselben Gebührenstil. Wenn die Ausgaben von Adressen in einem Cluster viele unterschiedliche Fingerprints aufweisen, wurden wahrscheinlich mehrere Wallets zusammengeführt. Kappos et al. (2022, „How to Peel a Million: Validating and Expanding Bitcoin Clusters“) nutzten clusterweite Merkmale dieser Art, um durch CoinJoins verunreinigte von unverfälschten Clustern zu trennen.
• Zeitliche Kohärenz. Ein Cluster, dessen Adressen in weit auseinanderliegenden Zeiträumen aktiv waren und zwischen diesen Zeiträumen nur durch eine einzige Transaktion verbunden sind, verdient eine Prüfung dieser Transaktion.
• Verhaltenskohärenz. Ein Cluster, der sich in einem Teil wie eine Börse verhält (Tausende Einzahlungen und Sammeltransaktionen) und in einem anderen wie ein einzelner Nutzer (einige wenige manuelle Zahlungen), könnte zwei Entitäten enthalten, die durch eine einzige Verknüpfung verbunden wurden.
• Größenverteilung. Ein plötzlicher Sprung bei der Größe der größten Cluster nach einer Methodenänderung deutet eher auf neue falsche Verknüpfungen als auf neue Erkenntnisse hin.

Nichts davon beweist, dass ein Cluster korrekt ist, aber jeder dieser Punkte kann zeigen, dass er wahrscheinlich falsch ist.

Was die Forschung über Fehlerraten zeigt

Daraus ergeben sich vier Schlussfolgerungen. Fehlerraten hängen stark davon ab, wie sie gemessen werden: Dieselbe Wechselgeld-Heuristik erzielt 0,17 % beim Falsifikationstest ihrer Autoren und 51,64 % bei unabhängigen verifizierten Clustern neun Jahre später. Heuristiken veralten, wenn sich Wallet-Software und Nutzergewohnheiten ändern. Die Kombination mehrerer Signale ist jeder einzelnen Regel überlegen. Und Heuristiken für Kontomodelle sind nach wie vor weitgehend unvalidiert.

Clusterkollaps

Ein Clusterkollaps tritt auf, wenn falsche Verknüpfungen nicht zusammengehörige Entitäten zu einem Supercluster zusammenführen. Die Literatur bietet mehrere Beispiele:

• Die naive Wechselgeld-Heuristik von Meiklejohn et al. erzeugte einen Cluster mit 1,6 Millionen Schlüsseln, der Mt. Gox, Instawallet, BitPay und Silk Road enthielt.
• Möser und Narayanan stellten fest, dass eine naive Zusammenführung anhand ihres Wechselgeld-Klassifikators einen Cluster mit 223,9 Millionen Adressen erzeugte, der 113 von 273 unabhängig gekennzeichneten Clustern aufnahm. Einschränkungen auf Grundlage des vorhergesagten Ausgabeverhaltens verhinderten 413.608 Zusammenführungen; der größte verbleibende Cluster hatte 40,5 Millionen Adressen, und sieben Paare gekennzeichneter Cluster wurden weiterhin zusammengeführt.
• Harrigan und Fretter (2016, „The Unreasonable Effectiveness of Address Clustering“) schlossen den Mt.-Gox-Cluster vollständig aus, weil eine Funktion zum Importieren von Schlüsseln die Common-Input-Regel dort unzuverlässig machte.

Praktische Warnzeichen:

1. Widersprüchliche Kennzeichnungen: Zwei verschiedene Börsen oder eine Börse und ein Mixer landen in einem Cluster.
2. Zusammenführungen großer Cluster: Harrigan und Fretter beobachteten, dass große Cluster nur selten auf natürliche Weise zusammengeführt werden; solche Zusammenführungen sollten daher überprüft werden.
3. Plötzlicher Zuwachs: Ein Cluster erreicht innerhalb eines Snapshots einen großen Anteil seiner Größe.
4. Einzelne Fehlerquellen: Eine Transaktion ist dafür verantwortlich, zwei große Komponenten zu verbinden; suchen Sie sie in der Evidenztabelle und untersuchen Sie sie.

Sensitivitätsanalyse

Bei einer Sensitivitätsanalyse wird ein Befund mit verschiedenen angemessenen Methoden erneut berechnet, und es wird berichtet, wie sich das Ergebnis verändert. Eine typische Abstufung:

Hier stimmen die ersten beiden Zeilen weitgehend überein, während sich die Zahl in der dritten Zeile fast verdreifacht. Ein sorgfältiger Bericht würde festhalten: „Mindestens 120 BTC und etwa 141 BTC unter Einbeziehung von Wechselgeld-Verknüpfungen mit hoher Konfidenz.“ Die Zahl von 410 BTC wäre als unzuverlässig zu behandeln und wahrscheinlich durch eine Zusammenführung überhöht. Die Forschung zeigt denselben Effekt in großem Maßstab: Möser und Narayanan stellten fest, dass die Ergänzung ihres Wechselgeld-Clusterings die geschätzten Zahlungsflüsse von Darknet-Märkten zu Börsen um 13,8 % erhöhte und eine Schätzung der Umlaufgeschwindigkeit von Coins um etwa 11,9 % senkte. Die Methodenwahl verändert die Schlagzeilenzahlen.

Annahmen dokumentieren

Jeder Bericht, der sich auf Cluster stützt, sollte Folgendes festhalten:

• das verwendete Heuristik-Set, seine Version und Schwellenwerte (zum Beispiel den CoinJoin-Filter und den Schwellenwert für den Wechselgeld-Score);
• den Datensnapshot: Blockchain, Blockhöhe und Node- oder Datensatzversion;
• die zur Bewertung der Cluster verwendete Ground Truth, ihren Umfang und ihre bekannten Verzerrungen;
• gemessene oder zitierte Fehlerraten mit Quelle und Datum;
• bekannte ausgeschlossene Clusterkollapse und überprüfte Zusammenführungen;
• die Sensitivitätsergebnisse für jeden wichtigen Befund;
• Quellen und Einstufungen der Kennzeichnungen (siehe die Lektion Attribution und Kennzeichnung).

Diese Dokumentation ermöglicht es einer prüfenden Person, die Cluster zu reproduzieren, eine bestimmte Verknüpfung infrage zu stellen und zu erkennen, welche Schlussfolgerungen Bestand hätten, wenn sich eine Heuristik als falsch herausstellte. Die Lektion Den Analysebericht verfassen zeigt, wo sie im Abschlussdokument hingehört.

Prüfungsschwerpunkt: Quellen der Ground Truth und ihre Verzerrungen, einschließlich Zirkelschlüssen bei Kennzeichnungen von Anbietern; Präzision und Trefferquote auf Adressebene gegenüber der paarweisen Betrachtung sowie die Berechnung beider Kennzahlen anhand eines kleinen Beispiels; warum paarweise Kennzahlen falsche Zusammenführungen stärker bestrafen; was die Forschungszahlen zeigen, vor allem 0,17 % gegenüber 51,64 % bei derselben Wechselgeld-Heuristik und warum selbst eine Rate von 0,06 % falsch positiven Ergebnissen Cluster in großem Maßstab kollabieren lassen kann; Clusterkollaps und seine Warnzeichen; Sensitivitätsanalyse und Berichterstattung einer robusten Untergrenze; Dokumentation von Heuristiken, Schwellenwerten, Snapshot, Ground Truth und Fehlerraten.