Nell’approfondimento verrà analizzato il funzionamento di alcuni degli algoritmi di mining (Proof of Work) utilizzati da alcune altcoin. Più in particolare, verrà approfondito l’Equihash, utilizzato da ZCash ed il Blake2b, al momento utilizzata da SiaCoin.

Read this article in the English version here.

Tra gli altri Proof of Work trattati vi sono anche i più recenti X16R ed X16S, usati da RavenCoin e PigeonCoin, seguiti da Tensority, utilizzato da Bytom.

E’ disponibile inoltre un altro approfondimento sugli algoritmi di mining principali utilizzati dalle monete più famose.

Algoritmi di Proof of Work: Blake2b, Equihash, Tensority ed X16R & S

Blake2b

Il Blake2b è una versione derivata dal Blake2. Il Blake2 è una funzione crittografica di hashing, ovvero produce un message digest di lunghezza fissa 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. Nello specifico, il Blake2 è più veloce di tante altre funzioni hashing, in particolare dello MD5, SHA-1, SHA-2 e SHA-3, come visibile nel grafico qua sotto. Nonostante ciò, consente comunque di mantenere un elevato livello di sicurezza, pari all’ultimo standard SHA-3.

La funzione Blake2 è completamente open source ed i sorgenti sono disponibili sull’omonimo repository GitHub. Il Blake2 presenta due varianti:

  • Il Blake2b (o semplicemente Blake2) è la versione ottimizzata per piattaforme a 64 bit, inclusi i processori ARM, e produce digest di qualsiasi dimensione tra 1 e 64 byte;
  • Il Blake2s, invece, è ottimizzato per piattaforme da 8 a 32 bit e produce digest di qualsiasi dimensione tra 1 e 32 byte;
  • Il Blake2x può produrre digest di lunghezza arbitraria.

L’algoritmo, inoltre, è in grado di sfruttare ampiamente il multi-core, in quanto sfrutta le istruzioni SIMD delle moderne CPU. Più nel dettaglio esistono due specifiche versioni designate per l’esecuzione parallela a 4 ed 8 vie, rispettivamente il Blake2bp ed il Blake2sp.

Nel mining vengono utilizzati anche altre derivazioni del Blake, in particolare il Blake256R14 ed il Blake256R8, praticamente uguali ma con un message digest di dimensione differente.

Funzionamento dell’algoritmo Blake2b

Blake2 in realtà una versione affinata e dunque migliorata del Blake. Rispetto a quest’ultimo, infatti, rimuove l’aggiunta di costanti alle parole del messaggio alla Round Function del Blake, cambia due costanti di rotazione e semplifica il padding.

Viene aggiunto poi uno XOR tra un blocco di parametri ed i vettori di inizializzazione ed infine viene ridotto il numero di round da 16 a 12 per il Blake2b e da 14 a 10 per Blake2s, così da velocizzare significativamente l’operazione di hashing.

Algoritmi mining Proof of Work Blake2b

La prima operazione consiste nell’inizializzare gli state vector (h) partendo dagli otto vettori di inizializzazione (da IV0 ad IV7). Successivamente si calcola h0, il quale verrà dato in pasto alla vera e propria funzione di compressione. Quest’ultima funzione calcolerà 16 vettori locali, i primi 8 partendo dagli state vector (h) e gli altri 8 utilizzando i vettori di inizializzazione IV.

A questo punto viene effettuata un’operazione di mixing fra gli state vector e due gruppi di 8 byte provenienti direttamente dal messaggio in ingresso m. La funzione di mixing non fa altro che eseguire operazioni di XOR, permutazioni e somme fra gli state vector e gli 8 byte del messaggio.

L’operazione di mix viene eseguita, nel caso del blake2b, per ben 12 round. Alla fine si ottiene un hash della lunghezza di 64 byte.

Equihash

Equihash è un meccanismo di Proof of Work asimmetrico fortemente vincolato alla memoria (memory-hard), dato che richiede molta memoria per generare una prova istantanea di verifica. Il vincolo memory hard ha reso l’algoritmo ASIC Proof per diverso tempo, ma lo scorso anno Bitmain ha annunciato un modello specifico proprio per le monete basate su Equihash.

Il cuore dell’Equihash è incentrato sul problema generalizzato del compleanno e sull’algoritmo avanzato di Wagner per la risoluzione. Per rendere la funzione difficile da implementare su ASIC e dunque utilizzabile prevalentemente su CPU e GPU, Equihash implementa un sistema di vincoli temporali ed alla memoria, così da penalizzare il calcolo su quei dispositivi con poca memoria. Di contro, però, essendo asimmetrico e con pochi passi sequenziali, Equihash può essere facilmente parallelizzato.

Funzionamento dell’algoritmo Equihash

E’ un po’ difficile spiegare il funzionamento di Equihash. Innanzitutto bisogna definire due parametri, ovvero n e k, necessari per il risolutore Equihash. Tali parametri vanno scelti accuratamente perché impattano sull’efficienza di risoluzione dell’algoritmo.

Nel caso di ZCash, vengono utilizzati come parametri n=200 e k=9, in quanto sono stati riscontrati come i parametri più efficienti da utilizzare, sia in termini di memoria utilizzata, che come tempistiche di elaborazione.

Algoritmi mining Proof of Work Equihash

Fissati i parametri, si risolve il problema generalizzato del compleanno. Quest’ultimo consiste nel trovare una serie di valori x1, x2, …, x2k, tutti minori di 2n/(k+1)+1, tali che l’operazione XOR fra i corrispettivi valori di hash calcolati tramite una funzione di hashing Blake2b, siano uguale a zero. Analiticamente parlando, si avrà dunque:

H(x1) xor H(x2) xor …xor H( x2k) = 0 dove H è la funzione di hashing Blake2b

E’ proprio l’algoritmo di Wagner che permette di risolvere tale problema di dimensionamento. L’algoritmo di Wagner richiede una quantità di memoria pari a O(2n/(k+1)), dunque dipendente dai parametri n e k come accennato prima. Fissati tali parametri, la riduzione della memoria disponibile aumenta vertiginosamente il tempo di esecuzione, motivo per Equihash è vincolato alla memoria.

Algoritmi mining Proof of Work Equihash

Più che alla quantità di memoria in sé (un Gigabyte circa, a seconda del software di mining, dovrebbe bastare), il vincolo prestazionale è dovuto al bandwidth, anche se ciò non sempre affligge in maniera significativa le prestazioni di mining, in quanto molto dipende dai parametri scelti.

Tensority

Tensority è un algoritmo di consenso Proof of Work abbastanza recente, all’interno del quale sono state introdotti l’uso delle matrici e dei tensori, così da sfruttare la potenza di mining non solo per l’hashing ma anche per l’accelerazione dell’Intelligenza Artificiale e per il calcolo parallelo distribuito.

Tensority ha debuttato sulla moneta Bytom. E’ un algoritmo ASIC friendly, tanto che Bitmain ha annunciato praticamente al day-one gli ASIC Antminer B3, dedicati esclusivamente al mining di Bytom e probabilmente caratterizzati dai nuovi chip destinati al deep learning ed all’intelligenza artificiale.

L’obiettivo di Tensority è quello di fornire un nuovo sistema di consenso per la blockchain ed al contempo creare una rete distribuita per i servizi di deep learning ed all’intelligenza artificiale, così da utilizzare in maniera utile ed efficiente tale potenza di calcolo.

Funzionamento dell’algoritmo Tensority

Tensority utilizza i parametri Seed e l’hash dell’header del blocco come input. Il seed è un array di 32 byte determinato da un certo periodo di vita della blockchain. Può dunque essere considerato come un’istantanea dello storico del consenso sulla rete. Per ottenere un blocco convalidato, i minatori dovranno continuare a generare un nonce fino a quando quest’ultimo non soddisferà il requisito della difficoltà.

Tensority prevede cinque passaggi: il calcolo della cache, la costruzione della matrice, le operazioni tra matrici, la generazione e la convalida del lavoro.

Algoritmi mining Proof of Work Tensority

La cache viene generata a partire dal seed, in quanto rispetto al tasso di creazione dei blocchi, il rinnovo dei seed avviene più lentamente. Quindi, la cache generata dal seed può essere riutilizzata per un certo periodo di tempo.

Successivamente si ha la parte più innovativa dell’algoritmo, ovvero la costruzione della matrice. Tale matrice viene costruita effettuando una serie di operazioni di partizionamento e raggruppamento della cache.

Dopo di che, si passa alle operazioni fra matrici. Il numero di operazioni eseguibili dipende principalmente dalla potenza di calcolo del minatore. Inoltre, invece che utilizzare le classiche matrici di interi, vengono utilizzati dei float64, così da supportare le operazioni svolte dagli algoritmi d’intelligenza artificiale, basati prevalentemente sui float64. Viene infine generata anche una hashmatrix.

A questo punto si ha il PoW vero e proprio, che è costituito, partendo dalla hashmatrix generata al passo precedente, da un hash da 32 byte. Infine, viene eseguito un confronto fra il valore del PoW eseguito con la difficoltà del blocco. Se il lavoro ha un valore inferiore, può essere ritenuto valido e viene dunque propagato agli altri minatori. Altrimenti, il minatore continuerà a rieseguire la procedura utilizzando un nonce differente fino alla ricezione di un nuovo blocco convalidato.

X16R & X16s

Infine, esistono due algoritmi di mining piuttosto recenti ed ASIC Resistant, ovvero X16R ed il derivato X16s. X16R è nato con l’obiettivo di proporre un meccanismo di Proof of Work volto a sconfiggere gli ASIC ed a renderne davvero poco conveniente lo sviluppo. Attualmente è utilizzato dalla moneta RavenCoin.

Gli algoritmi di mining CryptoNight, Etash ed Equihash sono algoritmi memory-hard, dunque fortemente vincolati alla memoria. I più recenti X11, X13 ed X15, invece, sono costituiti da una sequenza di algoritmi di hashing dove l’output di uno diventa l’input del il successivo. Tuttavia entrambi gli approcci non si sono rivelati immuni agli ASIC.

X16R riprende l’approccio degli algoritmi di mining X11/13 etc, ma a differenza di quest’ultimi non usa una sequenza fissa d’uso dei vari algoritmi. Essi infatti vengono scelti in maniera casuale. Gli algoritmi di hashing utilizzati, invece, sono gli stessi di utilizzati dall’X15, a cui viene aggiunto un hashing finale tramite lo SHA512. Tuttavia l’ordine di esecuzione e quali algoritmi eseguire viene modificato e scelto in base all’hash del blocco precedente, in particolare gli ultimi 8 byte.

Ciò non rende impossibile la realizzazione di un ASIC ma richiede il supporto di un ingresso aggiuntivo per l’elaborazione, attualmente più facile da implementare su CPU e GPU. Il riordino casuale, inoltre, impedisce anche il riutilizzo degli ASIC disponibili per l’X11 e per X15.

L’algoritmo di hashing X16R è costituito da 16 algoritmi di hashing che operano secondo una sequenza casuale, il cui ordinamento dipendente dagli ultimi 8 byte dell’hash del blocco precedente. Gli algoritmi utilizzati sono i seguenti:

  • 0=blake
  • 1=bmw
  • 2=groestl
  • 3=jh
  • 4=keccak
  • 5=skein
  • 6=luffa
  • 7=cubehash
  • 8=shavite
  • 9=simd
  • A=echo
  • B=hamsi
  • C=fugue
  • D=shabal
  • E=whirlpool
  • F=sha512

La variante del PoW X16S

X16S (Shuffle) è una variante dell’X16R. A differenza di quest’ultimo, il nuovo algoritmo X16S fornisce una certa stabilità dell’hashrate e dell’utilizzo della potenza computazionale. Può dunque essere considerato un una sorta di miglioramento, specialmente per i minatori. Attualmente è utilizzato dalla moneta Pigeoncoin, minabile solamente tramite CPU e GPU.

Algoritmi mining Proof of Work X16R

Con X16R, infatti, scegliendo gli algoritmi da eseguire in maniera casuale basandosi sul’hash di un blocco precedente può capitare di eseguire più volte la stessa stessa funzione di hash invece che eseguirle tutte. Dal momento che alcune funzioni di hashing sono più esose di altre, otteniamo dunque hashrate e consumi fortemente variabili. Di conseguenza, si ottengono prestazioni nel mining altalenanti, con tutte le conseguenze del caso.

L’algoritmo di Proof of Work X16S utilizza le ultime sedici cifre del blocco precedente per riordinare una lista contenente tutte le funzioni di hashing da eseguire. X16S ricrea l’elenco utilizzando il valore di ciascuna cifra presente nelle ultime sedici cifre, così da creare un indice all’interno della lista contenente tutti gli algoritmi.

In sintesi, X16S randomizza l’ordine in base all’hash del blocco precedente, ma a differenza del X16R nessun algoritmo è ripetuto o omesso. Ciò consente di sfruttare tutti i vantaggi della X16R, migliorando notevolmente la hashrate e la stabilità.

The post Algoritmi di mining (Proof of Work): Blake2b, Equihash, Tensority ed X16R e S appeared first on The Cryptonomist.



Leggi l’articolo su cryptominando.it