Annexe 2 : Implémentation des transactions
Sérialisation
Une transaction est un message structuré, qui peut être représenté par :
- un format binaire, utilisé pour le calcul de l'empreinte numérique, la signature et le transfert réseau,
- un format de source arbitraire, qui est un objet JSON dans cet article.
Nous appelons «sérialisation» la transformation d'un format source au format binaire. Le format binaire est le seul format "officiel". En effet, le format source n'est pas spécifié par le protocole. Par conséquent, tout processus applicable à une transaction s'applique au format binaire.
Les règles de conversion pour sérialiser un format source dans un format binaire sont les suivantes :
- la plupart des nombres sont encodés avec la convention Little-Endian sur 32 bits,
- une empreinte numérique est un grand nombre sur 256 bits, codé avec la convention Little-Endian,
- un montant est un entier sur 64 bits, codé avec la convention Little-Endian,
- un tableau commence par le nombre d'entrées, codé sur un octet, suivi de la séquence de toutes ses entrées,
- toute autre donnée commence par la taille de la donnée codée sur un octet.
La convention Little-Endian ordonne des octets du poids le plus faible vers le poids le plus fort, la convention Big-Endian ordonne des octets du poids le plus fort vers le poids le plus faible. Par exemple, le nombre 1 est sérialisé avec la convention Big-Endian sur 32 bits, en la suite d'octets 00000001 et avec Little-Endian convention sur 32 bits en la suite d'octets 01000000.
Le nombre 1 codé sur 32 bits avec la convention Big-Endian :
Octet 3 | Octet 2 | Octet 1 | Octet 0 --------+---------+---------+-------- 00 | 00 | 00 | 01Le nombre 1 encodé sur 32 bits avec la convention Little-Endian :
Octet 0 | Octet 1 | Octet 2 | Octet 3 --------+---------+---------+-------- 01 | 00 | 00 | 00
La fonction serializeTransaction sérialise une transaction représentée avec un objet JSON dans un tampon d'octets.
// an arbitrary structure
var transaction = {
version: 1,
paymentOrder: "Alice promises to pay the sum of one Bitcoin to Bob"
};
// convert an integer into a buffer of a single byte
var numberToInt8 = function (n) {
return new Buffer([n]);
}
// convert an integer into a buffer of 4 bytes using
// Little-Endian convention
var numberToInt32LE = function (n) {
var buffer = new Buffer(4);
buffer.writeUInt32LE(n,0);
return buffer;
};
var serializeTransaction = function (transaction) {
var buffers = [];
buffers.push (numberToInt32LE(transaction.version));
buffers.push (numberToInt8(transaction.paymentOrder.length));
buffers.push (new Buffer(transaction.paymentOrder));
return Buffer.concat(buffers);
}
> serializeTransaction (transaction).toString('hex');
'0100000033416c6963652070726f6d6973657320746f2070617920746865
2073756d206f66206f6e6520426974636f696e20746f20426f62'
Le tampon d'octets résultat est décrit ci-dessous :
|01 00 00 00| version as 32 bits Little-Endian
|33 | 51 bytes for payment order
|41 6c 69 63 65 20 70 72 6f 6d 69 73 65 73 20 74|Alice.promises.t|
|6f 20 70 61 79 20 74 68 65 20 73 75 6d 20 6f 66|o.pay.the.sum.of|
|20 6f 6e 65 20 42 69 74 63 6f 69 6e 20 74 6f 20|.one.Bitcoin.to.|
|42 6f 62 |Bob|
Certains sites Web affichent une notation hexadécimale de messages binaires binaires réels, y compris les transactions : https://blockchain.info/tx/9e9f1efee35b84bf71a4b741c19e1acc6a003f51ef8a7302a3dcd428b99791e4?format=hex
Empreinte numérique d'une transaction
Une fonction de hachage crytographique transforme un message d'entrée en un code numérique, appelé empreinte numérique du message. Cette empreinte reflète le message lui-même. La même fonction de hachage appliquée à un message modifié produira une autre empreinte distincte de la précédente.
SHA-256 (Secured Hash Algorithm) spécifie une méthode de hachage dont le résultat est un grand nombre encodé sur 256 bits. Il est considéré comme sécurisé, car une altération d'un seul bit du message produira une autre empreint numérique distincte, et la tentative de modifier un message pour obtenir une empreinte spécifique nécessiterait trop de tentatives.
Une empreinte d'une transaction est un double hachage du format binaire de la transaction. L'Algorithme SHA-256 est appliqué deux fois, pour des raisons historiques, et pour augmenter la sécurité.
Dans le code ci-dessous, nous définissons la fonction de hachage sha256 , puis nous définissons la fonction hachage pour calculer une empreinte numérique à partir d'une transaction source. Nous devons sérialiser la transaction dans son format binaire, avant d'appliquer la fonction sha256 deux fois. Nous définissons également la fonction toReverseHexaNotation pour afficher l'empreinte numérique, car le résultat est un nombre en utilisant la convention Little-Endian.
var crypto = require('crypto');
var sha256 = function(buffer) {
var f = crypto.createHash("SHA256");
var h = f.update(buffer);
return h.digest();
};
var hash = function (encodedTransaction) {
return sha256 (sha256 (encodedTransaction) );
}
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;
};
> hash (serializeTransaction (transaction)).toReverseHexaNotation();
'3e1a51c876a14ea0c09e87d17418910fdc5fb2380af4d040f2b00c2a13906d1c'
Clé privée et clé publique
Une signature numérique d'une transaction est le chiffrement de l'empreinte numérique de la transaction calculé avec une clé secrète. Cette clé secrète est appelée la clé privée. La signature de la transaction peut être vérifiée par une clé publique associée. La signature numérique prouve que la transaction n'a pas été modifiée et que la transaction a été émise par le propriétaire de la clé publique associée.
L'algorithme secp256k1 , basé sur des courbes elliptiques (également connu sous le nom de 'ECDSA': Elliptic Curve Digital Signature Algorithm), est approprié pour la signature numérique. Cet algorithme permet de générer une nouvelle paire de clés de chiffrement: une clé privée et une clé publique. La clé privée est un nombre de 256 bits généré aléatoirement. Et la clé publique est calculée à partir de cette clé privée.
var secp256k1 = require('secp256k1');
var generatePrivateKey = function () {
var privateKey;
do {
privateKey = crypto.randomBytes(32);
} while (!secp256k1.privateKeyVerify(privateKey));
return privateKey;
}
var alicePrivateKey = generatePrivateKey();
// get the public key in a compressed format
var alicePublicKey = secp256k1.publicKeyCreate(alicePrivateKey);
> alicePrivateKey.toString('hex');
'27d9b1f6d8567054f1542760ff943d0582e95bd8c1ba08355c02536a5aaac4cc'
> alicePublicKey.toString('hex');
'02c90ad3d07fcc5f92194c7c993ff5b373ce6025b23720f028a2ee1c3aaf97346f'
Signer et vérifier
Nous créons une signature numérique d'une transaction avec notre clé privée, et la fonction hash () :
var hashcode = hash (serializeTransaction(transaction));
var signature = secp256k1.sign(hashcode, alicePrivateKey).signature;
> signature.toString('hex');
'52990ea17ba23c88af7fc762644e3d1c5338a2e432142dae2b09576d259527aa...
>
Nous pouvons vérifier que la signature est valide en fonction de la clé publique et de l'empreinte numérique hashcode elle-même :
> secp256k1.verify(hashcode, signature, alicePublicKey);
true
Tenter d'utiliser une autre clé publique entraîne également un échec de vérification :
var bobPrivateKey = generatePrivateKey();
var bobPublicKey = secp256k1.publicKeyCreate(bobPrivateKey);
> secp256k1.verify(hashcode, signature, bobPublicKey);
> false
Tenter de modifier une transaction entraîne un échec de vérification :
transaction.paymentOrder = "Alice promises to pay the sum of 1000 Bitcoins to Bob";
hashcode = hash(serializeTransaction(transaction));
> secp256k1.verify(hashcode, signature, alicePublicKey);
false
Distinguished Encoding Rules
Une signature est une séquence de deux entiers appelés R et S. Pour une transaction, cette séquence est sérialisée en utilisant la convention DER (Distinguished Encoding Rules):
- Une séquence commence par l'octet 0x30 suivi du nombre total d'octets de la séquence et suivi des éléments.
- Un nombre commence par l'octet 0x02 suivi de la taille du nombre en octets et suivi du nombre lui-même en utilisant une convention Big-Endian.
Exemple de signature utilisant DER :
var signatureDER =
"3045" // sequence (0x30) of 69 (0x45) bytes
+ "0221" // fist item 'R' is an integer (0x02) of 33 (0x21 ) bytes
+ "009eb819743dc981250daaaab0ad51e37ba47f7fb4ace61f6a69111850d6f29905"
+ "0220" // second item 'S' is an integer (0x02) of 32 (0x20) bytes
+ "6b6e59e1c002a4e35ba2be4d00366ea0f3e0b14c829907920705bce336ab2945"
Pour utiliser une signature DER, le package secp256k1 fournit la fonction signatureImport :
var signature = secp256k1.signatureImport(signatureDER); // Decode a DER signature
Identifiant de transaction
L'empreinte numérique d'une transaction est nommé txid . Cet identifiant de transaction est utilisé pour référencer une transaction.
Nous introduisons une fonction getTxid pour obtenir l'identifiant txid pour notre format source. Nous ajoutons également la fonction hexaNotationToInt256LE pour obtenir le format binaire de l'identifiant txid.
// calculate a txid for a source format,
// return an hexa notation string for a source format
var getTxid = function (transaction) {
var encodedTransaction = serializeTransaction (transaction);
return hash (encodedTransaction).toReverseHexaNotation();
};
var txid = getTxid(transaction);
> txid
'3e1a51c876a14ea0c09e87d17418910fdc5fb2380af4d040f2b00c2a13906d1c'
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);
};
> hexaNotationToInt256LE(txid).toString('hex')
'1c6d90132a0cb0f240d0f40a38b25fdc0f911874d1879ec0a04ea176c8511a3e'
Grâce à la fonction getTxid , nous pouvons créer une table map pour stocker certaines transactions au format source et utiliser txid comme clé.
var dbtrx = {}; // our transaction table
dbtrx[txid] = transaction;
Machine virtuelle à pile
Un script est un ensemble d'instructions pour une machine virtuelle à pile. Une machine virtuelle à pile utilise une pile comme mémoire. Toute instruction lit/écrit des opérandes depuis/vers cette pile.
var OP_ADD = 0x93;
var OP_DUP = 0x76;
var script = [numberToInt32LE(16), OP_DUP, OP_ADD];
Le script ci-dessus effectuera les opérations suivantes :
| Instruction Pointer | Instruction | Operations | Stack after operations | ||
|---|---|---|---|---|---|
| 0 | 1000000 |
|
|
||
| 1 | OP_DUP |
|
|
||
| 2 | OP_ADD |
|
|
Ce script commence par une pile vide et s'arrête avec une pile contenant la valeur 0x20. Par défaut, à la fin de l'exécution de ce script, la machine virtuelle est arrêtée avec une valeur de retour 'true'. Cependant, certaines opérations de contrôle peuvent mettre fin à l'exécution du script avec une valeur de résultat 'false' lorsqu'elles échouent.
Compilation de script
Chaque instruction est codée avec un seul octet, cet octet est appelé opcode (code d'opération). Une instruction dont l'opcode est inférieur ou égal au nombre 0x75 spécifie le nombre d'octets suivants à pousser sur la pile en tant que données.
Ce langage de script ne nécessite pas d'analyseur et est donc facile à implémenter par tous les nœuds participants.
Le code ci-dessous compile un code source de script:
var compileScript = function(program) {
var buffers = [];
var bytes = 0;
for (var i = 0, len = program.length; i < len; i++) {
var code = program[i];
var type = typeof(code);
switch (type) {
case 'number':
buffers.push(numberToInt8(code));
bytes++;
break;
case 'object': // already encoded
operand = code;
buffers.push(numberToInt8(operand.length));
buffers.push(operand);
bytes += operand.length + 1;
break;
case 'string': // not yet encoded
var operand = new Buffer(code, 'hex');
buffers.push(numberToInt8(operand.length));
buffers.push(operand);
bytes += operand.length + 1;
break;
}
}
buffers.unshift(numberToInt8(bytes));
return Buffer.concat(buffers);
};
var script = [numberToInt32LE(16), OP_DUP, OP_ADD];
> compileScript(script).toString("hex")
'0704100000007693'
Exécution de script
Nous créons une fonction runScript pour interpréter le code compilé précédent. Cet interpréteur sera limité à 2 opcodes: OP_DUP et OP_ADD. Les opérandes des opérations arithmétiques sont des entiers signés sur 32 bits, codés avec la convention Little-Endian.
var runScript = function (program, stack)
{
var operand;
var operand1;
var operand2;
var ip = 0; // instruction pointer
var last = program[ip++];
while (ip <= last) {
var instruction = program[ip++];
switch (instruction) {
case OP_DUP:
operand = stack.pop();
stack.push(operand);
stack.push(operand);
break;
case OP_ADD:
operand1 = stack.pop().readInt32LE();
operand2 = stack.pop().readInt32LE();
stack.push(numberToInt32LE(operand1 + operand2));
break;
default:
var size = instruction;
var data = new Buffer(size);
program.copy(data, 0, ip, ip+size);
stack.push(data);
ip += size;
break;
}
}
return true;
};
var stack = [];
var script = compileScript ([numberToInt32LE(16), OP_DUP, OP_ADD]);
var result = runScript (script, stack);
> result
true
> tack[0].readInt32LE()
> 32
Code pour vérifier un paiement dans le bloc #266632
Le code entier vérifie le premier paiement de la transaction Bitcoin réelle suivante : 9e9f1efee35b84bf71a4b741c19e1acc6a003f51ef8a7302a3dcd428b99791e4.
Vous trouverez la représentation binaire de cette transaction avec l'URL suivante : https://blockchain.info/tx/9e9f1efee35b84bf71a4b741c19e1acc6a003f51ef8a7302a3dcd428b99791e4?format=hex
var crypto = require('crypto');
var secp256k1 = require('secp256k1');
var sha256 = function(buffer) {
var f = crypto.createHash("SHA256");
var h = f.update(buffer);
return h.digest();
};
var ripemd160 = function(buffer) {
var f = crypto.createHash("RIPEMD160");
var h = f.update(buffer);
return h.digest();
};
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;
};
var numberToInt8 = function (n) {
return new Buffer([n]);
};
var numberToInt32LE = function (n) {
var buffer = new Buffer(4);
buffer.writeUInt32LE(n,0);
return buffer;
};
var numberToInt64LE = function (n) {
var buffer = new Buffer(8);
buffer.writeUInt32LE(n % 0xFFFFFFFFFFFFFFFF, 0);
buffer.writeUInt32LE(Math.floor(n / 0xFFFFFFFFFFFFFFFF), 4);
return buffer;
};
var serializeAmount = function (amount)
{
return numberToInt64LE(amount * 100000000);
};
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);
};
var OP_ADD = 0x93;
var OP_DUP = 0x76;
var OP_HASH160 = 0xa9;
var OP_EQUALVERIFY = 0x88;
var OP_CHECKSIG = 0xac;
var serializeTransaction = function(tr) {
var buffers = [];
buffers.push(numberToInt32LE(tr.version));
buffers.push(serializeInputs(tr.inputs));
buffers.push(serializeOutputs(tr.outputs));
buffers.push(numberToInt32LE(tr.lockTime));
if (tr.hashType)
buffers.push(numberToInt32LE(Number(tr.hashType)));
return Buffer.concat(buffers);
};
var serializeInputs = function (inputs)
{
var buffers = [];
var inputsSize = inputs.length;
buffers.push(numberToInt8(inputsSize));
for (var i = 0; i < inputsSize; i++) {
var input = inputs[i];
buffers.push(hexaNotationToInt256LE(input.txid));
buffers.push(numberToInt32LE(input.index));
buffers.push(compileScript(input.script));
buffers.push(numberToInt32LE(0xffffffff));
}
return Buffer.concat (buffers);
};
var serializeOutputs = function (outputs)
{
var buffers = [];
var outputsSize = outputs.length;
buffers.push(numberToInt8(outputsSize));
for (var i = 0; i < outputsSize; i++) {
var output = outputs[i];
buffers.push(serializeAmount(output.amount));
buffers.push(compileScript(output.script));
}
return Buffer.concat (buffers);
};
var compileScript = function(program)
{
var buffers = [];
var bytes = 0;
for (var i = 0, len = program.length; i < len; i++) {
var code = program[i];
var type = typeof(code);
switch (type) {
case 'number':
buffers.push(numberToInt8(code));
bytes++;
break;
case 'string':
var operand = new Buffer(code, 'hex');
buffers.push(numberToInt8(operand.length));
buffers.push(operand);
bytes += operand.length + 1
break;
}
}
buffers.unshift(numberToInt8(bytes));
return Buffer.concat(buffers);
};
// A simple virtual machine to run a decoded P2SH (Pay to Script Hash) scripts
var runScript = function (program, stack, currentTransaction, currentInputIndex)
{
var operand;
var operand1;
var operand2;
var ip = 0; // instruction pointer
var last = program[ip++];
while (ip <= last) {
var instruction = program[ip++];
switch (instruction) {
case OP_DUP:
operand = stack.pop();
stack.push(operand);
stack.push(operand);
break;
case OP_ADD:
operand1 = stack.pop().readInt32LE();
operand2 = stack.pop().readInt32LE();
stack.push(numberToInt32LE(operand1 + operand2));
break;
case OP_HASH160:
operand = stack.pop();
stack.push(ripemd160(sha256(operand)));
break;
case OP_EQUALVERIFY:
operand1 = stack.pop();
operand2 = stack.pop();
if (! operand1.compare(operand2) == 0) return false;
break;
case OP_CHECKSIG:
operand1 = stack.pop();
operand2 = stack.pop();
// operand 1 is Public Key
var publicKey = operand1;
// operand 2 contains hashType
var hashType = operand2[operand2.length-1]; //get last byte of signature
// operand 2 contains DER Signature
var signatureDER = operand2.slice(0,-1);
var signature = secp256k1.signatureImport(signatureDER); // Decode a signature in DER format
// recover signed transaction and hash of this transaction
var copy = copyForSignature(currentTransaction, currentInputIndex, hashType);
var buffer = serializeTransaction(copy);
var hashcode = sha256 (sha256 (buffer));
// Check signature
if (! secp256k1.verify(hashcode, signature, publicKey)) return false;
break;
default:
var size = instruction;
var data = new Buffer(size);
program.copy(data, 0, ip, size+ip);
stack.push(data);
ip += size;
break;
}
}
return true;
};
var SIGHASH_ALL = "01";
var SIGHASH_NONE = "02";
var SIGHASH_SINGLE = "03";
var SIGHASH_ANYONECANPAY = "80";
// We create a previous transaction with an output
// We skip other data that are not required for validation
var previousTransaction =
{
version: 1,
inputs: {}, // missing actual data here
outputs: [
{}, // missing output[0]
{
amount: 0.09212969,
script: [
OP_DUP,
OP_HASH160,
'4586dd621917a93058ee904db1b7a43bfc05910a',
OP_EQUALVERIFY,
OP_CHECKSIG
]
}
],
lockTime: 0
};
var transaction = {
version: 1,
inputs: [
{
txid: "14e5c51d3bc1cf0d29f2457d61fbf8d6567883e0711f9877795783d2105b50c9",
index: 1,
script: [
"3045"
+ "0221"
+ "009eb819743dc981250daaaab0ad51e37ba47f7fb4ace61f6a69111850d6f29905"
+ "0220"
+ "6b6e59e1c002a4e35ba2be4d00366ea0f3e0b14c829907920705bce336ab2945" // signature
+ SIGHASH_ALL, // hashtype
"0275e9b1369179c24935337d597a06df0e388b53e8ac3f10ee426431d1a90c1b6e" // Public Key
]
},
{
txid: "5b7aeedc2e82c9646408ce0588d9f98d2107062e9291af0e9e6fa372b0d7d1fb",
index: 1,
script: [
"3045"
+ "0220"
+ "35a9e444883acaaae166d2ee1389272424ec7885f4210aaf118fee58b5683445"
+ "0221"
+ "00e40624a0df47943aa5ee63d8997dd36c5da44409ccc4dafcbfabc96a020d971c" // signature
+ SIGHASH_ALL, // hashtype
"033b18e24fb031dae396297516a54f3e46cc9902adfd1b8edea0d6a01dab0e027d" // Public Key
]
}
],
outputs: [
{
amount: 0.05580569,
script: [
OP_DUP,
OP_HASH160,
'4753945f3b34d6ca3fedcf41bf499c13d20bfec4',
OP_EQUALVERIFY,
OP_CHECKSIG
],
},
{
amount: 0.1,
script: [
OP_DUP,
OP_HASH160,
'81a9e7d0ab008005d36c61563a178ad20a3a5224',
OP_EQUALVERIFY,
OP_CHECKSIG
],
}
],
lockTime: 0
};
var dbtx = {};
dbtx["14e5c51d3bc1cf0d29f2457d61fbf8d6567883e0711f9877795783d2105b50c9"] = previousTransaction;
dbtx["9e9f1efee35b84bf71a4b741c19e1acc6a003f51ef8a7302a3dcd428b99791e4"] = transaction;
var copyForSignature = function(transaction, inputIndex, hashType)
{
var copy = Object.assign({}, transaction);
var inputs = copy.inputs;
for (var i = 0, len = inputs.length; i < len; i++) {
inputs[i].script = []; // reset script to nothing
}
var currentInput = inputs[inputIndex];
var previousTransaction = dbtx[currentInput.txid];
var previousOutput =previousTransaction.outputs[currentInput.index];
currentInput.script = previousOutput.script;
copy.hashType = hashType;
return copy;
};
var validateInput = function (transaction, inputIndex)
{
var stack = [];
var input = transaction.inputs[inputIndex];
var previousTransaction = dbtx[input.txid];
var previousOutput =previousTransaction.outputs[input.index];
var program1 = compileScript(input.script);
var program2 = compileScript(previousOutput.script);
var result = runScript (program1, stack, transaction, inputIndex);
if (result) result = runScript (program2, stack, transaction, inputIndex);
console.log(stack);
return result;
};
var currentTransaction = transaction;
var currentInputIndex = 0;
console.log(validateInput(currentTransaction, currentInputIndex));