====== Progetto di ASD 2022/2023 ====== Il progetto si propone di analizzare le 10 532 115 reali transazioni della moneta elettronica Bitcoin dal suo esordio (nel 2009) fino a dicembre 2012. Il progetto utilizza solo le transazioni che sono collegate a una o più transazioni successive e ignora completamente gli aspetti crittografici e quelli algoritmici legati al protocollo Bitcoin, per concentrarsi sul grafo delle transazioni in modo semplificato e accessiibile. Ciascuna di tali transazioni prende in ingresso zero o più quantità di moneta da (precedenti) transazioni, e fornisce in uscita una o più quantità di moneta verso (successive) transazioni. Per praticità, le transazioni sono raggruppate in blocchi, e un ordine temporale tra i blocchi è stabilito tramite un timestamp (per sapere quando le transazioni sono avvenute). Le transazioni possono avere un costo di commissione che vanno a chi ha generato il loro blocco di appartenenza. Il progetto è diviso in tre parti. La prima parte richiede di esaminare le transazioni in modo che nella secoda parte si possa costruire un opportuno grafo G. La terza parte richiede di utilizzare G per analizzare i flussi di moneta. ==== Prima parte ==== Questa parte richiede un po' di analisi dei dati per poter poi costruire il grafo G. I dati di interesse per il progetto sono in tre file testuali, inputs.csv, outputs.csv e transactions.csv, che possono essere scaricati dal seguente [[https://unipiit.sharepoint.com/:f:/s/a__td_53655/EpZSfavnOkxKpjl4340DKacB__kBZ9p0LZ1--7JmN3-hWw?e=zKGpcr|LINK]] (sono tre file da 183Mb, 100Mb e 30Mb). (Per fare una prova, si può usare un piccolo esempio {{ :matematica:asd:asd_22:small.zip |small.zip}}) Vediamoli in dettaglio, utilizzando il comando ''wc'' (word count) in Linux, dove ciascuno dei tre file corrisponde a una riga: nella prima colonna è riportato il numero di linee del file, nella terza il numero totale di caratteri (la seconda colonna non interessa nel nostro caso). wc *.csv 21378770 21378770 385600398 inputs.csv 24573071 24573071 700591153 outputs.csv 10532115 10532115 345843058 transactions.csv I file testuali in formato csv rappresentano una tabella in formato testuale, dove i campi di ciascuna riga sono separati da una virgola ([[https://it.wikipedia.org/wiki/Comma-separated_values|wikipedia]]). Vediamo cosa contengono nel nostro caso, con il comando ''tail'' in Linux che ce ne mostra le ultime righe: tail *.csv ==> inputs.csv <== 10572820,10572818,0 10572820,10572721,0 10572820,10572816,0 10572821,10572820,3 10572822,10572820,4 10572823,10572820,7 10572824,10572820,5 10572825,10572820,6 10572826,10572820,2 10572826,10569364,4 ==> outputs.csv <== 10572822,1,6137711,9899999,2 10572823,0,8707915,1,2 10572823,1,6137711,9899999,2 10572824,0,8707915,1,2 10572824,1,6137696,9899999,2 10572825,0,8707915,1,2 10572825,1,6137715,9899999,2 10572826,0,8707915,26651306,2 10572826,1,6137711,7991620447,2 10572826,2,6137491,7991620447,2 ==> transactions.csv <== 1356997957,214562,10572817,0,100000 1356997957,214562,10572818,0,100000 1356997957,214562,10572819,0,100000 1356997957,214562,10572820,0,100000 1356997957,214562,10572821,0,100000 1356997957,214562,10572822,0,100000 1356997957,214562,10572823,0,100000 1356997957,214562,10572824,0,100000 1356997957,214562,10572825,0,100000 1356997957,214562,10572826,0,100000 Iniziamo dalla descrizione del file transactions.csv. Per comodità di lettura da programma in C++, conviene separare i campi con uno spazio (blank) invece che con la virgola; per questo utilizziamo i comandi ''cat'' e ''tr'' (translate characters) in Linux: cat transactions.csv | tr ',' ' ' > transactions.txt Possiamo ora osservare che nel file transactions.txt così creato abbiamo i campi separati da uno spazio: tail transactions.txt 1356997957 214562 10572817 0 100000 1356997957 214562 10572818 0 100000 1356997957 214562 10572819 0 100000 1356997957 214562 10572820 0 100000 1356997957 214562 10572821 0 100000 1356997957 214562 10572822 0 100000 1356997957 214562 10572823 0 100000 1356997957 214562 10572824 0 100000 1356997957 214562 10572825 0 100000 1356997957 214562 10572826 0 100000 Ora possiamo leggere il file tramite il comando ''std::cin'' in C++: constexpr auto N_ROWS = 10532115; // numero di righe ottenuto con wc freopen("transactions.txt", "r", stdin); for (long i=1; i <= N_ROWS; i++){ long timestamp, blockId, txId, isCoinbase, fee; std::cin >> timestamp >> blockId >> txId >> isCoinbase >> fee; // i-esima linea del file } Si noti che la mole dei dati potrebbe richiedere qualche decina di secondi per la lettura del file; in alcuni casi, potrebbe convenire leggere il file un po' alla volta (oppure spezzare il file: in Linux, il comando ''tail'' e il suo omologo ''head'', i quali permettono di specificare il numero di linee mediante l'opzione ''-n''). Vediamo come interpretare i campi timestamp, blockId, txId, isCoinbase, fee: * ''timestamp'': sono calcolati in base al fuso orario GMT e servono a stabilire un ordine temporale tra le transazioni; * ''blockId'': più transazioni sono eseguite in blocco, con identificatore univoco: non usiamo questa informazione; * ''txId'': identificatore univoco della transazione; * ''isCoinbase'': flag che indica se la transazione utilizza il Bitcoin (isCoinbase=0) oppure valuta reale come dollari, ecc. (isCoinbase=1); * ''fee'': eventuale commissione applicata alla transazione. Nell'esempio mostrato sopra, ci sono più transazioni che hanno lo stesso blockId e quindi lo stesso timestamp perché sono state eseguite tutte insieme. Le transazioni, che sono nello stesso blocco, occupano posizioni consecutive in tale blocco, dove le posizioni sono numeri consecutivi da 0 in poi (come si fa con gli indici negli array in C++). Gli altri due file outputs.csv e inputs.csv possono essere letti in modo analogo, dopo aver sostituito la virgola. constexpr auto N_ROWS = 24573071; // numero di righe ottenuto con wc freopen("outputs.txt", "r", stdin); for (long i=1; i <= N_ROWS; i++){ long txId, txPos, addressId, amount, scriptType; std::cin >> txId >> txPos >> addressId >> amount >> scriptType; // i-esima linea del file } Vediamo come interpretare i campi: * ''txId'': indica la transizione da cui proviene il versamento (cioè output); * ''txPos'': indica qual è la posizione del suddetto output tra quelli della transazione suddetta (si parte da 0); * ''addressId'': identificatore di stringa univoca di chi riceve il versamento: non usiamo questa informazione che comunque è stata resa anonima (è in realtà un hash crittografico nei dati originali). * ''amount'': indica la quantià di moneta trasferita tramite l'output, dove l'unità di misura è chiamata **satoshi = 10^-8 Bitcoin** (cioè amount = 100000000 satoshi corrisponde a 1 Bitcoin). * ''scriptType'': indica il tipo di crittografia utilizzato: non usiamo questa informazione. Si noti che ogni transazione ha almeno una corrispondente riga in outputs.txt, cioè //almeno uno output//. constexpr auto N_ROWS = 21378770; // numero di righe ottenuto con wc freopen("inputs.txt", "r", stdin); for (long i=1; i <= N_ROWS; i++){ long txId, prevTxId, prevTxPos; std::cin >> txId >> prevTxId >> prevTxPos; // i-esima linea del file } Vediamo come interpretare i campi: * ''txId'': indica la transizione, come indicato sopra; * ''prevTxId'': indica qual è la transazione precedente da cui si preleva; * ''prevTxPos'': è la posizione di output in tale transazione precedente. Se una transazione ha il campo isCoinbase=1, potrebbe avere //zero input//, cioè nessuna riga corrispondente in inputs.csv: in tal caso, genera nuovo valore (sono le transazioni per creare nuovi Bitcoin e darli ai cosidetti miner). //__ESEMPIO__//: Prendiamo l'ultima transazione del nostro esempio, dove timestamp = 1356997957, blockId = 214562, txId = 10572826, isCoinbase = 0, fee = 100000. Cerchiamo txId = 10572826 nei due file outputs.txt e inputs.txt con il comando grep in Linux: cat outputs.txt | grep 10572826 10572826 0 8707915 26651306 2 10572826 1 6137711 7991620447 2 10572826 2 6137491 7991620447 2 cat inputs.txt | grep 10572826 10572826 10572820 2 10572826 10569364 4 La transazione txId = 10572826 ha quindi due input e tre output. I due input indicano che la transazione //preleva// dal terzo output (quindi in posizione 2) della transazione 10572820 e dal quinto output (quindi in posizione 4) della transazione 10569364. I tre output indicano che la transazione //versa// amount = 26651306 satoshi all'address 8707915, poi amount = 7991620447 satoshi all'address 6137711, e quindi amount = 7991620447 satoshi all'address 6137491. La transazione usa Bitcoin e paga una commissione di fee = 100000 satoshi al blocco di appartenenza. La prima parte richiede di svolgere il seguente compito: * Comprendere come sono strutturati i file inputs.txt, outputs.txt e transactions.txt. ==== Seconda parte ==== Viene naturale rappresentare le transazioni come un grafo orientato **G = (V,E)** dove * **V** è l'insieme di tutti i ''txId'' (cioè le transazioni nel file transactions.txt), osservando che non è detto siano necessariamente numeri consecutivi (questo perché sono state cancellate le transazioni senza output); * **E** è l'insieme degli archi tra coppie di transazioni, ottenuti come combinazione delle informazioni in input.txt e output.txt. * **Etichette**: G ha nodi e archi etichettati, per memorizzare le altre informazioni nei suddetti file, come discusso nella prima parte del progetto. Approfondiamo meglio come sono costruiti gli archi in E e le loro etichette. Preso un arco (x,y) in E, tale arco è presente in outputs.txt per x, e in inputs.txt per y (infatti, è un arco uscente per il nodo x ed entrante per il nodo y). Continuando nell'esempio sopra, sia y = 10572826: poiché ha due input, ci sono due archi (x1,y) e (x2,y) entranti in y, dove x1 = 10572820 e x2 = 10569364. Sappiamo inoltre che (x1,y) è l'output in posizione 2 per x1, e (x2,y) è l'output in posizione 4 per x2. Li cerchiamo con ''grep'' in outputs.txt usando anche la loro posizione: cat outputs.txt | grep "10572820 2" 10572820 2 3524243 10000000 2 cat outputs.txt | grep "10569364 4" 10569364 4 6137717 15999992200 2 A questo punto abbiamo le informazioni sul trasferimento di moneta per questi due archi: (x1,y) ha versato 10000000 satoshi e (x2,y) ne ha versati 15999992200 per un totale di 16009992200. Possiamo quindi rappresentare questi due archi come in figura (mostrati in blue e rosso): {{:matematica:asd:asd_22:graphbitcoin.jpg|}} Se continuiamo in questo modo, creiamo tutti gli archi etichettati in E. In particolare, i tre archi uscenti da y verseranno 26651306 + 7991620447 + 7991620447 = 16009892200 satoshi, come si può verificare nell'esempio sopra. La differenza tra entrate e uscite di una transazione y, costituisce il suo fee = 16009992200 - 16009892200 = 100000 satoshi, che è una delle etichette del nodo y. La seconda parte richiede di svolgere i seguenti compiti: * Costruire il grafo un po' alla volta se non si possiede abbastanza RAM sul proprio computer. * In tale grafo, prendere una delle componenti connesse più grandi, ignorando la direzione degli archi. Tale componente connessa gigante diventa il nostro grafo G. Si osservi che in principio G è aciclico, ma le transazioni all'interno di un blocco sono simultanee. Tra di loro si possono creare dei piccoli cicli in cui una transazione paga e la ricevente le fornisce "il resto": un po' come quando si paga con una banconota con resto e il vero valore trasferito è la differenza degli amount delle due transazioni (ricordiamo, stesso blocco) che sono collegate tra loro da due archi (c'è un [[https://www.blockchain.com/explorer/transactions/btc/43d41a287996d4df74d147308ae3d6ea7960af0b0b0ab967c836f39be96bef22|esempio estremo]] di tali coppie di transazioni dove, per pagare circa 26 dollari, viene inviato l'equivalente di 766 191 271 dollari in Bitcoin per ricevere come resto la differenza di 766 191 245 dollari in Bitcoin). ==== Terza parte ==== Una volta costruito il grafo G come una sola componente connessa gigante, quando la direzione degli archi è ignorata, la terza parte richiede di svolgere i seguenti compiti: * Rimuovere da G le coppie di archi (x,y) con amount = a1 e (y,x) con amount = a2, dove a1 > a2, rimuovere (y,x) e lasciare (x,y) con amount = a1 - a2. Verificare se G sia ancora ciclico o meno. * Modellare la nozione di flusso di moneta, che viene trasferita attraverso le varie transazioni, come un cammino orientato in G in cui si incontrano gli amount negli archi. * Progettare un algoritmo che, partendo da una transazione presa come nodo u di partenza, individua tutti i flussi di denaro che si propagano in G a partire da u e che superano una certa soglia di valore. Per favorire la programmazione e il debug, viene fornito un piccolo grafo di esempio {{ :matematica:asd:asd_22:small.zip |small.zip}} **Ringraziamenti.** Il dott. Damiano Di Francesco Maesa ha cortesemente fornito i file ripuliti, inputs.csv, outputs.csv e transactions.csv, e chiarimenti sul loro contenuto. I tutor Federico Lazzeri e Alberto L'Episcopo hanno fornito parte del codice e un piccolo esempio per fare il test.