Dagger-Hashimoto

Dagger-Hashimoto war die ursprüngliche Forschungsimplementierung und Spezifikation für den Mining-Algorithmus von Ethereum. Dagger-Hashimoto wurde durch Ethash ersetzt. Das Mining wurde beim Merge am 15. September 2022 vollständig abgeschaltet. Seitdem wird Ethereum stattdessen durch einen Proof-of-Stake-Mechanismus gesichert. Diese Seite ist von historischem Interesse – die hierin enthaltenen Informationen sind für das Post-Merge-Ethereum nicht mehr relevant.

Voraussetzungen

Um diese Seite besser zu verstehen, empfehlen wir Ihnen, sich zunächst über den Proof-of-Work-Konsens, Mining und Mining-Algorithmen zu informieren.

Dagger-Hashimoto zielt darauf ab, zwei Ziele zu erfüllen:

ASIC-Resistenz: Der Nutzen aus der Entwicklung spezialisierter Hardware für den Algorithmus sollte so gering wie möglich sein.
Verifizierbarkeit durch Light Clients: Ein Block sollte von einem Light Client effizient verifizierbar sein.

Mit einer zusätzlichen Modifikation spezifizieren wir auch, wie ein drittes Ziel auf Wunsch erfüllt werden kann, jedoch auf Kosten zusätzlicher Komplexität:

Speicherung der gesamten Chain: Das Mining sollte die Speicherung des gesamten Blockchain-Zustands erfordern (aufgrund der unregelmäßigen Struktur des Ethereum-Zustands-Tries gehen wir davon aus, dass ein gewisses Pruning möglich sein wird, insbesondere bei einigen häufig verwendeten Verträgen, aber wir möchten dies minimieren).

DAG-Generierung

Der Code für den Algorithmus wird unten in Python definiert. Zuerst geben wir encode_int an, um vorzeichenlose Ganzzahlen (unsigned ints) einer bestimmten Genauigkeit in Strings umzuwandeln. Die Umkehrung ist ebenfalls angegeben:

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
Alle anzeigen

Wir nehmen im Folgenden an, dass sha3 eine Funktion ist, die eine Ganzzahl annimmt und eine Ganzzahl ausgibt, und dbl_sha3 eine Double-SHA3-Funktion ist; wenn Sie diesen Referenzcode in eine Implementierung umwandeln, verwenden Sie:

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)))
Alle anzeigen

Parameter

Die für den Algorithmus verwendeten Parameter sind:

1SAFE_PRIME_512 = 2**512 - 38117 # Größte sichere Primzahl kleiner als 2**512
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS, # Größe des Datensatzes (4 Gigabyte); MUSS EIN VIELFACHES VON 65536 SEIN
5      "n_inc": 65536, # Erhöhung des Wertes von n pro Periode; MUSS EIN VIELFACHES VON 65536 SEIN
6                                        # mit epochtime=20000 ergibt sich ein Wachstum von 882 MB pro Jahr
7      "cache_size": 2500, # Größe des Caches des Light-Clients (kann vom Light-
8                                        # Client gewählt werden; nicht Teil der Algo-Spezifikation)
9      "diff": 2**14, # Schwierigkeit (wird während der Blockauswertung angepasst)
10      "epochtime": 100000, # Länge einer Epoche in Blöcken (wie oft der Datensatz aktualisiert wird)
11      "k": 1, # Anzahl der Elternknoten eines Knotens
12      "w": w, # Wird für modulares Exponentiations-Hashing verwendet
13      "accesses": 200, # Anzahl der Datensatzzugriffe während Hashimoto
14      "P": SAFE_PRIME_512 # Sichere Primzahl für Hashing und Zufallszahlengenerierung
15}
Alle anzeigen

In diesem Fall ist P eine Primzahl, die so gewählt wurde, dass log₂(P) nur geringfügig kleiner als 512 ist, was den 512 Bits entspricht, die wir zur Darstellung unserer Zahlen verwendet haben. Beachten Sie, dass nur die zweite Hälfte des DAG tatsächlich gespeichert werden muss, sodass der De-facto-RAM-Bedarf bei 1 GB beginnt und um 441 MB pro Jahr wächst.

Dagger-Graphenerstellung

Das Primitiv zur Erstellung des Dagger-Graphen ist wie folgt definiert:

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
Alle anzeigen

Im Wesentlichen beginnt es einen Graphen als einzelnen Knoten, sha3(seed), und fügt von dort aus sequenziell weitere Knoten basierend auf zufälligen vorherigen Knoten hinzu. Wenn ein neuer Knoten erstellt wird, wird eine modulare Potenz des Seeds berechnet, um zufällig einige Indizes kleiner als i auszuwählen (unter Verwendung von x % i oben), und die Werte der Knoten an diesen Indizes werden in einer Berechnung verwendet, um einen neuen Wert für x zu generieren, der dann in eine kleine Proof-of-Work-Funktion (basierend auf XOR) eingespeist wird, um letztendlich den Wert des Graphen am Index i zu generieren. Der Grund für dieses spezielle Design ist es, einen sequenziellen Zugriff auf den DAG zu erzwingen; der nächste Wert des DAG, auf den zugegriffen wird, kann erst bestimmt werden, wenn der aktuelle Wert bekannt ist. Schließlich hasht die modulare Exponentiation das Ergebnis weiter.

Dieser Algorithmus stützt sich auf mehrere Ergebnisse aus der Zahlentheorie. Siehe den Anhang unten für eine Diskussion.

Light-Client-Auswertung

Die obige Graphenkonstruktion zielt darauf ab, dass jeder Knoten im Graphen rekonstruiert werden kann, indem ein Teilbaum aus nur einer kleinen Anzahl von Knoten berechnet wird und nur eine geringe Menge an Hilfsspeicher benötigt wird. Beachten Sie, dass bei k=1 der Teilbaum nur eine Kette von Werten ist, die bis zum ersten Element im DAG reicht.

Die Light-Client-Berechnungsfunktion für den DAG funktioniert wie folgt:

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)
Alle anzeigen

Im Wesentlichen handelt es sich einfach um eine Umschreibung des obigen Algorithmus, die die Schleife zur Berechnung der Werte für den gesamten DAG entfernt und die frühere Knotensuche durch einen rekursiven Aufruf oder eine Cache-Suche ersetzt. Beachten Sie, dass für k=1 der Cache unnötig ist, obwohl eine weitere Optimierung tatsächlich die ersten paar tausend Werte des DAG vorberechnet und diese als statischen Cache für Berechnungen bereithält; siehe den Anhang für eine Code-Implementierung davon.

Doppelter Puffer von DAGs

In einem vollständigen Client wird ein doppelter Puffer (Double Buffer) (opens in a new tab) von 2 DAGs verwendet, die durch die obige Formel erzeugt wurden. Die Idee ist, dass DAGs alle epochtime Anzahl von Blöcken gemäß den obigen Parametern erzeugt werden. Anstatt dass der Client den zuletzt erzeugten DAG verwendet, verwendet er den vorherigen. Der Vorteil davon ist, dass die DAGs im Laufe der Zeit ersetzt werden können, ohne dass ein Schritt integriert werden muss, bei dem Miner plötzlich alle Daten neu berechnen müssen. Andernfalls besteht die Gefahr einer abrupten vorübergehenden Verlangsamung der Chain-Verarbeitung in regelmäßigen Abständen und einer dramatisch zunehmenden Zentralisierung. Somit bestehen Risiken für einen 51-%-Angriff innerhalb dieser wenigen Minuten, bevor alle Daten neu berechnet sind.

Der Algorithmus, der verwendet wird, um den Satz von DAGs zu generieren, die zur Berechnung der Arbeit für einen Block verwendet werden, lautet wie folgt:

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        # Kein Back-Buffer möglich, erstelle einfach einen 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"]}}
Alle anzeigen

Hashimoto

Die Idee hinter dem ursprünglichen Hashimoto ist es, die Blockchain als Datensatz zu verwenden und eine Berechnung durchzuführen, die N Indizes aus der Blockchain auswählt, die Transaktionen an diesen Indizes sammelt, ein XOR dieser Daten durchführt und den Hash des Ergebnisses zurückgibt. Der ursprüngliche Algorithmus von Thaddeus Dryja, der aus Konsistenzgründen in Python übersetzt wurde, lautet wie folgt:

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)

Obwohl Hashimoto als RAM-hart gilt, stützt es sich leider auf 256-Bit-Arithmetik, was einen erheblichen Rechenaufwand bedeutet. Dagger-Hashimoto verwendet jedoch nur die niedrigstwertigen 64 Bits bei der Indizierung seines Datensatzes, um dieses Problem zu beheben.

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)

Die Verwendung von Double-SHA3 ermöglicht eine Form der datenlosen, nahezu sofortigen Vorab-Verifizierung, bei der nur überprüft wird, ob ein korrekter Zwischenwert bereitgestellt wurde. Diese äußere Schicht des Proof-of-Work ist sehr ASIC-freundlich und ziemlich schwach, existiert aber, um DDoS noch schwieriger zu machen, da diese geringe Menge an Arbeit geleistet werden muss, um einen Block zu produzieren, der nicht sofort abgelehnt wird. Hier ist die Light-Client-Version:

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)

Mining und Verifizierung

Lassen Sie uns nun alles im Mining-Algorithmus zusammenfassen:

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
Alle anzeigen

Hier ist der Verifizierungsalgorithmus:

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

Light-Client-freundliche Verifizierung:

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

Beachten Sie auch, dass Dagger-Hashimoto zusätzliche Anforderungen an den Block-Header stellt:

Damit die zweischichtige Verifizierung funktioniert, muss ein Block-Header sowohl die Nonce als auch den mittleren Wert vor SHA3 enthalten.
Irgendwo muss ein Block-Header den SHA3 des aktuellen Seed-Sets speichern.

Weiterführende Literatur

Kennen Sie eine Community-Ressource, die Ihnen geholfen hat? Bearbeiten Sie diese Seite und fügen Sie sie hinzu!

Anhang

Wie oben angemerkt, stützt sich der für die DAG-Generierung verwendete RNG (Zufallszahlengenerator) auf einige Ergebnisse aus der Zahlentheorie. Erstens stellen wir sicher, dass der Lehmer-RNG, der die Basis für die Variable picker bildet, eine große Periode hat. Zweitens zeigen wir, dass pow(x,3,P) x nicht auf 1 oder P-1 abbildet, vorausgesetzt, x ∈ [2,P-2] zu Beginn. Schließlich zeigen wir, dass pow(x,3,P) eine niedrige Kollisionsrate aufweist, wenn es als Hash-Funktion behandelt wird.

Lehmer-Zufallszahlengenerator

Während die Funktion produce_dag keine unverzerrten Zufallszahlen erzeugen muss, besteht eine potenzielle Bedrohung darin, dass seed**i % P nur eine Handvoll Werte annimmt. Dies könnte Minern, die das Muster erkennen, einen Vorteil gegenüber denjenigen verschaffen, die dies nicht tun.

Um dies zu vermeiden, wird auf ein Ergebnis aus der Zahlentheorie zurückgegriffen. Eine sichere Primzahl (Safe Prime) (opens in a new tab) ist definiert als eine Primzahl P, bei der (P-1)/2 ebenfalls eine Primzahl ist. Die Ordnung eines Elements x der multiplikativen Gruppe (opens in a new tab) ℤ/nℤ ist definiert als das minimale m, sodass

xᵐ mod P ≡ 1

Unter Berücksichtigung dieser Definitionen haben wir:

Beobachtung 1. Sei x ein Element der multiplikativen Gruppe ℤ/Pℤ für eine sichere Primzahl P. Wenn x mod P ≠ 1 mod P und x mod P ≠ P-1 mod P, dann ist die Ordnung von x entweder P-1 oder (P-1)/2.

Beweis. Da P eine sichere Primzahl ist, gilt nach dem [Satz von Lagrange][lagrange], dass die Ordnung von x entweder 1, 2, (P-1)/2 oder P-1 ist.

Die Ordnung von x kann nicht 1 sein, da nach dem kleinen Satz von Fermat gilt:

x^P-1 mod P ≡ 1

Daher muss x eine multiplikative Identität von ℤ/nℤ sein, die eindeutig ist. Da wir angenommen haben, dass x ≠ 1, ist dies nicht möglich.

Die Ordnung von x kann nicht 2 sein, es sei denn, x = P-1, da dies verletzen würde, dass P eine Primzahl ist.

Aus der obigen Aussage können wir erkennen, dass die Iteration von (picker * init) % P eine Zykluslänge von mindestens (P-1)/2 haben wird. Dies liegt daran, dass wir P als eine sichere Primzahl ausgewählt haben, die ungefähr einer höheren Zweierpotenz entspricht, und init im Intervall [2,2**256+1] liegt. Angesichts der Größe von P sollten wir niemals einen Zyklus aus der modularen Exponentiation erwarten.

Wenn wir die erste Zelle im DAG zuweisen (die Variable mit der Bezeichnung init), berechnen wir pow(sha3(seed) + 2, 3, P). Auf den ersten Blick garantiert dies nicht, dass das Ergebnis weder 1 noch P-1 ist. Da P-1 jedoch eine sichere Primzahl ist, haben wir die folgende zusätzliche Sicherheit, die ein Korollar aus Beobachtung 1 ist:

Beobachtung 2. Sei x ein Element der multiplikativen Gruppe ℤ/Pℤ für eine sichere Primzahl P, und sei w eine natürliche Zahl. Wenn x mod P ≠ 1 mod P und x mod P ≠ P-1 mod P, sowie w mod P ≠ P-1 mod P und w mod P ≠ 0 mod P, dann ist xʷ mod P ≠ 1 mod P und xʷ mod P ≠ P-1 mod P

Modulare Exponentiation als Hash-Funktion

Für bestimmte Werte von P und w kann die Funktion pow(x, w, P) viele Kollisionen aufweisen. Zum Beispiel nimmt pow(x,9,19) nur die Werte {1,18} an.

Da P eine Primzahl ist, kann ein geeignetes w für eine modulare Exponentiations-Hash-Funktion unter Verwendung des folgenden Ergebnisses ausgewählt werden:

Beobachtung 3. Sei P eine Primzahl; w und P-1 sind teilerfremd, wenn und nur wenn für alle a und b in ℤ/Pℤ gilt:
aʷ mod P ≡ bʷ mod P wenn und nur wenn a mod P ≡ b mod P

Da P eine Primzahl ist und w teilerfremd zu P-1 ist, gilt somit |{pow(x, w, P) : x ∈ ℤ}| = P, was impliziert, dass die Hash-Funktion die minimal mögliche Kollisionsrate aufweist.

In dem speziellen Fall, dass P eine sichere Primzahl ist, wie wir sie ausgewählt haben, hat P-1 nur die Faktoren 1, 2, (P-1)/2 und P-1. Da P > 7, wissen wir, dass 3 teilerfremd zu P-1 ist, daher erfüllt w=3 die obige Aussage.

Effizienterer Cache-basierter Auswertungsalgorithmus

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)
Alle anzeigen

Dagger-Hashimoto

Voraussetzungen