HomeCriptovaluteMiningAlgoritmi di mining (Proof of Work): SHA-256, Scrypt, CryptoNight, Ethash e X11

Algoritmi di mining (Proof of Work): SHA-256, Scrypt, CryptoNight, Ethash e X11

Ad oggi esistono diverse criptovalute il cui mining si basa su diversi meccanismi di Proof of Work per la verifica e validazione dei blocchi da inserire nella blockchain. Tali Proof of Work spesso si basano su differenti algoritmi e funzioni di hashing.

Read this article in the English version here.

Ne esistono diversi. Tra di essi il più famoso è lo SHA-256, usato prevalentemente per il mining di Bitcoin ed il suo fork Bitcoin Cash. Vi è poi Scrypt, utilizzato da Litecoin ed anche dal simpatico DOGE.

Un altro famosissimo algoritmo è il CryptoNight, utilizzato da Monero e decine di altcoin differenti. Vi è poi l’Ethash, usato da Ethereum ed Ethereum Classic. Infine, DASH utilizza l’efficiente X11. Vi sono tanti altri PoW, ma in questo primo articolo verranno trattati solo i più diffusi.

SHA-256

Lo SHA-256, acronimo di Secure Hash Algorithm, in questo caso con un digest di 256 bit, appartiene ad un set di funzioni crittografiche ed è stato il primo ad essere utilizzato nel mondo delle criptovalute.

Come ogni algoritmo di hash, lo SHA-256 produce un message digest partendo da un messaggio di lunghezza variabile. Ciò non consente di risalire al messaggio originale conoscendo solo quest’ultimo dato, in quanto la funzione non è reversibile. Inoltre, tale meccanismo consente anche di impedire l’eventuale creazione intenzionale di due messaggi diversi con lo stesso digest.

La funzione di hashing dello SHA-256 non è particolarmente complessa, motivo per cui non servono troppe risorse per eseguirla. Infatti, la funzione sfrutta semplici operazioni logiche ed aritmetiche, senza la necessità di usare memorie troppo veloci ed istruzioni particolari, motivo per cui la funzione può essere facilmente implementata sugli FPGA o nel layout di chip progettati ad hoc, ovvero gli ASIC.

Gli ASIC vantano un’efficienza ed hashrate ben maggiore delle GPU e delle CPU, in quanto possono svolgere solamente la funzione di per cui sono stati progettati, in questo caso quella di hashing dello SHA-256. Generalmente il throughput degli ASIC su algoritmi di tipo SHA-256 si misura ormai Th/s.

Funzionamento dell’algoritmo SHA-256

Al messaggio originale vengono aggiunti dei bit ridondanti affinché la lunghezza finale del messaggio risulti congruente a 448 modulo 512 (famoso MD5). Il modulo non è altro che una funzione che ha come risultato il resto della divisione fra i due numeri quando è possibile eseguirla. In questo caso, 448 modulo 512 equivale a 448 bit. Così facendo la lunghezza di “messaggio+imbottitura” è pari ad un numero di 64 bit più piccolo di un multiplo di 512 bit.

Successivamente, alla sequenza di bit appena creata viene aggiunto un intero di 64 bit contenente la lunghezza del messaggio originale. Alla fine si otterrà dunque una sequenza di bit che è un multiplo di 512.

Il terzo passaggio consiste nell’inizializzare il buffer MD. Esso è un buffer di 256 bit suddiviso in otto registri da 32 bit ciascuno. Gli otto registri verranno convenzionalmente indicati con (A, B, C, D, E, F, G ed H) ed inizializzati con una serie di valori esadecimali.

Proof of Work SHA-256

Infine, avviene la vera e propria elaborazione dei blocchi da 512 bit. La sequenza di bit “messaggio+imbottitura+lunghezzaMessaggio” precedentemente generata viene divisa in blocchi da 512 bit. Tali blocchi vengono identificati con Bn, con n che va da 0 a N.

Il fulcro dell’algoritmo SHA è chiamato compression function ed è formato da 4 cicli di 20 passi cadauno. I cicli hanno una struttura molto simile tra loro se non per il fatto che utilizzano una differente funzione logica primitiva.

Ogni blocco viene preso come parametro di input da tutti e 4 i cicli insieme ad una costante K e i valori degli otto registri. Alla fine della computazione verranno ottenuti dei nuovi valori per A,B,C,D,E, F, G, H che verranno utilizzati per la computazione del blocco successivo sino ad arrivare al blocco finale H.

Scrypt

Per combattere gli ASIC e dunque il pericolo di “centralizzazione della potenza di calcolo”, fu sviluppato un altro algoritmo di mining, implementato poi nei protocolli di Proof of Work di alcune criptovalute. Lo Scrypt, questo il nome dell’algoritmo, sfrutta alcune funzione che fanno un largo uso della memoria per ridurre drasticamente l’efficienza dei circuiti logici tipici degli ASIC. Tuttavia, per rendere veloce ed efficiente l’uso dello Scrypt anche sui comuni PC, furono semplificati alcuni parametri con pessime conseguenze.

L’algoritmo inizialmente, aveva come unico obbiettivo il mining solamente su CPU. Tuttavia poco dopo il debutto arrivarono i primi tool software per il mining su GPU. Un anno dopo, verso la fine del 2013, arrivarono i primi Asic Scrypt based, decretando il fallimento degli obiettivi prefissati da tale algoritmo.

Nel caso di mining eseguito con computer ad alte prestazioni o ASIC, generalmente il throughput si misura in Kh/s o al più Mh/s.

Funzionamento dell’algoritmo Scrypt

L’algoritmo Scrypt ha diversi parametri, fra cui N, che va a definire il costo in termini di risorse dell’esecuzione dell’algoritmo. Troviamo poi il parametro p, che ne definisce la parallelizzazione ed r, che definisce la dimensione dei blocchi e dunque la memoria utilizzata. Sono presenti anche altri parametri legati alla funzione di hash ed alla lunghezza dell’hash in output.

Il funzionamento dello Scrypt prevede due parametri iniziali, ovvero il messaggio da crittografare ed il Salt, una stringa randomica utilizzata per aggiungere entropia e difendere il sistema dagli attacchi basati sulle Rainbow table precomputate. Esse non sono altro che tabelle di associazione che offrono un compromesso tempo-memoria per il recupero delle chiavi di cifratura in chiaro partendo da chiavi in formato hash.

I dati vengono quindi dati in pasto ad un’apposita funzione di derivazione delle chiavi, ovvero la PBKDF2, acronimo di Password-Based Key Derivation Function 2. Tale funzione, utilizzando i parametri dettati in precedenza all’algoritmo, riduce ulteriormente le vulnerabilità delle chiave crittografate ad attacchi di tipo brute force. Dal PBKDF2 vengono generati un numero p di blocchi da 128*r Bytes [B0…Bp−1].

A questo punto, utilizzando la funzione ROMix, in questo caso di tipo memory-hard sequenziale, i blocchi vengono mixati, anche in parallelo. I blocchi mixati in uscita vengono dunque passati come parametro Salt (expensive Salt) ad un’altra PBKDF2 che genera una chiave della lunghezza desiderata.

Proof of Work Scrypt

CryptoNight

Il CryptoNight è utilizzato per il mining di quelle monete caratterizzate dal protocollo CryptoNote, fra cui Monero. E’ una funzione strettamente vincolata alla memoria (memory hard hash), in questo caso alla memoria Cache di terzo livello delle CPU in quanto incentrata sulla latenza. Tale vincolo è stato imposto per rendere il CryptoNight poco efficiente su sistemi quali GPU ed FPGA, ma soprattuto ASIC, non dotati di memoria cache e dunque svantaggiati o praticamente impossibilitati all’utilizzo dell’algoritmo.

L’algoritmo di Proof of Work CryptoNight esegue come primo processo l’inizializzazione di uno Scratchpad, ovvero un’area di memoria utilizzata per conservare i dati utilizzati. Nel caso del CrytpoNight, vengono utilizzati dati pseudo casuali appositamente per inibirne l’utilizzo da parte di ASIC e per minimizzare l’efficienza delle GPU. L’algoritmo inoltre, esegue numerosi operazioni di lettura e scrittura nello scratchpad per enfatizzare la velocità delle memoria e farne risaltare la latenza, che deve essere la minore possibile. Infine, utilizzando i dati nello scratchpad ed una funzione di hashing, viene prodotto un opportuno valore.

Le dimensioni dello scratchpad del CryptoNight sono di circa 2 MB di memoria per ogni istanza a causa delle seguenti ragioni:

  1. può essere contenuto nelle cache L3 (per core) dei processori moderni;
  2. una memoria interna di un megabyte è (anzi era) una dimensione inaccettabile per la pipeline degli ASIC;
  3. le GPU possono eseguire decine o centinaia di thread ma saranno limitate dalla memoria GDDR5, con una latenza decisamente peggiore della cache L3 delle CPU moderne;
  4. una significativa espansione dello scratchpad richiederebbe un aumento delle interazioni. Ciò implicherebbe un aumento del tempo richiesto. Delle chiamate continue e prolungate alla rete p2p potrebbero dunque compromettere la rete e portare ad alcune vulnerabilità, in quanto i nodi sono obbligati ad effettuare una verifica della PoW di ogni blocco. Se un nodo spendesse un considerevole intervallo di tempo sull’hash di un blocco, potrebbe essere facilmente inondato con un meccanismo di flooding di falsi blocchi causando un DDoS.

Il CryptoNight rimanse inviolato dagli ASIC per diversi anni, sino a quando, il 15 Marzo 2018, Bitmain, Baikal e Halong Mining annunciarono diversi modelli di ASIC CryptoNight, in grado di restituire hashrate superiori ai 200 KH/s.

Da allora il team di Monero ha più volte agito sui parametri del CryptoNight, rendendo il Proof of Work ancor più vincolato alla memoria.

Funzionamento dell’algoritmo CryptoNight

L’input di hash viene inizializzato utilizzando il Keccak (funzione SHA3), ponendo i parametri B uguale a 1600 e C uguale a 512. I parametri finali del Keccak, ovvero i Bytes dallo 0 al 31, sono interpretati come una chiave AES 256 ed espansi in 10 round keys.

I Bytes fra il 64 ed il 191-esimo invece, vengono estratti in otto blocchi da 16 Bytes ciascuno, i quali verranno successivamente crittografati. Viene dunque allocato il tutto nello scartchpad, che avrà una dimensione prossima ai 2 MB, come precedentemente riportato.

Proof of Work Cryptonight

Fatto ciò, viene imposto uno XOR tra i primi 63 Bytes del Keccak per inizializzare i vincoli A e B, ciascuno di 32 Bytes. Tali variabili ed il relativo processing vengono utilizzate per imporre un loop di letture e scritture continue (ben 524288 volte) nello scratchpad, così da far risultare l’algoritmo strettamente vincolato alla latenza della memoria. Infine, viene computata la sequenza di hash finale dei dati precedentemente ottenuti.

Ethash

Ethash, come lascia intuire il nome, nasce come funzione per eseguire il Proof of Work della blockchain di Ethereum. Questo algoritmo mischia due funzioni standard di crittografia, ovvero lo SHA-3 ed il Keccak. Ciò ha come risultato una funzione resistente agli ASIC ma al contempo veloce da verificare ed eseguire.

La resistenza agli ASIC è garantita dalla natura memory hard dell’algoritmo, visto l’utilizzo di un data set pseudo casuale inizializzato in base alla lunghezza della blockchain, dunque variabile. Tale data set viene chiamato DAG (grafo aciclico diretto) e viene rigenerato ogni 30-mila blocchi (circa 5 giorni).

Nonostante ciò, lo scorso 3 Aprile 2018, Bitmain ha annunciato l’atteso Antminer E3, il primo ASIC per Ethash in grado di restituire un hashrate di circa 200 MH/s con un assorbimento di quasi 800 Watt.

Attualmente il DAG ha un dimensione di circa 3.4 GB, motivo per cui non è possibile effettuare mining di Ethereum con schede video dotate di meno di 3GB di memoria video, in quanto il set di dati è necessario per il funzionamento della funzione di hash.

Nel caso di mining eseguito con computer ad alte prestazioni, generalmente il throughput si misura in Mh/s o al più Gh/s.

Funzionamento dell’algoritmo Ethash

Per prima cosa, vengono combinati insieme – sfruttando lo SHA-3 – un header pre-processato derivante dall’ultimo blocco ed il Nonce attuale, ovvero un numero casuale a 32 bit generato dai miners come target di hash. Viene dunque creata una sequenza di Byte mixata lunga 128 Byte, chiamata Mix 0.

Il Mix è utilizzato per determinare quali dati collezionare dalla DAG, tramite un’apposita funzione di fetch. Successivamente, il Mix 0 ed i dati recuperati dal DAG vengono mixati, generando una nuova stringa di 128 Byte, chiamata Mix 1. Tale operazione viene eseguita con lo stesso procedimento per 64 volte, fino a raggiungere l’ultima stringa, ovvero la Mix 64.

Il Mix 64 viene dunque processato per ottenere una sequenza di 32 Bytes, chiamata Mix Digest. Tale sequenza viene dunque confrontata con una seconda sequenza target. Se esso risulta minore del target, allora il Nonce viene considerato raggiunto e viene avviato il broadcasting alla rete Ethereum. In caso contrario, l’algoritmo viene ri-eseguito con un nuovo Nonce.

Proof of Work Ethash

Il vincolo che rende l’algoritmo strettamente legato alla memoria ed al bandwitch in particolare, dunque anche il bus, consiste proprio nell’accesso al DAG per il fetch dei dati.

X11

L’X11, erede delle varianti X13, X15 ed X17, è un algoritmo di Proof of Work nato per essere molto efficiente sia su CPU che su GPU. Come lascia intuire il nome, sfrutta una combinazione di ben undici differenti algoritmi di crittografia.

Purtroppo, l’X11 non ha saputo dimostrarsi ASIC Proof, visto che dopo pochi mesi sono stati resi disponibili i primi ASIC dedicati a tale algoritmo.

Sfortunatamente non si trovano troppi dettagli tecnici inerenti al funzionamento di X11, se non i nomi degli undici algoritmi di hashing usati: blake, bmw, groestl, jh, keccak, skein, luffa, cubehash, shavite, simd, echo. L’uso combinato di tali funzioni di hash consente di raggiungere un elevato livello di sicurezza mantenendo un’efficienza del 30% superiore al classico SHA-256.

Emanuele Pagliari
Emanuele Pagliarihttps://www.emanuelepagliari.it/
Ingegnere delle telecomunicazioni appassionato di tecnologia. La sua avventura nel mondo del blogging è iniziata su GizChina.it nel 2014 per poi proseguire su LFFL.org e GizBlog.it. Emanuele è nel mondo delle criptovalute come miner dal 2013 ed ad oggi segue gli aspetti tecnici legati alla blockchain, crittografia e dApp, anche per applicazioni nell'ambito dell'Internet of Things
RELATED ARTICLES

2 COMMENTI

MOST POPULARS

GoldBrick