Ergo i mechanizm konsensusu Autolykos: Część II

W zeszłym tygodniu wprowadziliśmy szczegółowe badanie mechanizmu konsensusu Autolykos w Ergo. W tym artykule kończymy drugą część tej dyskusji i zagłębiamy się w dalsze szczegóły. Przed przeczytaniem tego dokumentu zaleca się, aby czytelnicy zapoznali się z Częścią I.

Przypominamy, oto pseudokody dotyczące wydobywania bloków i funkcji haszującej.

Pseudokod wydobywania bloków Autolykos

Funkcja haszująca oparta na Blake2b256

Linie 3, 4 – rozpocznij pętlę while i zgadywanie

Po obliczeniu listy R, górnik tworzy zgadywanie nonce i wchodzi w pętlę, aby sprawdzić, czy nonce ostatecznie generuje wynik, który jest poniżej podanej wartości docelowej.

Linie 5, 6 – ziarno do generowania indeksów

Linia 5, i = takeRight(8, H(m||nonce)) mod N, produkuje liczbę całkowitą w [0,N). Wykorzystywany jest algorytm 3, ale z m i nonce jako wejściami. Gdy hasz H(m||nonce) jest zwracany, 8 najmniej znaczących bajtów jest zachowywanych, a następnie przekazywanych przez mod N. Na marginesie, najwyższa możliwa wartość całkowita z 8 bajtów to 2⁶⁴ – 1, a zakładając N = 2²⁶, hasz 8-bajtowy mod N spowoduje, że pierwsze kilka cyfr będzie zerami. Liczba zer w i maleje w miarę wzrostu N.

Linia 6 produkuje e, ziarno do generowania indeksów. Algorytm 3 jest wywoływany z wejściami i (wygenerowanym w linii 5), h i M. Następnie, najbardziej znaczący bajt hasza numerycznego jest usuwany, a pozostałe 31 bajtów jest zachowywanych jako wartość e. Należy również zauważyć, że wartość e może być pobrana z listy R zamiast być obliczaną, ponieważ e jest wartością r.

Linia 7 – generator indeksów

Indeks elementu J jest tworzony za pomocą Algorytmu 6 z wejściami e, m, i nonce. Funkcja genIndexes jest pseudolosowa i zwraca listę k (=32) liczb w [0,N).

funkcja genIndexes

Istnieje kilka dodatkowych kroków, które nie są pokazane w pseudokodzie, takich jak zamiana bajtów. Tworzenie i zastosowanie genIndexes można wyjaśnić za pomocą następującego przykładu:

GenIndexes(e||m||nonce)...

hash = Blake2b256(e||m||nonce) = [0xF963BAA1C0E8BF86, 0x317C0AFBA91C1F23, 0x56EC115FD3E46D89, 0x9817644ECA58EBFB]

hash64to32 = [0xC0E8BF86, 0xF963BAA1, 0xA91C1F23, 0x317C0AFB, 0xD3E46D89 0x56EC115F, 0xCA58EBFB, 0x9817644E]

extendedhash (tj. zamiana bajtów i konkatenacja 4 bajtów przez powtarzanie pierwszych 4 bajtów) = [0x86BFE8C0, 0xA1BA63F9, 0x231F1CA9, 0xFB0A7C31, 0x896DE4D3, 0x5F11EC56, 0xFBEB58CA, 0x4E641798, 0x86BFE8C0]

Poniższy kod w Pythonie pokazuje proces krojenia rozszerzonego hasza, zwracając k indeksów. W tym przykładzie zakładamy, że h < 614,400, więc N = 2²⁶ (67,108,864).

Krojenie i mod N[1]
for i in range(8):
idxs[i << 2] = r[i] % np.uint32(ItemCount)
idxs[(i << 2) + 1] = ((r[i] << np.uint32(8)) | (r[i + 1] >> np.uint32(24))) % np.uint32(ItemCount)
idxs[(i << 2) + 2] = ((r[i] << np.uint32(16)) | (r[i + 1] >> np.uint32(16))) % np.uint32(ItemCount)
idxs[(i << 2) + 3] = ((r[i] << np.uint32(24)) | (r[i + 1] >> np.uint32(8))) % np.uint32(ItemCount)

Głównym wnioskiem jest to, że krojenie zwraca k indeksów, które są pseudolosowymi wartościami pochodzącymi z ziarna, tj. e, m, i nonce.

return [0x2BFE8C0, 0x3E8C0A1, 0xC0A1BA, 0xA1BA63, 0x1BA63F9, 0x263F923, 0x3F9231F, 0x1231F1C, 0x31F1CA9, 0x31CA9FB, 0xA9FB0A, 0x1FB0A7C, 0x30A7C31, 0x27C3189, 0x31896D, 0x1896DE4, 0x16DE4D3, 0x1E4D35F, 0xD35F11, 0x35F11EC, 0x311EC56, 0x1EC56FB, 0x56FBEB, 0x2FBEB58, 0x3EB58CA, 0x358CA4E, 0xCA4E64, 0x24E6417, 0x2641798, 0x179886, 0x39886BF, 0x86BFE8]

Ten indeks można przetłumaczyć na wartości w systemie dziesiętnym, ponieważ odnosi się do liczb w [0, N). Na przykład, 0x2BFE8C0 = 46131392, 0x3E8C0A1 = 65585313, 0xC0A1BA = 12624314, i tak dalej. Górnik używa tych indeksów do pobrania k r wartości.

Funkcja genIndexes zapobiega optymalizacjom, ponieważ niezwykle trudno, praktycznie niemożliwe, jest znalezienie ziarna, tak aby genIndexes(seed) zwracało pożądane indeksy.

Linia 8 – suma elementów r podanych k

Używając indeksu wygenerowanego w linii 7, górnik pobiera odpowiadające k (=32) r wartości z listy R i sumuje te wartości. Może to brzmieć myląco, ale rozłóżmy to na czynniki.

Kontynuując powyższy przykład, górnik przechowuje następujące indeksy:

{0 | 46,131,392},
{1 | 65,585,313},
{2 | 12,624,314},
{3 | 10,599,011},
…
{31 | 8,830,952}

Biorąc pod uwagę powyższe indeksy, górnik pobiera następujące wartości r z listy R przechowywanej w pamięci.

{0 | 46,131,392} → dropMsb(H(46,131,392||h||M))
{1 | 65,585,313} → dropMsb(H(65,585,313||h||M))
{2 | 12,624,314} → dropMsb(H(12,624,314||h||M))
{3 | 10,599,011} → dropMsb(H(10,599,011||h||M))
…
{31 | 8,830,952} → dropMsb(H(8,830,952||h||M))

Zauważ, że Takeright(31) działający na 32-bajtowym haszu można również zapisać jako dropMsb – usuń najbardziej znaczący bajt.

Ponieważ górnik już przechowuje listę R w RAM, górnik nie musi obliczać k (= 32) funkcji Blake2b256 i zamiast tego przeszukuje wartości. To jest kluczowa cecha odporności na ASIC. ASIC z ograniczoną pamięcią musi obliczyć 32 iteracje Blake2b256, aby uzyskać wartości, które mogłyby być pobrane z pamięci, a pobieranie z pamięci zajmuje znacznie mniej czasu. Nie wspominając o tym, że ASIC z ograniczoną pamięcią wymagałby 32 instancji Blake2b256 fizycznie na chipie, aby osiągnąć jeden hasz na cykl, co wymagałoby większej powierzchni i wyższych kosztów. Łatwo udowodnić, że przechowywanie listy R w pamięci jest warte tej wymiany. Załóżmy, że GPU ma wskaźnik haszowania G = 100MH/s, _N = 2²⁶, k = 32, interwał blokowy t = 120 sekund, a elementy są przeszukiwane co 4 hasze. Lubię zakładać, że elementy są przeszukiwane co 4 hasze, ponieważ dla każdego zgadywania nonce wiele elementów, takich jak i, J, i H(f) wymaga instancji Algorytmu 3, tj. hasza blake2b. Możemy oszacować, że każda wartość r będzie używana średnio (G * k * t)/(N*4) = 1430.51 razy.

Gdy 32 r wartości są pobrane, są sumowane.

Linie 9, 10, 11, 12 – sprawdź, czy hasz sumy jest poniżej celu

Suma 32 r wartości jest haszowana za pomocą Algorytmu 3, a jeśli wynik jest poniżej celu b, PoW jest udane, m i nonce są zwracane do węzłów sieci, a górnik otrzymuje nagrodę w ERG. Jeśli suma hasza jest powyżej celu, Linie 4 – 11 są powtarzane z nowym nonce.

Jeśli dotarłeś tak daleko, gratulacje! Po przeczytaniu wszystkich tych informacji powinieneś mieć dobre zrozumienie Autolykos v2! Jeśli chciałbyś zobaczyć wizualną demonstrację Autolykos, zapraszam do zapoznania się z grafiką na końcu tego dokumentu. Jeśli chciałbyś wideo wyjaśniające, możesz je znaleźć tutaj.

Odporność na ASIC

Wiemy z Ethereum, że algorytmy „trudne pamięciowo” mogą być pokonane przez integrację pamięci w ASIC. Ergo jest inne, ale najpierw przypomnijmy sobie, dlaczego ASIC z ograniczoną pamięcią jest niekonkurencyjny i dlaczego górnik musi przechowywać listę R. Linia 8 wydobywania bloków Autolykos zniechęca maszyny z ograniczoną pamięcią. Jeśli górnik ASIC nie przechowuje listy R, potrzebuje wielu rdzeni, aby generować 31-bajtowe hasze numeryczne na bieżąco. 32 r wartości nie mogą być efektywnie obliczane za pomocą pojedynczej pętli rdzeniowej, ponieważ wynik byłby generowany tylko co 32 cykl haszowania. Biorąc pod uwagę J, aby obliczyć jeden nonce na cykl haszowania, potrzebne są co najmniej 32 instancje Blake2b256 działające na dropMsb(H(j||h||M)). Jak wspomniano powyżej, zwiększa to znacznie rozmiar die i koszty. Jasne jest, że przechowywanie listy R jest opłacalne, ponieważ posiadanie 32, a nawet 16 rdzeni jest bardzo kosztowne. Co więcej, odczyt pamięci jest szybszy niż obliczanie instancji Blake za każdym razem, gdy testowany jest nonce.

Zobaczmy, czy ASIC z wystarczającą pamięcią jest konkurencyjny, ponieważ to jest bardziej istotne dla dyskusji. Porównując Ethash i Autolykos, różnica polega na tym, że Ethash obejmuje N elementów podczas haszowania nonce i nagłówka 64 razy, podczas gdy Autolykos obejmuje N elementów podczas pobierania 32 r wartości na podstawie wygenerowanych indeksów. Dla każdego testowanego nonce, Autolykos uruchamia około 4 instancji Blake2b256 i 32 pobrania pamięci, podczas gdy Ethash uruchamia około 65 instancji SHA-3 i 64 pobrania pamięci. Nie wspominając o tym, że k jest obecnie ustawione na 32, ale ta wartość może być zwiększona, aby pobrać więcej r wartości, jeśli zajdzie taka potrzeba. ASIC, które uruchamiają Ethash, mają dużo miejsca na zwiększenie prędkości haszowania SHA3, ponieważ 65 haszy jest ukończonych na każdy testowany nonce w porównaniu do około 4 w Autolykos. Stosunek pobrań pamięci do instancji haszujących jest znacznie większy w Autolykos. Z tego powodu Autolykos jest bardziej trudny pamięciowo niż Ethash, ponieważ przepustowość pamięci odgrywa znacznie większą rolę w porównaniu do prędkości haszowania.

Obszar, w którym można by zoptymalizować Autolykos, to wypełnienie listy R. Wypełnienie listy R wymaga N instancji funkcji Blake2b256. N jest duże i tylko rośnie, więc to dużo haszowania. ASIC mógłby zoptymalizować prędkość Blake2b256, co dałoby więcej czasu na wydobywanie bloków, ponieważ lista R byłaby wypełniana szybciej. Chociaż można to zrobić, wypełnienie listy R wymaga cyklicznego przechodzenia przez [0, N) i GPU z 32 szerokimi multiprocesorami może już bardzo szybko wypełnić listę R (w ciągu kilku sekund). Potrzebny byłby ASIC z wieloma rdzeniami Blake, aby być znacznie szybszym – znowu, bardzo kosztownym, i prawdopodobnie nieopłacalnym, ponieważ wąskim gardłem mogłaby stać się przepustowość pamięci zapisu (tj. zapisywanie listy R do RAM zamiast prędkości haszowania).

Ostatnim obszarem, który można zoptymalizować dla Autolykos, jest prędkość odczytu/zapisu pamięci. Górnicy ASIC Ethash mają nieco szybszą prędkość odczytu w porównaniu do GPU, ponieważ pamięć jest taktowana wyżej bez efektu ograniczenia GPU. Jednak ta różnica jest dość nieistotna i oczekuje się, że stanie się jeszcze mniej istotna w miarę postępu GPU. Dzieje się tak, ponieważ sprzęt pamięciowy jest taki sam: DRAM. Można się zastanawiać, czy można by wykorzystać szybszy sprzęt pamięciowy, w którym prędkość odczytu i zapisu pamięci jest znacznie szybsza… SRAM, na przykład, mogłoby być wyobrażalnym następnym krokiem w łamaniu algorytmów trudnych pamięciowo, jednak SRAM nie jest wykonalnym rozwiązaniem, ponieważ jest mniej gęsty.

SRAM na FPGA[2]

Powyższe zdjęcie przedstawia FPGA z 8 układami pamięci z przodu, a z tyłu znajduje się kolejne 8. Całkowita pamięć SRAM wynosi tylko 576MB. Umieszczenie wystarczającej ilości SRAM na die nie zadziała, ponieważ SRAM będzie musiał być umieszczony dalej od rdzenia, ponieważ nie jest wystarczająco gęsty, aby zmieścić się w jednej warstwie wokół rdzenia. Może to prowadzić do opóźnień w odczycie/zapisie, ponieważ elektryczność musi podróżować na dłuższe odległości, nawet jeśli sam sprzęt jest szybszy. Dodatkowo, aby wydobywać Ergo, wymagania dotyczące pamięci rosną w miarę wzrostu N, więc umieszczenie wystarczającej ilości SRAM nie jest wykonalne w dłuższej perspektywie. Dlatego ASIC z SRAM nie są warte badania, nawet jeśli miałoby się wystarczająco dużo pieniędzy na sam SRAM.

Blake2b256

Jedną z głównych różnic między algorytmem takim jak Autolykos a innymi jest użycie Blake2b256. To nie jest przypadek. Blake w dużej mierze opiera się na operacjach dodawania do mieszania haszy zamiast operacji XOR. Operacja taka jak XOR może być wykonywana bit po bicie, podczas gdy dodawanie wymaga bitów przeniesienia. Dlatego Blake wymaga więcej mocy i powierzchni rdzenia w porównaniu do algorytmów SHA, ale jest nadal tak samo bezpieczny, a w rzeczywistości szybszy. Jak wspomniano na stronie Blake2, „BLAKE2 jest szybki w oprogramowaniu, ponieważ wykorzystuje cechy nowoczesnych procesorów, a mianowicie równoległość na poziomie instrukcji, rozszerzenia zestawu instrukcji SIMD i wiele rdzeni.”[3] Dlatego, podczas gdy ASIC może szybciej generować instancje Blake, wrodzona natura funkcji ogranicza optymalizacje, wymagając dodawania i angażując cechy występujące w procesorach oraz GPU.

Prędkość Blake2b w porównaniu do innych funkcji haszujących

Podsumowanie

Autolykos to wspaniała innowacja, która jest konieczną odpowiedzią na wzrost maszyn ASIC zoptymalizowanych pod kątem PoW. Mamy nadzieję, że ta dwuczęściowa seria pomogła Ci zrozumieć Autolykos na bardziej technicznym poziomie i dlaczego jest bardziej trudny pamięciowo niż Ethash. W miarę jak Ethereum przechodzi na sieć PoS, będzie duża społeczność górników szukających miejsca, aby skierować swoją moc haszowania, a Ergo powinno być znaczącym graczem w przyciąganiu tych górników.

Jeśli podobał Ci się ten artykuł, autor zaprasza do zapoznania się z innymi treściami za pośrednictwem swojego konta na Twitterze, @TheMiningApple.

[1] Kredyt dla Wolf9466#9466 na Discordzie
[2] http://www.ldatech.com/_images/imageGallery/SBM09P-3_front.jpg
[3] https://www.blake2.net/#:~:text=A%3A%20BLAKE2%20is%20fast%20in,of%20the%20designers%20of%20BLAKE2).