Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- matematica:asd:asd_22:progetto_21 [27/05/2023 alle 16:16 (23 mesi fa)] – Roberto Grossi
+++ matematica:asd:asd_22:progetto_21 [17/07/2023 alle 11:44 (21 mesi fa)] (versione attuale) – Roberto Grossi
@@ Linea 9: / Linea 9: @@
 ==== 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).
+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).
@@ Linea 105: / Linea 106: @@
 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 inputs.csv e outputs.csv possono essere letti in modo analogo, dopo aver sostituito la virgola.
+Gli altri due file outputs.csv e inputs.csv possono essere letti in modo analogo, dopo aver sostituito la virgola.
+<code>
+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
+}
+</code>
+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//.
 <code>
@@ Linea 119: / Linea 138: @@
   * ''txId'': indica la transizione, come indicato sopra;
   * ''prevTxId'': indica qual è la transazione precedente da cui si preleva;
-  * ''prevTxPos'': è la posizione di tale transazione precedente nel suo rispettivo blocco.
+  * ''prevTxPos'': è la posizione di output in tale transazione precedente.
 Se una transazione ha il campo isCoinbase=1, potrebbe avere //zero input//,
@@ Linea 125: / Linea 144: @@
 (sono le transazioni per creare nuovi Bitcoin e darli ai cosidetti miner).
-<code>
-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
-}
-</code>
-Vediamo come interpretare i campi:
+//__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:
-  * ''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 è 10^-8 Bitcoin (cioè amount = 100000000 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//.
-//__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 inputs.txt e outputs.txt con il comando grep in Linux:
 <code>
-cat inputs.txt | grep 10572826
-    10572826 10572820 2
-    10572826 10569364 4
 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
 </code>
-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 = 26651306x10^-8 Bitcoin all'address 8707915, poi amount = 7991620447x10^-8 Bitcoin all'address 6137711, e quindi amount = 7991620447x10^-8 Bitcoin all'address 6137491. La transazione usa Bitcoin e paga una commissione di fee=100000x10^-8 Bitcoin al blocco di appartenenza.
+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:
@@ Linea 178: / Linea 180: @@
 </code>
-A questo punto abbiamo le informazioni sul trasferimento di moneta per questi due archi: (x1,y) ha versato 10000000x10^-8 Bitcoin e (x2,y) ne ha versati 15999992200x10^-8 per un totale di 16009992200^10-8. Possiamo quindi rappresentare questi due archi come in figura (mostrati in blue e rosso):
+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^10-8 + 7991620447^10-8 + 7991620447^10-8 = 16009892200^10-8, come si può verificare nell'esempio sopra. La differenza tra entrate e uscite di una transazione y, costituisce il suo fee = 16009992200^10-8 - 16009892200^10-8 = 100000^10-8, che è una delle etichette del nodo y.
+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 la componente connessa più grande, ignorando la direzione degli archi. Tale componente connessa gigante diventa il nostro grafo G.
+  * 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 e il vero valore trasferito è la differenza degli amount delle due transazioni (ricordiamo, stesso blocco) che sono collegate tra loro da due archi (qui c'è un esempio estremo di tali coppie di  [[https://www.blockchain.com/explorer/transactions/btc/43d41a287996d4df74d147308ae3d6ea7960af0b0b0ab967c836f39be96bef22|transazioni]] che per pagare circa $25 viene inviato l'equivalente di $766191271 in Bitcoin per ricevere come resto la differenza $766191245 in Bitcoin). Volendo si possono ignorare tale transazioni ai fini del progetto.
+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 ripulito, G risulta essere una sola componente connessa gigante quando la direzione degli archi è ignorata.
+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:
-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 nei nodi.
+  * 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, verrà fornito un piccolo grafo di esempio al seguente LINK:
+Per favorire la programmazione e il debug, viene fornito un piccolo grafo di esempio {{ :matematica:asd:asd_22:small.zip |small.zip}}
-NOTA del docente: preparazione di un piccolo esempio in corso!
-**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.
+**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.