Ergo e il meccanismo di consenso di Autolykos: parte I

Explainers
Devs
Mining
Ergo Platform

28 agosto 2022

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
Screenshot 2022-06-01 at 23.41.49.png

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]
senza nome (1).png

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 2256 (= 1664 = 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
Screenshot 2022-06-02 at 03.17.18.png

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 = 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 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
senza nome (3).png
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

Share post

Loading...