Passer au contenu principal
Change page

Ethash

Ethash était l'algorithme de minage par preuve de travail (PoW) d'Ethereum. La preuve de travail a maintenant été entièrement désactivée et Ethereum est désormais sécurisé en utilisant la preuve d'enjeu (PoS) à la place. Pour en savoir plus, consultez La Fusion, la preuve d'enjeu et le staking. Cette page est conservée à des fins historiques !

Ethash est une version modifiée de l'algorithme Dagger-Hashimoto. La preuve de travail d'Ethash est difficile en mémoire (opens in a new tab) (memory hard), ce qui était censé rendre l'algorithme résistant aux ASIC. Des ASIC Ethash ont finalement été développés, mais le minage par GPU est resté une option viable jusqu'à ce que la preuve de travail soit désactivée. Ethash est toujours utilisé pour miner d'autres cryptomonnaies sur d'autres réseaux à preuve de travail non-Ethereum.

Comment fonctionne Ethash ?

La difficulté en mémoire est obtenue grâce à un algorithme de preuve de travail qui nécessite de choisir des sous-ensembles d'une ressource fixe dépendant du nonce et de l'en-tête de bloc. Cette ressource (d'une taille de quelques gigaoctets) est appelée un DAG. Le DAG est modifié tous les 30 000 blocs, une fenêtre d'environ 125 heures appelée une époque (environ 5,2 jours) et prend un certain temps à générer. Puisque le DAG ne dépend que de la hauteur du bloc, il peut être pré-généré, mais s'il ne l'est pas, le client doit attendre la fin de ce processus pour produire un bloc. Si les clients ne pré-génèrent pas et ne mettent pas en cache les DAG à l'avance, le réseau peut subir un retard massif de blocs à chaque transition d'époque. Notez que le DAG n'a pas besoin d'être généré pour vérifier la preuve de travail, ce qui permet essentiellement une vérification avec un faible processeur (CPU) et une petite mémoire.

Le cheminement général que suit l'algorithme est le suivant :

  1. Il existe une graine (seed) qui peut être calculée pour chaque bloc en parcourant les en-têtes de bloc jusqu'à ce point.
  2. À partir de la graine, on peut calculer un cache pseudo-aléatoire de 16 Mo. Les clients légers stockent le cache.
  3. À partir du cache, nous pouvons générer un ensemble de données de 1 Go, avec la propriété que chaque élément de l'ensemble de données ne dépend que d'un petit nombre d'éléments du cache. Les clients complets et les mineurs stockent l'ensemble de données. L'ensemble de données croît de manière linéaire avec le temps.
  4. Le minage implique de récupérer des tranches aléatoires de l'ensemble de données et de les hacher ensemble. La vérification peut être effectuée avec peu de mémoire en utilisant le cache pour régénérer les morceaux spécifiques de l'ensemble de données dont vous avez besoin, vous n'avez donc besoin de stocker que le cache.

Le grand ensemble de données est mis à jour une fois tous les 30 000 blocs, de sorte que la grande majorité des efforts d'un mineur consistera à lire l'ensemble de données, et non à y apporter des modifications.

Définitions

Nous employons les définitions suivantes :

L'utilisation de 'SHA3'

Le développement d'Ethereum a coïncidé avec le développement de la norme SHA3, et le processus de normalisation a apporté une modification tardive au remplissage (padding) de l'algorithme de hash finalisé, de sorte que les hashs "sha3_256" et "sha3_512" d'Ethereum ne sont pas des hashs sha3 standards, mais une variante souvent appelée "Keccak-256" et "Keccak-512" dans d'autres contextes. Voir la discussion, par exemple, ici (opens in a new tab), ici (opens in a new tab), ou ici (opens in a new tab).

Veuillez garder cela à l'esprit car les hashs "sha3" sont mentionnés dans la description de l'algorithme ci-dessous.

Paramètres

Les paramètres pour le cache et l'ensemble de données d'Ethash dépendent du numéro de bloc. La taille du cache et la taille de l'ensemble de données croissent toutes deux de manière linéaire ; cependant, nous prenons toujours le nombre premier le plus élevé en dessous du seuil de croissance linéaire afin de réduire le risque de régularités accidentelles conduisant à un comportement cyclique.

Des tableaux des valeurs de taille de l'ensemble de données et du cache sont fournis en annexe.

Génération du cache

Maintenant, nous spécifions la fonction pour produire un cache :

Le processus de production du cache implique d'abord de remplir séquentiellement 32 Mo de mémoire, puis d'effectuer deux passages de l'algorithme RandMemoHash de Sergio Demian Lerner issu de Strict Memory Hard Hashing Functions (2014) (opens in a new tab). La sortie est un ensemble de 524 288 valeurs de 64 octets.

Fonction d'agrégation de données

Nous utilisons un algorithme inspiré du hash FNV (opens in a new tab) dans certains cas comme substitut non associatif au XOR. Notez que nous multiplions le nombre premier avec l'entrée complète de 32 bits, contrairement à la spécification FNV-1 qui multiplie le nombre premier avec un octet à la fois.

FNV_PRIME = 0x01000193

def fnv(v1, v2):
    return ((v1 * FNV_PRIME) ^ v2) % 2**32

Veuillez noter que, même si le livre jaune spécifie fnv comme v1*(FNV_PRIME ^ v2), toutes les implémentations actuelles utilisent systématiquement la définition ci-dessus.

Calcul de l'ensemble de données complet

Chaque élément de 64 octets dans l'ensemble de données complet de 1 Go est calculé comme suit :

Essentiellement, nous combinons les données de 256 nœuds de cache sélectionnés de manière pseudo-aléatoire, et nous hachons cela pour calculer le nœud de l'ensemble de données. L'ensemble de données complet est ensuite généré par :

def calc_dataset(full_size, cache):
    return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]

Boucle principale

Maintenant, nous spécifions la boucle principale de type "hashimoto", où nous agrégeons les données de l'ensemble de données complet afin de produire notre valeur finale pour un en-tête et un nonce particuliers. Dans le code ci-dessous, header représente le hash SHA3-256 de la représentation RLP d'un en-tête de bloc tronqué, c'est-à-dire d'un en-tête excluant les champs mixHash et nonce. nonce correspond aux huit octets d'un entier non signé de 64 bits dans l'ordre grand-boutiste (big-endian). Ainsi, nonce[::-1] est la représentation petit-boutiste (little-endian) de huit octets de cette valeur :

Essentiellement, nous maintenons un "mélange" (mix) de 128 octets de large, et nous récupérons de manière répétée et séquentielle 128 octets de l'ensemble de données complet et utilisons la fonction fnv pour le combiner avec le mélange. 128 octets d'accès séquentiel sont utilisés afin que chaque tour de l'algorithme récupère toujours une page complète de la RAM, minimisant ainsi les échecs du répertoire des pages (translation lookaside buffer misses) que les ASIC seraient théoriquement capables d'éviter.

Si la sortie de cet algorithme est inférieure à la cible souhaitée, alors le nonce est valide. Notez que l'application supplémentaire de sha3_256 à la fin garantit qu'il existe un nonce intermédiaire qui peut être fourni pour prouver qu'au moins une petite quantité de travail a été effectuée ; cette vérification rapide de la PoW externe peut être utilisée à des fins anti-DDoS. Cela sert également à fournir une assurance statistique que le résultat est un nombre non biaisé de 256 bits.

Minage

L'algorithme de minage est défini comme suit :

def mine(full_size, dataset, header, difficulty):
    # Compléter la cible avec des zéros pour la comparer avec le hash sur le même chiffre
    target = zpad(encode_int(2**256 // difficulty), 64)[::-1]
    from random import randint
    nonce = randint(0, 2**64)
    while hashimoto_full(full_size, dataset, header, nonce) > target:
        nonce = (nonce + 1) % 2**64
    return nonce

Définition du hash de la graine

Afin de calculer le hash de la graine qui serait utilisé pour miner au-dessus d'un bloc donné, nous utilisons l'algorithme suivant :

 def get_seedhash(block):
     s = '\x00' * 32
     for i in range(block.number // EPOCH_LENGTH):
         s = serialize_hash(sha3_256(s))
     return s

Notez que pour un minage et une vérification fluides, nous recommandons de pré-calculer les futurs hashs de graine (seedhashes) et ensembles de données dans un thread séparé.

Lectures complémentaires

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

Annexe

Le code suivant doit être ajouté au début si vous souhaitez exécuter la spécification Python ci-dessus en tant que code.

Tailles des données

Les tables de correspondance suivantes fournissent environ 2048 époques tabulées de tailles de données et de tailles de cache.