Ergo e il Meccanismo di Consenso di Autolykos – Parte 2

Tempo di lettura stimato: 13 minuti

La scorsa settimana, abbiamo introdotto un’esplorazione approfondita del meccanismo di consenso Autolykos di Ergo. Con questo articolo, completiamo la seconda parte di quella discussione e ci immergiamo in ulteriori dettagli. Prima di leggere questo documento, si consiglia ai lettori di dare un’occhiata alla Parte 1 che trovate qui.

Come promemoria, ecco gli pseudocodici di block mining e hash function.

Funzione hash basata su Blake2b256

Linee 3, 4 – iniziano durante il loop e indovinando

Dopo aver calcolato l’elenco R, il minatore crea un’ipotesi nonce ed entra in un ciclo per verificare se il nonce alla fine crea un output inferiore al valore target specificato.

Linee 5, 6 – seme per la generazione di indici

Linea 5, i = takeRight(8, H(m|| nonce)) mod N, produce un numero intero in [0,N). L’algoritmo 3 viene utilizzato ma con m e il nonce come input. Una volta l’hash H(m|| nonce) viene restituito, gli 8 byte meno significativi vengono mantenuti e quindi passati attraverso la mod N. Come nota a margine, il valore intero più alto possibile con 8 byte è 264 – 1, e assumendo N = 226, un mod N hash a 8 byte farà sì che le prime cifre siano zero. Il numero di zeri in i diminuisce man mano che N cresce.

La linea 6 produce e, un seme per la generazione di indici. L’algoritmo 3 viene chiamato con gli input i (generati nella riga 5), h e M. Quindi, il byte più significativo dell’hash numerico viene eliminato e i restanti 31 byte vengono mantenuti come valore e. Va anche notato che il valore e può essere recuperato dall’elenco R invece di essere calcolato poiché e è un valore r.

Linea 7 – generatore di indici

L’indice degli elementi J viene creato utilizzando l’algoritmo 6 con gli input e, m e nonce. La funzione genIndexes è uno pseudocasuale unidirezionale che restituisce un elenco di numeri k (=32) in [0,N).

Ci sono un paio di passaggi aggiuntivi che non vengono visualizzati nello pseudocodice, ad esempio uno spreco di byte. La creazione e l’applicazione di genIndexes può essere spiegata tramite il seguente esempio:

GenIndexes(e|| m|| nonce)…

hash = Blake2b256(e|| m|| nonce) = [0xF963BAA1C0E8BF86, 0x317C0AFBA91C1F23, 0x56EC115FD3E46D89, 0x9817644ECA58EBFB]

hash64to32 = [0xC0E8BF86, 0xF963BAA1, 0xA91C1F23, 0x317C0AFB, 0xD3E46D89 0x56EC115F, 0xCA58EBFB, 0x9817644E]

extendedhash (cioè byteswap e concatenare 4 byte ripetendo i primi 4 byte) = [0x86BFE8C0, 0xA1BA63F9, 0x231F1CA9, 0xFB0A7C31, 0x896DE4D3, 0x5F11EC56, 0xFBEB58CA, 0x4E641798, 0x86BFE8C0]

Il seguente codice python mostra il processo di slicing dell’hash esteso, restituendo indici k. In questo esempio assumiamo h < 614.400, quindi N = 226 (67,108,864).

Slicing e mod N[1]
for i in range(8):
idxs[i << 2] = r[i] % np.uint32(ItemCount)
idxs[(i << 2) + 1] = ((r[i] << np.uint32(8)) | (r[i + 1] >> np.uint32(24))) % np.uint32(ItemCount)
idxs[(i << 2) + 2] = ((r[i] << np.uint32(16)) | (r[i + 1] >> np.uint32(16))) % np.uint32(ItemCount)
idxs[(i << 2) + 3] = ((r[i] << np.uint32(24)) | (r[i + 1] >> np.uint32(8))) % np.uint32(ItemCount)

Il principale takeaway è che lo slicing restituisce k indici che sono valori pseudocasuali derivati dal seme, cioè e, m e nonce.

restituire [0x2BFE8C0, 0x3E8C0A1, 0xC0A1BA, 0xA1BA63, 0x1BA63F9, 0x263F923, 0x3F9231F, 0x1231F1C, 0x31F1CA9, 0x31CA9FB, 0xA9FB0A, 0x1FB0A7C, 0x30A7C31, 0x27C3189, 0x31896D, 0x1896DE4, 0x16DE4D3, 0x1E4D35F, 0xD35F11, 0x35F11EC, 0x311EC56, 0x1EC56FB, 0x56FBEB, 0x2FBEB58, 0x3EB58CA, 0x358CA4E, 0xCA4E64, 0x24E6417, 0x2641798, 0x179886, 0x39886BF, 0x86BFE8]

Questo indice può essere convertito in valori in base 10 in quanto si riferisce ai numeri in [0, N). Ad esempio, 0x2BFE8C0 = 46131392, 0x3E8C0A1 = 65585313, 0xC0A1BA = 12624314 e così via. Il minatore utilizza questi indici per recuperare i valori k r.

La funzione genIndexes impedisce le ottimizzazioni in quanto è estremamente difficile, praticamente impossibile, trovare un seed tale che genIndexes(seed) restituisca gli indici desiderati.

Linea 8 – somma di elementi r dati k

Utilizzando l’indice generato nella riga 7, il minatore recupera i corrispondenti valori k (=32) r dall’elenco R e somma questi valori. Questo potrebbe sembrare confuso, ma analizziamolo.

Continuando l’esempio precedente, il minatore memorizza i seguenti indici:

{0 | 46,131,392},
{1 | 65,585,313},
{2 | 12,624,314},
{3 | 10,599,011},

{31 | 8.830.952}

Dati gli indici di cui sopra, il minatore recupera i seguenti valori r dall’elenco R memorizzato in memoria.

{0 | 46,131,392} → dropMsb(H(46,131,392|| h|| M))
{1 | 65.585.313} → dropMsb(H(65.585.313|| h|| M))
{2 | 12,624,314} → dropMsb(H(12,624,314|| h|| M))
{3 | 10.599.011} → dropMsb(H(10.599.011|| h|| M))

{31 | 8,830,952} → dropMsb(H(8,830,952|| h|| M))

Si noti che Takeright(31) operato su un hash a 32 byte può anche essere scritto come dropMsb – drop most significant byte.

Poiché il minatore memorizza già l’elenco R nella RAM, il minatore non ha bisogno di calcolare k (= 32) funzioni Blake2b256 e cerca invece i valori. Questa è una caratteristica chiave della resistenza ASIC. Un ASIC con memoria limitata deve calcolare 32 iterazioni Blake2b256 per ottenere i valori che avrebbero potuto essere cercati in memoria e il recupero dalla memoria richiede molto meno tempo. Per non parlare, un ASIC con memoria limitata richiederebbe 32 istanze Blake2b256 fisicamente sul die per ottenere un hash per ciclo, il che richiederebbe più area e costi più elevati. È semplice dimostrare che la memorizzazione della lista R in memoria vale la pena di essere compromessa. Supponiamo quanto segue, una GPU ha una velocità di hash di G = 100MH / s, _N = 226k = 32, intervallo di blocco t = 120 secondi e gli elementi vengono cercati ogni 4 hash. Mi piace supporre che gli elementi vengano cercati ogni 4 hash perché, per ogni ipotesi nonce, più elementi come i, J e H (f) richiedono l’algoritmo 3, cioè l’hash blake2b, istanze. Possiamo stimare che ogni valore r verrà utilizzato, in media, (G * k * t) / (N * 4) = 1430,51 volte.

Una volta che i valori di 32 r sono stati cercati, vengono sommati.

Linea 9, 10, 11, 12 – controlla se l’hash della somma è inferiore all’obiettivo

La somma dei valori di 32 r viene sottoposta a hashing utilizzando l’algoritmo 3 e, se l’output è inferiore al target b, il PoW ha esito positivo, m e nonce vengono restituiti ai nodi di rete e il minatore viene ricompensato in ERG. Se l’hash della somma è superiore alla destinazione, le righe da 4 a 11 vengono ripetute con un nuovo nonce.

Se sei arrivato fin qui, complimenti! Dopo aver letto tutte queste informazioni, dovresti avere una buona comprensione di Autolykos v2! Se desideri vedere una dimostrazione visiva di Autolykos, consulta il grafico alla fine di questo documento. Se desideri una spiegazione video, puoi trovarla qui.

Resistenza ASIC

Sappiamo da Ethereum che gli algoritmi “memory hard” possono essere conquistati integrando la memoria sugli ASIC. Ergo è diverso, ma prima rivediamo perché un ASIC con memoria limitata non è competitivo e perché un minatore deve memorizzare la lista R. La linea 8 di Autolykos block mining scoraggia le macchine con memoria limitata. Se un minatore ASIC non memorizza l’elenco R, richiede molti core per generare gli hash numerici a 31 byte al volo. I valori di 32 r non possono essere calcolati in modo efficiente utilizzando un singolo ciclo core perché un output verrebbe generato solo ogni 32° ciclo hash. Dato J, per calcolare un nonce per ciclo hash, almeno 32 istanze Blake2b256 eseguono dropMsb(H(j|| h|| M)) sono necessari. Come accennato in precedenza, questo aumenta significativamente le dimensioni e il costo dello stampo. È chiaro che la memorizzazione della lista R vale la pena perché avere 32, o anche 16, core è molto costoso. Più precisamente, la lettura della memoria è più veloce rispetto al calcolo delle istanze Blake ogni volta che viene testato un nonce.

Vediamo se un ASIC con memoria sufficiente è competitivo perché è più rilevante per la discussione. Confrontando Ethash e Autolykos, la differenza è che Ethash coinvolge N elementi quando l’hashing del nonce e dell’intestazione si mescola 64 volte, mentre Autolykos coinvolge N elementi quando recupera valori di 32 r in base agli indici generati. Per ogni nonce testato, Autolykos esegue circa 4 istanze Blake2b256 e 32 recuperi di memoria mentre Ethash esegue circa 65 istanze SHA-3 like e 64 recuperi di memoria. Per non parlare, k è attualmente impostato su 32 ma questo valore può essere aumentato per recuperare più valori r, se necessario. Gli ASIC che eseguono Ethash hanno molto spazio per aumentare la velocità di hashing SHA3 poiché vengono completati 65 hash per nonce testato rispetto a circa 4 su Autolykos. Il rapporto tra recuperi di memoria e istanze hash è molto maggiore su Autolykos. Per questo motivo, Autolykos è più difficile dalla memoria di Ethash poiché la larghezza di banda della memoria gioca un ruolo molto più importante rispetto alla velocità di hashing.

Un’area in cui l’ottimizzazione di Autolykos potrebbe avvenire è la compilazione della lista R. Il riempimento dell’elenco R richiede N istanze di una funzione Blake2b256. N è grande e sta solo diventando più grande, quindi è un sacco di hashing. Un ASIC potrebbe ottimizzare la velocità di Blake2b256, producendo più tempo per il block mining poiché l’elenco R viene riempito prima. Anche se questo può essere fatto, riempire l’elenco R richiede il ciclo attraverso [0, N) e una GPU con multiprocessori a 32 larghezze può già riempire l’elenco R molto velocemente (in pochi secondi). Si avrebbe bisogno di un ASIC con molti core Blake per essere significativamente più veloce – di nuovo, molto costoso e probabilmente non utile poiché il collo di bottiglia potrebbe diventare la larghezza di banda di scrittura della memoria (ad esempio, scrivere l’elenco R su RAM piuttosto che la velocità di hashing).

L’ultima area che può essere ottimizzata per Autolykos è la velocità di lettura/scrittura della memoria. I minatori EThash ASIC hanno una velocità di lettura leggermente superiore rispetto alle GPU poiché la memoria ha un clock più alto senza l’effetto della limitazione della GPU. Tuttavia, questa differenza è piuttosto insignificante e si prevede che diventerà più insignificante con l’avanzare delle GPU. Questo perché l’hardware di memoria stesso è lo stesso: DRAM. Ci si potrebbe chiedere se un hardware di memoria più veloce potrebbe essere utilizzato in cui la velocità di lettura e scrittura della memoria è molto più veloce … SRAM, ad esempio, potrebbe essere un passo successivo immaginabile nella rottura degli algoritmi hard di memoria, tuttavia, SRAM non è una soluzione fattibile semplicemente perché è meno densa.

SRAM su FPGA[2]

La foto sopra è un FPGA con 8 chip di memoria sul davanti, e ce ne sono altri 8 sul retro. La memoria SRAM totale è di soli 576 MB. Il montaggio di una SRAM sufficiente su un die non funzionerà perché la SRAM dovrà essere posizionata più lontano dal nucleo in quanto è abbastanza densa da adattarsi a uno strato attorno al nucleo. Ciò può comportare ritardi di lettura / scrittura perché l’elettricità deve percorrere distanze più lunghe anche se l’hardware stesso è più veloce. Inoltre, per estrarre Ergo, il requisito di memoria aumenta all’aumentare di N, quindi non è possibile montare una SRAM sufficiente nel tempo. Pertanto, gli ASIC SRAM non valgono la pena di essere esplorati anche se si disponesse di abbastanza denaro da spendere per la SRAM stessa.

Blake2b256

Una delle principali differenze tra un algoritmo come Autolykos e altri è l’uso di Blake2b256. Non è una coincidenza. Blake fa molto affidamento sulle operazioni di aggiunta per l’hash mixing anziché sulle operazioni XOR. Un’operazione come XOR può essere eseguita bit per bit mentre l’aggiunta richiede bit di trasporto. Pertanto, Blake richiede più potenza e area core rispetto agli algoritmi SHA, ma è ancora sicuro e, di fatto, più veloce. Come accennato sul sito Web di Blake2, “BLAKE2 è veloce nel software perché sfrutta le funzionalità delle CPU moderne, vale a dire il parallelismo a livello di istruzione, le estensioni del set di istruzioni SIMD e i core multipli”. [3] Pertanto, mentre un ASIC può produrre istanze Blake più velocemente, la natura innata della funzione limita le ottimizzazioni richiedendo l’aggiunta e coinvolgendo le funzionalità presenti nelle CPU e nelle GPU.

Velocità blake2b rispetto ad altre funzioni hash

Conclusione

Autolykos è una grande innovazione che è una risposta necessaria per combattere l’ascesa delle macchine ASIC ottimizzate per PoW. Speriamo che questa serie in 2 parti ti abbia aiutato a capire Autolykos a un livello più tecnico e perché è più difficile da ricordare di Ethash. Mentre Ethereum passa a una rete PoS, ci sarà una grande comunità di minatori alla ricerca di un posto dove dirigere il loro potere di hashrate, ed Ergo dovrebbe essere un attore significativo nell’attrarre quei minatori.

Se ti è piaciuto questo articolo, l’autore ti invita a controllare più contenuti tramite il loro account Twitter, @TheMiningApple.

[1] Credito a Wolf9466#9466 su Discord
[2] http://www.ldatech.com/_images/imageGallery/SBM09P-3_front.jpg
[3] https://www.blake2.net/#:~:text=A%3A%20BLAKE2%20is%20fast%20in,of%20the%20designers%20of%20BLAKE2).

Fonte:

Ergo and The Autolykos Consensus Mechanism: Part II | Ergo Platform

Articoli Correlati

Risposte