Introduzione alla tecnologia Blockchain

III parte: Blockchain in Java. PoW e Timestampdi

Introduzione

Nella puntata precedente della nostra serie, abbiamo cominciato a vedere come realizzare una Blockchain in Java: in quella occasione, mi sono soffermato sui processi di creazione dei blocchi e sulla gestione della lista dei nodi collegati.

Ho volutamente tralasciato una serie di controlli che ci avrebbero permesso di garantire la qualità dei dati, per affrontali in modo più dettagliato nelle puntate successive. Ora inizieremo ad analizzare questi punti, per capire quali sono gli errori commessi, sia dal punto di vista logico, che dal punto di vista implementativo.

Commettere degli errori in un programma, soprattutto se in fase di sviluppo, è normale. I successivi processi di analisi e di evoluzione del software, forti dei comportamenti notati durante l’utilizzo, permettono di indirizzare lo sviluppo verso i reali utilizzi della tecnologia che si deve implementare.

 

Proof-of-work : PoW

Quando si parla di Blockchain spesso si incontra il concetto di Proof of Work (PoW) [4], ma cos’è un PoW?

Il PoW è un’operazione costosa, dal punto di vista elaborativo, che viene chiesta al richiedente di un servizio per dimostrare che sia stato speso del tempo per generare la richiesta.

I requisiti minimi di un PoW sono costo di elaborazione e velocità di verifica, in modo che il richiedente debba perdere un congruo intervallo di tempo nel creare la richiesta e la relativa verifica possa essere fatta in tempo reale.

Le ragioni del PoW

Leggendo queste poche righe, la prima domanda che ci si può porre è: perché devo obbligare un utilizzatore del mio servizio a effettuare un’operazione che fa perdere tempo e consumare risorse? Non rischio di degradarne le prestazioni?

La risposta è altrettanto semplice: per evitare che un servizio sia riempito di richieste, obblighiamo il richiedente a perdere del tempo per elaborarne una.

Non è un mistero che i primi sistemi che hanno utilizzato un meccanismo di PoW sono stati quelli di gestione della posta elettronica: lo scopo era quello di limitare lo spam. Si partiva dal concetto che chiedere del tempo di elaborazione per una singola email non incidesse negativamente sulla normale gestione della posta elettronica. Diversamente, se il numero di email fosse stato molto elevato, il costo di elaborazione avrebbe scoraggiato la creazione massiva di messaggi indesiderati.

I meccanismi di gestione del PoW

Esistono almeno due meccanismi di gestione del PoW.

  • Challenge Response: il client chiede un servizio, il server invia una sfida con il PoW da risolvere, il client risolve la sfida e invia la soluzione, il server verifica la soluzione e concede il servizio.
  • Solution Verification: il client è già a conoscenza della sfida, la risolve e invia la soluzione al server che la verifica e concede il servizio.

Per semplificare la comprensione, all’interno di questo articolo, utilizzeremo il meccanismo del Solution Verification, preimpostando un livello di difficoltà nella sfida abbastanza basso da poter essere risolto in pochi secondi.

 

Mining

Nella puntata precedente abbiamo visto quanto sia semplice aggiungere un blocco a una blockchain. Se lasciamo però questa libertà, rischiamo di avere il problema dello spam e della proliferazione incontrollata dei blocchi sulla catena.

Proviamo così ad inserire un’attività di PoW nella fase di creazione del blocco, in modo da renderla costosa e scoraggiarne l’utilizzo massivo.

Rispetto a quanto sviluppato nella prima versione, per migliorare la leggibilità del codice, ho introdotto una nuova classe chiamata Block, il cui compito è la gestione del Chaindata in modo da renderlo un semplice POJO delle informazioni che andremo ad aggiungere a Blockchain.

Chaindata e il calcolo dello hash

All’interno dei Chaindata ho poi inserito un elemento variabile nonce [8] propedeutico al calcolo del PoW:

public class Chaindata {
     private String previousHash;
     private long timestamp;
     private String payload;
     private long nonce;
     private String hash;
 }

Questo elemento cambia la struttura del Chaindata e di conseguenza l’algoritmo di calcolo del suo hash. Se ricordate anche come veniva calcolato lo hash, ho revisionato quella parte di codice, passando da un calcolo basato sull’hash di payload e previousHash a un calcolo basato su tutti i dati del blocco.

Questa modifica si è resa necessaria per garantire la congruenza dell’intero blocco di informazioni e non solo di alcune sue parti. Il calcolo è quindi diventato una somma di elementi

StringBuilder string2Hash = new StringBuilder();
string2Hash.append(cd.getPreviousHash());
string2Hash.append(Long.toString(cd.getTimestamp()));
string2Hash.append(cd.getPayload());
string2Hash.append(Long.toString(cd.getNonce()));

sulla quale poi calcolare il digest basato su SHA-256

// Digest
MessageDigest digest = MessageDigest.getInstance("SHA-256");
// Hash
byte[] hash = digest.digest(string2Hash.toString().getBytes());

Infine tale valore viene convertito in una stringa esadecimale, utilizzando uno StringBuilder e un calcolo matematico di veloce risoluzione, in modo da poter ridurre al minimo il numero di operazioni necessarie alla creazione della stringa esadecimale:

// HEX
String HEXES = "0123456789ABCDEF";
StringBuilder hashString = new StringBuilder(2 * hash.length);
for (byte b : hash) {
    hashString.append(HEXES.charAt((b & 0xF0) >> 4))
              .append(HEXES.charAt((b & 0x0F)));
}

Il risultato viene poi memorizzato nel setter di hash del POJO:

// Setter
cd.setHash(hashString.toString());

Quello che abbiamo ottenuto è così un calcolo di hash basato su tutti gli elementi del blocco, che utilizzi l’elemento variabile necessario al calcolo del PoW.

 

Scriviamo un PoW

Un modo abbastanza semplice per creare un PoW è dato dall’obbligare un miner a calcolare uno hash che inizi la sua sequenza con un certo numero di zeri.

Dato che le sequenze di hash non possono essere pilotate a piacere, l’unico modo per arrivare ad un hash con determinate caratteristiche è quello di variare il blocco con dei nuovi valori. Nel nostro caso, avendo una serie di dati fissi e immutabili, l’unico elemento che è possibile variare per raggiungere l’obiettivo è nonce. Per questo motivo, creeremo un algoritmo che si limiterà ad aumentare il suo valore, fino al punto in cui lo hash derivato non avrà le caratteristiche desiderate.

Dato come obiettivo difficulty che rappresenta il numero di zeri col quale il nostro hash dovrà iniziare, inizieremo ad azzerare nonce:

cd.setNonce(0);

A questo punto andremo a calcolare il target: una stringa lunga quanto l’obiettivo da raggiungere, riempita di zero:

String target = new String(new char[difficulty]).replace('\0', '0');

Per trovare l’obiettivo basterà ora realizzare un ciclo di incremento del nonce fino al momento in cui lo hash calcolato inizierà con tanti zeri quanti ne servono al nostro obiettivo:

while (!cd.getHash().substring(0, difficulty).equals(target)) {
    cd.setNonce(cd.getNonce() + 1);
    calculateHash();
}

Si capisce quanto questo algoritmo a forza bruta sia semplice, dal punto di vista del calcolo, ma allo stesso tempo di quanto sia immediata la verifica del raggiungimento dell’obiettivo.

Riporto alcuni blocchi “minati” con l’obiettivo dei 5 zeri iniziali e il relativo tempo di elaborazione: come si nota c’è una certa variabilità del calcolo, che comunque non è mai immediato:

hash 0000081364371052023443D14E1120172E6500A3C4CA3C6020B0F1E0D979F489 in 1709 ms
hash 0000000650E80118B18796423DBCD906DC6F7DB8DE269C48D0F50624A50F2F68 in 11137 ms
hash 000006F01F4E70E5AB6DBFFAF469D6873745CC402255738BBBC5D6E20DAB2DA5 in 158 ms

Nel caso si voglia aumentare il tempo di elaborazione, basterà aumentare il valore di difficoltà, in modo che sia necessario un numero maggiore di iterazioni per trovare il numero di zeri dell’obiettivo.

È interessante notare come le criptovalute tendano a gestire il PoW in modo da mantenere costante il tempo di generazione di un blocco [9]. Nel caso di Bitcoin l’obiettivo è quello di mantenere 600 secondi.

Figura 1 – Il valore di difficoltà del BitCoin punta a mantenere il tempo di generazione di un blocco costante a 600 secondi.

Figura 1 – Il valore di difficoltà del BitCoin punta a mantenere il tempo di generazione di un blocco costante a 600 secondi.

 

Problemi e alternative a PoW

Per alcune criptovalute basate su Blockchain, calcolare un PoW è diventata un’operazione sempre più lunga e costosa. Questo sforzo ha così portato a un maggior consumo energetico nella risoluzione del problema matematico proposto: l’effetto è stato quello di scoraggiare chi si poneva l’obiettivo di guadagnare dalle operazioni di PoW, a meno che non disponesse di una centrale elettrica o abitasse in un sobborgo di una città africana.

Ridurre il costo energetico del PoW

Per questa ragione, per rendere il PoW meno costoso, si stanno cercando delle alternative che abbiano un’incidenza diversa sul consumo energetico. Quelle che al momento hanno riscosso maggior successo sono PoC e PoS.

  • PoSpace o PoC (Proof of Space o Proof of Capacity) [6]: per dimostrare l’interesse verso un servizio, al posto di tempo di CPU, viene concesso dello spazio disco o dello spazio in memoria. Questo tipo di approccio è alla base di criptovalute come SpaceMint, Burstcoin, Chia e Bitcoin Ore.
  • Proof Of Stake (PoS) [7]: in questo caso si valuta l’esposizione del singolo attore verso il servizio. Nel caso delle criptovalute si parla di numero di token posseduti. Si parte dal concetto che, chi ha una forte esposizione verso un servizio, probabilmente si comporterà in modo corretto. Per questo motivo, non si ragiona col concetto: dedichi delle risorse al sistema, ma mi fido in quanto soggetto noto. Il concetto di PoS è normalmente utilizzato nelle criptovalute “pre-minate”, dove non ci sono compensi di elaborazione, ma compensi di conio.

Nonostante queste alternative, il PoW, al momento è l’algoritmo più diffuso e criticato dei sistemi basati su Blockchain.

 

Timestamp

Un altro aspetto interessante della Blockchain è dato dal concetto di data certa del blocco appena inserito all’interno della catena.

Riflettiamo su un concetto: siamo all’interno di una rete di nodi distribuiti, dei quali non abbiamo garanzie. Non possiamo quindi usare un server di riferimento per avere il timestamp corrente: come possiamo fare a capire se il timestamp che generiamo o che riceviamo è valido?

Per gestire in modo algoritmico questo aspetto, possiamo usare lo stesso approccio usato da Bitcoin core [1]: calcoliamo la mediana all’interno di un gruppo di date e definiamo un offset di scostamento entro il quale stare. In base alla grandezza della rete di nodi, il dato sarà più o meno accurato. Chiaramente è obiettivo di tutti i nodi fornire delle date corrette, per evitare di invalidare l’intero sistema e rendere la Blockchain inconsistente.

Nel caso di Bitcoin la mediana è calcolata prima sugli ultimi 11 blocchi della catena, poi sui nodi connessi: tale valore è chiamato “Network-adjusted time“.

In base al valore trovato, il timestamp di un nuovo blocco è considerato valido se è compreso fra la prima mediana e la seconda più uno scostamento di 2 ore.

La classe per calcolare la mediana

Alla luce di questo, ci serve sicuramente una classe per il calcolo della mediana fra date. Per questa implementazione possiamo prendere spunto dal core di Bitcoin [2], rifacendo lo stesso tipo di calcolo in ambiente Java.

Interessante notare l’uso di un unsigned integer per la gestione delle date, aspetto necessario per supera il problema dell’anno 2038 [3] e garantire che il calcolo sia possibile fino al 7 febbraio 2106. Dopo tale data non sarà più possibile generare blocchi, o meglio, ripartendo da zero il calcolo della mediana potrebbe iniziare a dare dei risultati imprevisti, almeno nell’attuale modalità implementativa.

Dato vSorted come l’array ordinato dei Timestamp, la mediana è il valore centrale se l’array ha elementi dispari ed è la media dei valori centrati se è di elementi pari:

public Long median() {
    Long ret;
    int vSortedSize = vSorted.length;
    if ((vSortedSize & 1)==1) {
        ret = vSorted[vSortedSize / 2];
    } else {
        ret = (vSorted[vSortedSize / 2 - 1] + vSorted[vSortedSize / 2]) / 2;
    }
    return ret;
}

 

Conclusioni

All’interno di questa puntata abbiamo toccato due aspetti fondamentali per la costruzione di una Blockchain: il concetto di PoW pensato per evitare il sovrautilizzo del sistema e per gestire in modo costante l’aumento dei blocchi, e il concetto di Timestamp, che si discosta dal concetto classico di marca temporale [10], per introdurre un concetto basato sulla fiducia della rete di nodi connessi e sulla fiducia dei blocchi precedentemente aggiunti.

Nella prossima puntata arricchiremo ulteriormente questi concetti e vedremo il loro impatto all’interno degli algoritmi di verifica della Blockchain.

 

Riferimenti

[1] Block timestamp

https://en.bitcoin.it/wiki/Block_timestamp

 

[2] CMedianFilter

https://goo.gl/3X2cu1

 

[3] Bug dell’anno 2038

https://it.wikipedia.org/wiki/Bug_dell%27anno_2038

 

[4] Proof of work

https://it.wikipedia.org/wiki/Proof-of-work

 

[5] Hashcash

https://it.wikipedia.org/wiki/Hashcash

 

[6] PoSpace

https://en.wikipedia.org/wiki/Proof-of-space

 

[7] PoS

https://en.bitcoin.it/wiki/Proof_of_Stake

 

[8] Nonce

https://en.wikipedia.org/wiki/Cryptographic_nonce

 

[9] Bitcoin difficulty

https://bitcoinwisdom.com/bitcoin/difficulty

 

[10] Marca Temporale

https://it.wikipedia.org/wiki/Marca_temporale

 

Condividi

Pubblicato nel numero
237 marzo 2018
Matteo Baccan è un informatico per passione. Si occupa di sviluppo e architetture software da quando 64k erano sufficienti per qualsiasi tipo di applicazione. Al momento gestisce team di programmatori e sviluppa progetti mission critical per alcune aziende italiane e internazionali. Parte del suo lavoro è consultabile sul sito http://www.baccan.it
Articoli nella stessa serie
Ti potrebbe interessare anche