Vérifier l’existence d’une transaction Bitcoin2018-02-22T12:10:29+00:00

Cover_Blockchain

Comment vérifier l’existence d’une transaction Bitcoin ?

Lorsqu’un mineur souhaite vérifier une transaction, il peut se permettre de télécharger l’intégralité de la blockchain pour vérifier l’intégrité des transactions. Le problème avec cette méthode, c’est qu’elle requiert une large bande passante.

En effet, la blockchain pèse plus de 140 GB en Novembre 2017 et la télécharger dans son intégralité demande un certain temps et une certaine capacité de stockage. Il est donc difficile pour un smartphone d’effectuer cette procédure en un temps réduit, ce qui projeté sur des milliers d’utilisateurs, augmenterait la latence du réseau et causerait de dangereux engorgements. Il est donc nécessaire de permettre aux utilisateurs de vérifier l’intégrité des transactions sans avoir à télécharger l’intégralité de la blockchain.

La solution à ce problème commence par la séparation des utilisateurs en deux catégories : les full nodes, qui détiennent un équipement assez puissant pour télécharger fréquemment et scanner l’intégralité de la blockchain efficacement (tous les mineurs sont des full nodes), et les light nodes qui ne disposent pas d’un tel équipement, et qui ne peuvent pas se permettre de télécharger l’intégralité de la blockchain lors de la vérification d’un paiement.

Bitcoin fait également appel à une structure de données appelée Arbre de Merkle pour permettre aux light nodes d’évaluer l’intégrité d’un paiement sans télécharger l’intégralité de la blockchain. Cette approche permet d’alléger drastiquement les informations requises pour prouver l’existence d’une transaction passée dans laquelle se trouve l’input dont on veut vérifier l’intégrité. Grâce à cette méthode, il suffit de télécharger les block headers (et non l’intégralité des transactions).

Un arbre de Merkle est construit à partir de feuilles (les transactions). Ces transactions sont toutes hachées une première fois, puis les hashs obtenus sont à leur tour hachés deux par deux. L’opération d’assemblage et de hachage se répète jusqu’à ce qu’il ne reste qu’un seul et unique hash : La racine de Merkle.

Si le nombre de hashs d’une étape est impair, la transaction restante est dupliquée pour rendre le hashage deux par deux possible. Pour trouver la racine de Merkle d’un arbre contenant 16 000 000 de transactions, il faudra par exemple répéter 24 fois la procédure.

Schéma d’un Arbre de Merkle :

Merkle 1
Dans les blocs de la blockchain Bitcoin, toutes les transactions sont regroupées dans un arbre de Merkle, et seule la racine de Merkle est inclue dans le block header. Les transactions contenues dans l’Arbre de Merkle ne sont donc qu’indirectement inclues dans le block hash.

Notre destinataire light node commence par envoyer une requête à un mineur afin qu’il vérifie la transaction. Le mineur reçoit la transaction et vérifie que ces Inputs soient intègres, c’est-à-dire qu’ils fassent partie des Outputs non-dépensés. Si un des Inputs n’est pas intègre, le mineur signale au destinataire que la transaction est non-valide. Sinon, le mineur envoie au destinataire les informations nécessaires à la reconstitution de la branche de Merkle dans laquelle se trouve la transaction passée ayant généré les Outputs utilisés par le payeur en Inputs de la nouvelle transaction.

Un hash par étage est nécessaire pour reconstituer une branche de Merkle à partir d’une transaction et jusqu’à la racine. Prenons un exemple d’arbre à trois étages, le destinataire a donc besoin de trois hashs pour reconstituer la racine de Merkle.

Merkle 2

Hash(F) haché avec Hash(E) permet de trouver Hash(Hash(E),Hash(F)), puis Hash(Hash(G), Hash(H)) haché avec Hash(Hash(E), Hash(F)) permet de trouver Hash(Hash(Hash (E), Hash (F)), Hash((Hash(G), Hash(H))), et enfin, Hash(Hash(Hash (E), Hash (F)), Hash((Hash(G), Hash(H))) haché avec Hash(Hash(Hash(A), Hash(B)), Hash((Hash(C), Hash(D))) permet de trouver la Racine de Merkle.

Une fois ces racines obtenues, le destinataire du paiement n’a qu’à vérifier, pour chacune d’entre elles, qu’il existe bien une racine correspondante dans les headers des blocs qu’il avait téléchargés auparavant. En fonction de la profondeur des blocs dans lesquels se trouvent ces transactions, le destinataire va pouvoir se faire une idée probabiliste de l’Intégrité du paiement qu’il a reçu.