Dagger-Hashimoto

Dagger-Hashimoto war die ursprüngliche Forschungsimplementierung und Spezifikation für den Mining-Algorithmus von Ethereum. Dagger-Hashimoto wurde durch Ethash abgelöst. Das Mining wurde mit der Zusammenführung am 15. September 2022 komplett ausgeschaltet. Seitdem wird die Sicherheit von Ethereum durch einen Proof-of-Stake-Mechanismus gewährleistet. Diese Seite dient dem geschichtlichen Interesse – die Informationen hier sind seit der Zusammenführung für Ethereum nicht mehr relevant.

Voraussetzungen

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

Dagger-Hashimoto

Dagger-Hashimoto will zwei Ziele erreichen:

1. ASIC-Resistenz: Der Vorteil der Erstellung von spezieller Hardware für den Algorithmus sollte so gering wie möglich sein.
2. Light-Client-Verifizierbarkeit: Ein Block sollte durch einen Light-Client effizient verifiziert werden können.

Durch eine weitere Modifikation spezifizieren wir außerdem, wie – sofern gewünscht – ein drittes Ziel erreicht wird, was jedoch zusätzliche Komplexität mit sich bringt:

Speichern der vollen Kette: Mining sollte das Speichern des gesamten Blockchain-Status erfordern (wegen der irregulären Struktur des Ethereum-Statusbaums wird erwartet, dass einige Kürzungen möglich sein werden, insbedondere von eingen oft genutzten Contracts; dies soll aber minimiert werden).

DAG-Generierung

Der Code für den Algorithmus wird unten in Python definiert. Zunächst geben wir encode_int zur Anordnung nicht unterzeichneter Einheiten spezifizierter Präzision an Strings. Die entsprechend Umkehrung wird ebenfalls bereitgestellt:

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
Alles anzeigen
 Kopieren

Als Nächstes gehen wir davon aus, dass sah3 eine Funktion ist, die eine Ganzzahl bezieht und eine Ganzzahl ausgibt, und dbl_sah3 eine Doppelt-sah3-Funktion ist; wenn man diesen Referenzcode in eine Implementierungsanwendung umwandelt:

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)))
Alles anzeigen
 Kopieren

Parameter

Folgende Parameter werden für den Algorithmus verwendet:

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}
Alles anzeigen
 Kopieren

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

Bau eines Dagger-Graphen

Der Primitiv des Baus eines 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
Alles anzeigen
 Kopieren

Im Wesentlichen wird ein Graph mit einem einzigen Knoten begonnen, sha3(seed), und von dort aus werden nacheinander weitere Knoten auf der Grundlage zufälliger vorheriger Knoten hinzugefügt. Wenn ein neuer Knoten erstellt wird, wird eine modulare Potenz des Seeds berechnet, um zufällig einige Indizes auszuwählen, die kleiner sind als i (bei 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, welcher dann in eine kleine Proof-of-Work-Funktion (auf XOR-Basis) hinzugegeben wird, um letztlich den Wert des Graphen an Index i zu generieren. Der Grundgedanke hinter diesem speziellen Design ist, einen sequentiellen Zugriff auf den DAG zu erzwingen; der nächste Wert des DAG, auf den zugegriffen wird, kann nicht bestimmt werden, bis der aktuelle Wert bekannt ist. Schließlich wird das Ergebnis durch modulare Potenzierung weiter gehasht.

Dieser Algorithmus stützt sich auf mehrere Ergebnisse aus der Zahlentheorie. Schauen Sie sich den unteren Zusatz mit einer Diskussion an.

Light-Client-Bewertung

Die oben beschriebene Konstruktion des Graphen soll es ermöglichen, jeden Knoten des Graphen zu rekonstruieren, indem ein Unterbaum mit nur wenigen Knoten berechnet wird und wobei nur nur eine geringe Menge an Zusatzspeicher notig ist. Beachten Sie, dass mit „k=1“ dieser Unterbaum nur eine Kette von Werten ist, die sich bis zum ersten Element im DAG hochziehen.

Diese 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)
Alles anzeigen
 Kopieren

Im Wesentlichen handelt es sich einfach um eine neue Implementierung des obigen Algorithmus, bei der die Schleife zur Berechnung der Werte für den gesamten DAG entfällt und die frühere Knotensuche durch einen rekursiven Aufruf oder eine Cache-Suche ersetzt wird. Beachten Sie, dass für k=1 der Cache unnötig ist, obwohl eine weitere Optimierung die ersten paar Tausend Werte der DAG vorab berechnet und diese als statischen Cache für Berechnungen aufbewahrt; im Zusatz finden Sie eine entsprechende Code-Implementierung.

Doppelte DAG-Puffer

In einem vollen Client wird ein doppelter Puffer(opens in a new tab) von 2 DAGs verwendet, die mithilfe der obigen Formel produziert wurden. Der Gedanke dahinter ist, dass DAGs jede epochtime Anzahl von Blöcken entsprechend den obigen Parametern erzeugt werden. Der Client verwendet nicht den zuletzt erstellten DAG, sondern den vorherigen. Das hat den Vorteil, dass die DAGs im Laufe der Zeit ersetzt werden können, ohne dass ein Schritt eingefügt 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. Dadurch könnte es 51-%-Angriffe in diesen wenigen Minuten geben, bevor alle Daten neu berechnet sind.

Der Algorithmus für das Generieren des DAG-Sets zur Berechnung der Arbeit für einen Block ist 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        # 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"]}}
Alles anzeigen
 Kopieren

Hashimoto

Die Idee hinter dem ursprünglichen Hashimoto besteht darin, die Blockchain als Datensatz zu nutzen, 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 Konsistenz halber in Python übersetzt – 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)
 Kopieren

Leider gilt Hashimoto zwar als RAM-intensiv, jedoch basiert er auf einer 256-Bit-Arithmetik, die eine erhebliche Rechenlast verursacht. Dagger-Hashimoto verwendet jedoch nur die 64 am wenigsten signifikanten Bits, wenn er seinen Datensatz indiziert, um dieses Problem zu lösen.

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)
 Kopieren

Der Einsatz von Doppel-SHA3 ermöglicht eine Form der sofortigen Vorab-Verifizierung ohne Datenübertragung, bei der lediglich geprüft wird, ob ein korrekter Zwischenwert bereitgestellt wurde. Diese äußere Schicht von Proof-of-Work ist äußerst ASIC-freundlich und relativ schwach ausgelegt. Sie existiert jedoch, um DDoS-Angriffe noch weiter zu erschweren, da dieser kleine Arbeitsaufwand erbracht werden muss, um einen Block zu erzeugen, 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)
 Kopieren

Mining und Verifizierung

Nun setzen wir das alles in einem Mining-Algorithmus zusammen:

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
Alles anzeigen
 Kopieren

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
 Kopieren

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
 Kopieren

Beachten Sie außerdem, dass Dagger-Hashimoto zusätzliche Anforderungen an den Blockheader stellt:

• Damit eine Verifizierung mit zwei Ebenen funktioniert, muss ein Block-Header sowohl die Nonce als auch den mittleren Wert vor sha3 haben.
• Irgendwo muss ein Block-Header den sha3 des aktuellen Seed-Sets speichern.

Weiterführende Informationen

Kennst du eine Community-Ressource, die dir geholfen hat? Bearbeite diese Seite und füge sie hinzu!

Anhang

Wie oben erwähnt, basiert der für die DAG-Generierung verwendete RNG auf einigen Ergebnissen aus der Zahlentheorie. Zunächst stellen wir sicher, dass der Lehmer-RNG, welcher die Grundlage für die Variable picker bildet, eine lange Periode besitzt. Im zweiten Schritt zeigen wir, dass pow(x,3,P) x nicht 1 oder P-1 zuordnet, sofern x ∈ [2,P-2] als Startwert gilt. Schließlich zeigen wir, dass pow(x,3,P) eine niedrige Kollisionsrate hat, wenn es als Hashing-Funktion behandelt wird.

Lehmer-Zufallszahlengenerator

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

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

1xᵐ mod P ≡ 1

Beobachtung 1. Lassen Sie x ein Mitglied der multiplikativen Gruppe ℤ/Pℤ für eine sichere Primzahl P sein. Bei x mod P ≠ 1 mod P und x mod P ≠ P-1 mod P 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 wir gemäß dem Little Theorem von Fermat Folgendes haben:

1xP-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, weil dies die Aussage verletzen würde, dass P eine Primzahl ist.

Aus dem obigen Vorschlag können wir erkennen, dass die Iteration von (picker * init) % P eine Zykluslänge von mindestens (P-1)/2 hat. Das liegt daran, dass wir P als sichere Primzahl gewählt haben, die etwa einer höheren Potenz von zwei entspricht, und init im Intervall [2,2**256+1] liegt. Angesichts der Größe von P sollten wir niemals einen Zyklus aus der modularen Potenzierung 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 stellt dies nicht sicher, 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 eine Folgerung aus Beobachtung 1 ist:

Beobachtung 2. x sei ein Element der multiplikativen Gruppe ℤ/Pℤ für eine sichere Primzahl P, und w sei 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 xʷ mod P ≠ 1 mod P und xʷ mod P ≠ P-1 mod P.

Modulare Potenzierung als Hash-Funktion

Bei bestimmten Werten von P und w kann es bei der Funktion pow(x, w, P) zu zahlreichen Kollisionen kommen. Beispielsweise nimmt pow(x,9,19) nur die Werte {1,18} an.

Wenn P eine Primzahl ist, kann ein geeignetes w für eine Hash-Funktion zur modularen Potenzierung mithilfe des folgenden Ergebnisses ausgewählt werden:

Beobachtung 3. P sei eine Primzahl; w und P-1 sind nur dann teilerfremd, wenn für alle a und b in ℤ/Pℤ Folgendes gilt:

„aʷ mod P ≡ bʷ mod P“ gilt nur dann, wenn „a mod P ≡ b mod P“

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

Im 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 ist, 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)
Alles anzeigen
 Kopieren