Le minage bitcoin

Le minage bitcoin consiste à intégrer des transactions proposées par des utilisateurs dans un cahier de compte officiel, publique et partagé. Miner un bloc de transaction consiste à trouver un identifiant pour ce bloc qui doit être suffisamment rare pour ne pas pouvoir être choisi sans un calcul préalable conséquent. Cela s'appelle du minage, les participants qui se chargent de proposer les identifiants vont devoir essayer de nombreuses valeurs avant de trouver un identifiant possédant une caractéristique particulière et rare. Par exemple un calcul conséquent pourrait être de trouver la millionième décimale de PI, puis la suivante etc ... Chaque nouvelle décimale demande un travail de la part de calculateur. Dans le cas de bitcoin il s'agit de trouver le hash d'un document décrivant un ensemble de transactions. Le hash recherché sert d'identifiant du document et doit commencer par un nombre minimal de caractères '0'. Le hash d'un document est unique. Pour trouver les '0' de début, il faut donc modifier le document sans en changer sa signification, puis relancer la fonction de hash. Par exemple, on calcule avec la fonction md5 les chaînes "test", "test ", "test ". On peut constater qu'elles contiennent toutes la même information test, et que la dernière commence par 2 '0' (ceci est un coup de chance).

md5 "test"   -> b854aa2444158ca0fdd3b70cd2aeedfc  
md5 "test "  -> aec64827aeb5a3a58f81f80a3faaf54c  
md5 "test  " -> 00683b0f4ccefe2932446ba790a10099  

Pour augmenter la difficulté requise, on augmente le nombre de '0' en tête, ce qui devient de plus en plus rare. A titre de comparaison la difficulté actuelle de 16 '0', fait qu'il n'y a qu'une chance sur 1019 (10 exaBytes) de trouver l'identifiant d'un bloc, revenant à chercher un grain de sable particulier à la surface de la terre. De nombreux mineurs travaillent en parallèle pour une puissance cumulée d'essais représentant 25 Million Giga Hash/s (25 petaBytes), ce qui fait un identifiant miné toutes les 10 minutes.

Avant minage, les utilisateurs fabriquent les transactions concernant leurs bitcoins puis les annoncent dans le réseau. Ces transactions ne sont pas officielles tant qu'un membre du réseau ne les a pas intégrés dans le journal. Un mineur écoute les transactions anoncées, les ajoute dans un document local appelé bloc de transactions, mine ce document pour trouver un identifiant, puis en cas de succès, l'insère dans le journal. Les noeuds cumulent en moyenne 300 transactions dans un bloc avant de démarrer le minage. Le noeud mineur possède initialement les données suivantes :

  • Le hash du bloc précédent. C'est à dire le dernier bloc validé qu'il connait du réseau bitcoin.
  • La liste et la description de toutes les transactions qu'il veut intégrer dans son bloc.
  • Un niveau de difficulté courant qui permet de rendre plus ou moins rare l'apparition d'un identifiant correct.

A partir de ces données initiales, les mineurs en compétition ajoutent trois éléments.

  • Le premier élément est une transaction supplémentaire qui lui attribue, si le bloc est effectivement miné, un peu plus de 25 BTC (12000 €) en récompense de son travail. Cette transaction appelée coinbase ou origin possède en description 'TxIn' un champ libre 'coinbase' et un champ numérique 'nonce' qui peut être modifié pour cherger les hashs.
  • Le second élément ajouté à la structure est un hash représentant l'ensemble des transactions du bloc.
  • Le troisième élément est une date de fabrication du bloc.
  • Le dernier élement est un nonce de bloc.

La figure suivante représente la structure finale avant minage.

Avant de démarrer, le mineur effectue les opérations suivantes :

  1. Se synchroniser avec le réseau bitcoin pour connaitre le dernier hash de bloc connu. Accessible ici https://blockexplorer.com/q/latesthash.

  2. Ecouter et cumuler des transactions annoncées.

  3. Ajouter la transaction coinbase d'auto-rémunération.

  4. Calculer le hash général des transactions du bloc.

  5. Ajouter les derniers champs (date, nonce).

Miner un bloc est une opération très simple, mais très longue, et qui n'aboutit que très rarement. L'algorithme de minage est le suivant.

1 Calculer le hash du bloc  
2 Si le hash est suffisamment rare on a gagné  
3 Sinon, modifier une donnée du bloc et recommencer  

A la date d'écriture, le dernier bloc ajouté au journal était 0000000000000000308121DEC45C01C38DA8CD4E9E3B44BC84B1F4D42A6A9448 (256 bits, 64 caractères hexadécimaux). La difficulté au moment de ce calcul imposait que le hash gagnant était inférieur à '00000000000000009d8c00000000000000000000000000000000000000000000'. Pour trouver un hash différent à chaque essai, les nonces permettent de modifier les données du document sans en modifier les transactions décrites. Changer un caractère du document produit une valeur de hash différente mais ne permet pas de se rapprocher de la valeur ciblée. La figure suivante illustre quelques progressions des valeurs de hash en modifiant de 1 le nonce d'un bloc.

On a ici triché, car le bloc choisi est un bloc disponible publiquement qui a déjà été miné. On voit qu'il faut faire tourner la boucle précédente 856192328 fois avant de trouver le résultat. Certains résultats précédent possèdent un certain nombre de 0, mais pas suffisamment pour que le bloc soit considéré suffisamment rare. En trouvant le nonce 856192328 le mineur a prouvé un travail. Ce calcul est en compétition avec d'autres mineurs qui réalisent simultanément les mêmes types d'essais/erreurs. Le premier mineur trouvant un hash de bloc, le diffuse dans le réseau et attend un certain temps avant de pouvoir profiter des bitcoins de récompense. Pour être très clair, miner intégralement un bloc demanderai 35000 ans sur une machine personnelle. Le hazard aidant on peut imaginer tomber sur un bloc avant les autres mineurs tous les 2, 3 ans...

La complexité du minage est réglé toutes les deux semaines, afin que de nouveaux blocs sortent toutes les 10 min. Par construction du protocole, le nombre total de BTC généré est de 21 000 000. Au lancement en Janvier 2009, la récompense était de 50 BTC par bloc miné. Elle est divisée par 2 tous les 21 000 blocs calculés, environ tous les 4 ans. La récompense actuelle est de 25BTC, et l'épuisement des BTC surviendra en 2140. Pour réguler le rythme de découverte d'identifiants valides, le système mesure le temps de création de 2016 blocs, qui doit osciller autour de 2 semaines. Ce qui correspond à un bloc généré toutes les 10min (6 bloc/heure x 24h x 14 j). Si on est inférieur à 2 semaines, on augmente la difficulté, si on est plus rapide, on diminue la difficulté.

Actuellement la valeur du champ difficulté est 6,978,842,649.59. On multiplie cette valeur par une base de compléxité valant 0x00000000FFFF0000000000000000000000000000000000000000000000000000 pour obtenir la valeur maximal du hash recherché. On voit que si la difficulté était de 1, un hash débutant avec 8 '0' serait valide. Avec la valeur courante le hash doit être inférieur à '00000000000000009d8c00000000000000000000000000000000000000000000' (16 '0'), 7 milliards de fois plus complexe que la base initiale.

Il y a de fortes chances qu'il n'existe pas de hash rare correspondant au bloc que vous avez en cours de minage. Il faut donc agir sur les différents paramètres du bloc. Le nonce du bloc peut être incrémenté (jusqu'à une limite max), la date peut être modifiée (de nombreux blocs ne sont pas du tout à la bonne heure...), le nonce de la transaction coinbase peut être modifié, mais il faut alors recalculer le hash global des transactions, enfin on peut modifier le nombre de transactions dans le bloc. Tous ces facteurs sont exploités par les mineurs pour chercher de nouveaux hash.

Pour comprendre l'intérêt du minage de groupe, je vais mettre en perspective quelques chiffres. La puissance actuelle mesurée de tous les mineurs est de 50 Millions de GHash/s. Prenons une machine à miner performante et actuellement en vente comme la CoinTerra TerraMiner IV. Si on prend sa statistiques de 2200 MHash/s/W, on obtient le calcul suivant :

2200 MHash/s/W  
Pour 50 Milliards de MHash/s  
-----
22MW de consommation  

22MW est la consommation d'un pays comme Belize (200 400 MWh/an * 114), et représente pour un tarif français de 0.13€ le kWh 68 640 €/j. 1 bloc est généré toutes les 10 minutes, ce qui fait un volume de 1 152 000€/j (6 blocs/heure x 24 heures x 25 BTC x 320€/BTC). Ramené à l'echelle d'un bloc miné, on a un coût de production de 476€ (68640 /(6 x 24)) pour un gain de 8000€ (25BTC * 320€/BTC). Le gain est actuellement rentable à condition que le taux de change du BTC reste à 1:320€ et que le coût de l'électricité ne grimpe pas. Pour augmenter ses chances de minage personnel, un mineur doit se mettre en groupe. C'est le principe des pools de mineurs.

Pour miner en pool, on utilise des systèmes de minage coopératifs comme https://ghash.io/. Ils reposent sur des protocoles comme stratum qui gèrent la répartition des travaux entre participants et collectent les résultats. Les sites de minage distribuent les blocs à miner aux différents participants en leur indiquant des nonces de départ différents pour un même bloc. L'intelligence de ces sites est de récompenser tous les mineurs ayant participé à la recherche, de manière équitable en fonction de leur participation. Le système accepte des réponses même partielles de la part des participants et les comptabilise comme 'effort de participation'. Par exemple, si la difficulté est de 16 '0' de début, le système récompense un participant qui trouve par exemple 11 '0' de début. Ceci réduit sa difficulté de 1000000000 de fois et prouve qu'il cherche activement le hash rare. Si le hash est trouvé, le mineur qui tombe sur la pépite reçoit la plus grosse part, puis les mineurs ayant trouvé les hashs les plus proches, etc... Il existe plusieurs principes de redistribution des résultats, mais le principe général, reste d'arriver à attirer suffisamment de mineurs collaboratifs pour augmenter les chances de tomber sur un bloc valide.

Pour finir le code de minage d'un bloc en coffeescript / javascript. Il permet de tester le rôle du nonce, et de comprendre la difficulté correspondant à une valeurs de bits, puis enfin de calculer des identifiants de blocs.

require('buffertools').extend()  
bignum = require 'bignum'  
sprintf = require('sprintf-js').sprintf  
bufferpack = require 'bufferpack'  
CryptoJS = (require 'cryptojs').Crypto

ver = 2  
prev_block = "000000000000000117c80378b8da0e33559b5997f2ad55e2f7d18ec1975b9717"  
mrkl_root = "871714dcbae6c8193a2bb9b2a69fe1c0440399f38d94b3a0f1b447275a29978a"  
time_ = 0x53058b35 # 2014-02-20 04:57:25

#bits = bignum(0x19009d8c)
bits = bignum(0x19015f53)

# https://en.bitcoin.it/wiki/Difficulty
exp = bits.shiftRight(24)  
mant = bits & 0xffffff

target_str = bignum(mant).mul(bignum(1).shiftLeft(8*(exp - 3)))  
target_hexstr = sprintf('%064x', (target_str).toNumber())

nonce = 856192310  
while nonce < 0x100000000  
  packed = bufferpack.pack("<L", [ver]).
    concat((new Buffer(prev_block, 'hex')).reverse()).
    concat((new Buffer(mrkl_root, 'hex')).reverse()).
    concat(bufferpack.pack("<LLL",[time_,bits,nonce]))

  hash = CryptoJS.SHA256(CryptoJS.SHA256(packed, {asBytes: true}), {asBytes: true})
  rev_hash = (new Buffer(hash)).reverse()
  console.log nonce, rev_hash.toString('hex')


  if rev_hash.toString('hex') < target_hexstr
    console.log "success", rev_hash.toString('hex'), ' < ', target_hexstr
    process.exit()
  nonce++

ps : je n'ai pas chercher à trop l'optimiser... Comments welcome.

Cet article est fortement inspiré de
http://www.righto.com/2014/02/bitcoin-mining-hard-way-algorithms.html.

Pour visualiser et accéder à des blocs bitcoins.
https://blockexplorer.com/
https://blockchain.info

comments powered by Disqus