Ergo e il meccanismo di consenso di Autolykos: parte I

Quello che segue è un'analisi tecnica approfondita 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 a scomporre lo pseudocodice di block mining e ci guida attraverso la creazione della "lista R".

Parte I

Autolykos, il meccanismo di consenso Ergo, è uno dei pochi enigmi asimmetrici con memoria dura, a prova di lavoro che è ancora resistente all'ASIC, assicurando così che la blockchain sia mantenuta il più decentralizzata possibile. Autolykos si basa sul documento Equihash[1] e sul cosiddetto problema del compleanno. Per riassumere, il minatore ha il compito di trovare k (=32) su 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 Pseudocode

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

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

Non ci concentreremo ampiamente sul gruppo ciclico poiché copre solo un piccolo segmento dello schema PoW. Ora, affrontiamo il mining di Autolykos Block linea per linea.

Linea 1 – Ingresso h e m

Il PoW inizia con i due input: l'altezza del blocco h e l'hash dell'intestazione del blocco in arrivo m. L'hash dell'intestazione del blocco è un hash dei componenti dell'intestazione del blocco, come l'hash dell'intestazione del blocco precedente, merkle root, nonce, ecc.

Riga 2 – Calcola lista R

In primo luogo, è importante notare la notazione H() nella riga 2. Questa notazione chiama la funzione di hashing Algoritmo 3. L'algoritmo 3 è una funzione hash basata su Blake2b256 ed è usata in Autolykos. L'algoritmo 3 afferma che se l'hash Blake degli input è inferiore a 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA00000000000000000), viene restituito hash.mod(q). In caso contrario, l'algoritmo 3 si ripete finché non raggiunge un hash numerico all'interno dell'intervallo valido. Per riferimento, si noti che q è l'ordine primo del gruppo G, gli output hash Blake2b256 sono lunghi 256 bit e 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 di list R. Lista 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 del blocco
• M, 8kb di dati costanti - riempimento per rallentare il calcolo dell'hash

La sezione takeRight(31,H(…)) significa che dato H(…), un output Blake2b256 a 32 byte, i 31 byte a destra (cioè in little endian (mentre altri algoritmi hash sono bit endian)) sono restituito. In altre parole, viene eliminato il byte più significativo, il byte più a sinistra. Di conseguenza, ogni valore r corrisponde ai 31 byte meno significativi derivati ​​dall'output H(j||h||M)) a 32 byte. Ad esempio, se j = 1, r1 = takeRight(31,H(1||h||M)).List 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 list R consiste di r0, 1, 2, 3 … N-1 e list R ⊂ Z/qZ. Come affermato nel whitepaper di Autolykos v2[3], "N elementi derivano dall'altezza e dalle costanti del blocco, a differenza di Autolykos v1, quindi i minatori possono ricalcolare facilmente i candidati al blocco ora (solo gli indici dipendono da essi)." In altre parole, j è sempre in [0,N), N è determinato da h, M è sempre costante e h cambia ogni blocco, l'unica variabile di cui un minatore ha bisogno per calcolare list R è h.

Lista R è memorizzato nella RAM. In Autolykos, N = 2²⁶ (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 nel blocco 614400. Post blocco 614400, ogni 51200 blocchi, N aumenta del 5%. In altre parole, il fabbisogno 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 di list 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 si verifica un blocco Ergo ogni 2 minuti, in che modo i minatori Ergo sono in grado di generare un set di dati di oltre 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 per calcolare list R è N istanze dell'algoritmo 3; ricorda, ogni r valore è calcolato come takeRight(31,H(j||h||M)). Tuttavia, una GPU può farlo molto rapidamente. Le GPU generalmente hanno multiprocessori da 32 o 64 larghezze, il che significa che è possibile eseguire 32 o 64 istanze dell'algoritmo 3 contemporaneamente a seconda della GPU. Ad esempio, una GPU da 32 pollici come l'RTX570 può riempire l'elenco R in pochi secondi.

Per la Parte II, riprenderemo da qui e continueremo la spiegazione di Autolykos v2. Resta sintonizzato sui canali dei social media 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] Ringraziamo Wolf9466#9466 su Discord