Ergo und der Autolykos-Konsensmechanismus: Teil I

Im Folgenden finden Sie eine detaillierte technische Analyse des Konsensmechanismus von Ergo, Autolykos. Da dies ein langwieriges und detailliertes Thema ist, werden wir es in Segmenten über die nächsten zwei Wochen veröffentlichen. Für Teil I beginnt der Autor mit der Analyse des Pseudocodes für das Block-Mining und führt uns durch die Erstellung von "Liste R."

Teil I

Autolykos, der Konsensmechanismus von Ergo, ist eines der wenigen asymmetrischen speicherharten Proof-of-Work-Puzzles, das weiterhin ASIC-resistent ist - und somit sicherstellt, dass die Blockchain so dezentralisiert wie möglich bleibt. Autolykos basiert auf dem Equihash-Papier[1] und dem Geburtstagsproblem. Zusammenfassend hat der Miner die Aufgabe, k (=32) aus N Elementen zu finden, sodass der Hash der Summe der Elemente kleiner als das Ziel ist. Der folgende Pseudocode erklärt den Mining-Prozess, und diese Analyse wird jede Zeile ausführlich aufschlüsseln, da es nur sehr wenige Online-Ressourcen gibt, die Autolykos in seiner Gesamtheit erklären.

Autolykos Block Mining Pseudocode

Bevor wir das Verfahren zum Block-Mining besprechen, benötigt der Algorithmus zunächst eine sehr große zyklische Gruppe G mit primärer Ordnung q und festem Generator g sowie dem Identitätselement e. Diese primäre Gruppe wird verwendet, um ganze Zahlen in Z/qZ während der auf Blake2b256 basierenden Hash-Funktion zurückzugeben.

Beispiel für eine zyklische Gruppe mit Generator z, Identitätselement 1, Ordnung 6[2]

Wir werden uns nicht ausführlich mit der zyklischen Gruppe befassen, da sie nur einen kleinen Teil des PoW-Schemas abdeckt. Lassen Sie uns nun das Autolykos-Block-Mining Zeile für Zeile angehen.

Zeile 1 – Eingabe h und m

Das PoW beginnt mit den beiden Eingaben: der Blockhöhe h und dem bevorstehenden Block-Header-Hash m. Der Block-Header-Hash ist ein Hash der Komponenten des Block-Headers, wie dem Hash des vorherigen Block-Headers, dem Merkle-Wurzel, dem Nonce usw.

Zeile 2 – Berechnung der Liste R

Zunächst ist es wichtig, die H()-Notation in Zeile 2 zu beachten. Diese Notation ruft die Hash-Funktion Algorithmus 3 auf. Algorithmus 3 ist eine Hash-Funktion, die auf Blake2b256 basiert und während des gesamten Autolykos verwendet wird. Algorithmus 3 besagt, dass, wenn der Blake-Hash der Eingaben unter 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000) liegt, dann hash.mod(q) zurückgegeben wird. Andernfalls wiederholt Algorithmus 3, bis er einen numerischen Hash im gültigen Bereich erreicht. Zur Referenz: Beachten Sie, dass q die primäre Ordnung der Gruppe G ist, die Ausgaben des Blake2b256-Hashes 256 Bit, 64 Ziffern lang sind und Algorithmus 3 immer einen numerischen Hash in Z/qZ zurückgibt.

Blake2b256 basierte Hash-Funktion

In Zeile 2 liegt der Fokus auf der Erstellung von Liste R. Liste R enthält r Werte, die 31-Byte numerische Hashes sind, die aus ganzen Zahlen in [0, N) erstellt werden. r Werte werden durch takeRight(31,H(j||h||M)) generiert. Die Variablen sind wie folgt:

• j, ganze Zahl in [0, N)
• h, Blockhöhe
• M, 8kb konstante Daten - Padding, um die Hash-Berechnung zu verlangsamen

Der Abschnitt takeRight(31,H(…)) bedeutet, dass gegeben H(…), eine 32-Byte Blake2b256-Ausgabe, die 31 Bytes rechts (d.h. in little endian (während andere Hash-Algorithmen bit endian sind)) zurückgegeben werden. Mit anderen Worten, das bedeutendste Byte, das Byte ganz links, wird verworfen. Infolgedessen ist jeder r Wert die 31 am wenigsten signifikanten Bytes, die aus der 32-Byte H(j||h||M)) Ausgabe abgeleitet sind. Zum Beispiel, wenn j = 1, dann r1 = takeRight(31,H(1||h||M)). Liste R besteht aus N Elementen und kann für jeden Block generiert werden, indem j N-1 Mal um 1 erhöht wird. Da H(…) hash.mod(q) zurückgibt, können wir feststellen, dass Liste R aus r0, 1, 2, 3 … N-1 besteht und Liste R ⊂ Z/qZ. Wie im Autolykos v2-Whitepaper[3] angegeben, „N Elemente stammen von der Blockhöhe und Konstanten, im Gegensatz zu Autolykos v1, sodass Miner Blockkandidaten jetzt leicht neu berechnen können (nur Indizes hängen von ihnen ab).“ Mit anderen Worten, j ist immer in [0,N), N wird durch h bestimmt, M ist immer konstant, und h ändert sich mit jedem Block, die einzige Variable, die ein Miner benötigt, um Liste R zu berechnen, ist h.

Liste R wird im RAM gespeichert. In Autolykos wird N = 2²⁶ (67.108.864 ganze Zahlen) in der Implementierung für jeden Block vor 614400 verwendet. Daher beträgt der Speicherbedarf für Blöcke vor Block 614400 (226 * 31 Bytes =) 2,08 GB. N wurde erstmals bei Block 614400 erhöht. Nach Block 614400 erhöht sich N alle 51200 Blöcke um 5 %. Mit anderen Worten, der Speicherbedarf eines Ergo-Miners steigt alle ~71 Tage um 5 %. Bei Block 4198400 wird der Wert von N konstant und gleich 2.143.944.600[4]. Beachten Sie, dass die letzten 2 Werte in der Tabelle 2.143.944.600 und nicht 2.147.387.550 sein sollten. Nach Block 4198400 beträgt der Speicherbedarf von Liste R (31 Bytes * 2.143.944.600) = 66,46 GB.

N-Elemente basierend auf der Blockhöhe

N-Elemente, Ethash vs. Autolykos

Autolykos ist wie Ethash in dem Sinne, dass die Blockhöhe die N Elemente bestimmt, die im RAM gespeichert werden. Bei Autolykos bestimmt die Blockhöhe die N 31-Byte numerischen Hashes, die gespeichert werden. Bei Ethash bestimmt die Blockhöhe die N 128B DAG-Seiten, die gespeichert werden. Sie fragen sich vielleicht, wenn alle 2 Minuten ein Ergo-Block auftritt, wie Ergo-Miner so schnell ein Dataset von über 2 GB generieren können? Ethereum-Miner regenerieren das DAG nur alle 100 Stunden, weil es so lange dauert… Für einen Ergo-Miner besteht die Belastung, Liste R zu berechnen, aus N Instanzen von Algorithmus 3; denken Sie daran, dass jeder r-Wert als takeRight(31,H(j||h||M)) berechnet wird. Ein GPU kann dies jedoch sehr schnell tun, da GPUs im Allgemeinen 32- oder 64-breit sind, was bedeutet, dass 32 oder 64 Instanzen von Algorithmus 3 gleichzeitig ausgeführt werden können, je nach GPU. Zum Beispiel kann eine 32-breite GPU wie die RTX570 Liste R in nur wenigen Sekunden füllen.

Für Teil II werden wir hier weitermachen und die Erklärung von Autolykos v2 fortsetzen. Bleiben Sie dran für Updates zu Teil II dieser Serie auf Ergos sozialen Medien.

[1] https://www.researchgate.net/publication/316904748_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem
[2] https://de.wikipedia.org/wiki/Zyklische_Gruppe#/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] Kredit an Wolf9466#9466 auf Discord