Ergo e il Meccanismo di Consenso di Autolykos – Parte 1

Tempo di lettura stimato: 7 minuti

Quello che segue è un approfondimento tecnico del meccanismo di consenso di Ergo, Autolykos. Poiché si tratta di un argomento lungo e dettagliato, lo pubblicheremo in segmenti nelle prossime due settimane. Per la Parte I, l’autore inizia ad abbattere lo pseudocodice del block mining e ci guida attraverso la creazione della “lista R”.

Parte I

Autolykos, il meccanismo di consenso di Ergo, è uno dei pochi puzzle asimmetrici di memoria e prova di lavoro che è ancora resistente all’ASIC, garantendo così che la blockchain sia mantenuta il più decentralizzata possibile. Autolykos si basa sul documento Equihash[1] e sul problema del compleanno. Per riassumere, il minatore ha il compito di trovare k (= 32) da N elementi, in modo tale che l’hash della somma degli elementi sia inferiore al target. Il seguente pseudocodice spiega il processo di mining e questa analisi analizzerà ampiamente ogni riga poiché ci sono pochissime risorse online che spiegano Autolykos nella sua interezza.

Autolykos Block Mining Pseudocodice

Prima di discutere la procedura di block mining, l’algoritmo richiede innanzitutto un gruppo ciclico G molto grande di ordine primo q con generatore fisso g ed elemento identità e. Questo gruppo primo viene utilizzato per restituire interi in Z/qZ durante la funzione di hashing basata su Blake2b256.

Esempio di gruppo ciclico con generatore z, elemento identità 1, ordine 6[2]

Non ci concentreremo ampiamente sul gruppo ciclico in quanto copre solo un piccolo segmento dello schema PoW. Ora, affrontiamo Autolykos Block mining linea per riga.

Linea 1 – Ingresso h e m

Il PoW inizia con i due ingressi: l’altezza del blocco h e l’imminente hash dell’intestazione del blocco m. L’hash dell’intestazione del blocco è un hash dei componenti dell’intestazione del blocco, come l’hash dell’intestazione del blocco precedente, la radice del merkle, il nonce, ecc.

Linea 2 – Calcola lista R

In primo luogo, è importante notare la notazione H() nella riga 2. Questa notazione chiama la funzione di hashing Algorithm 3. L’algoritmo 3 è una funzione hash basata su Blake2b256 ed è utilizzata in autolykos. L’algoritmo 3 afferma che se l’hash Blake degli input è inferiore a 2256 (= 1664 = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000), quindi viene restituito hash.mod(q). In caso contrario, l’algoritmo 3 si ripete fino a raggiungere un hash numerico all’interno dell’intervallo valido. Per riferimento, si noti che q è l’ordine primo del gruppo G, gli output hash di Blake2b256 sono lunghi 256 bit, 64 cifre e l’algoritmo 3 restituirà sempre un hash numerico in Z / qZ.

Funzione hash basata su Blake2b256

Nella riga 2, il focus è la creazione della lista RL’elenco R contiene valori r che sono hash numerici a 31 byte creati da numeri interi in [0, N). i valori r sono generati da takeright(31,H(j|| h|| M)). Le variabili sono le seguenti:

  • j, intero in [0, N)
  • h, altezza blocco
  • M, 8kb di dati costanti – padding per rallentare il calcolo hash

La sezione takeRight(31,H(…)) significa che dato H(…), un output Blake2b256 a 32 byte, vengono restituiti i 31 byte a destra (cioè in little endian (mentre altri algoritmi hash sono bit endian)). In altre parole, il byte più significativo, il byte più a sinistra, viene eliminato. Di conseguenza, ogni valore r è il 31 byte meno significativo derivato dal 32 byte H(j|| h|| M)) uscita. Ad esempio, se j = 1, r1 = takeRight(31,H(1|| h|| M))L’elenco R è costituito da N elementi e può essere generato per ogni blocco incrementando j di 1 N-1 volte. Poiché H(…) restituisce hash.mod(q), possiamo affermare che l’elenco R è composto da r0, 1, 2, 3 … N-1 e lista R ⊂ Z/qZ. Come affermato nel white paper di Autolykos v2[3], “N elementi sono derivati dall’altezza e dalle costanti dei blocchi, a differenza di Autolykos v1, quindi i minatori possono ricalcolare facilmente i candidati ai blocchi ora (solo gli indici dipendono da loro).” In altre parole, j è sempre in [0,N), N è determinato da hM è sempre costante e h cambia ogni blocco, l’unica variabile di cui un minatore ha bisogno per calcolare la lista R è h.

L’elenco R è memorizzato nella RAM. In Autolykos, N = 226 (67.108.864 interi) viene utilizzato nell’implementazione per ogni blocco prima di 614400. Pertanto, il requisito di memoria per i blocchi prima del blocco 614400 è (226 * 31 byte =) 2,08 GB. N è aumentato per la prima volta sul blocco 614400. Post blocco 614400, ogni 51200 blocchi, N aumenta del 5%. In altre parole, il requisito di memoria di un minatore Ergo aumenta del 5% ogni ~ 71 giorni. Sul blocco 4198400 il valore di N diventa costante e uguale a 2.143.944.600[4]. Si noti che gli ultimi 2 valori elencati nella tabella devono essere 2.143.944.600 e non 2.147.387.550. Dopo il blocco 4198400, il requisito di archiviazione dell’elenco R sarà (31 byte * 2.143.944.600) = 66,46 GB.

N elementi basati sull’altezza

del blocco N elementi, Ethash vs. Autolykos

Autolykos è come Ethash nel senso che l’altezza del blocco determina N elementi da memorizzare nella RAM.

Con Autolykos, l’altezza del blocco determina N hash numerici a 31 byte da memorizzare. Con Ethash, l’altezza del blocco determina N 128B pagine DAG da memorizzare. Potresti chiederti, se un blocco Ergo si verifica ogni 2 minuti, come fanno i minatori Ergo a generare un set di dati da 2 GB + così rapidamente? I minatori di Ethereum rigenerano il DAG solo ogni 100 ore perché ci vuole così tanto tempo … Per un minatore Ergo, l’onere di calcolare la lista R è di N istanze dell’algoritmo 3; ricorda, ogni valore r viene calcolato come takeRight(31,H(j|| h|| M)). Tuttavia, una GPU può farlo molto rapidamente Le GPU generalmente hanno multiprocessori a 32 o 64 larghezze, il che significa che 32 o 64 istanze dell’algoritmo 3 possono essere eseguite contemporaneamente a seconda della GPU. Ad esempio, una GPU a 32 larghezze come la RTX570 può riempire l’elenco R in pochi secondi.

Per la Parte II, riprenderemo da qui e continueremo la spiegazione di Autolykos v2. Restate sintonizzati su questo blog e sui canali social di Ergo per gli aggiornamenti sulla Parte II di questa serie.

[1] https://www.researchgate.net/publication/316904748_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem
[2] https://en.wikipedia.org/wiki/Cyclic_group#/media/File:Cyclic_group.svg
[3] https://www.docdroid.net/mcoitvK/ergopow-pdf
[4] https://www.ergoforum.org/t/autolykos-v-2-details/480
[5] Credito a Wolf9466#9466 su Discord

Articoli Correlati

Risposte