Passer au contenu principal
Change page

Dagger-Hashimoto

Dagger-Hashimoto était l'implémentation de recherche et la spécification d'origine pour l'algorithme de minage d'Ethereum. Dagger-Hashimoto a été remplacé par Ethash. Le minage a été complètement désactivé lors de La Fusion le 15 septembre 2022. Depuis lors, Ethereum est sécurisé à l'aide d'un mécanisme de preuve d'enjeu (PoS) à la place. Cette page est à des fins d'intérêt historique - les informations ici ne sont plus pertinentes pour l'Ethereum post-Fusion.

Prérequis

Pour mieux comprendre cette page, nous vous recommandons de vous renseigner d'abord sur le consensus par preuve de travail (PoW), le minage et les algorithmes de minage.

Dagger-Hashimoto

Dagger-Hashimoto vise à satisfaire deux objectifs :

  1. Résistance aux ASIC : l'avantage de créer du matériel spécialisé pour l'algorithme doit être aussi faible que possible.
  2. Vérifiabilité par client léger : un bloc doit pouvoir être vérifié efficacement par un client léger.

Avec une modification supplémentaire, nous précisons également comment atteindre un troisième objectif si souhaité, mais au prix d'une complexité accrue :

Stockage complet de la chaîne : le minage devrait nécessiter le stockage de l'état complet de la chaîne de blocs (en raison de la structure irrégulière du trie d'état d'Ethereum, nous prévoyons qu'un certain élagage sera possible, en particulier pour certains contrats souvent utilisés, mais nous voulons minimiser cela).

Génération du DAG

Le code de l'algorithme sera défini en Python ci-dessous. Tout d'abord, nous donnons encode_int pour la conversion d'entiers non signés d'une précision spécifiée en chaînes de caractères. Son inverse est également donné :

Nous supposons ensuite que sha3 est une fonction qui prend un entier et renvoie un entier, et que dbl_sha3 est une fonction double-sha3 ; si vous convertissez ce code de référence en une implémentation, utilisez :

Paramètres

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

P dans ce cas est un nombre premier choisi de telle sorte que log₂(P) soit juste légèrement inférieur à 512, ce qui correspond aux 512 bits que nous avons utilisés pour représenter nos nombres. Notez que seule la seconde moitié du DAG a réellement besoin d'être stockée, de sorte que l'exigence de RAM de facto commence à 1 Go et augmente de 441 Mo par an.

Construction du graphe Dagger

La primitive de construction du graphe Dagger est définie comme suit :

Essentiellement, il démarre un graphe sous la forme d'un seul nœud, sha3(seed), et à partir de là, commence à ajouter séquentiellement d'autres nœuds en fonction de nœuds précédents aléatoires. Lorsqu'un nouveau nœud est créé, une puissance modulaire de la graine est calculée pour sélectionner aléatoirement certains indices inférieurs à i (en utilisant x % i ci-dessus), et les valeurs des nœuds à ces indices sont utilisées dans un calcul pour générer une nouvelle valeur pour x, qui est ensuite introduite dans une petite fonction de preuve de travail (basée sur XOR) pour finalement générer la valeur du graphe à l'indice i. La logique derrière cette conception particulière est de forcer l'accès séquentiel au DAG ; la prochaine valeur du DAG qui sera accédée ne peut pas être déterminée tant que la valeur actuelle n'est pas connue. Enfin, l'exponentiation modulaire hache davantage le résultat.

Cet algorithme s'appuie sur plusieurs résultats de la théorie des nombres. Voir l'annexe ci-dessous pour une discussion.

Évaluation par client léger

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

La fonction de calcul du client léger pour le DAG fonctionne comme suit :

Essentiellement, il s'agit simplement 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 recherche de nœud précédente par un appel récursif ou une recherche dans le cache. Notez que pour k=1, le cache n'est pas nécessaire, bien qu'une optimisation supplémentaire précalcule en fait les quelques milliers de premières valeurs du DAG et les conserve comme cache statique pour les calculs ; voir l'annexe pour une implémentation de code de ceci.

Double tampon de DAG

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

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

Hashimoto

L'idée derrière le Hashimoto original est d'utiliser la chaîne de blocs comme un ensemble de données, en effectuant un calcul qui sélectionne N indices de la chaîne de blocs, rassemble les transactions à ces indices, effectue un XOR de ces données et renvoie le hash du résultat. L'algorithme original de Thaddeus Dryja, traduit en Python pour des raisons de cohérence, est le suivant :

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)

Malheureusement, bien que Hashimoto soit considéré comme exigeant en RAM, il s'appuie sur une arithmétique 256 bits, ce qui entraîne une surcharge de calcul considérable. Cependant, Dagger-Hashimoto n'utilise que les 64 bits de poids faible lors de l'indexation de son ensemble de données pour résoudre ce problème.

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)

L'utilisation du double SHA3 permet une forme de pré-vérification quasi instantanée sans données, vérifiant uniquement qu'une valeur intermédiaire correcte a été fournie. Cette couche externe de preuve de travail est très favorable aux ASIC et assez faible, mais existe pour rendre les attaques DDoS encore plus difficiles, car cette petite quantité de travail doit être effectuée afin de produire un bloc qui ne sera pas rejeté immédiatement. Voici la version pour client léger :

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)

Minage et vérification

Maintenant, rassemblons tout cela dans l'algorithme de minage :

Voici l'algorithme de vérification :

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

Vérification adaptée aux clients légers :

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

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

  • Pour que la vérification à deux couches fonctionne, un en-tête de bloc doit comporter à la fois le nonce et la valeur intermédiaire pré-sha3
  • Quelque part, un en-tête de bloc doit stocker le sha3 de l'ensemble de graines actuel

Complément d'information

Vous connaissez une ressource communautaire qui vous a aidé ? Modifiez cette page et ajoutez-la !

Annexe

Comme indiqué ci-dessus, le RNG (générateur de nombres aléatoires) utilisé pour la génération du DAG s'appuie sur certains résultats de la théorie des nombres. Premièrement, nous garantissons que le RNG de Lehmer qui est à la base de la variable picker a une large période. Deuxièmement, nous montrons que pow(x,3,P) ne mappera pas x sur 1 ou P-1 à condition que 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 nombres aléatoires de Lehmer

Bien que la fonction produce_dag n'ait pas besoin de produire des nombres aléatoires non biaisés, une menace potentielle est que seed**i % P ne prenne qu'une poignée de valeurs. Cela pourrait donner un avantage aux mineurs reconnaissant le modèle par rapport à ceux qui ne le font pas.

Pour éviter cela, on fait appel à un résultat de la théorie des nombres. Un nombre premier sûr (opens in a new tab) est défini comme étant un nombre premier P tel que (P-1)/2 est également premier. L'ordre d'un membre x du groupe multiplicatif (opens in a new tab) ℤ/nℤ est défini comme étant le m minimal tel que 

xᵐ mod P ≡ 1
Compte tenu de ces définitions, nous avons :

Observation 1. Soit x un membre du groupe multiplicatif ℤ/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ûr, alors par le [théorème de Lagrange][lagrange] nous avons que l'ordre de x est soit 1, 2, (P-1)/2, ou P-1.

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

xP-1 mod P ≡ 1

Par conséquent, x doit être une identité multiplicative de ℤ/nℤ, qui est unique. Puisque nous avons supposé que x ≠ 1 par hypothèse, ce n'est pas possible.

L'ordre de x ne peut pas être 2 à moins que x = P-1, car cela violerait le fait que P est premier.

À partir de la proposition ci-dessus, nous pouvons reconnaître que l'itération de (picker * init) % P aura une longueur de cycle d'au moins (P-1)/2. C'est parce 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]. Étant donné la magnitude de P, nous ne devrions jamais nous attendre à un cycle de l'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 avons l'assurance supplémentaire suivante, qui est un corollaire de l'Observation 1 :

Observation 2. Soit x un membre du groupe multiplicatif ℤ/Pℤ pour un nombre premier sûr P, et soit w un entier naturel. Si x mod P ≠ 1 mod P et x mod P ≠ P-1 mod P, ainsi que 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

L'exponentiation modulaire comme fonction de hachage

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

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

Observation 3. Soit P un nombre premier ; w et P-1 sont premiers entre eux si et seulement si pour tout a et b dans ℤ/Pℤ :

aʷ mod P ≡ bʷ mod P si et seulement si a mod P ≡ b mod P

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

Dans le cas particulier où P est un nombre premier sûr comme nous l'avons sélectionné, alors P-1 n'a que les facteurs 1, 2, (P-1)/2 et P-1. Puisque P > 7, nous savons que 3 est premier avec P-1, par conséquent w=3 satisfait la proposition ci-dessus.

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