Whitepaper – Recupero spazio su disco

Davide

Febbraio 7, 2023

Continua la nostra saga di approfondimento del Whitepaper di Bitcoin.

Nello scorso episodio abbiamo compreso perchè l’incentivo dato dalle block rewards e dalle commissioni sulle transazioni ha di fatto dato vita ad una vera e propria industria di mining.

In questo nuovo articolo, affronteremo un argomento molto diverso ma che ha afflitto non poco il nostro Satoshi: l’occupazione di memoria delle transazioni.

Ricordatevi che siamo in un mondo digitale e quindi lo spazio occupato si misura in byte (B), chilobyte (Kb) megabyte (Mb), gigabyte (GB), …

Com’è strutturato un blocco?

Un blocco Bitcoin è una struttura dati che aggrega al suo interno tutte le transazioni che dovranno essere collegate alla timechain.

Un blocco è così composto:

La maggior parte della sua dimensione è occupata dalle transazioni.

Infatti, una singola transazione occupa circa 400 bytes. In media ogni blocco contiene 1900 transazioni. Quindi:

400 per 1900 = 760000 byte. Non male 🙂

Quanto occupa la timechain?

Circa ogni 10 minuti, un nuovo blocco di Bitcoin di quasi 1 megabyte viene aggiunto alla timechain. Questo significa che:

ogni ora vengono aggiunti 6 blocchi con un occupazione di circa 6 MB
ogni giorno vengono aggiunti 144 nuovi blocchi con occupazione di 144 MB
ogni anno vengono aggiunti 52560 blocchi con occupazione di circa 52 GB.

Oggi, dopo 13 anni, l’intera timechain di Bitcoin occupa circa 445 GB!!

Immaginate ora di dover dimostrare a qualcuno che una determinata transazione sia veritiera. Per farlo dovreste dimostrare che l’hash di tutte le transazioni effettuate fino a quel momento corrisponda e non sia stato alterato. Il che significa avere a disposizione sul proprio dispositivo mobile l’intero storico delle transazioni, circa 445 GB.

Vi verrebbe voglia di utilizzare Bitcoin sapendo che vi serve un dispositivo mobile con circa 500 GB di hard disk? Penso proprio di no.

Abbiamo quindi bisogno di un modo moooltooo più smart per riuscire a recuperare le transazioni e dimostrare che non siano state alterate.

Una soluzione presa dal passato

Come ennesima dimostrazione che Bitcoin è un protocollo che assembla le più brillanti idee nel campo crittografico, Satoshi sfrutta il lavoro fatto nel 1980 da Ralph Merkle e descritto nel paper “Protocols for public key cryptosystems”.

Merkle, per verificare in modo rapido ed economico un intero set di dati sfrutta una struttura ad albero, chiamata appunto Merkle Tree.

Piccola curiosità: Merkle non è solo un appassionato di crittografia, ma ha dato contributi anche nel campo delle nanotecnologie e della criogenia. Nel 1998 è diventato direttore dell’azienda Alcor, azienda leader nel settore criogenico e dove, dal 2014, riposa criogenizzato Hal Finney: padre fondatore di Bitcoin e che ha ricevuto da Satoshi la prima transazione Bitcoin in assoluto.

Il mistero si infittisce 😉

Cos’è un Merkle Tree?

Il Merkle Tree è una struttura dati suddivisa in più livelli il cui scopo è di consentire una verifica efficiente e sicura dei contenuti all’interno di grandi strutture di dati.

Nel caso di Bitcoin, la struttura dati che vogliamo organizzare in modo efficiente sono le transazioni inserite all’interno dei vari blocchi.

Un Merkle Tree può essere immaginato come un albero rovesciato dove ogni foglia dell’albero corrisponde ad un nodo. Eseguendo poi l’hashing ricorsivo di coppie di nodi si arriva ad ottenere un unico hash chiamato Merkle Root.

Come sappiamo, l’algoritmo di hash crittografico utilizzato in Bitcoin è lo SHA256. Nel Merkle Tree delle transazioni lo SHA256 viene applicato due volte (double-SHA256).

Per rendere l’idea, vediamo come viene costruito il Merkle Tree nel caso di 4 transazioni che, per semplicità, chiameremo con A, B, C, D.

Le transazioni A, B, C, D sono le foglie dell’albero.

Le transazioni non sono custodite nell’albero, ma è il loro hash che viene salvato:

HA = SHA256(SHA256(Transazione A))

lo stesso vale per HB, HC e HD.

Ognuno di essi occupa una spazio di 32 byte.

Le coppie consecutive dei nodi foglia vengono poi riassunte in un nodo genitore ottenuto concatenando HA e HB ed il risultato nuovamente hashato:

HAB = SHA256(SHA256(HA + HB))

Il risultato è ancora una stringa che occupa 32 byte.

Il procedimento continua fino arrivare alla radice dell’albero, chiamata Merkle Root, ottenuta dalla concatenazione dall’hash di HAB e HCD

HABCD = SHA256(SHA256(HAB + HCD))

Indovinate un po’? Ancora una volta la stringa ottenuta occupa 32 byte.

Il risultato finale, che riassume le 4 transazioni, viene poi memorizzato sull’header del blocco, permettendo così un enorme risparmio occupazionale.

L’albero di Merkle è un albero binario e per arrivare alla radice servono un numero pari di transazioni. Come fare se le transazioni sono dispari?

Molto semplice, si duplica l’ultima transazione, ottenendo così il seguente albero:

Lo stesso metodo di costruzione di un albero con 4 transazioni può essere generalizzato per costruire alberi di qualsiasi dimensione.

Con questa spiegazione siamo ora in grado di capire anche le affermazioni riportate da Satoshi. Basterà sostituire le Tx1, Tx2, Tx3, Tx4 con TxA, TxB, TxC, TxD ed il gioco è fatto.

Il secondo disegno di destra sarà comprensibile con il proseguo della lettura 😉

Dove viene salvato il Merkle Root?

Per rispondere a questa domanda dobbiamo scavare ancora un po’ ed analizzare la struttura del Block Headers.

Ecco trovato dove si nasconde il Merkle Root all’interno di un blocco Bitcoin 🙂

Quanto spazio occupano i Block Headers?

In Bitcoin, ogni blocco può avere da centinaia alle migliaia di transazione. La cosa importante da ricordarsi è che le transazioni, indipendentemente dal loro numero, vengono tutte riassunte in una stringa di 32 byte chiamata Merkle Root e salvata sull’intestazione (header) di ogni blocco.

Lo stesso Nakamoto, ci fornisce anche un calcolo a spanne di quanto spazio è necessario prevedere se si conservano solo i block headers e non l’intera blockchain.

Se ogni 10 minuti viene generato un nuovo blocco si avrà che:

ogni ora vengono aggiunti 6 blocchi con un occupazione di circa 480 bytes
ogni giorno vengono aggiunti 144 nuovi blocchi con occupazione di 11520 bytes
ogni anno vengono aggiunti 52560 blocchi con occupazione di circa 4,2 Mbytes

Un bel salto di qualità se si considerano i 52 GB aggiunti ogni anno all’intera timechain.

Come provare che una transazione è inclusa in un blocco?

Supponiamo ora che qualcuno chieda ad un nodo di provare che la transazione M sia inclusa in un blocco.

Il nodo dovrà fornire solo il risultato degli hash segnati in verdi, quindi: HN, HOP, HIJKL e HABCDEFGH.

A quel punto chiunque può provare che la transazione M fa parte di quel blocco.

Infatti, conoscendo HN e conoscendo la transazione M da verificare, possiamo facilmente risalire l’albero, calcolando l’hash HMN. Conoscendo HOP fornita dal nodo, possiamo calcolare l’hash HMNOP. Conoscendo HIJKL possiamo calcolarci HIJKLMNOP. E infine, conoscendo HABCDEFGH possiamo calcolarci il merkle root HABCDEFGHIJKLMNOP verificando che il risultato corrisponda a quello riportato sull’header del blocco.

Se così non fosse, la transazione non risulterebbe valida.

Con 4 calcoli di hash siamo riusciti a verificare l’appartenenza al blocco e la validità della transazione M.

A questo punto, risulta chiaro anche il secondo disegno del whitpaper lasciato precedentemente in sospeso 😉

Conclusioni

Il Merkle Tree, ci permette con dei semplici hash di verificare la validità delle nostre transazioni senza dover essere a conoscenza di tutte le transazioni avvenute in un determinato blocco. Questo punto è di vitale importanza per molti wallet e applicazioni che non possono permettersi di avere a disposizione tutto lo storico delle transazioni.

Nel prossimo articolo di approfondimento, Satoshi parlerà proprio di questo introducendo il Simplified Payment Verification (SPV). Ovvero, come verificare i pagamenti senza per forza avere a disposizione un full node.

A presto 🙂