veille sur la transition numérique et l'économie collaborative

rédigé par Luc PETITNICOLAS

UX design et lean startup, référent mastère management et entrepreneuriat de projets numériques @Campuslfi

Contrer la double dépense dans la blockchain Bitcoin

Romaric Ludinard - ENSAI
La compétition de minage pour mettre à jour le grand livre des comptes qu’est la Blockchain peut entraîner des incohérences transitoires communément appelées forks. La malveillance de certains utilisateurs qui chercheraient à exploiter cette compétition afin de dépenser plusieurs fois un même Bitcoin est connue sous le nom de double-dépense. Romaric Ludinard fait le point sur 3 propositions d’amélioration pour contrer toute possibilité de double-dépense ou de fork dans le cadre d’une conférence lors de la journée Blockchain organisée par la SIF à Télécom ParisTech.

Romaric Ludinard

Professeur associé à l’ENSAI (École Nationale de la Statistique et de l’Analyse de l’Information) / CREST UMR 9194 et responsable de la spécialité Data Scientist est l’auteur d’une thèse “Caractérisation locale de fautes dans les systèmes large échelle” soutenue à l’Université de Rennes 1 en 2014. C’est un spécialiste de la sûreté de fonctionnement des systèmes distribués. https://cv.archives-ouvertes.fr/romaric-ludinard

Vidéo de la conférence blockchain de Romaric Ludinard

Fonctionnement de Bitcoin

Le système Bitcoin est basé sur une technologie P2P (pair à pair) composé de 3 types d’acteur. L’utilisateur émetteur/récepteur, le pair qui conserve un historique du registre et le mineur chargé de la validation de la transaction. Le transfert de valeur entre 2 utilisateurs est validé et crypté contre rémunération par un tiers, le mineur qui fournit une preuve de travail (PoW) puis l’historique du registre est répliqué sur chaque pair.

Ce fonctionnement soulève plusieurs problèmes car il n’y a pas d’autorité, tiers de confiance dans le dispositif :

Validité et unicité des transactions
  • Comment vérifier la validité d’une transaction ?
  • Comment vérifier l’unicité d’une transaction ?
  • Comment l’enregistrer ?

La technologie Blockchain y répond partiellement. D’une part, le registre distribué est public et la compétition entre mineur pour enregistrer les transactions est facteur de neutralité. D’autre part, l’historique des transactions est inclus dans les blocs. Mais ce dispositif ne suffit pas pour se prémunir en théorie de toutes malveillances.

Transactions bien formées

Une transaction est dite bien formée si elle respecte 2 conditions. Toutes les entrées (les valeurs) appartiennent à l’émetteur et que le montant de la transaction est inférieur au total du montant détenu par l’émetteur. Ainsi, on peut assurer que la transaction sera honorée (ce qui est pris à l’un est directement transmis à l’autre).

Validité d’une transaction

Avant d’ajouter le bloc et de le diffuser dans le réseau, un pair doit s’assurer que 3 conditions sont vérifiées :

  • Les entrées ont bien été alimentées par une transaction précédente.
  • Les entrées sont disponibles en vérifiant que les valeurs n’ont pas été dépensées précédemment dans une autre transaction.
  • L’adresse est une adresse originale (une adresse déjà utilisée est non valide)

Définition

Étant donné un pair p du réseau Bitcoin, p considère la k-ème transaction T = (I;O) reçue comme localement valide si et seulement si les trois propriétés suivantes sont vérifiées
Propriété transaction valide

Utilisation des transactions

Un client fournit une transaction signée à un vendeur. Le vendeur vérifie la validité de la transaction en interrogeant aléatoirement un pair dans le système. Un mineur, par la suite, créera un bloc (environ toutes les 10 minutes) et le propagera publiquement à l’ensemble des pairs. La transaction est alors confirmée. Le fait que la transaction soit rendu publique permettra ensuite la validation des futures transactions selon les 3 propriétés énoncées plus haut.

La double dépense

Il y a double dépense lorsque 2 transactions dépensent le même Bitcoin

Une transaction est en situation de double dépense si 2 transactions dépensent le même Bitcoin [ T1 = (I1;O1) et T2 = (I2;O2) ]
double dépense
Une transaction est non conflictuelle si elle n’est pas en double dépense et qu’elle respecte les 3 conditions de validité (voir plus haut) . Cette transaction finira par atteindre un niveau de confirmation suffisant pour un pair correct (qui respecte le protocole, NDLR). C’est la propriété de vivacité. Cette confirmation sera ensuite reconnue, grâce à cette première confirmation, par tous les autres pairs corrects du système. C’est la propriété de sûreté.

Ces 2 propriétés, vivacité et sûreté, garantissent un préfixe commun à tous les pairs corrects du réseau mais elles ne concernent que les transactions non conflictuelles sans garantie à la réception.

Attaque par double dépense

attaque par double dépense
Un client fournit à un vendeur une transaction signée, le vendeur vérifie la validité auprès d’un pair qui confirme la transaction. Si le client est malveillant, il peut créer une transaction conflictuelle en générant une double dépense (le même Bitcoin dépensé 2 fois) et en la faisant valider par un autre pair avant que la première transaction ne se soit propagée sur l’ensemble du réseau. Les 2 transactions sont donc proposées au minage. En fonction de celle qui sera traitée en premier, c’est cette vérité qui s’imposera à l’ensemble du réseau par l’inscription dans un bloc et qui invalidera l’autre. Dans ce cas, si le vendeur avait livré avant la validation par le mineur, il s’est fait voler…

3 propositions d’amélioration

3 propositions concurrentes pour l’amélioration de la sécurité et prévenir les attaques par double dépense sont apparues cette année.

  • BitcoinNG : I. Eyal, A. E. Gencer, E. G. Sirer et R. V. Renesse, “Bitcoin-NG : A scalable blockchain protocol”, USENIX Symposium on Networked Systems Design and Implementation (NSDI), 2016.
  • PeerCensus : C. Decker, J. Seidel et R. Wattenhofer, “Bitcoin Meets Strong Consistency”, International Conference on Distributed Computing and Networking (ICDCN), 2016.
  • ByzCoin : E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser et B. Ford, “Enhancing bitcoin security and performance with strong consistency via collective signing.”, USENIX Security Symposium (USENIX Security), 2016.

Les 3 propositions s’appuient exclusivement sur les mineurs et poursuivent un même objectif de recherche de cohérence renforcée dans Bitcoin en découplant la génération de bloc de la validation des transactions.

E1 correspond au dernier mineur, Ew le w dernier mineur, et E∞ à la totalité des mineurs qui ont généré un bloc dans la Blockchain.
proposition d'amélioration Bitcoin

Évaluation de la sûreté

BitcoinNG [NSDI 2016]

BitcoinNG

L’idée générale de BitcoinNG c’est de considérer que la création de blocs correspond à une élection de leader car la compétition pour le minage désigne celui qui est le plus rapide, le plus performant. Le leader valide toutes les transactions émises dans le système et seules les transactions recevant sa signature sont éligibles à l’inclusion dans un bloc et pourront ensuite être diffusées dans la Blockchain.

2 cas sont possibles soit un leader malveillant (M) est élu soit c’est un leader honnête (H). Comme le leader valide toutes les transactions alors un leader malveillant a tout pouvoir pendant 10 minutes pour réordonner ou manipuler toutes les transactions.

PeerCensus [ICDCN 2016]

PeerCensus

Avec la solution PeerCensus, on s’appuie sur l’ensemble des mineurs (E∞ ). L’ensemble des mineurs constitués en quorum vont s’accorder, en permanence, sur la validité des transactions et du quorum.

La limitation ici est d’une part à la scalabilité du modèle due au nombre de mineurs (435000 à ce jour) avec une complexité des algorithmes pour les consensus résilients de n3 et d’autre part, toujours un problème rémanent de sûreté.

On identifie 2 zones. Une zone sûre avec une majorité de mineurs honnêtes et une zone où les malveillants sont suffisamment nombreux pour pouvoir corrompre et biaiser le résultat d’un consensus.
h=nombre de blocs générés par des mineurs honnêtes,
m=nombre de blocs générés par des mineurs malveillants.

PeerCensus

Quelle est la probabilité pour que les transactions évoluent dans la section sécurisée ?

Il faut que le calcul de probabilité informe à l’instant T de la sûreté de l’environnement mais également qu’il soit capable de prendre en considération l’historique pour évaluer la probabilité que le mineur est validé des transactions dans une zone malhonnête.

Ainsi, en 20 blocs, on converge très rapidement vers la limite (environ une demi journée) et de plus la limite décroît en fonction de la puissance de l’adversaire malhonnête. Si l’adversaire manipule un dixième des mineurs, il ne reste plus que 80% des transactions correctes et si l’adversaire manipule un quart des mineurs on tombe à 30% de transactions correctes.

Taux de transactions correctes

ByzCoin [USENIX Security 2016]

ByzCoin

Dans la proposition ByzCoin, on s’appuie sur un nombre restreint de mineurs et non plus sur l’ensemble ni sur un seul comme dans les 2 solutions précédentes. La génération de bloc est également découplée de leur validation. Les membres reconnus s’accordent sur la validité des transactions et sur les nouveaux entrants. Le quorum est fluctuant avec un turnover naturel entre les entrants et les sortants lié aux transactions. Les fenêtres de temps analysées, démontrent que plus le temps de référence est long moins il y a de risques face à un adversaire peu puissant par contre si l’adversaire est puissant, il faut alors des fenêtres plus courtes.

Fenêtre de temps pour les transactions

État des lieux du minage

La figure ci-dessous présente la proportion des blocs minés par les 5 mining pools les plus représentés en fonction de la durée. Certaines configurations représentent à elles seules près de 30% du minage. D’une manière générale, les mining pools les plus représentés représente autour de 20% des blocs créés dans la Blockchain.

Dans ce cadre, une question se pose. Qu’est-ce qu’il se passerait si les principaux mining pools se mettaient à coopérer ? Cela est d’autant plus important que les mining pools pourraient avoir un intérêt géopolitique à défendre. À noter par exemple que sur les 5 mining pools les plus représentatifs, 4 sont chinois. Entre autre, la borne de 51% pourrait ainsi être facilement atteinte.

activitée des principaux mining pools

Conclusion

Les propositions consistant à s’appuyer exclusivement sur les mineurs pour garantir une sûreté et se prémunir contre les attaques de double dépense ne sont pas convaincantes et révèlent encore de nombreuses failles. Le champ de la recherche théorique sur le Bitcoin est encore pleinement ouvert pour comprendre et améliorer Bitcoin et la technologie Blockchain.

Journée SIF

Blockchain : émergence d’une nouvelle forme de confiance numérique

log SIF - Société Informatique de France

Télécom ParisTechlogo ChainTech   Pascaline logo labo des savoirs logo-campus-800

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.