Distributed Union Find Data Structures for Skewed Data

Abstract

Moderne Blockchain-Systeme wie Bitcoin stellen einen öffentlich zugänglichen Graphen von Transaktionen bereit. Transaktionen enthalten pseudonyme Adressen als Eingaben. In der Blockchain-Analyse wird häufig angenommen, dass innerhalb einer Transaktion alle Eingabeadressen von einem einzigen Nutzer kontrolliert werden, während verschiedene Transaktionen unterschiedlichen Nutzern zugeordnet sein können.Diese Arbeit untersucht das Adressclustering auf einem großen Bitcoin-Transaktionsdatensatz mithilfe einer verteilten Union-Find-Datenstruktur bei einer stark ungleichmäßigen Verteilung der Clustergrößen. Diese Ungleichverteilung erschwert die verteilte Implementierung, da die Cluster über mehrere logische Server mit begrenzter Kapazität verwaltet werden müssen, während gleichzeitig Adressverschiebungen zwischen Servern minimiert und eine gleichmäßige Serverauslastung gewährleistet werden sollen.Wir haben einen verteilten Union-Find-Algorithmus implementiert, der einen Strom von Bitcoin-Transaktionen verarbeitet und Adresscluster über mehrere Server hinweg verwaltet. Dabei werden unterschiedliche Verschiebungsstrategien angewendet, wenn Cluster auf verschiedenen Servern zusammengeführt werden.Die Evaluierung berücksichtigt die Anzahl der verschobenen Adressen, die Anzahl der serverübergreifenden Zusammenführungen und die Serverauslastung. Darüber hinaus wird der verteilte Union-Find-Ansatz mit einer Apache Spark GraphX-Implementierung des Zusammenhangskomponentenalgorithmus verglichen. Der Vergleich zeigt, dass GraphX zwar dieselben Zusammenhangskomponenten berechnet, jedoch die Serverkapazitätsbegrenzte Umgebung nicht direkt modelliert und für größere Eingabegrößen einen erheblichen Shuffle-Kommunikationsaufwand erfordert.

Modern blockchain systems, such as Bitcoin, provide a publicly accessible graph of transactions. Transactions contain pseudonymous addresses as inputs, and there is a common heuristic in blockchain analytics that assumes that, within a given transaction, all input addresses are controlled by a single user, whereas different transactions may correspond to distinct users.This thesis examines address clustering on a large Bitcoin transaction dataset using a distributed union-find data structure on a very skewed distribution of cluster sizes. Such skewness creates difficulties for a distributed implementation because clusters must be maintained across multiple logical servers with limited capacity while minimizing address movement across servers and preserving balanced server occupancy. We implemented a distributed union-find algorithm that processes a stream of Bitcoin transactions and maintains address clusters across multiple servers while applying different movement strategies when merges involve clusters stored on different servers. The evaluation considers the number of moved addresses, the number of cross-server merges, and server occupancies. In addition, the distributed union-find approach is compared with an Apache Spark GraphX implementation of the connected components algorithm. The comparison shows that GraphX computes the same connected components, but it does not model the capacity-bounded server setting directly and requires substantial shuffle communication for larger input sizes.