Ergo i mechanizm konsensusu Autolykos: Część I

Poniżej znajduje się szczegółowe, techniczne omówienie mechanizmu konsensusu Ergo, Autolykos. Ponieważ jest to obszerny i szczegółowy temat, opublikujemy go w segmentach w ciągu najbliższych dwóch tygodni. W Części I autor zaczyna analizować pseudokod wydobywania bloków i prowadzi nas przez tworzenie „listy R.”.

Część I

Autolykos, mechanizm konsensusu Ergo, jest jednym z nielicznych asymetrycznych, pamięciochłonnych zagadek proof of work, które są nadal odporne na ASIC - co zapewnia, że blockchain pozostaje jak najbardziej zdecentralizowany. Autolykos opiera się na pracy Equihash[1] oraz problemie urodzin. Podsumowując, górnik ma za zadanie znaleźć k (=32) z N elementów, tak aby hash sumy elementów był mniejszy niż cel. Poniższy pseudokod wyjaśnia proces wydobywania, a ta analiza szczegółowo omówi każdą linię, ponieważ istnieje bardzo mało zasobów online, które wyjaśniają Autolykos w całości.

Pseudokod wydobywania bloków Autolykos

Zanim omówimy procedurę wydobywania bloków, algorytm najpierw wymaga bardzo dużej grupy cyklicznej G o pierwszym porządku q z ustalonym generatorem g i elementem tożsamości e. Ta grupa pierwsza jest używana do zwracania liczb całkowitych w Z/qZ podczas funkcji haszującej opartej na Blake2b256.

Przykładowa grupa cykliczna z generatorem z, elementem tożsamości 1, porządkiem 6[2]

Nie będziemy się szczegółowo skupiać na grupie cyklicznej, ponieważ obejmuje ona tylko mały segment schematu PoW. Teraz zajmijmy się wydobywaniem bloków Autolykos linia po linii.

Linia 1 – Wejście h i m

PoW zaczyna się od dwóch wejść: wysokości bloku h i nadchodzącego hasha nagłówka bloku m. Hash nagłówka bloku to hash komponentów nagłówka bloku, takich jak hash poprzedniego nagłówka bloku, korzeń merkle'a, nonce itp.

Linia 2 – Oblicz listę R

Po pierwsze, ważne jest, aby zauważyć notację H() w linii 2. Ta notacja wywołuje funkcję haszującą Algorytm 3. Algorytm 3 to funkcja haszująca oparta na Blake2b256 i jest używana w całym Autolykos. Algorytm 3 stwierdza, że jeśli hash Blake'a wejść jest poniżej 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000), to zwracany jest hash.mod(q). W przeciwnym razie Algorytm 3 powtarza się, aż osiągnie numeryczny hash w dozwolonym zakresie. Dla odniesienia, zauważ, że q jest pierwszym porządkiem grupy G, wyjścia hasha Blake2b256 mają 256 bitów, 64 cyfry długości, a Algorytm 3 zawsze zwraca numeryczny hash w Z/qZ.

Funkcja haszująca oparta na Blake2b256

W linii 2 skupiamy się na tworzeniu listy R. Lista R zawiera r wartości, które są 31-bajtowymi numerycznymi hashami utworzonymi z liczb całkowitych w [0, N). Wartości r są generowane przez takeright(31,H(j||h||M)). Zmienne są następujące:

• j, liczba całkowita w [0, N)
• h, wysokość bloku
• M, 8kb stałych danych - padding, aby spowolnić obliczenia hasha

Sekcja takeRight(31,H(…)) oznacza, że biorąc H(…), 32-bajtowe wyjście Blake2b256, zwracane są 31 bajty po prawej stronie (tj. w małym porządku bajtów (gdzie inne algorytmy haszujące są w porządku bajtów dużych)). Innymi słowy, najbardziej znaczący bajt, bajt najdalej po lewej, jest pomijany. W rezultacie każda wartość r to 31 najmniej znaczących bajtów pochodzących z 32-bajtowego H(j||h||M)). Na przykład, jeśli j = 1, r1 = takeRight(31,H(1||h||M)). Lista R składa się z N elementów i może być generowana dla każdego bloku przez inkrementację j o 1 N-1 razy. Ponieważ H(…) zwraca hash.mod(q), możemy stwierdzić, że lista R składa się z r0, 1, 2, 3 … N-1 i lista R ⊂ Z/qZ. Jak stwierdzono w białej księdze Autolykos v2[3], „N elementy są pochodnymi wysokości bloku i stałych, w przeciwieństwie do Autolykos v1, więc górnicy mogą teraz łatwo przeliczać kandydatów na bloki (tylko indeksy zależą od nich).” Innymi słowy, j jest zawsze w [0,N), N jest określone przez h, M jest zawsze stałe, a h zmienia się z każdym blokiem, jedyną zmienną, którą górnik musi obliczyć listę R, jest h.

Lista R jest przechowywana w RAM. W Autolykos, N = 2²⁶ (67,108,864 liczby całkowite) jest używane w implementacji dla każdego bloku przed 614400. Zatem wymagania pamięciowe dla bloków przed blokiem 614400 wynoszą (226 * 31 bajtów =) 2.08GB. N po raz pierwszy wzrosło w bloku 614400. Po bloku 614400, co 51200 bloków, N wzrasta o 5%. Innymi słowy, wymagania pamięciowe górnika Ergo wzrastają o 5% co ~71 dni. W bloku 4198400 wartość N staje się stała i równa 2,143,944,600[4]. Zauważ, że ostatnie 2 wartości wymienione w tabeli powinny wynosić 2,143,944,600, a nie 2,147,387,550. Po bloku 4198400, wymagania dotyczące przechowywania listy R będą wynosić (31 bajtów * 2,143,944,600) = 66.46GB.

N elementów opartych na wysokości bloku

N elementów, Ethash vs. Autolykos

Autolykos jest podobny do Ethash w tym sensie, że wysokość bloku określa N elementów do przechowywania w RAM. W przypadku Autolykos wysokość bloku określa N 31-bajtowych numerycznych hashy do przechowywania. W przypadku Ethash wysokość bloku określa N 128B stron DAG do przechowywania. Możesz zapytać, jeśli blok Ergo występuje co 2 minuty, jak górnicy Ergo są w stanie tak szybko wygenerować zestaw danych o wielkości 2GB+? Górnicy Ethereum regenerują DAG tylko co 100 godzin, ponieważ to zajmuje tak długo… Dla górnika Ergo obciążenie obliczania listy R to N instancji Algorytmu 3; pamiętaj, że każda wartość r jest obliczana jako takeRight(31,H(j||h||M)). Jednak GPU mogą to robić bardzo szybko, GPU zazwyczaj mają 32-szerokie lub 64-szerokie multiprocesory, co oznacza, że 32 lub 64 instancji Algorytmu 3 mogą być wykonywane jednocześnie, w zależności od GPU. Na przykład, GPU o szerokości 32, takie jak RTX570, może wypełnić listę R w zaledwie kilka sekund.

W Części II przejdziemy stąd i kontynuujemy wyjaśnienie Autolykos v2. Śledź kanały mediów społecznościowych Ergo, aby uzyskać aktualizacje na temat Części II tej serii.

[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] Kredyt dla Wolf9466#9466 na Discordzie