Clustering und die Heuristik gemeinsamer Input-Kontrolle

Fast jede On-Chain-Aussage darüber, „wer“ hinter einer Aktivität steht, beruht auf einem Clustering-Schritt. Wenn ein Bericht feststellt, dass eine Börse 40 BTC erhalten hat oder eine Ransomware-Gruppe 300 Adressen kontrolliert, hängt diese Aussage von einer Methode ab, die Adressen zusammengefasst hat, und von den Fehlern dieser Methode. Auf UTXO-Blockchains stammen die meisten Verknüpfungen innerhalb eines Clusters aus einer einzigen Regel: der Heuristik gemeinsamer Input-Kontrolle. Sie trifft meist zu; wenn sie jedoch falschliegt, führt sie ganze Wallets zusammen. Diese Lektion behandelt, was Clustering ist, warum die Regel funktioniert, welche Transaktionen sie verletzen und wie Sie Cluster so dokumentieren, dass eine prüfende Person sie Verknüpfung für Verknüpfung zerlegen kann.

Adressen, Cluster und Entitäten

Drei Ebenen werden leicht verwechselt:

Clustering ist die Blockchain-Variante der Entitätsauflösung, also des allgemeinen Datenproblems, zu entscheiden, welche Datensätze sich auf dasselbe zugrunde liegende Objekt beziehen. Das Ergebnis ist keine aus der Blockchain abgelesene Tatsache, sondern eine Schlussfolgerung auf Grundlage von Annahmen darüber, wie sich Wallets und Menschen verhalten. Dass eine Transaktion drei Inputs ausgegeben hat, ist eine aufgezeichnete Tatsache; dass eine Partei alle drei kontrolliert hat, ist eine heuristische Schlussfolgerung. Der Bericht muss beides auseinanderhalten.

Beachten Sie das Wort kontrolliert. Eine Heuristik kann bestenfalls zeigen, dass dieselben Schlüssel oder dieselbe Software im Auftrag eines Betreibers die Mittel bewegt haben. Eine verwahrende Börse kontrolliert die Schlüssel für Millionen von Kunden. Ein als „Börse X“ gekennzeichnetes Cluster repräsentiert daher den Dienst, nicht einen seiner Kunden. Kontrolle ist nicht Eigentum, und keines von beiden ist Identität (Lektion 4.5).

Wie Cluster aufgebaut werden

Clustering erfolgt in zwei Schritten. Zunächst erzeugen Heuristiken Verknüpfungsbelege: Adresspaare, die nach einer bestimmten Regel von derselben Instanz kontrolliert werden. Die Regel gemeinsamer Inputs verknüpft alle Inputs einer Transaktion; die Wechselgelderkennung verknüpft einen Absender mit seinem Wechselgeld-Output (Lektion 4.2); kontobasierte Blockchains nutzen Verhaltensverknüpfungen wie gemeinsam genutzte Einzahlungsadressen (Lektion 4.3). Anschließend bildet der Analyst die transitive Hülle dieser Verknüpfungen: Ist A mit B und B mit C verknüpft, bilden A, B und C ein Cluster, obwohl kein einzelner Beleg A und C verbindet. Graphentheoretisch sind Cluster die Zusammenhangskomponenten des Beleggraphen.

Beispielsweise gibt die Transaktion 4f3a…c21e Mittel von den Adressen a1 und a2 aus, und die Transaktion 9b7d…e014 eine Woche später von a2 und a3. Die Regel liefert die Verknüpfungen a1–a2 und a2–a3; die transitive Hülle ergibt ein Cluster {a1, a2, a3}. Die Verknüpfung a1–a3 wurde nie beobachtet; sie wird übernommen. War eine der beiden Transaktionen tatsächlich eine gemeinschaftliche Transaktion mit zwei Eigentümern, ist das gesamte Cluster falsch, nicht nur eine Verknüpfung.

Die Heuristik gemeinsamer Input-Kontrolle

Die Logik

Um einen UTXO auszugeben, muss eine Transaktion ein gültiges Entsperrskript oder einen gültigen Witness dafür bereitstellen, in der Praxis eine Signatur des kontrollierenden Schlüssels. Drei Inputs benötigen somit Signaturen für drei Coins. Im gewöhnlichen Gebrauch wählt eine Wallet Coins aus ihrem eigenen Bestand aus und signiert sie alle. Wenn also mehrere Adressen als Inputs einer Transaktion erscheinen, ist die wahrscheinlichste Erklärung, dass eine Wallet und damit eine kontrollierende Instanz alle zugehörigen Schlüssel hält.

Die Idee ist so alt wie Bitcoin: Der Abschnitt zum Datenschutz im Whitepaper von 2008 warnt, dass Transaktionen mit mehreren Inputs „zwangsläufig offenlegen, dass ihre Inputs demselben Eigentümer gehörten“. Reid und Harrigan (2011) nutzten sie zum Aufbau eines Nutzernetzwerks, und Meiklejohn et al. (2013, „A Fistful of Bitcoins“) formulierten sie als ihre Heuristik 1: Wenn zwei oder mehr Adressen Inputs derselben Transaktion sind, werden sie von demselben Nutzer kontrolliert. Sie wird auch als Common-Input Ownership Heuristic (CIOH) oder Multi-Input-Heuristik bezeichnet.

Ein durchgerechnetes Beispiel

Eine dekodierte Transaktion, vereinfacht auf die für das Clustering relevanten Felder (Kennungen gekürzt):

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

Die drei Inputs ergeben zusammen 0,0830 BTC und die Outputs 0,0828 BTC. Die Gebühr beträgt somit 0,0002 BTC (20.000 Satoshis). Die Regel gemeinsamer Inputs verknüpft bc1q…k3f7, bc1q…m9a2 und bc1q…x0d1. Über die Outputs sagt sie nichts aus: Ob bc1q…r4t6 Wechselgeld ist, das zu derselben Wallet gehört, ist eine gesonderte und deutlich schwächere Schlussfolgerung (Lektion 4.2).

Wenn bc1q…m9a2 bereits zu einem Cluster mit 2.000 Adressen und bc1q…x0d1 zu einem Cluster mit 300 Adressen gehörte, führt diese eine Transaktion sie zu einem Cluster mit 2.301 Adressen zusammen. Darin liegen die Hebelwirkung der Regel und ihre Gefahr.

Am stärksten ist die Regel bei Diensten. Verwahrende Börsen und Zahlungsabwickler konsolidieren regelmäßig viele kleine Einzahlungen zu einem Output: eine Fan-in-Transaktion, die Mittel von Hunderten von Einzahlungsadressen gleichzeitig ausgeben kann. Jede solche Sammelübertragung verknüpft all diese Adressen mit der Wallet des Dienstes. Deshalb wachsen Dienst-Cluster auf Millionen von Adressen an, und deshalb reicht oft eine verifizierte Einzahlung aus, um sie zu kennzeichnen (Lektion 4.5). Ein Nutzer, der ein Dutzend alter Coins zusammenführt, um künftige Gebühren zu sparen, legt auf dieselbe Weise offen, dass eine Wallet sie alle hielt. Beide Fälle sind korrekt, solange niemand sonst einen Input beigesteuert hat.

Wie gut sie funktioniert

Meiklejohn et al. wandten die Regel 2013 auf die gesamte Blockchain an und reduzierten 12.056.684 öffentliche Schlüssel auf etwa 5,58 Millionen Cluster. Nick (2015, Masterarbeit) gewann selten verfügbare gesicherte Referenzdaten aus einem Datenschutzleck in den Bloom-Filtern leichtgewichtiger Wallets, durch das die Adressmengen realer Wallets offengelegt wurden. Die Regel gemeinsamer Inputs identifizierte mehr als 69 % der Adressen in diesen Wallets. Beachten Sie, was diese Zahl misst: Recall (wie viel von jeder Wallet gefunden wurde), nicht Präzision (wie viele Verknüpfungen korrekt waren). Für gewöhnliche Transaktionen gilt die Regel allgemein als hochpräzise. Das ist jedoch eine Annahme über das Wallet-Verhalten, die durch die nachfolgend beschriebenen Transaktionen verletzt wird (Lektion 4.4 behandelt die Messung der Clusterqualität).

Wo die Annahme scheitert

CoinJoin. Mehrere Nutzer vereinbaren eine gemeinsame Transaktion. Jeder steuert Inputs bei und signiert nur seine eigenen. Die Outputs umfassen typischerweise mehrere mit identischem Wert, sodass niemand erkennen kann, welcher Output wem gehört. Die Anwendung der Regel gemeinsamer Inputs führt die Wallets aller Teilnehmer zusammen. Genau diese falsche Verknüpfung soll CoinJoin hervorrufen (Lektion 6.2).

PayJoin. Bei einem PayJoin (BIP 78) fügt der Zahlungsempfänger einen eigenen Input zur Transaktion des Absenders hinzu. Das Ergebnis sieht wie eine gewöhnliche Zahlung mit zwei Inputs aus. Die Regel verknüpft daher die Coins des Absenders und des Empfängers, und auch der scheinbare Zahlungsbetrag wird verzerrt. Ein gut umgesetzter PayJoin lässt sich nicht zuverlässig von einer normalen Transaktion unterscheiden. Seine Existenz begrenzt daher die Stärke jeder einzelnen Verknüpfung. Die Verbreitung ist bisher gering, was den Gesamtschaden begrenzt, einen PayJoin im konkreten Fall aber nicht ausschließt.

Andere Transaktionen mit mehreren Parteien. Beidseitig finanzierte Eröffnungen von Lightning-Kanälen, einige Swap- und Bündelungsprotokolle sowie Transaktionen, die mit SIGHASH_ANYONECANPAY signiert werden, enthalten Inputs mehrerer Parteien. Dieses Flag erlaubt anderen, nach der ersten Signatur weitere Inputs hinzuzufügen, und wird beispielsweise in Crowdfunding-ähnlichen Verträgen verwendet.

Gemeinsame Kontrolle. Eine Multisig-Adresse, die von mehreren Personen gemeinsam gehalten wird, hat im Sinne des Skripts einen „Eigentümer“. Die korrekte Entität ist die gemeinsame Struktur, nicht ein einzelner Unterzeichner.

Verwahrung und Schlüsselimport. Ein verwahrender Dienst gibt Kundeneinzahlungen gemeinsam aus. Sein Cluster ist daher für den Dienst korrekt, sagt aber nichts über die Kunden aus. Wallets, die Nutzern den Import privater Schlüssel oder die Übertragung sämtlicher Mittel von privaten Schlüsseln erlauben, die sie von anderen erhalten haben (Paper-Wallets, Geschenkkarten), können Coins verknüpfen, die unterschiedliche Eigentümer hatten. Harrigan und Fretter („The Unreasonable Effectiveness of Address Clustering“, 2016) schlossen genau aus diesem Grund das größte Bitcoin-Cluster aus: über 10 Millionen Adressen, die ursprünglich Mt. Gox gehörten.

Cluster sind keine Entitäten

Die Zuordnung zwischen Clustern und realen Entitäten scheitert in beide Richtungen.

• Eine Entität, viele Cluster (unzureichende Zusammenführung). Die Cold-Wallets einer Börse werden möglicherweise nie gemeinsam mit ihren Hot-Wallets ausgegeben; eine Person kann drei voneinander unabhängige Wallet-Anwendungen nutzen; auf kontobasierten Blockchains ohne gemeinsame Ausgabe mehrerer Inputs erscheint ein Betreiber oft als Dutzende nicht verknüpfter Adressen.
• Ein Cluster, viele Entitäten (übermäßige Zusammenführung). CoinJoins, die Bündelung verwahrter Mittel und der oben beschriebene Schlüsselimport verbinden Wallets, die unterschiedlichen Personen gehören.

Cluster verändern sich auch im Laufe der Zeit: Ein bei Block 800.000 berechnetes Cluster kann bis Block 850.000 mit einem anderen zusammengeführt werden. Jedes Cluster ist eine Momentaufnahme und sollte die Blockhöhe tragen, bei der es berechnet wurde.

Falsch positive und falsch negative Ergebnisse und die Ausbreitung von Fehlern

Eine falsch positive Verknüpfung verbindet Adressen, die nicht von derselben Partei kontrolliert werden; ein falsch negatives Ergebnis ist eine tatsächlich bestehende Verknüpfung, die die Methode übersehen hat. Die Folgen treffen unterschiedliche Nutzer:

Kein Heuristiksatz ist für alle am besten geeignet: Ein Compliance-Team, das Transaktionen aufgrund von Clusterkennzeichnungen blockiert, sollte Präzision bevorzugen. Ein Ermittler, der Ermittlungsansätze entwickelt, kann mehr falsch positive Ergebnisse akzeptieren, sofern jeder Ansatz überprüft wird, bevor er in einen Bericht eingeht.

Clustering-Fehler sind nicht proportional zur Anzahl falscher Verknüpfungen. Da Cluster transitive Hüllen sind, erzeugt eine einzige falsche Verknüpfung zwischen einem Cluster mit 5.000 Adressen und einem mit 40.000 Adressen ein Cluster mit 45.000 Adressen. Jede Adresse teilt nun sämtliche Kennzeichnungen, die eine der beiden Seiten trug. Fehler häufen sich außerdem mit zunehmender Größe. Wenn jede Verknüpfung unabhängig mit der Wahrscheinlichkeit p falsch ist, ist ein aus n Verknüpfungen aufgebautes Cluster mit der Wahrscheinlichkeit (1 − p)^n fehlerfrei. Bei p = 0,001 und n = 1.000 Verknüpfungen ergibt das 0,999^1.000 ≈ 0,37: eine Wahrscheinlichkeit von 63 %, dass das Cluster mindestens eine falsche Zusammenführung enthält. Große Cluster sind daher mit höherer Wahrscheinlichkeit fehlerbehaftet, obwohl Analysten gerade ihnen häufig am meisten vertrauen. Meiklejohn et al. stellten fest, dass eine naive Version ihrer Wechselgeldheuristik ein Supercluster aus 1,6 Millionen öffentlichen Schlüsseln erzeugte, das Mt. Gox, Instawallet, BitPay und Silk Road enthielt (Lektion 4.4 behandelt solche Supercluster). In nachgelagerten Analysen verändert die zusammengeführte Kennzeichnung die Statistiken zu Mittelflüssen und die Risikobewertungen. Am Ende formuliert ein Bericht eine Schlussfolgerung, die durch die Belege nicht gestützt wird, obwohl jeder einzelne Zwischenschritt plausibel erschien.

Schutzmaßnahmen und Dokumentation der Belege

Vor dem Verknüpfen prüfen und beobachten

1. Wahrscheinliche CoinJoins herausfiltern. Der einfachste Test sucht nach mehreren Outputs mit exakt demselben Wert:

-- Mögliche CoinJoins markieren, damit ihre Inputs nicht verknüpft werden
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;  -- Diesen Schwellenwert anpassen und dokumentieren

Die Abfrage zählt pro Transaktion, wie viele Outputs jeweils denselben Wert haben, behält die größte solche Gruppe bei und markiert Transaktionen mit mehreren Inputs, bei denen mindestens drei Outputs identisch sind. Die Wahl des Schwellenwerts ist eine Ermessensentscheidung. Die Abfrage erfasst auch einige gebündelte Auszahlungen von Börsen mit gleichen Beträgen. Diese auszuschließen kostet lediglich einige Verknüpfungen (ein falsch negatives Ergebnis), also den weniger gefährlichen Fehler. CoinJoin-Varianten, die gleichwertige Outputs vermeiden, werden nicht erfasst. Es handelt sich daher um einen Filter, nicht um einen Detektor. Clustering-Ansätze aus der Forschung wie der von Goldfeder et al. (2018) ergänzen aus demselben Grund einen CoinJoin-Ausschluss.

1. Ungewöhnliche Input-Mischungen markieren. Inputs unterschiedlicher Skripttypen (beispielsweise ein herkömmlicher P2PKH-Input neben einem P2TR-Input) sind bei Software einer einzelnen Wallet ungewöhnlich und verdienen eine genauere Prüfung.
2. Zusammenführungen beobachten. Prüfen Sie jede Verknüpfung, die zwei große Cluster oder zwei Cluster mit unterschiedlichen Kennzeichnungen zusammenführen würde. Harrigan und Fretter beobachteten, dass große Cluster nur selten auf natürliche Weise zusammengeführt werden. Eine solche Zusammenführung ist daher ein Warnsignal. Prüfen Sie auch jedes Cluster, das zwischen Momentaufnahmen stark wächst.

Die Belege aufbewahren, nicht nur die Cluster

Speichern Sie für jeden Verknüpfungsbeleg eine Zeile:

-- Eine Zeile pro Verknüpfungsbeleg, nicht eine Zeile pro Cluster
CREATE TABLE cluster_evidence (
  addr_a        VARCHAR NOT NULL,
  addr_b        VARCHAR NOT NULL,
  heuristic     VARCHAR NOT NULL,  -- z. B. 'common_input', 'change_v3'
  evidence_tx   VARCHAR NOT NULL,  -- txid oder Transaktionshash
  block_height  BIGINT  NOT NULL,
  strength      VARCHAR            -- 'high', 'moderate' oder 'low' (siehe Tabelle unten)
);

-- Cluster ausschließlich aus den stärksten Belegen neu aufbauen
SELECT addr_a, addr_b
FROM cluster_evidence
WHERE heuristic = 'common_input'
  AND strength = 'high';

Da Cluster aus dieser Tabelle abgeleitet werden, kann der Analyst sie mit einem strengeren oder weniger strengen Heuristiksatz neu aufbauen, eine später als CoinJoin oder PayJoin erkannte Transaktion entfernen und prüfen, was auseinanderfällt, oder einer prüfenden Person zeigen, warum zwei Adressen zusammengeführt wurden. Die Berechnung von Zusammenhangskomponenten ist in reinem SQL umständlich (rekursive CTEs funktionieren, skalieren aber schlecht). Die meisten Teams exportieren die ausgewählten Kanten in eine Graphenbibliothek oder eine Union-Find-Routine. Die Erzeugung der Input-Paare in großem Maßstab mit demselben CoinJoin-Ausschluss wird in Lektion 2.9 behandelt (die Spaltennamen hier folgen deren UTXO-Schema).

Stärke und Berichterstattung

Auf der A–D-Skala des Kurses (Lektion 3.2) entspricht jede Verknüpfung gemeinsamer Inputs der Stufe C, einer einzelnen Heuristik, unabhängig von ihrer Zeile in dieser Tabelle. Die Tabelle ordnet die Stärke der Verknüpfungen innerhalb dieser Stufe ein und bestimmt, welche Kennzeichnungen übertragen dürfen (Lektion 4.5). Der Kurs reserviert das Wort „Konfidenz“ für die Grundlage einer in einem Bericht formulierten Beurteilung (Lektion 9.2). Heuristische Verknüpfungen werden daher nach ihrer Stärke bewertet. Benennen und datieren Sie für jedes von Ihnen angeführte Cluster den zugrunde liegenden Heuristiksatz, die Ausschlüsse, Schwellenwerte und die Blockhöhe der Momentaufnahme. Schreiben Sie „durch die Heuristik gemeinsamer Inputs geclusterte Adressen, CoinJoin-Filter aktiviert, auf Grundlage einer Testeinzahlung als Dienst X gekennzeichnet“ statt „Wallet von Dienst X“ (Lektion 9.2 behandelt die Berichtssprache). Prüfen Sie abschließend die Sensitivität: Berechnen Sie zentrale Ergebnisse erneut ohne die schwächste Heuristik und berichten Sie, ob sie weiterhin Bestand haben.

Prüfungsschwerpunkt: der Unterschied zwischen Adresse, Cluster und Entität sowie Kontrolle gegenüber Eigentum bei verwahrenden Diensten; Clustering als Entitätsauflösung und als transitive Hülle (Zusammenhangskomponenten) von Verknüpfungsbelegen; warum gemeinsam ausgegebene Inputs auf eine gemeinsame kontrollierende Instanz schließen lassen und der Ursprung der Regel (Whitepaper, Heuristik 1 von Meiklejohn et al.); Recall gegenüber Präzision bei den Bloom-Filter-Belegen (mehr als 69 % der Wallet-Adressen gefunden); die Ausnahmen (CoinJoin, PayJoin gemäß BIP 78, beidseitig finanzierte Kanäle, SIGHASH_ANYONECANPAY, Multisig, Verwahrung und Schlüsselimport); unzureichende und übermäßige Zusammenführung; die unterschiedlichen Folgen falsch positiver und falsch negativer Ergebnisse; warum eine falsche Verknüpfung ganze Cluster zusammenführt und Kennzeichnungen verbreitet, sowie die Überlegung zu (1 − p)^n; das Herausfiltern gleichwertiger Outputs mit einem dokumentierten Schwellenwert; die Speicherung von Belegen mit Heuristik, Transaktion und Blockhöhe, damit Cluster neu aufgebaut werden können.