Ergo a konsenzusný mechanizmus Autolykos: Časť I

Nasleduje podrobný technický rozbor konsenzusného mechanizmu Ergo, Autolykos. Keďže ide o rozsiahlu a podrobnú tému, zverejníme ju v segmentoch počas nasledujúcich dvoch týždňov. V Časti I autor začína rozoberať pseudokód ťažby blokov a vedie nás cez vytvorenie „zoznamu R.“

Časť I

Autolykos, konsenzusný mechanizmus Ergo, je jedným z mála asymetrických pamäťovo náročných, proof of work hádaniek, ktoré sú stále odolné voči ASIC - čím sa zabezpečuje, že blockchain zostáva čo najviac decentralizovaný. Autolykos je založený na dokumente Equihash[1] a probléme narodenín. Aby sme to zhrnuli, ťažiar má za úlohu nájsť k (=32) z N prvkov, tak, aby hash súčtu prvkov bol menší ako cieľ. Nasledujúci pseudokód vysvetľuje proces ťažby a táto analýza podrobne rozoberie každý riadok, pretože existuje veľmi málo online zdrojov, ktoré vysvetľujú Autolykos v jeho celistvosti.

Pseudokód ťažby blokov Autolykos

Predtým, ako sa budeme zaoberať procedúrou ťažby blokov, algoritmus najprv vyžaduje veľmi veľkú cyklickú skupinu G s prvočíselným poradím q s pevným generátorom g a identitným prvkom e. Táto prvočíselná skupina sa používa na vracanie celých čísel v Z/qZ počas hashovacej funkcie založenej na Blake2b256.

Príklad cyklickej skupiny s generátorom z, identitným prvkom 1, poradím 6[2]

Nebudeme sa podrobne zaoberať cyklickou skupinou, pretože pokrýva len malý segment schémy PoW. Teraz sa pozrime na ťažbu blokov Autolykos riadok po riadku.

Riadok 1 – Vstup h a m

PoW začína s dvoma vstupmi: výškou bloku h a nadchádzajúcim hashom hlavičky bloku m. Hash hlavičky bloku je hash komponentov hlavičky bloku, ako je hash predchádzajúcej hlavičky bloku, merkle root, nonce atď.

Riadok 2 – Vypočítaj zoznam R

Najprv je dôležité si všimnúť notáciu H() v riadku 2. Táto notácia volá hashovaciu funkciu Algoritmus 3. Algoritmus 3 je hashovacia funkcia založená na Blake2b256 a používa sa počas celého Autolykosu. Algoritmus 3 uvádza, že ak je Blake hash vstupov pod 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000), potom sa vráti hash.mod(q). Ak nie, Algoritmus 3 sa opakuje, kým nedosiahne číselný hash v platnom rozsahu. Pre referenciu, poznamenajte, že q je prvočíselné poradie skupiny G, výstupy hashovacej funkcie Blake2b256 sú 256 bitov, 64 číslic dlhé a Algoritmus 3 vždy vráti číselný hash v Z/qZ.

Hashovacia funkcia založená na Blake2b256

V riadku 2 je zameranie na vytvorenie zoznamu R. Zoznam R obsahuje r hodnoty, ktoré sú 31-bajtové číselné hashe vytvorené z celých čísel v [0, N). r hodnoty sú generované takeright(31,H(j||h||M)). Premenné sú nasledovné:

• j, celé číslo v [0, N)
• h, výška bloku
• M, 8kb konštantných údajov - padding na spomalenie výpočtu hashu

Sekcia takeRight(31,H(…)) znamená, že vzhľadom na H(…), 32-bajtový výstup Blake2b256, sa vracia 31 bajtov vpravo (t.j. v little endian (kde iné hashovacie algoritmy sú bit endian)). Inými slovami, najvýznamnejší bajt, bajt najďalej vľavo, je odstránený. V dôsledku toho je každá r hodnota 31 najmenej významných bajtov odvodených z 32-bajtového H(j||h||M)) výstupu. Napríklad, ak j = 1, r1 = takeRight(31,H(1||h||M)).Zoznam R pozostáva z N prvkov a môže byť generovaný pre každý blok inkrementovaním j o 1 N-1 krát. Keďže H(…) vracia hash.mod(q), môžeme uviesť, že zoznam R pozostáva z r0, 1, 2, 3 … N-1 a zoznam R ⊂ Z/qZ. Ako je uvedené v bielej knihe Autolykos v2[3], „N prvky sú odvodené z výšky bloku a konštánt, na rozdiel od Autolykos v1, takže ťažiarom sa teraz ľahko prepočítavajú kandidáti na blok (iba indexy závisia od nich).“ Inými slovami, j je vždy v [0,N), N je určené h, M je vždy konštantné a h sa mení s každým blokom, jediná premenná, ktorú ťažiar potrebuje na výpočet zoznamu R, je h.

Zoznam R je uložený v RAM. V Autolykos, N = 2²⁶ (67,108,864 celých čísel) sa používa v implementácii pre každý blok pred 614400. Takže, požiadavka na pamäť pre bloky pred blokom 614400 je (226 * 31 bajtov =) 2.08GB. N prvýkrát vzrástol na bloku 614400. Po bloku 614400, každých 51200 blokov, N vzrastie o 5%. Inými slovami, požiadavka na pamäť ťažiarov Ergo sa zvyšuje o 5% každých ~71 dní. Na bloku 4198400 sa hodnota N stáva konštantnou a rovná sa 2,143,944,600[4]. Poznamenajte, že posledné 2 hodnoty uvedené v tabuľke by mali byť 2,143,944,600 a nie 2,147,387,550. Po bloku 4198400 bude požiadavka na úložisko zoznamu R (31 bajtov * 2,143,944,600) = 66.46GB.

N prvky založené na výške bloku

N prvky, Ethash vs. Autolykos

Autolykos je ako Ethash v tom zmysle, že výška bloku určuje N prvky, ktoré sa majú uložiť v RAM. S Autolykos, výška bloku určuje N 31-bajtových číselných hashov, ktoré sa majú uložiť. S Ethash, výška bloku určuje N 128B DAG strán, ktoré sa majú uložiť. Môžete sa pýtať, ak sa blok Ergo vyskytuje každé 2 minúty, ako sú ťažiarom Ergo schopní tak rýchlo generovať dataset s veľkosťou 2GB+? Ťažiari Ethereum regenerujú DAG iba každých 100 hodín, pretože to trvá tak dlho… Pre ťažiarov Ergo je záťaž na výpočet zoznamu R N inštancií Algoritmu 3; pamätajte, že každá r hodnota sa počíta ako takeRight(31,H(j||h||M)). Avšak, GPU to môže robiť veľmi rýchlo, GPU zvyčajne majú 32-široké alebo 64-široké multiprocesory, čo znamená, že 32 alebo 64 inštancií Algoritmu 3 môže byť vykonaných súčasne v závislosti od GPU. Napríklad, 32-široké GPU ako RTX570 môže naplniť zoznam R len za niekoľko sekúnd.

Pre Časť II, tu pokračujeme a pokračujeme vo vysvetlení Autolykos v2. Sledujte Ergo sociálne médiá pre aktualizácie o Časti II tejto série.

[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] Kredit Wolf9466#9466 na Discorde