Ergo és az Autolykos Konszenzus Mechanizmus: I. rész

Az alábbiakban az Ergo konszenzus mechanizmusának, az Autolykosnak a részletes, technikai elemzése található. Mivel ez egy hosszú és részletes téma, a következő két hétben szakaszokban fogjuk közzétenni. Az I. részben a szerző elkezdi elemezni a blokk bányászatának álnézetét, és végigvezet minket az "R lista" létrehozásán.

I. rész

Az Autolykos, az Ergo konszenzus mechanizmusa, az egyik kevés aszimmetrikus memória-nehéz, munkaigényes rejtvény, amely még mindig ASIC ellenálló - így biztosítva, hogy a blokklánc a lehető legdecentralizáltabb maradjon. Az Autolykos az Equihash cikkre[1] és a születésnapi problémára épül. Összefoglalva, a bányásznak k (=32) elemet kell találnia N közül, úgy, hogy az elemek összegének hash-e kisebb legyen, mint a cél. Az alábbi álnézet magyarázza a bányászati folyamatot, és ez az elemzés részletesen lebontja az egyes sorokat, mivel nagyon kevés online forrás magyarázza el az Autolykost teljes egészében.

Autolykos Blokk Bányászati Álnézet

Mielőtt a blokk bányászati eljárásról beszélnénk, az algoritmus először egy nagyon nagy ciklikus csoportot G igényel, amelynek elsőrendű rendje q, fix generátor g és identitás elem e. Ezt az elsőrendű csoportot használják az egész számok Z/qZ visszaadására a Blake2b256 alapú hash funkció során.

Példa ciklikus csoportra z generátorral, identitás elem 1, rend 6[2]

Nem fogunk részletesen foglalkozni a ciklikus csoporttal, mivel ez csak a PoW séma egy kis szegmensét fedi le. Most nézzük meg az Autolykos Blokk bányászatot soronként.

1. sor – Bemenet h és m

A PoW a két bemenettel kezdődik: a blokk magassága h és a következő blokk fejléc hash-e m. A blokk fejléc hash-e a blokk fejléc összetevőinek hash-e, mint például az előző blokk fejléc hash-e, merkle gyökér, nonce stb.

2. sor – R lista kiszámítása

Először is fontos észrevenni a H() jelölést a 2. sorban. Ez a jelölés a hash funkciót, a 3. algoritmust hívja meg. A 3. algoritmus egy Blake2b256 alapú hash funkció, amelyet az Autolykos során használnak. A 3. algoritmus azt állítja, hogy ha a bemenetek Blake hash-e 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000) alatt van, akkor hash.mod(q) kerül visszaadásra. Ha nem, a 3. algoritmus megismétli, amíg el nem ér egy numerikus hash-t a érvényes tartományon belül. Hivatkozásként vegyük figyelembe, hogy q a G csoport elsőrendű rendje, a Blake2b256 hash kimenetek 256 bit hosszúak, 64 számjegyűek, és a 3. algoritmus mindig numerikus hash-t ad vissza Z/qZ-ben.

Blake2b256 Alapú Hash funkció

A 2. sorban a figyelem az R lista létrehozására összpontosít. Az R lista r értékeket tartalmaz, amelyek 31 bájtos numerikus hash-ek, amelyeket az [0, N) közötti egész számokból hoznak létre. Az r értékeket a takeRight(31,H(j||h||M)) generálja. A változók a következők:

• j, egész szám az [0, N) tartományban
• h, blokk magasság
• M, 8kb állandó adat - padding a hash számítás lelassítására

A takeRight(31,H(…)) szakasz azt jelenti, hogy a H(…), egy 32 bájtos Blake2b256 kimenet, a jobb oldali 31 bájt (azaz kis végű (míg más hash algoritmusok bit végűek)) kerül visszaadásra. Más szavakkal, a legjelentősebb bájt, a bal szélen lévő bájt, eldobásra kerül. Ennek eredményeként minden r érték a 32 bájtos H(j||h||M)) kimenetből származó 31 legkevésbé jelentős bájtot tartalmazza. Például, ha j = 1, akkor r1 = takeRight(31,H(1||h||M)). Az R lista N elemet tartalmaz, és minden blokkhoz generálható, ha j-t 1 N-1 alkalommal növeljük. Mivel a H(…) visszaadja a hash.mod(q), kijelenthetjük, hogy az R lista r0, 1, 2, 3 … N-1 elemekből áll, és R lista ⊂ Z/qZ. Ahogy az Autolykos v2 fehér könyvében[3] is szerepel, “N elemek a blokk magasságból és állandókból származnak, ellentétben az Autolykos v1-el, így a bányászok most könnyen újraszámolhatják a blokk jelölteket (csak az indexek függenek tőlük).” Más szavakkal, j mindig az [0,N) tartományban van, N a h-től függ, M mindig állandó, és h minden blokkban változik, az egyetlen változó, amelyet a bányásznak a R lista kiszámításához figyelembe kell vennie, az h.

Az R lista a RAM-ban tárolódik. Az Autolykosban N = 2²⁶ (67,108,864 egész szám) kerül felhasználásra a 614400 blokk előtti megvalósítás során. Így a memóriaigény a 614400 blokk előtti blokkokra (226 * 31 bájt =) 2.08GB. Az N először a 614400 blokkban nőtt. A 614400 blokk után, minden 51200 blokkban, N 5%-kal nő. Más szavakkal, az Ergo bányász memóriaigénye körülbelül 5%-kal nő 71 naponta. A 4198400 blokkban az N értéke állandóvá válik és 2,143,944,600-ra[4] egyenlő. Vegye figyelembe, hogy a táblázatban felsorolt utolsó 2 értéknek 2,143,944,600-nak kell lennie, és nem 2,147,387,550-nek. A 4198400 blokk után az R lista tárolási igénye (31 bájt * 2,143,944,600) = 66.46GB.

N elemek a blokk magasság alapján

N elemek, Ethash vs. Autolykos

Az Autolykos hasonló az Ethash-hoz abban az értelemben, hogy a blokk magassága határozza meg az N elemeket, amelyeket a RAM-ban kell tárolni. Az Autolykos esetében a blokk magassága határozza meg az N 31 bájtos numerikus hash-t, amelyet tárolni kell. Az Ethash esetében a blokk magassága határozza meg az N 128B DAG oldalt, amelyet tárolni kell. Talán megkérdezi magától, ha egy Ergo blokk 2 percenként történik, hogyan tudnak az Ergo bányászok ilyen gyorsan generálni egy 2GB+ adathalmazt? Az Ethereum bányászok csak 100 óránként regenerálják a DAG-ot, mert ez olyan sokáig tart... Egy Ergo bányász számára a R lista kiszámításának terhe N példányai a 3. algoritmusnak; ne feledje, hogy minden r érték a takeRight(31,H(j||h||M)) alapján kerül kiszámításra. Azonban egy GPU ezt nagyon gyorsan meg tudja tenni, a GPU-k általában 32 széles vagy 64 széles multiprocesszorokkal rendelkeznek, ami azt jelenti, hogy 32 vagy 64 3. algoritmus példány végezhető el párhuzamosan a GPU-tól függően. Például egy 32 széles GPU, mint az RTX570, néhány másodperc alatt ki tudja tölteni az R listát.

A II. részhez innen folytatjuk, és tovább folytatjuk az Autolykos v2 magyarázatát. Kövesse az Ergo közösségi média csatornáit a II. rész frissítéseiért.

[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] Köszönet Wolf9466#9466-nak a Discordon