Przejdź do głównej treści
Change page

Dagger-Hashimoto

Dagger-Hashimoto był oryginalną badawczą implementacją i specyfikacją algorytmu kopania Ethereum. Dagger-Hashimoto został zastąpiony przez Ethash. Kopanie zostało całkowicie wyłączone podczas The Merge 15 września 2022 roku. Od tego czasu Ethereum jest zabezpieczane za pomocą mechanizmu dowodu stawki (PoS). Ta strona ma charakter historyczny – zawarte tu informacje nie są już aktualne dla Ethereum po The Merge.

Wymagania wstępne

Aby lepiej zrozumieć tę stronę, zalecamy najpierw zapoznać się z konsensusem dowodu pracy (PoW), kopaniem oraz algorytmami kopania.

Dagger-Hashimoto

Dagger-Hashimoto ma na celu osiągnięcie dwóch celów:

  1. Odporność na ASIC: korzyści z tworzenia specjalistycznego sprzętu dla tego algorytmu powinny być jak najmniejsze.
  2. Weryfikowalność przez lekkiego klienta: blok powinien być łatwy do wydajnej weryfikacji przez lekkiego klienta.

Dzięki dodatkowej modyfikacji określamy również, jak w razie potrzeby spełnić trzeci cel, jednak kosztem dodatkowej złożoności:

Przechowywanie pełnego łańcucha: kopanie powinno wymagać przechowywania kompletnego stanu blockchaina (ze względu na nieregularną strukturę drzewa stanu Ethereum przewidujemy, że możliwe będzie pewne przycinanie, w szczególności niektórych często używanych kontraktów, ale chcemy to zminimalizować).

Generowanie DAG

Kod algorytmu zostanie zdefiniowany w języku Python poniżej. Najpierw podajemy encode_int do przekształcania liczb całkowitych bez znaku o określonej precyzji na ciągi znaków. Podano również jego odwrotność:

Następnie zakładamy, że sha3 jest funkcją, która przyjmuje liczbę całkowitą i zwraca liczbę całkowitą, a dbl_sha3 jest funkcją podwójnego SHA-3; w przypadku konwersji tego kodu referencyjnego na implementację należy użyć:

Parametry

Parametry używane w algorytmie to:

P w tym przypadku jest liczbą pierwszą wybraną tak, aby log₂(P) było tylko nieznacznie mniejsze niż 512, co odpowiada 512 bitom, których używaliśmy do reprezentowania naszych liczb. Należy zauważyć, że w rzeczywistości musi być przechowywana tylko druga połowa DAG, więc faktyczne zapotrzebowanie na pamięć RAM zaczyna się od 1 GB i rośnie o 441 MB rocznie.

Budowanie grafu Dagger

Prymityw budowania grafu Dagger jest zdefiniowany następująco:

Zasadniczo rozpoczyna on graf jako pojedynczy węzeł, sha3(seed), a stamtąd zaczyna sekwencyjnie dodawać inne węzły na podstawie losowych poprzednich węzłów. Kiedy tworzony jest nowy węzeł, obliczana jest potęga modularna ziarna (seed), aby losowo wybrać pewne indeksy mniejsze niż i (używając x % i powyżej), a wartości węzłów pod tymi indeksami są używane w obliczeniach do wygenerowania nowej wartości dla x, która jest następnie wprowadzana do małej funkcji dowodu pracy (opartej na XOR), aby ostatecznie wygenerować wartość grafu pod indeksem i. Uzasadnieniem tego konkretnego projektu jest wymuszenie sekwencyjnego dostępu do DAG; następna wartość DAG, do której nastąpi dostęp, nie może zostać określona, dopóki nie zostanie poznana bieżąca wartość. Na koniec potęgowanie modularne dodatkowo haszuje wynik.

Algorytm ten opiera się na kilku wynikach z teorii liczb. Zobacz dodatek poniżej, aby zapoznać się z dyskusją na ten temat.

Ewaluacja przez lekkiego klienta

Powyższa konstrukcja grafu ma na celu umożliwienie rekonstrukcji każdego węzła w grafie poprzez obliczenie poddrzewa składającego się tylko z niewielkiej liczby węzłów i wymagającego jedynie niewielkiej ilości pamięci pomocniczej. Należy zauważyć, że przy k=1 poddrzewo jest tylko łańcuchem wartości sięgającym do pierwszego elementu w DAG.

Funkcja obliczeniowa lekkiego klienta dla DAG działa następująco:

Zasadniczo jest to po prostu przepisanie powyższego algorytmu, które usuwa pętlę obliczania wartości dla całego DAG i zastępuje wcześniejsze wyszukiwanie węzłów wywołaniem rekurencyjnym lub wyszukiwaniem w pamięci podręcznej. Należy zauważyć, że dla k=1 pamięć podręczna jest niepotrzebna, chociaż dalsza optymalizacja w rzeczywistości wstępnie oblicza kilka tysięcy pierwszych wartości DAG i przechowuje je jako statyczną pamięć podręczną do obliczeń; zobacz dodatek, aby zapoznać się z implementacją kodu dla tego rozwiązania.

Podwójny bufor DAG

W pełnym kliencie używany jest podwójny bufor (opens in a new tab) 2 DAG-ów wyprodukowanych według powyższego wzoru. Chodzi o to, że DAG-i są produkowane co epochtime bloków zgodnie z powyższymi parametrami. Zamiast używać najnowszego wyprodukowanego DAG, klient używa poprzedniego. Zaletą tego rozwiązania jest to, że pozwala na wymianę DAG-ów w czasie bez konieczności wprowadzania kroku, w którym kopiący muszą nagle ponownie obliczyć wszystkie dane. W przeciwnym razie istnieje potencjalne ryzyko nagłego, tymczasowego spowolnienia przetwarzania łańcucha w regularnych odstępach czasu i drastycznego wzrostu centralizacji. Tym samym wzrasta ryzyko ataku 51% w ciągu tych kilku minut, zanim wszystkie dane zostaną ponownie obliczone.

Algorytm używany do generowania zestawu DAG-ów wykorzystywanych do obliczania pracy dla bloku jest następujący:

Hashimoto

Ideą oryginalnego algorytmu Hashimoto jest wykorzystanie blockchaina jako zbioru danych, wykonanie obliczeń, które wybierają N indeksów z blockchaina, zebranie transakcji pod tymi indeksami, wykonanie operacji XOR na tych danych i zwrócenie hasha wyniku. Oryginalny algorytm Thaddeusa Dryji, przetłumaczony na język Python dla zachowania spójności, wygląda następująco:

def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
    hash_output_A = sha256(prev_hash + merkle_root + nonce)
    txid_mix = 0
    for i in range(64):
        shifted_A = hash_output_A >> i
        transaction = shifted_A % len(list_of_transactions)
        txid_mix ^= list_of_transactions[transaction] << i
    return txid_mix ^ (nonce << 192)

Niestety, chociaż Hashimoto jest uważany za trudny dla pamięci RAM (RAM hard), opiera się na 256-bitowej arytmetyce, co wiąże się ze znacznym narzutem obliczeniowym. Jednak Dagger-Hashimoto używa tylko 64 najmniej znaczących bitów podczas indeksowania swojego zbioru danych, aby rozwiązać ten problem.

def hashimoto(dag, dagsize, params, header, nonce):
    m = dagsize / 2
    mix = sha3(encode_int(nonce) + header)
    for _ in range(params["accesses"]):
        mix ^= dag[m + (mix % 2**64) % m]
    return dbl_sha3(mix)

Użycie podwójnego SHA-3 pozwala na formę niemal natychmiastowej wstępnej weryfikacji bez danych (zero-data), weryfikującej jedynie, czy podano poprawną wartość pośrednią. Ta zewnętrzna warstwa dowodu pracy jest wysoce przyjazna dla układów ASIC i dość słaba, ale istnieje po to, aby jeszcze bardziej utrudnić ataki DDoS, ponieważ ta niewielka ilość pracy musi zostać wykonana w celu wyprodukowania bloku, który nie zostanie natychmiast odrzucony. Oto wersja dla lekkiego klienta:

def quick_hashimoto(seed, dagsize, params, header, nonce):
    m = dagsize // 2
    mix = sha3(nonce + header)
    for _ in range(params["accesses"]):
        mix ^= quick_calc(params, seed, m + (mix % 2**64) % m)
    return dbl_sha3(mix)

Kopanie i weryfikacja

Teraz połączmy to wszystko w algorytm kopania:

Oto algorytm weryfikacji:

def verify(daggerset, params, block, nonce):
    result = hashimoto(daggerset, get_dagsize(params, block),
                       params, decode_int(block.prevhash), nonce)
    return result * params["diff"] < 2**256

Weryfikacja przyjazna dla lekkiego klienta:

def light_verify(params, header, nonce):
    seedset = get_seedset(params, block)
    result = quick_hashimoto(seedset["front_hash"], get_dagsize(params, block),
                             params, decode_int(block.prevhash), nonce)
    return result * params["diff"] < 2**256

Należy również zauważyć, że Dagger-Hashimoto nakłada dodatkowe wymagania na nagłówek bloku:

  • Aby dwuwarstwowa weryfikacja działała, nagłówek bloku musi zawierać zarówno nonce, jak i środkową wartość przed SHA-3
  • Gdzieś nagłówek bloku musi przechowywać SHA-3 obecnego zestawu ziaren (seedset)

Dalsza lektura

Znasz zasoby społeczności, które Ci pomogły? Edytuj tę stronę i dodaj je!

Dodatek

Jak zauważono powyżej, generator liczb losowych (RNG) używany do generowania DAG opiera się na pewnych wynikach z teorii liczb. Po pierwsze, zapewniamy, że generator Lehmera, który jest podstawą zmiennej picker, ma szeroki okres. Po drugie, pokazujemy, że pow(x,3,P) nie zmapuje x na 1 ani P-1 pod warunkiem, że na początku x ∈ [2,P-2]. Na koniec pokazujemy, że pow(x,3,P) ma niski wskaźnik kolizji, gdy jest traktowany jako funkcja skrótu.

Generator liczb losowych Lehmera

Chociaż funkcja produce_dag nie musi generować nieobciążonych liczb losowych, potencjalnym zagrożeniem jest to, że seed**i % P przyjmuje tylko garść wartości. Mogłoby to dać przewagę kopiącym rozpoznającym wzorzec nad tymi, którzy go nie rozpoznają.

Aby tego uniknąć, odwołano się do wyniku z teorii liczb. Bezpieczna liczba pierwsza (opens in a new tab) (Safe Prime) jest definiowana jako liczba pierwsza P taka, że (P-1)/2 jest również liczbą pierwszą. Rząd elementu x grupy multiplikatywnej (opens in a new tab) ℤ/nℤ jest definiowany jako minimalne m takie, że 

xᵐ mod P ≡ 1
Biorąc pod uwagę te definicje, mamy:

Obserwacja 1. Niech x będzie elementem grupy multiplikatywnej ℤ/Pℤ dla bezpiecznej liczby pierwszej P. Jeśli x mod P ≠ 1 mod P i x mod P ≠ P-1 mod P, to rząd x wynosi P-1 lub (P-1)/2.

Dowód. Ponieważ P jest bezpieczną liczbą pierwszą, to z [twierdzenia Lagrange'a][lagrange] wynika, że rząd x wynosi 1, 2, (P-1)/2 lub P-1.

Rząd x nie może wynosić 1, ponieważ z małego twierdzenia Fermata mamy:

xP-1 mod P ≡ 1

Stąd x musi być elementem neutralnym mnożenia w ℤ/nℤ, który jest unikalny. Ponieważ założyliśmy, że x ≠ 1, nie jest to możliwe.

Rząd x nie może wynosić 2, chyba że x = P-1, ponieważ naruszałoby to fakt, że P jest liczbą pierwszą.

Z powyższego twierdzenia możemy wywnioskować, że iterowanie (picker * init) % P będzie miało długość cyklu wynoszącą co najmniej (P-1)/2. Wynika to z faktu, że wybraliśmy P jako bezpieczną liczbę pierwszą w przybliżeniu równą wyższej potędze dwójki, a init znajduje się w przedziale [2,2**256+1]. Biorąc pod uwagę wielkość P, nigdy nie powinniśmy spodziewać się cyklu z potęgowania modularnego.

Kiedy przypisujemy pierwszą komórkę w DAG (zmienną oznaczoną jako init), obliczamy pow(sha3(seed) + 2, 3, P). Na pierwszy rzut oka nie gwarantuje to, że wynik nie jest ani 1, ani P-1. Ponieważ jednak P-1 jest bezpieczną liczbą pierwszą, mamy następujące dodatkowe zapewnienie, które jest wnioskiem z Obserwacji 1:

Obserwacja 2. Niech x będzie elementem grupy multiplikatywnej ℤ/Pℤ dla bezpiecznej liczby pierwszej P, a w niech będzie liczbą naturalną. Jeśli x mod P ≠ 1 mod P i x mod P ≠ P-1 mod P, a także w mod P ≠ P-1 mod P i w mod P ≠ 0 mod P, to xʷ mod P ≠ 1 mod P i xʷ mod P ≠ P-1 mod P

Potęgowanie modularne jako funkcja skrótu

Dla pewnych wartości P i w funkcja pow(x, w, P) może mieć wiele kolizji. Na przykład pow(x,9,19) przyjmuje tylko wartości {1,18}.

Biorąc pod uwagę, że P jest liczbą pierwszą, odpowiednie w dla funkcji skrótu opartej na potęgowaniu modularnym można wybrać, korzystając z następującego wyniku:

Obserwacja 3. Niech P będzie liczbą pierwszą; w i P-1 są względnie pierwsze wtedy i tylko wtedy, gdy dla wszystkich a i b w ℤ/Pℤ:

aʷ mod P ≡ bʷ mod P wtedy i tylko wtedy, gdy a mod P ≡ b mod P

Zatem, biorąc pod uwagę, że P jest liczbą pierwszą, a w jest względnie pierwsze z P-1, mamy |{pow(x, w, P) : x ∈ ℤ}| = P, co oznacza, że funkcja skrótu ma minimalny możliwy wskaźnik kolizji.

W szczególnym przypadku, gdy P jest bezpieczną liczbą pierwszą, tak jak wybraliśmy, to P-1 ma tylko dzielniki 1, 2, (P-1)/2 i P-1. Ponieważ P > 7, wiemy, że 3 jest względnie pierwsze z P-1, stąd w=3 spełnia powyższe twierdzenie.

Bardziej wydajny algorytm ewaluacji oparty na pamięci podręcznej