L’algorithme pour miner le bitcoin en Python

Cet article décrit une implémentation en python du minage du bitcoin qui s’appuie sur un algorithme basé sur un double hash SHA-256.

bitcoin python algorithme miner minage

Introduction – Principe de l’agorithme de minage du bitcoin

Les mineurs du réseau bitcoin doivent rechercher le nonce qui est un un nombre de 32 bits. Le mineur va tester successivement plusieurs NONCE (1,2,3 ….10^32-1), pour chacun des nonce il crée l’entête suivante et le hasher 2 fois avec une fonction de hachage SHA-256 bits.

FieldDescriptionSize
versionVersion 4
Hash du bloc précédent256-bit hash du block précédent32
Merkle rootIl s’agit d’un hash sur les données du bloc. Il est fournit au mineur et il contient un résumé des transactions qui sont contenues dans le bloc. 32
timeUn timestamp numérique qui représente le nombre de seconde depuis 1970-01-01T00:00 UTC4
bitsLa cible actuelle (Current target) en format compacté4
nonce32-bit number (starts at 0)4

Une fois le hash obtenu le mineur doit ensuite vérifier que le hash obtenu est inférieur au facteur de difficulté cible du bloc. Si le hash obtenu est supérieur alors le nonce n’est pas le bon il faut en tester un autre.

Exemple sur le bloc 671712

Si vous utilisez un explotateur de blochain bitoin (par exemple blocstream info), si on prends par exemple le bloc 671712 :

https://blockstream.info/block/000000000000000000062a949bc297739a12e639ba9e2107638b469afe11d0f8?expand

bitcoin python algorithme miner minage

Dans ce cas voici un algorithme en python qui permet de miner ce bloc :

Dans cette simulation j’affiche le header et le hash calculé ainsi que le hash rate.

Le nonce a trouver pour le bloc 671712 était 4107802144

Soit en hexa : 0xf4d81620

Cette algorithme démarre avec un nonce = 4107802144 – 400 nous allons faire comme si on était à très proche de trouver le bloc (il manque 400 double hash à effectuer pour trouver le bloc) :

import hashlib
from hashlib import sha256
import time
import struct
import binascii
import datetime
from binascii import unhexlify, hexlify
from dateutil import parser
from datetime import datetime
from datetime import timedelta 

nontrouve = True
dtprec = datetime.now()
inonc = 4107802134 - 400 #Starting 400 before the good nonce
resultat = []

while(nontrouve):
    inonc +=1
    if(inonc%50==0):
        print(str(round(timedelta(seconds=1)/(datetime.now() - dtprec))) + ' H/s')
    dtprec = datetime.now()
    header_hex = (binascii.hexlify(struct.Struct('<L').pack(int('0x2fffe000',16))).decode()  + 
     binascii.hexlify(binascii.unhexlify('000000000000000000078908d256fa7a9f97b2e1ea532fb1ce45ee4bf050d221')[::-1]).decode()+
     binascii.hexlify(binascii.unhexlify('c504fc3a406f11c7c5b598da7f50916f4e298041e6f9b91535a80db113af109a')[::-1]).decode() +
     binascii.hexlify(struct.Struct('<L').pack(int(hex(int(parser.parse('2021-02-22 15:14:22 GMT +1').timestamp())-3600),16))).decode() +
     binascii.hexlify(struct.Struct('<L').pack(int("0x170cf4e3",16))).decode() + 
     binascii.hexlify(struct.Struct('<L').pack(int(hex(inonc),16))).decode()) 
    header_bin = unhexlify(header_hex)
    dt1 = datetime.now().strftime("%H:%M:%S.%f")
    hash = hashlib.sha256(hashlib.sha256(header_bin).digest()).digest()
    hexlify(hash).decode("utf-8")
    hexlify(hash[::-1]).decode("utf-8")
    hash=hexlify(hash[::-1]).decode("utf-8") 
    resultat.append([round(int(hash,16)/10**65)])
    
    MAX_TARGET = int("00000000FFFF0000000000000000000000000000000000000000000000000000", 16)           
    Difficulty = 21724134900047.27                     
    target = int(MAX_TARGET / Difficulty)
    target32 = '{:0>64x}'.format(target)    
    if(int(hash,16) < int(target32,16)):
        print('###########BLOC MINED###################')
        print('HEADER=' + header_hex)
        print('HASH=' + hash)
        print('NONCE=' + str(inonc))
        print('NONCE (hex)=' + hex(inonc))
        print('###########BLOC MINED###################')
        break

La sortie est la suivante :

1149 H/s
4405 H/s
4115 H/s
1534 H/s
3831 H/s
2392 H/s
4386 H/s
3165 H/s
###########BLOC MINED###################
HEADER=00e0ff2f21d250f04bee45ceb12f53eae1b2979f7afa56d20889070000000000000000009a10af13b10da83515b9f9e64180294e6f91507fda98b5c5c7116f403afc04c53ebc3360e3f40c172016d8f4
HASH=000000000000000000062a949bc297739a12e639ba9e2107638b469afe11d0f8
NONCE=4107802144
NONCE (hex)=0xf4d81620
###########BLOC MINED###################

Lien externe – minage de bitcoin en python

https://en.bitcoin.it/wiki/Block_hashing_algorithm

Lien interne

http://128mots.com/index.php/2020/03/30/construire-une-application-decentralisee-full-stack-pas-a-pas-ethereum-blockchain-dapp-en-plus-de-128-mots-partie-1/

Implémentation des graphes en Python – Exemple BFS

Implémentation des graphes en Python par l’exemple : Le parcours en largeur python d’un graphe (BFS) est un algorithme utilisé pour parcourir les structures de donnée de graphe. BFS met en œuvre une stratégie spécifique pour visiter tous les sommets d’un graphe.

Introduction – Implémentation des graphes en Python

BFS commence par un sommet, puis il vérifie les voisins du sommet initial, puis les voisins des voisins, etc.

En entrée de l’algorithme il y a le graphe G et un sommet de départ D pour lequel on considère que la distance est 0.

En sortie de l’algorithme sont calculées toutes les distances entre le sommet D et chaque sommet du graphe G ainsi que l’arbre couvrant si le graphe G est connexe (c’est à dire que pour toute paire de sommet il existe un chemin entre eux dans le graphe).

Description de l’algorithme

On utilise les tableaux suivants :

  • Distance[.] : Stocke la distance entre D (sommet de départ) et un autre sommet du graphe.
  • Father[.] : Stocke le sommet père d’un sommet du graphe parcouru.
  • Visite[.] : Stocke l’état de visite du sommet, liste des valeurs possible 0:pas encore visité,1:Visite en cours,2:Visité

On utilise les fonctions suivantes pour une file F :

  • First(F) : Retourne l’élément en tête de la file F sans le supprimer.
  • Dequeue(F) : Retourne l’élément en tête de la file F en le supprimant.
  • Append(F, A) : Mettre l’élément A dans la file F en queue de la file.

Les étapes de l’algorithme :

  • Phase d’initialisation
    • 1. Pour tous les sommets faire
      • Visite = 0 (Pas encore visité)
      • Pere = null (Initialise le tableau)
      • Distance = -1
    • 2. Append(F,D) (ajoute l’élément de départ)
    • 3. Distance[R] = 0 (postulat de départ)
  • Phase d’action (parcours du graphe G)
    • Tant que la file F n’est pas vide
      • t = First(F)
      • Pour tous les voisins v de t faire
        • Si Visite[v] = 0 (sommet non visité) alors
          • Visite[v] = 1 (Visite en cours)
          • Distance[v] = Distance[t] + 1
          • Father[v] = t
          • Append(F,v)
      • Dequeue(F)
      • Visite[t] = 2

Si on détaille les étapes avec le cas du graphe exemple ci-dessous.

Phase d’initialisation :

Implémentation des graphes en python par l'exemple : Le parcours en largeur python d'un graphe, algorithme utilisé pour parcourir les graphes.

Initialisation l’élément A est l’élément de départ à distance 0, il est coloré en orange pour indiquer que la visite est en cours.

Visite des voisins du sommet A (Visite du sommet B)

Parcours en largeur Python - Algorithme sur les Graphes
Le sommet B passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

implémentation des graphes en python – Visite des voisins du sommet A (Visite du sommet C)

Implémentation des graphes en python par l'exemple : Le parcours en largeur python d'un graphe, algorithme utilisé pour parcourir les graphes.
Le sommet C passe à en cours de visite, sa distance de A est calculée et le sommet A est ajouté comme sommet père. Il est ajouté à la file.

Marquage de A comme visité et suppression de la file

Parcours en largeur Python - Algorithme sur les Graphes
A est marqué comme visité (couleur bleue) et retiré de la tête de la file

Visite des voisins du sommet B (Visite du sommet D)

Le sommet C etant marqué comme en cours de visite il ne sera pas visité, on visite le sommet D on calcule sa distance = 2 et on note le sommet B comme père du sommet B.

Marquage de B et C comme visité et suppression de la file

B est marqué comme visité (couleur bleue) et retiré de la tête de la file
C est marqué comme visité (couleur bleue) et retiré de la tête de la file (son voisin D est marqué en cours de visite)

Marquage de D comme visité et fin de l’algorithme

D est marqué comme visité (couleur bleue) et retiré de la tête de la file.
Fin de l’algorithme

Construction de l’arbre couvrant si le graphe est connexe

Si le graphe est connexe on déplie le résultat du parcours et on obtient l’arbre couvrant du graphe qui contient tous les sommets.

Application : Le parcours en largeur d’un graphe (BFS) est utile pour :

  • Vérifier si un graphe est connexe (tous les sommets sont alors marqués comme visités à la fin de l’algorithme).
  • Calculer les distances à partir d’un sommet donné
  • Construire un arbre couvrant du graphe
from collections import deque
def bfs(graph, vertex):
    queue = deque([vertex])
    distance = {vertex: 0}
    pere = {vertex: None}
    while queue:
      t = queue.popleft()
      for voisin in graph[t]:
        if voisin not in distance:
          queue.append(voisin)
          distance[voisin] = distance[t] + 1
          pere[voisin] = t
    return distance, pere
#Liste d'ajacence du graphe
graph = {
  'A': ['B','C'],
  'B': ['A','C', 'D'],
  'C': ['D'],
  'D': ['C','A']
}
distance,pere = bfs(graph,'A')
print("Distances" + str(distance))
print("Pere = " + str(pere))

Parcours en largeur python – Liens externes

https://fr.wikipedia.org/wiki/Python_(langage)

https://www.python.org/

https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur

Implémentation des graphes en python – Liens internes

http://128mots.com/index.php/category/python/

http://128mots.com/index.php/2021/01/21/algorithme-glouton-python/