Přejít na hlavní obsah
Change page

Dagger-Hashimoto

Upravit stránku (opens in a new tab)

Dagger-Hashimoto byla původní výzkumná implementace a specifikace pro těžební algoritmus Etherea. Dagger-Hashimoto byl nahrazen algoritmem Ethash. Těžba byla kompletně vypnuta při Merge 15. září 2022. Od té doby je Ethereum zabezpečeno pomocí mechanismu důkaz podílem (PoS). Tato stránka slouží pro historickou zajímavost – zde uvedené informace již nejsou pro Ethereum po Merge relevantní.

Předpoklady

Pro lepší pochopení této stránky doporučujeme nejprve si přečíst o konsensu důkazu prací (PoW), těžbě a těžebních algoritmech.

Dagger-Hashimoto

Dagger-Hashimoto má za cíl splnit dva cíle:

  1. Odolnost vůči ASIC: výhoda z vytvoření specializovaného hardwaru pro tento algoritmus by měla být co nejmenší.
  2. Ověřitelnost lehkým klientem: blok by měl být efektivně ověřitelný lehkým klientem.

S dodatečnou úpravou také specifikujeme, jak v případě potřeby splnit třetí cíl, avšak za cenu vyšší složitosti:

Ukládání celého řetězce: těžba by měla vyžadovat uložení kompletního stavu blockchainu (kvůli nepravidelné struktuře stavové trie Etherea předpokládáme, že bude možné určité prořezávání, zejména u některých často používaných kontraktů, ale chceme to minimalizovat).

Generování DAG

Kód algoritmu bude níže definován v jazyce Python. Nejprve uvádíme encode_int pro převod (marshaling) celých čísel bez znaménka se zadanou přesností na řetězce. Je uvedena i jeho inverzní funkce:

Dále předpokládáme, že sha3 je funkce, která přijímá celé číslo a vrací celé číslo, a dbl_sha3 je funkce double-sha3; pokud převádíte tento referenční kód do implementace, použijte:

Parametry

Parametry použité pro algoritmus jsou:

P je v tomto případě prvočíslo zvolené tak, aby log₂(P) bylo jen o něco menší než 512, což odpovídá 512 bitům, které používáme k reprezentaci našich čísel. Všimněte si, že ve skutečnosti je nutné ukládat pouze druhou polovinu DAG, takže de facto požadavek na RAM začíná na 1 GB a roste o 441 MB ročně.

Budování grafu Dagger

Primitivum pro budování grafu Dagger je definováno následovně:

V podstatě začíná graf jako jediný uzel, sha3(seed), a odtud začne postupně přidávat další uzly na základě náhodných předchozích uzlů. Když je vytvořen nový uzel, vypočítá se modulární mocnina seedu, aby se náhodně vybraly některé indexy menší než i (pomocí x % i výše), a hodnoty uzlů na těchto indexech se použijí ve výpočtu k vygenerování nové hodnoty pro x, která je pak předána do malé funkce důkazu prací (založené na XOR), aby se nakonec vygenerovala hodnota grafu na indexu i. Důvodem tohoto konkrétního návrhu je vynutit sekvenční přístup k DAG; další hodnotu DAG, ke které se bude přistupovat, nelze určit, dokud není známa aktuální hodnota. Nakonec modulární umocňování výsledek dále zahashuje.

Tento algoritmus se opírá o několik výsledků z teorie čísel. Diskusi naleznete v příloze níže.

Vyhodnocení lehkým klientem

Výše uvedená konstrukce grafu má umožnit rekonstrukci každého uzlu v grafu výpočtem podstromu pouze malého počtu uzlů a vyžaduje pouze malé množství pomocné paměti. Všimněte si, že při k=1 je podstrom pouze řetězec hodnot sahající až k prvnímu prvku v DAG.

Výpočetní funkce lehkého klienta pro DAG funguje následovně:

V podstatě se jedná o pouhý přepis výše uvedeného algoritmu, který odstraňuje smyčku výpočtu hodnot pro celý DAG a nahrazuje dřívější vyhledávání uzlů rekurzivním voláním nebo vyhledáváním v mezipaměti (cache). Všimněte si, že pro k=1 je mezipaměť zbytečná, ačkoli další optimalizace ve skutečnosti předpočítává prvních několik tisíc hodnot DAG a udržuje je jako statickou mezipaměť pro výpočty; implementaci kódu naleznete v příloze.

Dvojitý buffer DAGů

V plném klientovi se používá dvojitý buffer (opens in a new tab) 2 DAGů vytvořených podle výše uvedeného vzorce. Myšlenka spočívá v tom, že DAGy jsou produkovány každých epochtime bloků podle výše uvedených parametrů. Místo toho, aby klient používal nejnovější vyprodukovaný DAG, používá ten předchozí. Výhodou toho je, že to umožňuje postupnou výměnu DAGů bez nutnosti začlenit krok, kdy by těžaři museli náhle přepočítat všechna data. V opačném případě by hrozilo náhlé dočasné zpomalení zpracování řetězce v pravidelných intervalech a dramatické zvýšení centralizace. Tím by vzniklo riziko 51% útoku během těch několika minut, než by byla všechna data přepočítána.

Algoritmus používaný ke generování sady DAGů použitých k výpočtu práce pro blok je následující:

Hashimoto

Myšlenkou původního algoritmu Hashimoto je použít blockchain jako datovou sadu, provést výpočet, který vybere N indexů z blockchainu, shromáždí transakce na těchto indexech, provede XOR těchto dat a vrátí hash výsledku. Původní algoritmus Thaddeuse Dryji, přeložený do Pythonu pro konzistenci, je následující:

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)

Bohužel, ačkoli je Hashimoto považován za náročný na RAM, spoléhá se na 256bitovou aritmetiku, která má značnou výpočetní režii. Dagger-Hashimoto však k řešení tohoto problému používá při indexování své datové sady pouze 64 nejméně významných bitů.

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)

Použití dvojitého SHA3 umožňuje formu téměř okamžitého předběžného ověření s nulovými daty, které ověřuje pouze to, že byla poskytnuta správná mezihodnota. Tato vnější vrstva důkazu prací je velmi přátelská k ASIC a poměrně slabá, ale existuje proto, aby ještě více ztížila DDoS útoky, protože toto malé množství práce musí být vykonáno, aby byl vytvořen blok, který nebude okamžitě odmítnut. Zde je verze pro lehkého 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)

Těžba a ověřování

Nyní to všechno spojme do těžebního algoritmu:

Zde je ověřovací algoritmus:

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

Ověřování přátelské k lehkým klientům:

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

Všimněte si také, že Dagger-Hashimoto klade další požadavky na hlavičku bloku:

  • Aby fungovalo dvouvrstvé ověřování, musí mít hlavička bloku jak nonce, tak střední hodnotu před sha3.
  • Někde musí hlavička bloku ukládat sha3 aktuální sady seedů.

Další čtení

Znáte komunitní zdroj, který vám pomohl? Upravte tuto stránku a přidejte ho!

Příloha

Jak bylo uvedeno výše, generátor náhodných čísel (RNG) použitý pro generování DAG se opírá o některé výsledky z teorie čísel. Zaprvé poskytujeme ujištění, že Lehmerův RNG, který je základem pro proměnnou picker, má širokou periodu. Zadruhé ukazujeme, že pow(x,3,P) nenamapuje x na 1 nebo P-1 za předpokladu, že na začátku je x ∈ [2,P-2]. Nakonec ukazujeme, že pow(x,3,P) má nízkou míru kolizí, když se s ním zachází jako s hashovací funkcí.

Lehmerův generátor náhodných čísel

Ačkoli funkce produce_dag nemusí produkovat nezkreslená náhodná čísla, potenciální hrozbou je, že seed**i % P nabývá pouze hrstky hodnot. To by mohlo poskytnout výhodu těžařům, kteří tento vzorec rozpoznají, oproti těm, kteří jej nerozpoznají.

Aby se tomu zabránilo, využívá se výsledek z teorie čísel. Bezpečné prvočíslo (opens in a new tab) je definováno jako prvočíslo P takové, že (P-1)/2 je také prvočíslo. Řád prvku x multiplikativní grupy (opens in a new tab) ℤ/nℤ je definován jako minimální m takové, že 

xᵐ mod P ≡ 1
Vzhledem k těmto definicím máme:

Pozorování 1. Nechť x je prvek multiplikativní grupy ℤ/Pℤ pro bezpečné prvočíslo P. Pokud x mod P ≠ 1 mod P a x mod P ≠ P-1 mod P, pak řád x je buď P-1 nebo (P-1)/2.

Důkaz. Protože P je bezpečné prvočíslo, pak podle [Lagrangeovy věty][lagrange] platí, že řád x je buď 1, 2, (P-1)/2 nebo P-1.

Řád x nemůže být 1, protože podle Malé Fermatovy věty máme:

xP-1 mod P ≡ 1

Proto x musí být multiplikativní identitou ℤ/nℤ, která je jedinečná. Vzhledem k tomu, že jsme předpokládali x ≠ 1, není to možné.

Řád x nemůže být 2, pokud neplatí x = P-1, protože by to porušovalo skutečnost, že P je prvočíslo.

Z výše uvedeného tvrzení můžeme vyvodit, že iterace (picker * init) % P bude mít délku cyklu alespoň (P-1)/2. Je to proto, že jsme zvolili P jako bezpečné prvočíslo přibližně rovné vyšší mocnině dvou a init je v intervalu [2,2**256+1]. Vzhledem k velikosti P bychom nikdy neměli očekávat cyklus z modulárního umocňování.

Když přiřazujeme první buňku v DAG (proměnná označená init), počítáme pow(sha3(seed) + 2, 3, P). Na první pohled to nezaručuje, že výsledek není ani 1, ani P-1. Protože je však P-1 bezpečné prvočíslo, máme následující dodatečné ujištění, které je důsledkem Pozorování 1:

Pozorování 2. Nechť x je prvek multiplikativní grupy ℤ/Pℤ pro bezpečné prvočíslo P a nechť w je přirozené číslo. Pokud x mod P ≠ 1 mod P a x mod P ≠ P-1 mod P, a zároveň w mod P ≠ P-1 mod P a w mod P ≠ 0 mod P, pak xʷ mod P ≠ 1 mod P a xʷ mod P ≠ P-1 mod P

Modulární umocňování jako hashovací funkce

Pro určité hodnoty P a w může mít funkce pow(x, w, P) mnoho kolizí. Například pow(x,9,19) nabývá pouze hodnot {1,18}.

Vzhledem k tomu, že P je prvočíslo, lze vhodné w pro hashovací funkci modulárního umocňování zvolit pomocí následujícího výsledku:

Pozorování 3. Nechť P je prvočíslo; w a P-1 jsou nesoudělná právě tehdy, když pro všechna a a b v ℤ/Pℤ platí:

aʷ mod P ≡ bʷ mod P právě tehdy, když a mod P ≡ b mod P

Tedy, vzhledem k tomu, že P je prvočíslo a w je nesoudělné s P-1, platí, že |{pow(x, w, P) : x ∈ ℤ}| = P, což znamená, že hashovací funkce má minimální možnou míru kolizí.

Ve speciálním případě, kdy je P bezpečné prvočíslo, jak jsme zvolili, má P-1 pouze dělitele 1, 2, (P-1)/2 a P-1. Protože P > 7, víme, že 3 je nesoudělné s P-1, a proto w=3 splňuje výše uvedené tvrzení.

Efektivnější vyhodnocovací algoritmus založený na mezipaměti

Poslední aktualizace stránky: 3. dubna 2026

lukassiml (opens in a new tab)
joaolago1113j (opens in a new tab)
corwintinesc (opens in a new tab)
+2