Annexe : Implémentation d'un en-tête de bloc

L'empreinte numérique

Une fonction de hachage cryptographique transforme un message en un code numérique appelé l'empreinte numérique du message. Ce code reflète entièrement le message. La même fonction de hachage appliquée à un message altéré produira un code numérique distinct de son code initial.

L'algorithme SHA-256

L'algorithme SHA-256 (Secured Hash Algorithm) spécifie une méthode de hachage qui produit une empreinte numérique sur 256 bits. Elle est dite sécurisée car l'altération d'un seul bit du message, produit une empreinte numérique distincte. Il est donc impossible d'altérer un message tout en conservant la même empreinte.

La fonction hash ci-dessous applique l'algorithme SHA-256 au message passé en paramètre, le résultat est affiché dans sa représentation hexadécimale :

// Calculate a hash code from a binary buffer
var crypto = require("crypto");
var hash = function(buffer) { 
    var f = crypto.createHash('sha256'); 
    var h = f.update(buffer);
    return h.digest(); 
};

> var message = new Buffer('hello world');
> message.toString('hex');
'68656c6c6f20776f726c64'
> var hashCode = hash(message);
> hashCode.toString('hex');
'b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9'

Le "nonce"

Un nonce est une valeur arbitraire adjointe à un message pour influer sur l'empreinte numérique obtenue ; on applique la fonction de hachage au message concaténé à un nonce codé sur 32 bits avec la convention Little-Endian.

La convention Little-Endian ordonne les octets du poids le plus faible vers le poids le plus fort, la convention Big-Endian ordonne les octets du poids le plus fort vers le poids le plus faible. Par exemple le nombre 1 est représenté en hexadécimal sur 32 bits par 00000001 avec la convention Big-Endian et 01000000 avec la convention Little-Endian.

Le nombre 1 sur 32 bits avec la convention Big-Endian :
Octet 3 | Octet 2 | Octet 1 | Octet 0
--------+---------+---------+--------
     00 |     00  |     00  |      01
Le nombre 1 sur 32 bits avec la convention Little-Endian :
Octet 0 | Octet 1 | Octet 2 | Octet 3
--------+---------+---------+--------
     01 |      00 |      00 |      00

Dans le code ci-dessous, nous représentons le nonce avec un Buffer d'octets, indépendamment de la convention Little-Endian/Big-Endian propre au processeur, puis nous concaténons le message avec le nonce, pour obtenir une nouvelle empreinte numérique.

var numberToInt32LE = function (n) {
    var buffer = new Buffer(4);
    buffer.writeUInt32LE(n,0);
    return buffer;
};

> var nonce = numberToInt32LE (1000);
> nonce.toString('hex');
'e8030000'

> var message = new Buffer('hello world');
> var hashCode = hash(Buffer.concat([message,nonce]));
> hashCode.toString('hex');
'51b2583117a8e0c8551883127bba6bdc3fe6603ac58ce4ad5c1c2a6def9be485'

La preuve-de-travail

La preuve-de-travail vise

à rendre difficile le calcul d'une empreinte numérique en exigeant du temps d'exécution du processeur ;
à rendre aléatoire le temps nécessaire à ce calcul (cf. le principe du consensus).

L'algorithme SHA-256 produit un nombre qui peut être représenté sur 256 bits, soit un nombre entre 0 et 2²⁵⁶ - 1. Si on considère la fonction de hachage basée sur l'algorithme SHA-256 comme une fonction pseudo-aléatoire, la probabilité d'obtenir un nombre qui commence par N bits à 0 pour sa représentation sur 256 bits est de 1/(2^N). Cela revient à segmenter l'intervalle des nombres de 0 à 2²⁵⁶ - 1, en 2, 4, 8, ...2^N segments, et à évaluer la probabilité d'obtenir un nombre du premier segment.

Le tableau ci-dessous donne un échantillon de quelques probabilités :

Nombre de bits à zéro	Probabilité
1	1 / 2
2	1 / 4
3	1 / 8
4	1 / 16
5	1 / 32
16	1 / 65536

Une preuve-de-travail spécifie le nombre N de bits à 0 que doit satisfaire une empreinte numérique par l'adjonction d'un nonce. Pour satisfaire cette contrainte, il faut rechercher un nonce, avec une probabilité de succès de 1/(2^N). Cette recherche peut être faite simplement par une itération du nonce jusqu'à satisfaire la contrainte, ou par toute autre méthode, par exemple en tirant des valeurs au "hasard". Quelle que soit la méthode, elle nécessitera du temps d'exécution du processeur, un temps d'autant plus long que la probabilité de succès sera faible.

Pour tester l'empreinte numérique, nous utiliserons la fonction toReverseHexaNotation qui inverse la représentation hexadécimal d'un nombre codé sur 32 bits ou 256 bits avec la convention Little-Endian

Buffer.prototype.toReverseHexaNotation = function () 
{
    var hexa = "";
    for (var i = this.length-1; i >= 0; i--) {
       var digits =  this[i].toString(16);
        hexa += ("0" + digits).slice(-2); // Add "0" for single digit
    }
    return hexa;     
};

/* Return a nonce value for a number of expected bits.
 * Warning: May take a while if the proof-of-work is difficult
 * proof is a string of '0' characters, each character is 
 * a hexadecimal digit, so it is 4 zero-bits
 */   
var calculateProofOfWork = function(proof, message) { 
   var len = proof.length; 
   for(var nonce=0;;nonce++){ 
        var nonceLE= numberToInt32LE(nonce);
        var hashCode = hash(Buffer.concat([message, nonceLE]));
        var result = hashCode.toReverseHexaNotation();
        if (result.substr(0, len) == proof)  
            return nonceLE; 
    } 
};

> var message = new Buffer('hello world');
> var nonce = calculateProofOfWork('00', message);
> nonce.toString('hex');
'0e000000'

Une fois la valeur du nonce trouvée, la vérification de la preuve-de-travail est immédiate :

> var hashCode = hash(Buffer.concat([message, nonce]));
> hashCode.toReverseHexaNotation();
'003a669f5c15dd75046bae1661f6a7326bbb80ec217080bff5c97286dc03d7c6'

Le temps et l'effort de calcul pour trouver le nonce augmente à mesure que la probabilité de succès décroit :

var testProofOfWork = function (message, loops) {
    var proof = "0";
    for (var i = 0; i < loops; i++) {
        var t1 = Date.now();
        var nonce = calculateProofOfWork(proof, message);
        var t2 = Date.now();
        var hashCode = hash(Buffer.concat([message, nonce]));
        console.log ("hash:", hashCode.toReverseHexaNotation(),
                     "nonce:", nonce.toReverseHexaNotation(), 
                     "elapsedTime:", t2-t1);
        proof += "0";
    }
};

> testProofOfWork(message, 5); 
hash: 003a669f5c15dd75...80bff5c97286dc03d7c6 nonce: 0000000e elapsedTime: 1
hash: 003a669f5c15dd75...80bff5c97286dc03d7c6 nonce: 0000000e elapsedTime: 1
hash: 0001c1c7a764d470...76d596b136ef255ba911 nonce: 00001f0a elapsedTime: 254
hash: 00008e8dc456ce49...a36d96dfafab3f18fba0 nonce: 0000fca8 elapsedTime: 1486
hash: 000003aaa63ca127...35ba4de259c2625b617f nonce: 0008e973 elapsedTime: 12241

La cible de la preuve-de-travail

Le protocole Bitcoin a fait évoluer la preuve-de-travail. Elle n'est plus spécifiée comme un nombre de bits à 0 mais comme une valeur maximale que l'empreinte numérique peut atteindre. Cette valeur maximale est appelée la cible.

Cette cible est représentée sous une forme compacte de 32 bits, appelée bits. Cette représentation est basée sur les fonctions OpenSSL BN_bn2mpi() et BN_mpi2bn() :

Les 23 bits de poids faible représentent une valeur.
Le 24ième bit représente le signe négatif.
L'octet de poids fort est utilisé pour établir un décalage à gauche en nombre d'octets.

La valeur correspondante s'obtient par le calcul suivant :

var bigInt = require("big-integer");

var bitsToTarget = function (bits) {
    bits = bigInt(bits);
    var sign = bits.and(0x00800000).shiftRight(24).toJSNumber();
    var exponent = bits.and(0xFF000000).shiftRight(24).toJSNumber();
    var mantissa = bits.and(0x007FFFFF);
    var target = mantissa.times(Math.pow(-1,sign)).shiftLeft(8 * (exponent-3));
    return target;
}

> bitsToTarget(0x04012345).toString(16);
'1234500'

La valeur limite choisie pour la cible, soit l'effort minimum de preuve-de-travail exigé, commence par 32 bits à 0, soit :

0x00000000FFFF0000000000000000000000000000000000000000000000000000

soit dans sa forme compacte sur 32 bits :

0x1d00ffff

L'indice de difficulté

L'indice de difficulté est calculé par le rapport de la valeur limite de la preuve-de-travail avec la cible courante. Cet indice donne une estimation de l'effort de calcul nécessaire pour satisfaire la preuve-de-travail. Plus l'indice est grand, plus l'effort de calcul est important. Une valeur de l'indice égale à 1 correspond à l'effort minimum.

> var bigInt = require("big-integer");
> var limit = bigInt("00000000FFFF0000000000000000000000000000000000000000000000000000",16);
> var target = bigInt("00000000000404CB000000000000000000000000000000000000000000000000",16);
> var difficultyIndex = limit.divide(target).toJSNumber();
16307

L'ajustement de la preuve-de-travail

La cible de la preuve-de-travail doit être ajustée de façon à générer un bloc en moyenne toutes les 10 minutes.

Si un bloc est généré en moyenne toutes les 10 minutes, alors sur une période de 14 jours, 2016 blocs doivent être générés (2016 blocs = 14 jours * 24 heures * 6 blocs par heure). Ainsi tous les 2016 blocs, la cible est ajustée en la multipliant par un facteur. Ce facteur est déduit de la différence de temps de création effectif des 2016 blocs avec la durée attendue de 14 jours.

Le jeton d'horodatage

Le jeton d'horodatage de chaque bloc est calculé avec l'empreinte numérique de la concaténation des éléments de son en-tête. Cet en-tête est constitué :

du numéro de version de la structure du bloc (version) ;
du jeton d'horodatage du bloc précédent (previousToken) ;
de l'empreinte numérique du contenu du bloc (merkleRootHash) ;
de l'horodatage du bloc sur 32 bits (time);
de la valeur compacte de la cible de la preuve-de-travail (bits) ;
du nonce qui permet de satisfaire la preuve-de-travail (nonce).

L'empreinte numérique du contenu du bloc est calculée via un arbre de Merkle, la racine de l'arbre de Merkle est l'empreinte numérique pour l'ensemble des transactions enregistrées.

// Header from block 125552
var header = {
    version: 1,
    previousToken: '00000000000008a3a41b85b8b29ad444def299fee21793cd8b9e567eab02cd81',
    merkleRootHash: '2b12fcf1b09288fcaff797d71e950e71ae42b91e8bdb2304758dfcffc2b620e3',
    time: new Date ("Sat May 21 2011 17:26:31 GMT+0000 (UTC)"),
    bits: 440711666,
    nonce: 2504433986
};

Tous les éléments de l'en-tête sont considérés comme des nombres sur 32 bits ou 256 bits, encodés avec la convention Little-Endian. La fonction serializeHeader permet de compiler ces données dans des buffers, avec la convention Little-Endian :


var serializeHeader = function (header) {
  var buffers = [];
  buffers.push (numberToInt32LE(header.version));
  buffers.push (hexaNotationToInt256LE(header.previousToken));
  buffers.push (hexaNotationToInt256LE(header.merkleRootHash));  
  buffers.push (dateToInt32LE(header.time));    
  buffers.push (numberToInt32LE(header.bits));  
  buffers.push (numberToInt32LE(header.nonce));    
  return Buffer.concat (buffers);
};

var dateToInt32LE = function (date) {
    var time = date.getTime() / 1000; // remove milliseconds
    return numberToInt32LE(time);
};

var hexaNotationToInt256LE = function (hexa)
{
    var bytes = new Array(32);
    for (var i = 0, j = 31, len = hexa.length; i < len; i+=2, j--) {
        bytes[j] = parseInt(hexa[i]+hexa[i+1],16);
    }    
    return new Buffer(bytes);
};

> serializeHeader (header).toString('hex');
'0100000081cd02ab7e569e8bcd9317e2fe99f2de44d49ab2b8851ba4a308000000000000e320b6c2fffc8d750423db8b1eb942ae710e951ed797f7affc8892b0f1fc122bc7f5d74df2b9441a42a14695'
>

Une première empreinte numérique d'un bloc est calculée sur la concaténation des éléments de l'en-tête, puis une seconde empreinte est calculée sur ce résultat, pour des raisons historiques et par prévention. Le jeton d'horodatage est cette seconde empreinte numérique.

> var hashcode = hash ( hash (serializeHeader (header) ) ); // hash twice
> hashcode.toReverseHexaNotation();
'00000000000000001e8d6829a8a21adc5d38d0a473b144b6765798e61f98bd1d'

L'en-tête du bloc genesis est particulier car le jeton d'horodatage du bloc précédent est 0.

// Header from block 0
var header = {
    version: 1,
    previousToken: '0000000000000000000000000000000000000000000000000000000000000000',
    merkleRootHash: '4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b',
    time: new Date ("Sat Jan 03 2009 18:15:05 GMT+0000 (UTC)"),
    bits: 0x1d00ffff,
    nonce: 2083236893
};

> var hashcode = hash ( hash (serializeHeader (header) ) ); // hash twice
> hashcode.toReverseHexaNotation();
'000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f'

Annexe 1: Implémentation d'un en-tête de bloc