Algoritmi Mining Mining Wiki

Algoritmi di mining: SHA-256, Scrypt, CryptoNight, Ethash ed X11, le differenze

Nell’approfondimento di oggi andremo a vedere come funzionano e quali sono i principali algoritmi utilizzati nel mining di criptovalute. Se non sapete cos’è il mining, potete trovare alcuni dettagli basilari qui.

Potrebbe interessarti anche: algoritmi di mining parte due: Blake2b, Equihash, Tensority, X16R & X16S: CLICCA QUI

Quali sono i principali algoritmi di mining?

Cominciamo subito con un elenco dei principali e dei più utilizzati. Tra di essi cito lo SHA-256, usato prevalentemente per il mining di Bitcoin ed il suo fork Bitcoin Cash. Abbiamo poi lo Scrypt, utilizzato prevalentemente da Litecoin, Verge, dal Feathercoin ed anche dal simpatico DOGE. Un altro famosissimo algoritmo è il CryptoNight, utilizzato dal protocollo CryptoNote per il PoW Egalitario. Sono diverse le monete ad utilizzarlo, fra cui Monero, Electroneum ByteCoin. Troviamo poi Ethash, usato da Ethereum ed Ethereum Classic. Infine, segnalo anche l’efficiente X11, utilizzato da DASH.

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 in Gh/s o al più Th/s.

asic

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 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.

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 otterremo dei nuovi valori per A,B,C,D,E, F, G, H che useremo 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, ovvero 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.

Scrypt

CryptoNight

Come già detto, il CryptoNight è utilizzato per il mining di quelle monete caratterizzate dal protocollo CryptoNote. 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 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.

CryptoNote

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 è una dimensione inaccettabile per la pipeline degli ASIC moderni;
  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.

UPDATE: Lo scorso 15 Marzo 2018, Bitmain, Baikal e Halong Mining ha annunciato diversi modelli di ASIC CryptoNight, in grado di restituire hashrate superiori ai 200 KH/s. Per maggiori informazioni vi rimandiamo al nostro articolo dedicato: CLICCA QUI.

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.

CryptoNight Mining

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). Attualmente il DAG ha un dimensione di circa 2.3 GB, motivo per cui non è possibile effettuare mining di Ethereum con schede video dotate di meno di 2.5-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.

UPDATE: 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 180 MH/s. Per maggiori informazioni vi rimandiamo al nostro articolo dedicato: CLICCA QUI.

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 creato 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.

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

Concludiamo con uno degli ultimi algoritmi arrivati nel mondo delle criptovalute (2015), ovvero l’X11, anche se esistono ulteriori varianti X13, X15 ed X17. X11 è un algoritmo molto efficiente sia su CPU che GPU che, 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. Essi sono: 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.

Potrebbe interessarti anche: algoritmi di mining parte due: Blake2b, Equihash, Tensority, X16R & X16S: CLICCA QUI

Per questo approfondimento è tutto. Alla prossima!

sharing-caring

Vi invitiamo a seguirci sul nostro canale Telegram ed anche sul gruppo ufficiale Telegram, dove sarà possibile discutere insieme delle notizie e dell’andamento del mercato, sulla nostra pagina Facebook e sul nostro account Twitter.

[ VIA | VIA | VIA | VIA ]

Emanuele Pagliari

Ingegnere delle telecomunicazioni appassionato di tecnologia. La mia avventura nel mondo del blogging è iniziata su GizChina.it nel 2014 per poi proseguire su LFFL.org, GizBlog.it, ed ora su CryptoMinando.it. Sono nel mondo delle criptovalute come minatore dal 2013 ed ad oggi seguo gli aspetti tecnici legati alla blockchain, crittografia e dApps, anche per applicazioni nell'ambito dell'Internet of Things, la mia branca di studio.
Follow Me:

Related Posts

Rispondi