Improving the extraction of knowledge from the blockchain

Bitcoin is a cryptocurrency that allows its users to operate in semi- anonymity. This feature inevitably brought malicious agents to use Bitcoin as a payment method, for example, ransomware or online black markets, to not be tracked. However, the history of all transactions is public, and it’s saved in each node of the Blockchain network, making possible to retrieve all the data related to the transactions. In particular, these transactions are linked to- gether by the sets of addresses used to pay and collect the Bitcoins. One of the features of this cryptocurrency system is the possibility to automatically recollect the unspent amount of a transaction in an output address, called change address, which is the only output address that belongs to the same entity that owns the input addresses. Hence, it allows linking the addresses belonging to the same entities through different transactions. Current solutions that try to clusters addresses belonging to the same entities are composed of different modules: a parser to obtain the Blockchain data, a clusterizer that uses different heuristics to group Bitcoin addresses, and a grapher that is used to analyze the relations between the addresses inside clusters. The main limitations of these works are the usage of dep- recated heuristics, and the lack of suggestions on how to use and combine them during the clustering process to enhance the results. This thesis is focused on improving BitIodine, a tool developed by our research group, giving a measurement of the impact of the current heuristics, optimizing the detection of the change address in a transaction, and allowing an efficient clusterizing. We give, for each heuristic, an estimated percentage of its applicability in the entire Blockchain, looking for a correlation between these heuristics in order to combine them. In addition, we propose two new heuristics that are able to efficiently find the change addresses. To enhance the post-clustering module, we propose a module that adds semantic information to clusters by a set of web scrapers that can link the addresses to real-world entities like ransomware, scammers, exchange services related to illegal activities. Finally, we develop a module to find the relations between addresses. The results of this module can be imported in Gephi to obtain a graphical visualization. Thanks to an experimental evaluation on the Blockchain, we are able to find the most efficient combination of heuristics that can be used in the clus- tering process, and find patterns among the ransomware addresses analyzing the ransomware victims’ payments.

Bitcoin é la piú famosa cripto valuta presente al mondo, basata su un sis- tema peer-to-peer decentralizzato chiamato Blockchain. Essa é composta da una rete di migliaia di nodi che hanno la possibilitá di interagire e scambiare transazioni. Le informazioni riguardanti le transazioni degli utenti sono pub- blicamente accessibili. Una transazione Bitcoin comporta il trasferimento della crypto valuta da un utente all’altro. Questa transazione é pubblicata e salvata in tutti i nodi della Blockchain. Tuttavia, l’unica informazione non accessibile pubblicamente, é l’identitá degli utenti, ai quali viene fornito un indirizzo che é usato come pseudonimo durante le transazioni. Questi indi- rizzi sono composti da una chiave privata ed una pubblica, che sono utilizzate rispettivamente per recuperare e inviare i Bitcoin da un utente all’altro. In poche parole, un utente usa la chiave pubblica dell’utente a cui trasferisce i Bitcoin per firmare la crypto valuta , ed infine l’utente che riceve i Bitcoin usa la propria chiave privata per poterli ottenere definitivamente. Questo meccanismo, oltre a garantire la privacy degli utenti, ha favorito il nascere di comportamenti malevoli: dai pagamenti dei ransomware fino ai mercati neri. Le soluzioni correnti si sono concentrate sul creare clusters di indirizzi, in modo da identificare tutti quegli indirizzi legati tra loro. Queste soluzioni sono composte da diversi moduli: un parser che recupera tutti i dati presenti nella Blockchain, un clusterizzatore che si occupa di creare i clusters degli indirizzi e un grapher che visualizza i risultati ottenuti. I clusters vengono creati tramite euristiche, collezionate attraverso lo studio di diversi dati dei pagamenti Bitcoin: la quantit di Bitcoin scambiati, i pattern di transazioni e i metodi di utilizzo degli indirizzi. Queste euristiche cercano di identificare l'indirizzo usato per collezionare il resto di una transazione, il quale appar- tiene alla stessa entitá che effettua il pagamento. Questo indirizzo, permette di legare diverse transazioni alla stessa entitá. Le limitazioni principali delle soluzioni correnti sono l’uso di euristiche deprecate e la mancanza di un adeguato studio dietro il loro utilizzo che possa migliorare il risultato del processo di clusterizzazione. L’obiettivo di questa tesi é migliorare BitIodine, un tool sviluppato dal nostro gruppo di ricerca, su due diversi aspetti: da una parte miglioriamo le euristiche usate, con uno studio del loro impatto nella Blockchain e la proposta di due nuove euristiche che permettono di identificare in modo ef- ficiente l’indirizzo contenente il resto. Dallaltra miglioriamo il processo di analisi dei cluster ottenuti attraverso un metodo di visualizzazione in grado di evidenziare pattern all’interno dei clusters. In aggiunta, proponiamo un set di web scrapers i quali ottengono attraverso il web informazioni non con- tenute all’interno della Blockchain, al fine di collegare gli indirizzi ad entitá reali. Per la prima parte, focalizzata sulle euristiche, utilizziamo la libreria di analisi di BlockSci, analizzando il loro utilizzo nelle diverse transazioni. Suc- cessivamente, otteniamo il grado di correlazione presente tra le diverse eu- ristiche, per valutare la possibilitá di creare un sottoinsieme. Questi studi cercano di portare maggiore consapevolezza ai ricercatori, in modo che pos- sano applicare le euristiche nelle combinazioni pi efficaci e in diversi step del processo di clusterizzazione. In aggiunta, proponiamo due nuove euristiche che attraverso l’analisi delle relazioni tra input e output di diverse transazioni, riescono a raggruppare in modo efficiente gli indirizzi appartenenti alle stesse entitá. Gli esperimenti relativi a questa parte sono composti da: le percentu- ali delle transazioni nelle quali le euristiche vengono attivate singolarmente, la maggior combinazione di euristiche usata in tutta la Blockchain e le com- binazioni di euristiche che non vengono mai attivate. Per la parte relativa al processo post clusterizzazione utilizziamo BlockSci come clusterizzatore. Visualizziamo i dati ottenuti con uno strumento di visualizzazione e usiamo il tagging semantico per collegare gli indirizzi ad entitá reali. Dopo aver ottenuti i cluster, vengono create due matrici rappre- sentanti i diversi collegamenti degli indirizzi appartenenti al loro interno: la prima rappresenta semplicemente il numero di transazioni in cui compaiono insieme gli indirizzi e la seconda rappresenta quelle transazioni in cui un in- dirizzo appare nel set degli input e uno in quello degli output. La seconda matrice viene creata in modo tale da poter evidenziare pattern tra gli indirizzi appartenenti allo stesso cluster. Abbiamo testato questa parte ottenendo con il tagging semantico alcuni indirizzi appartenenti al malware di WannaCry e abbiamo trovato, grazie allo strumento di visualizzazione, un pattern tra i suoi indirizzi che suggerisce un movimento di Bitcoin utilizzato per offuscare i precedenti pagamenti delle vittime.