Dagger-Hashimoto

Dagger-Hashimoto représentait l'implémentation et la spécification originales de recherche pour l'algorithme de minage d'Ethereum. Dagger-Hashimoto a été remplacé par Ethash. Le minage a été complètement arrêté avec La Fusion du 15 septembre 2022. Depuis lors, Ethereum a été sécurisé en utilisant à la place un mécanisme de preuve d'enjeu. Cette page a un intérêt historique - l'information fournie n'est plus pertinente depuis La Fusion Ethereum.

Prérequis

Pour mieux comprendre cette page, nous vous recommandons de lire d'abord le consensus de preuve de travail, le minage, et les algorithmes de minage.

Dagger-Hashimoto vise à satisfaire deux objectifs :

Résistance aux ASIC : l'avantage de créer du matériel spécialisé pour l'algorithme devrait être aussi faible que possible
Vérification possible par les clients allégés : un bloc doit être vérifié efficacement par un client allégé.

Avec une modification supplémentaire, et si cela vous intéresse, nous vous spécifierons également comment réaliser un troisième objectif mais au prix d'une complexité supplémentaire :

Le stockage de chaîne complète : le minage doit nécessiter un stockage de l'état de la blockchain complète (en raison de la structure irrégulière de la tentative d'état d'Ethereum, nous nous attendons à ce qu'un certain raccourcissement soit possible, en particulier pour certains contrats souvent utilisés tout en minimisant ceci).

Génération DAG

Le code de l'algorithme sera défini ci-dessous en Python. Premièrement, nous donnons un encode_int pour le marquage des entiers non signés de précision spécifiés aux chaînes de caractères. L'inverse est également donné :

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
Afficher tout
 Copier

Nous supposons maintenant que sha3 est une fonction qui prend un entier et donne un entier, et dbl_sha3 est une fonction double-sha3 ; si vous convertissez ce code de référence dans une utilisation d'implémentation :

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)))
Afficher tout
 Copier

Paramètres

Les paramètres utilisés pour l'algorithme sont :

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}
Afficher tout
 Copier

Dans ce cas P est une prime choisie telle que log₂(P) soit juste un peu en deçà de 512, qui correspond aux 512 bits que nous utilisons pour représenter nos nombres. Notez que seule la dernière moitié du DAG doit être stockée, ainsi le besoin de mémoire commence de fait à 1 Go et augmente de 441 Mo par an.

Construction graphique Dagger

La construction graphique Dagger primitive est définie comme suit :

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
Afficher tout
 Copier

Essentiellement, cela commence par un graphique en tant que nœud unique, sha3(seed), puis, à partir de ce stade, comment l'ajout séquentiel sur d'autres nœuds basés sur des nœuds précédents aléatoires. Lorsqu'un nouveau nœud est créé, la puissance modulaire de la graine est calculée pour sélectionner aléatoirement des indices inférieurs à i (en utilisant x % i ci-dessus), et les valeurs des noeuds au regard de ces indices sont utilisées dans un calcul pour générer une nouvelle valeur pour x, qui est ensuite alimentée par une fonction de preuve de travail sommaire (basée sur XOR) pour finalement générer la valeur du graphique à l'indice i. La raison d'être de cette conception particulière est de forcer l'accès séquentiel du DAG ; la valeur suivante du DAG qui sera accessible ne peut pas être déterminée tant que la valeur courante n'est pas connue. Enfin, l’exponentiation modulaire permet de hacher le résultat.

Cet algorithme repose sur plusieurs résultats de la théorie des nombres. Consultez l'annexe ci-dessous à des fins de discussion.

Évaluation du client allégé

La construction du graphique ci-dessus vise à permettre à chaque nœud du graphique d'être reconstruit en calculant une sous-arborescence d'un petit nombre de nœuds et en ne nécessitant qu'une petite quantité de mémoire auxiliaire. Notez qu'avec k=1, la sous-arborescence n'est qu'une chaîne de valeurs allant jusqu'au premier élément du DAG.

Pour que le DAG fonctionne, la fonction de calcul du client allégé est la suivante :

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)
Afficher tout
 Copier

Il s'agit essentiellement d'une réécriture de l'algorithme ci-dessus qui supprime la boucle de calcul des valeurs pour l'ensemble du DAG et remplace la précédente recherche du nœud par un appel récursif ou une recherche de cache. Notez que pour k=1 le cache n'est pas nécessaire, bien qu'une optimisation supplémentaire calcule au préalable en fait les premiers milliers de valeurs du DAG et conserve cela en tant que cache statique pour les calculs ; voir l'annexe pour une implémentation de code de cette fonction.

Double tampon de DAG

Dans un client complet, un double tampon(opens in a new tab) de 2 DAG produit par la formule ci-dessus est utilisé. L'idée est que les DAG produisent tous les nombres de blocs epochtime selon les paramètres ci-dessus. Au lieu d'utiliser le dernier DAG produit, le client utilise le précédent. L'avantage est qu'il permet aux DAG d'être remplacés au fil du temps sans avoir besoin d'incorporer une étape où les mineurs devraient soudainement recalculer toutes les données. Sinon, il existe un risque de ralentissement brutal et temporaire du traitement en chaîne à intervalles réguliers et d'augmentation spectaculaire de la centralisation. Ainsi, il existe un risque d'attaques de 51% au cours de ces quelques minutes avant que toutes les données ne soient recalculées.

L'algorithme utilisé pour générer l'ensemble des DAG utilisés pour calculer le travail d'un bloc est le suivant :

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"]}}
Afficher tout
 Copier

Hashimoto

L'idée derrière le Hashimoto original est d'utiliser la blockchain comme jeu de données, effectuant un calcul qui sélectionne N indices de la blockchain, rassemble les transactions sur ces indices, exécute un XOR de ces données, et retourne le hachage du résultat. L'algorithme original de Thaddeus Dryja, traduit en Python pour la cohérence, est le suivant :

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

Malheureusement, bien que Hashimoto soit considéré comme de la RAM en dur, il repose sur l'arithmétique 256-bit, qui présente des frais supplémentaires de calcul considérables. Cependant, Dagger-Hashimoto n'utilise que les 64 bits les moins significatifs lors de l'indexation de son jeu de données pour résoudre ce problème.

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

L'utilisation du double SHA3 permet à un formulaire de zéro donnée, une pré-vérification quasi instantanée, vérifiant uniquement qu'une valeur intermédiaire correcte a été fournie. Cette couche extérieure de preuve de travail est très favorable aux ASIC et assez faible, mais existe pour rendre les attaques DDoS encore plus difficiles puisque cette petite quantité de travail doit être réalisée pour produire un bloc qui ne sera pas immédiatement rejeté. Voici la version client allégé :

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

Minage et vérification

Maintenant, mettons tout cela ensemble dans l'algorithme de minage :

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
Afficher tout
 Copier

Voici l'algorithme de vérification :

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
 Copier

Vérification conviviale du client allégé :

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
 Copier

Notez également que Dagger-Hashimoto impose des exigences supplémentaires à l'en-tête du bloc:

Pour que la vérification de deux couches fonctionne, un en-tête de bloc doit avoir à la fois la valeur nonce et la valeur moyenne pré-sha3
Quelque part, un en-tête de bloc doit stocker la sha3 de l'actuel ensemble de données

Complément d'information

Une ressource communautaire vous a aidé ? Modifiez cette page et ajoutez-la !

Annexe

Comme mentionné ci-dessus, le RNG utilisé pour la génération de DAG repose sur des résultats tirés de la théorie des nombres. Premièrement, nous fournissons l'assurance que le RNG Lehmer qui est la base de la variable picker dispose d'une période longue. Deuxièmement, nous montrons que pow(x,3,P) ne fera pas correspondre x à 1 ou P-1 fourni x ∈ [2,P-2] pour commencer. Enfin, nous montrons que pow(x,3,P) a un faible taux de collision lorsqu'il est traité comme une fonction de hachage.

Générateur de nombre aléatoire Lehmer

Alors que la fonction produce_dag n'a pas besoin de produire des nombres aléatoires impartiaux, une menace potentielle est que seed**i % P prenne uniquement une poignée de valeurs. Cela pourrait être un avantage pour les mineurs qui reconnaissent le modèle par rapport à ceux qui ne le font pas.

Pour éviter cela, un résultat de la théorie du nombre est exercé. Un Safe Prime(opens in a new tab) est défini comme un premier P tel que (P-1)/2 est également un nombre premier. L'ordre d'un membre x du groupe multiplicateur(opens in a new tab) ℤ/nℤ est défini pour être le minimum m tel que

1xᵐ mod P ≡ 1

Compte tenu de ces définitions, nous avons :

Observation 1. Laisser x être un membre du groupe multiplicateur ℤ/Pℤ pour un nombre premier sûr P. Si x mod P ≠ 1 mod P et x mod P ≠ P-1 mod P, alors l'ordre de x est soit P-1 soit (P-1)/2.

Preuve. Puisque P est un nombre premier sécurisé, puis par [Lagrange's Theorem][lagrange] nous trouvons que l'ordre de x est soit 1, 2, (P-1)/2, soit P-1.

L'ordre de x ne peut pas être 1, puisque suivant le petit théorème de Fermat, nous avons :

1xP-1 mod P ≡ 1

C'est pourquoi x doit être une identité multiplicative de ℤ/nℤ, ce qui est unique. Puisque nous supposons que x ≠ 1 par hypothèse, ce n'est pas possible.

L'ordre de x ne peut pas être 2 sauf si x = P-1, car cela violerait le principe que P soit un nombre premier.

À partir de la proposition ci-dessus, nous pouvons reconnaître que l'itération (picker * init) % P aura une longueur de cycle d'au moins (P-1)/2. Ceci est dû au fait que nous avons sélectionné P pour être un nombre premier sûr approximativement égal à une puissance supérieure de deux, et init est dans l'intervalle [2,2**256+1]. Compte tenu de la magnitude de P, nous ne devrions jamais nous attendre à un cycle d'exponentiation modulaire.

Lorsque nous assignons la première cellule dans le DAG (la variable étiquetée init), nous calculons pow(sha3(seed) + 2, 3, P). À première vue, cela ne garantit pas que le résultat n'est ni 1 ni P-1. Cependant, puisque P-1 est un nombre premier sûr, nous émettons l'hypothèse supplémentaire suivante, qui est un corollaire de l'observation 1 :

Observation 2. Laissons x être membre du groupe multiplicateur ℤ/Pℤ pour un nombre premier sûr P, et laissons w être un nombre naturel. Si x mod P ≠ 1 mod P et x mod P ≠ P-1 mod P, tout comme w mod P ≠ P-1 mod P et w mod P ≠ 0 mod P, alors xʷ mod P ≠ 1 mod P et xʷ mod P ≠ P-1 mod P

Exponentiation modulaire comme fonction de hachage

Pour certaines valeurs de P et w, la fonction pow(x, w, P) peut présenter de nombreuses collisions. Par exemple, pow(x,9,19) ne prend que les valeurs {1,18}.

Étant donné que P est un nombre premier, alors un w approprié pour une fonction de hachage d'exponentiation modulaire peut être choisi en utilisant le résultat suivant :

Observation 3. Laissez P être un nombre premier ; w et P-1 sont relativement premiers si et seulement si pour tous les a et b en ℤ/Pℤ :
`aʷ mod P ≡ bʷ mod P` si et seulement si `a mod P ≡ b mod P`

Ainsi, étant donné que P est un nombre premier et que w est relativement premier à P-1, nous avons |{pow(x, w, P) : x ∈ ℤ}| = P, ce qui implique que la fonction de hachage a le taux de collision minimal possible.

Dans le cas spécial ou P est un nombre premier sûr comme nous l'avons sélectionné, alors P-1 n'aura que les facteurs 1, 2, (P-1)/2 et P-1. Puisque P > 7, nous savons que 3 est relativement premier à P-1, donc w=3 satisfait la proposition ci-dessus.

Algorithme d'évaluation basé sur un cache plus efficace

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)
Afficher tout
 Copier

Dagger-Hashimoto

Prérequis