Dagger-Hashimoto

A Dagger-Hashimoto volt az Ethereum bányászati algoritmusának eredeti fejlesztési implementációja és specifikációja. A Dagger-Hashimoto algoritmust az Ethash váltotta le. A bányászatot teljesen kikapcsolták az egyesítés (Merge) frissítés életbe lépésekor, 2022. szeptember 15-én. Azóta az Ethereumot a proof-of-stake (letéti igazolás) mechanizmusa biztosítja. Ez az oldal elavult témákat tartalmaz, amelyek többé már nem relevánsak az egyesítés (Merge) utáni Ethereummal kapcsolatban.

Előfeltételek

A jelen téma könnyebb megértéséhez javasoljuk, hogy tekintse meg a proof-of-work konszenzus, a bányászat, és a bányászati algoritmusok témáit.

A Dagger-Hashimoto két célt szolgál:

ASIC-ellenálló: az algoritmus futtatásához a specializált hardver kialakításából adódó előny a lehető legkisebb legyen
Könnyű kliens általi ellenőrizhetőség: a blokkot egy könnyű kliens is le tudja ellenőrizni hatékonyan.

Egy újabb módosítással meghatározhatjuk, hogyan tud egy harmadik célt is kielégíteni, de ez a komplexitás növekedésével jár:

A teljes lánc tárolása: a bányászathoz a teljes blokklánc státuszát le kell tárolni (az Ethereum státuszfa szabálytalan struktúrája miatt talán lehetséges ennek megrövidítése, főleg a gyakori szerződéseknél, de ezt minimalizálni szeretnénk).

DAG létrehozása

Az algoritmus kódját pythonban alább találja. Először az encode_int kódot adjuk meg, hogy a megadott pontosságú nem aláírt egész számokat sztringekké alakítsa. Ennek fordítottja is megadásra kerül:

1NUM_BITS = 512
2
3def encode_int(x):
4    "Encode an integer x as a string of 64 characters using a big-endian scheme"
5    o = ''
6    for _ in range(NUM_BITS / 8):
7        o = chr(x % 256) + o
8        x //= 256
9    return o
10
11def decode_int(s):
12    "Unencode an integer x from a string using a big-endian scheme"
13    x = 0
14    for c in s:
15        x *= 256
16        x += ord(c)
17    return x
Összes megjelenítése
 Másolás

Ezután, feltételezve, hogy az sha3 egy olyan függvény, ami egész számot kap és azt is ad ki eredményként, továbbá a dbl_sha3 egy dupla sha3 függvény; ha ezt a referenciakódot implementációvá alakítjuk:

1from pyethereum import utils
2def sha3(x):
3    if isinstance(x, (int, long)):
4        x = encode_int(x)
5    return decode_int(utils.sha3(x))
6
7def dbl_sha3(x):
8    if isinstance(x, (int, long)):
9        x = encode_int(x)
10    return decode_int(utils.sha3(utils.sha3(x)))
Összes megjelenítése
 Másolás

Paraméterek

Az algoritmushoz a következő paramétereket használjuk:

1SAFE_PRIME_512 = 2**512 - 38117     # Largest Safe Prime less than 2**512
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS,  # Size of the dataset (4 Gigabytes); MUST BE MULTIPLE OF 65536
5      "n_inc": 65536,                   # Increment in value of n per period; MUST BE MULTIPLE OF 65536
6                                        # with epochtime=20000 gives 882 MB growth per year
7      "cache_size": 2500,               # Size of the light client's cache (can be chosen by light
8                                        # client; not part of the algo spec)
9      "diff": 2**14,                    # Difficulty (adjusted during block evaluation)
10      "epochtime": 100000,              # Length of an epoch in blocks (how often the dataset is updated)
11      "k": 1,                           # Number of parents of a node
12      "w": w,                          # Used for modular exponentiation hashing
13      "accesses": 200,                  # Number of dataset accesses during hashimoto
14      "P": SAFE_PRIME_512               # Safe Prime for hashing and random number generation
15}
Összes megjelenítése
 Másolás

A P ebben az esetben egy olyan prímszám, hogy a log₂(P) éppen csak kisebb legyen, mint 512, ami az 512 bithez kapcsolódik, amit a számok reprezentálására használunk. Érdemes megjegyezni, hogy a DAG-nek csak a második felét kell eltárolni, így a RAM-igény 1 GB-tól indul és 441 MB-tal növekszik évente.

Dagger-gráfépítés

A dagger-gráfépítési függvényt a következőképpen definiáljuk:

1def produce_dag(params, seed, length):
2    P = params["P"]
3    picker = init = pow(sha3(seed), params["w"], P)
4    o = [init]
5    for i in range(1, length):
6        x = picker = (picker * init) % P
7        for _ in range(params["k"]):
8            x ^= o[x % i]
9        o.append(pow(x, params["w"], P))
10    return o
Összes megjelenítése
 Másolás

Lényegében a gráfot egy egyszerű csomópontként kezdi (sha3(seed)), és innen ad hozzá szekvenciálisan újabb csomópontokat a véletlenszerű előzők csomópontok alapján. Egy új csomópont létrehozásakor a mag moduláris hatványát kiszámítjuk, hogy véletlenszerűen kiválasszunk néhány i-nél kisebb indexet (a fenti x % i használatával), és az ezeknél az indexeknél lévő csomópontok értékeit egy számításban felhasználjuk az x új értékének létrehozásához, amelyet aztán egy kis (XOR-alapú) proof-of-work függvénybe táplálunk, hogy végül az i indexnél lévő gráf értékét generáljuk. E sajátos kialakítás értelme az, hogy a DAG-hoz szekvenciális hozzáférést biztosítson; a DAG következő értékét nem lehet meghatározni addig, amíg a jelenlegi nem ismert. Végül a moduláris exponenciálás hasheli tovább az eredményt.

Ez az algoritmus a számelmélet számos eredményén alapszik. Az alábbi függelékben megtalálhatja az erről szóló beszélgetést.

Könnyű kliens általi értékelés

Ez a gráfkonstrukció arra való, hogy a gráf minden csomópontja újraépíthető legyen egy kis számú csomópontból álló alfa segítségével, és csak kevés kiegészítő memória kelljen hozzá. Vegye figyelembe, hogy ha k=1, akkor az alfastruktúra csak az értékek egy olyan lánca, ami a DAG első eleméig tart.

A DAG-re a következőképpen működik a könnyű kliens számítási függvénye:

1def quick_calc(params, seed, p):
2    w, P = params["w"], params["P"]
3    cache = {}
4
5    def quick_calc_cached(p):
6        if p in cache:
7            pass
8        elif p == 0:
9            cache[p] = pow(sha3(seed), w, P)
10        else:
11            x = pow(sha3(seed), (p + 1) * w, P)
12            for _ in range(params["k"]):
13                x ^= quick_calc_cached(x % p)
14            cache[p] = pow(x, w, P)
15        return cache[p]
16
17    return quick_calc_cached(p)
Összes megjelenítése
 Másolás

Lényegében ez a fenti algoritmus átirata, ami kiveszi a teljes DAG számítási ciklusát, és a korábbi csomópontkereső függvényt cseréli le egy rekurzív hívásra vagy egy cache-keresőre. Érdemes megjegyezni, hogy k=1 esetén a cache szükségtelen, bár egy további optimalizálással a DAG első néhány ezer értékét előre kiszámítja, és statikus cache-ként tárolja a számításokhoz; ennek kódmegvalósítását tekintse meg a függelékben.

A DAG-ek dupla puffere

Egy teljes kliensben 2 DAG dupla pufferét(opens in a new tab) használják, melyet a fenti képlet ad meg. Az elképzelés szerint a DAG-eket minden epochtime (korszakban) blokkszámonként készítik a fenti paramétereknek megfelelően. Ahelyett, hogy a kliens a legutóbbi DAG-et használná, az eggyel korábbit veszi figyelembe. Ennek előnye az, hogy a DAG-eket le lehet cserélni idővel anélkül, hogy a bányászoknak hirtelen az összes adatot újra kellene számolniuk. Máskülönben felmerül egy hirtelen, átmeneti lelassulás esélye a láncfeldolgozásnak, ami drasztikusan növeli a centralizációt. Így megnő az 51%-os támadás kockázata is az adat újraszámítása előtti percekben.

A blokkhoz szükséges munka kiszámításához használt DAG-ek halmazának létrehozására használt algoritmus a következő:

1def get_prevhash(n):
2    from pyethereum.blocks import GENESIS_PREVHASH
3    from pyethereum import chain_manager
4    if n <= 0:
5        return hash_to_int(GENESIS_PREVHASH)
6    else:
7        prevhash = chain_manager.index.get_block_by_number(n - 1)
8        return decode_int(prevhash)
9
10def get_seedset(params, block):
11    seedset = {}
12    seedset["back_number"] = block.number - (block.number % params["epochtime"])
13    seedset["back_hash"] = get_prevhash(seedset["back_number"])
14    seedset["front_number"] = max(seedset["back_number"] - params["epochtime"], 0)
15    seedset["front_hash"] = get_prevhash(seedset["front_number"])
16    return seedset
17
18def get_dagsize(params, block):
19    return params["n"] + (block.number // params["epochtime"]) * params["n_inc"]
20
21def get_daggerset(params, block):
22    dagsz = get_dagsize(params, block)
23    seedset = get_seedset(params, block)
24    if seedset["front_hash"] <= 0:
25        # No back buffer is possible, just make front buffer
26        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
27                          "block_number": 0}}
28    else:
29        return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
30                          "block_number": seedset["front_number"]},
31                "back": {"dag": produce_dag(params, seedset["back_hash"], dagsz),
32                         "block_number": seedset["back_number"]}}
Összes megjelenítése
 Másolás

Hashimoto

Az eredeti Hashimoto lényege, hogy a blokkláncot adathalmazként használja, és olyan számítást végez, amely kiválaszt N indexet a blokkláncból, összegyűjti a tranzakciókat ezeken az indexeken, elvégzi a XOR-t ezekre az adatokra, és visszaadja az eredmény hashét. Thaddeus Dryja eredeti algoritmusa, Pythonra átfordítva a konzisztencia érdekében, így néz ki:

1def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
2    hash_output_A = sha256(prev_hash + merkle_root + nonce)
3    txid_mix = 0
4    for i in range(64):
5        shifted_A = hash_output_A >> i
6        transaction = shifted_A % len(list_of_transactions)
7        txid_mix ^= list_of_transactions[transaction] << i
8    return txid_mix ^ (nonce << 192)
 Másolás

Sajnálatos módon, miközben a Hashimoto nagy RAM-igényű, 256 bites aritmetikán alapszik, ami jelentős számítási többletköltséggel jár. Ugyanakkor a Dagger-Hashimoto csak a legkevésbé szignifikáns 64 bitet használja az adathalmaz indexálására, hogy ezt a problémát kezelje.

1def hashimoto(dag, dagsize, params, header, nonce):
2    m = dagsize / 2
3    mix = sha3(encode_int(nonce) + header)
4    for _ in range(params["accesses"]):
5        mix ^= dag[m + (mix % 2**64) % m]
6    return dbl_sha3(mix)
 Másolás

A dupla SHA3 használata lehetővé teszi a nulla adatot tartalmazó, szinte azonnali előzetes ellenőrzést, amely csak azt ellenőrzi, hogy a helyes közbenső értéket adták meg. A proof-of-worknek ez a külső rétege rendkívül ASIC-barát és meglehetősen gyenge, de azért létezik, hogy még nehezebbé tegye a DDoS-t, mivel ezt a kis mennyiségű munkát kell elvégezni ahhoz, hogy egy olyan blokkot hozzanak létre, amelyet nem utasítanak el azonnal. Ez a könnyű kliens verziója:

1def quick_hashimoto(seed, dagsize, params, header, nonce):
2    m = dagsize // 2
3    mix = sha3(nonce + header)
4    for _ in range(params["accesses"]):
5        mix ^= quick_calc(params, seed, m + (mix % 2**64) % m)
6    return dbl_sha3(mix)
 Másolás

Bányászat és ellenőrzés

Most vezessük be mindezt a bányászati algoritmusba:

1def mine(daggerset, params, block):
2    from random import randint
3    nonce = randint(0, 2**64)
4    while 1:
5        result = hashimoto(daggerset, get_dagsize(params, block),
6                           params, decode_int(block.prevhash), nonce)
7        if result * params["diff"] < 2**256:
8            break
9        nonce += 1
10        if nonce >= 2**64:
11            nonce = 0
12    return nonce
Összes megjelenítése
 Másolás

Ez az ellenőrzési algoritmus:

1def verify(daggerset, params, block, nonce):
2    result = hashimoto(daggerset, get_dagsize(params, block),
3                       params, decode_int(block.prevhash), nonce)
4    return result * params["diff"] < 2**256
 Másolás

Ez a könnyű kliens általi barátságos ellenőrzés:

1def light_verify(params, header, nonce):
2    seedset = get_seedset(params, block)
3    result = quick_hashimoto(seedset["front_hash"], get_dagsize(params, block),
4                             params, decode_int(block.prevhash), nonce)
5    return result * params["diff"] < 2**256
 Másolás

Emellett érdemes megjegyezni, hogy a Dagger-Hashimoto a blokkfejlécre egyéb követelményeket is megfogalmazott:

A kétszintű ellenőrzéshez a blokkfejlécnek tartalmaznia kell a nonce-t és az sha3 előtti köztes értéket
Valahol a blokkfejlécnek tárolnia kell a jelenlegi seed-halmaz sha3-ját

További olvasnivaló

Ismersz olyan közösségi anyagot, mely segített neked? Módosítsd az oldalt és add hozzá!

Függelék

Mint fentebb említettük, a DAG generálásához használt RNG a számelmélet néhány eredményére támaszkodik. Először is biztosítjuk, hogy a picker változó alapjául szolgáló Lehmer RNG széles periódussal rendelkezik. Másodszor, megmutatjuk, hogy a pow(x,3,P) nem fogja x kódot 1 vagy P-1 értékre leképezni, feltéve, hogy x ∈ [2,P-2]. Végül megmutatjuk, hogy a pow(x,3,P) alacsony ütközési rátával rendelkezik, ha hash függvényként kezeljük.

Lehmer véletlenszám-generátor

Bár a produce_dag függvénynek nem kell torzítatlan véletlen számokat produkálnia, és potenciális veszélyt jelent, hogy a seed**i % P csak néhány értéket vesz fel. Ez előnyt jelenthet azoknak a bányászoknak, akik felismerik a mintát, miközben mások nem.

Ennek elkerülése érdekében egy számelméleti eredményre hivatkozunk. A biztonságos prímszám(opens in a new tab) egy olyan prím P, amelynél a (P-1)/2 szintén prímszám. A multiplikatív csoport(opens in a new tab) egy x tagjának rendje a ℤ/nℤ meghatározása szerint a minimális m úgy, hogy

1xᵐ mod P ≡ 1

Ezen definíciók szerint:

megfigyelés. Legyen x a ℤ/Pℤ multiplikatív csoport tagja egy biztonságos P prímszámhoz. Ha x mod P ≠ 1 mod P és x mod P ≠ P-1 mod P, akkor x rendje vagy P-1 vagy (P-1)/2.

Bizonyítás. Mivel P egy biztonságos prímszám, akkor a [Lagrange-tétel][lagrange] alapján azt kell mondanunk, hogy x rendje vagy 1, 2, (P-1)/2 vagy P-1.

A x sorrendje nem lehet 1 Fermat kis tételéből következően:

1xP-1 mod P ≡ 1

Ezért x a ℤ/nℤ multiplikatív azonosságának kell lennie, ami egyedi. Mivel feltételezésünk szerint x ≠ 1, ez nem lehetséges.

Az x sorrendje nem lehet 2, kivéve, ha x = P-1, mivel ez sértené, hogy P prímszám.

A fenti tételből felismerhetjük, hogy a (picker * init) % P ismétlése legalább (P-1)/2 ciklushosszúságú lesz. Ennek az az oka, hogy a P értékének egy biztonságos prímszámot választottunk, amely megközelítőleg egyenlő a kettő nagyobb hatványával, és init a [2,2**256+1] intervallumban van. A P nagyságát tekintve a moduláris exponenciálástól nem várhatunk ciklust.

A DAG első cellájának (az init feliratú változó) hozzárendelésekor kiszámítjuk a pow(sha3(seed) + 2, 3, P) értékét. Első pillantásra ez nem garantálja, hogy az eredmény nem 1 és nem P-1. Mivel azonban P-1 egy biztonságos prímszám, a következő további bizonyosságunk van, amely az 1. megfigyelés következménye:

megfigyelés. Legyen x a ℤ/Pℤ multiplikatív csoport tagja egy biztonságos P prímszámhoz, és legyen w egy természetes szám. Ha x mod P ≠ 1 mod P és x mod P ≠ P-1 mod P, valamint w mod P ≠ P-1 mod P és w mod P ≠ 0 mod P, akkor xʷ mod P ≠ 1 mod P és xʷ mod P ≠ P-1 mod P

Moduláris exponenciálás hashfüggvényként

A P és w bizonyos értékei esetén a pow(x, w, P) függvénynek sok ütközése lehet. Például a pow(x,9,19) csak {1,18} értékeket vesz fel.

Adott, hogy P prímszám, akkor egy megfelelő w moduláris exponenciálási hashfüggvényhez a következő eredmény segítségével választható ki:

megfigyelés. Legyen P egy prímszám; w és P-1 akkor, és csak akkor relatív prímszámok, ha minden a és b esetén ℤ/Pℤ:
`aʷ mod P ≡ bʷ mod P`, ha és csak ha `a mod P ≡ b mod P`

Így, feltéve, hogy P prím és w relatíve prím P-1-hez, akkor |{pow(x, w, P) : x ∈ ℤ}| = P, ami azt jelenti, hogy a hashfüggvény a lehető legkisebb ütközési rátával rendelkezik.

Abban a speciális esetben, ha P egy biztonságos prímszám, ahogyan azt választottuk, akkor P-1 csak 1, 2, (P-1)/2 és P-1 faktorokkal rendelkezik. Mivel P > 7, tudjuk, hogy 3 relatív prím a P-1-hez, ezért w=3 kielégíti a fenti tételt.

Hatékonyabb cache-alapú kiértékelő algoritmus

1def quick_calc(params, seed, p):
2    cache = produce_dag(params, seed, params["cache_size"])
3    return quick_calc_cached(cache, params, p)
4
5def quick_calc_cached(cache, params, p):
6    P = params["P"]
7    if p < len(cache):
8        return cache[p]
9    else:
10        x = pow(cache[0], p + 1, P)
11        for _ in range(params["k"]):
12            x ^= quick_calc_cached(cache, params, x % p)
13        return pow(x, params["w"], P)
14
15def quick_hashimoto(seed, dagsize, params, header, nonce):
16    cache = produce_dag(params, seed, params["cache_size"])
17    return quick_hashimoto_cached(cache, dagsize, params, header, nonce)
18
19def quick_hashimoto_cached(cache, dagsize, params, header, nonce):
20    m = dagsize // 2
21    mask = 2**64 - 1
22    mix = sha3(encode_int(nonce) + header)
23    for _ in range(params["accesses"]):
24        mix ^= quick_calc_cached(cache, params, m + (mix & mask) % m)
25    return dbl_sha3(mix)
Összes megjelenítése
 Másolás

Dagger-Hashimoto

Előfeltételek