Bitcoin : un système de monnaie électronique de pair à pair
Une version purement de pair à pair de la monnaie électronique permettrait d'envoyer des paiements en ligne directement d'une partie à une autre sans passer par une institution financière. Les signatures numériques fournissent une partie de la solution, mais les principaux avantages sont perdus si un tiers de confiance est toujours nécessaire pour prévenir la double dépense. Nous proposons une solution au problème de la double dépense en utilisant un réseau de pair à pair. Le réseau horodate les transactions en les hachant dans une chaîne continue de preuve de travail basée sur le hachage, formant un enregistrement qui ne peut pas être modifié sans refaire la preuve de travail. La plus longue chaîne sert non seulement de preuve de la séquence des événements observés, mais aussi de preuve qu'elle provient du plus grand pool de puissance CPU. Tant qu'une majorité de la puissance CPU est contrôlée par des nœuds qui ne coopèrent pas pour attaquer le réseau, ils généreront la plus longue chaîne et devanceront les attaquants. Le réseau lui-même nécessite une structure minimale. Les messages sont diffusés sur une base de meilleur effort, et les nœuds peuvent quitter et rejoindre le réseau à volonté, acceptant la plus longue chaîne de preuve de travail comme preuve de ce qui s'est passé pendant leur absence.
1. Introduction Le commerce sur Internet en est venu à dépendre presque exclusivement des institutions financières servant de tiers de confiance pour traiter les paiements électroniques. Bien que le système fonctionne suffisamment bien pour la plupart des transactions, il souffre encore des faiblesses inhérentes au modèle basé sur la confiance. Les transactions totalement non réversibles ne sont pas vraiment possibles, puisque les institutions financières ne peuvent éviter de médiatiser les litiges. Le coût de la médiation augmente les coûts de transaction, limitant la taille minimale pratique des transactions et coupant la possibilité de petites transactions occasionnelles, et il y a un coût plus large dans la perte de la capacité à effectuer des paiements non réversibles pour des services non réversibles. Avec la possibilité de réversion, le besoin de confiance se répand. Les commerçants doivent se méfier de leurs clients, les harcelant pour obtenir plus d'informations qu'ils n'en auraient autrement besoin. Un certain pourcentage de fraude est accepté comme inévitable. Ces coûts et incertitudes de paiement peuvent être évités en personne en utilisant de la monnaie physique, mais aucun mécanisme n'existe pour effectuer des paiements sur un canal de communication sans un tiers de confiance. Ce qu'il faut, c'est un système de paiement électronique basé sur une preuve cryptographique plutôt que sur la confiance, permettant à deux parties prêtes de transiger directement entre elles sans avoir besoin d'un tiers de confiance. Des transactions qui sont computationnellement impraticables à réverser protégeraient les vendeurs contre la fraude, et des mécanismes d'entiercement de routine pourraient facilement être mis en œuvre pour protéger les acheteurs. Dans cet article, nous proposons une solution au problème de la double dépense en utilisant un serveur de timestamp distribué pair-à-pair pour générer une preuve computationnelle de l'ordre chronologique des transactions. Le système est sécurisé tant que des nœuds honnêtes contrôlent collectivement plus de puissance CPU qu'un groupe d'attaquants coopérants.
2. Vérifier les Transactions Nous définissons une pièce électronique comme une chaîne de signatures numériques. Chaque propriétaire transfère la pièce au suivant en signant numériquement un hash de la transaction précédente et la clé publique du prochain propriétaire et en ajoutant cela à la fin de la pièce. Un bénéficiaire peut vérifier les signatures pour vérifier la chaîne de propriété. Transaction Vérifier Clé Publique du Propriétaire 1 Hash Signature du Propriétaire 0 Clé Privée du Propriétaire 1 Transaction Clé Publique du Propriétaire 2 Hash Signature du Propriétaire 1 Clé Privée du Propriétaire 2 Transaction Clé Publique du Propriétaire 3 Hash Signature du Propriétaire 2 Clé Privée du Propriétaire 3 Le problème, bien sûr, est que le bénéficiaire ne peut pas vérifier qu'un des propriétaires n'a pas dépensé deux fois la pièce. Une solution courante consiste à introduire une autorité centrale de confiance, ou une monnaie, qui vérifie chaque transaction pour double dépense. Après chaque transaction, la pièce doit être retournée à la monnaie pour émettre une nouvelle pièce, et seules les pièces émises directement par la monnaie sont fiables pour ne pas être dépensées deux fois. Le problème avec cette solution est que le sort de l'ensemble du système monétaire dépend de l'entreprise qui gère la monnaie, chaque transaction devant passer par elle, tout comme une banque. Nous avons besoin d'un moyen pour que le bénéficiaire sache que les propriétaires précédents n'ont pas signé de transactions antérieures. Pour nos besoins, la transaction la plus ancienne est celle qui compte, donc nous ne nous soucions pas des tentatives ultérieures de double dépense. Le seul moyen de confirmer l'absence d'une transaction est d'être au courant de toutes les transactions. Dans le modèle basé sur la monnaie, la monnaie était au courant de toutes les transactions et décidait de celles qui arrivaient en premier. Pour accomplir cela sans partie de confiance, les transactions doivent être annoncées publiquement [1], et nous avons besoin d'un système pour que les participants s'accordent sur une seule histoire de l'ordre dans lequel elles ont été reçues. Le bénéficiaire a besoin de la preuve qu'au moment de chaque transaction, la majorité des nœuds s'accordait à dire que c'était la première reçue.
3. Serveur de Timestamp La solution que nous proposons commence par un serveur de timestamp. Un serveur de timestamp fonctionne en prenant un hash d'un bloc d'éléments à timestamp et en publiant largement le hash, comme dans un journal ou un post Usenet [2-5]. Le timestamp prouve que les données devaient exister à ce moment-là, évidemment, afin de figurer dans le hash. Chaque timestamp inclut le timestamp précédent dans son hash, formant une chaîne, chaque timestamp supplémentaire renforçant les précédents. Hash Hash Bloc Élément Élément Bloc ... Élément Élément ...
4. Preuve de Travail Pour mettre en œuvre un serveur de timestamp distribué sur une base pair-à-pair, nous devrons utiliser un système de preuve de travail similaire à Hashcash d'Adam Back [6], plutôt que des journaux ou des posts Usenet. La preuve de travail implique de rechercher une valeur qui, lorsqu'elle est hachée, comme avec SHA-256, commence par un certain nombre de bits zéro. Le travail moyen requis est exponentiel par rapport au nombre de bits zéro requis et peut être vérifié en exécutant un seul hash. Pour notre réseau de timestamp, nous mettons en œuvre la preuve de travail en incrémentant un nonce dans le bloc jusqu'à ce qu'une valeur soit trouvée qui donne au hash du bloc les bits zéro requis. Une fois que l'effort CPU a été dépensé pour le faire satisfaire à la preuve de travail, le bloc ne peut être changé sans refaire le travail. À mesure que les blocs suivants sont enchaînés après, le travail pour changer le bloc inclurait le fait de refaire tous les blocs après lui. Bloc Hash Précédent Tx Bloc Nonce Tx ... Hash Précédent Nonce Tx Tx ... La preuve de travail résout également le problème de la détermination de la représentation dans la prise de décision majoritaire. Si la majorité était basée sur un IP-unique-un-vote, elle pourrait être subvertie par quiconque capable d'allouer de nombreux IP. La preuve de travail est essentiellement un-CPU-un-vote. La décision majoritaire est représentée par la chaîne la plus longue, qui a le plus grand effort de preuve de travail investi en elle. Si une majorité de puissance CPU est contrôlée par des nœuds honnêtes, la chaîne honnête croîtra le plus rapidement et dépassera toutes les chaînes concurrentes. Pour modifier un bloc passé, un attaquant devrait refaire la preuve de travail du bloc et de tous les blocs après lui, puis rattraper et surpasser le travail des nœuds honnêtes. Nous montrerons plus tard que la probabilité qu'un attaquant plus lent rattrape diminue exponentiellement à mesure que des blocs suivants sont ajoutés. Pour compenser l'augmentation de la vitesse du matériel et l'intérêt variable à exécuter des nœuds au fil du temps, la difficulté de la preuve de travail est déterminée par une moyenne mobile visant un nombre moyen de blocs par heure. S'ils sont générés trop rapidement, la difficulté augmente.
5. Réseau Les étapes pour faire fonctionner le réseau sont les suivantes : 1) De nouvelles transactions sont diffusées à tous les nœuds. 2) Chaque nœud collecte de nouvelles transactions dans un bloc. 3) Chaque nœud travaille à la recherche d'une preuve de travail difficile pour son bloc. 4) Lorsqu'un nœud trouve une preuve de travail, il diffuse le bloc à tous les nœuds. 5) Les nœuds acceptent le bloc uniquement si toutes les transactions qu'il contient sont valides et non déjà dépensées. 6) Les nœuds expriment leur acceptation du bloc en travaillant à créer le prochain bloc dans la chaîne, en utilisant le hash du bloc accepté comme le hash précédent. Les nœuds considèrent toujours la chaîne la plus longue comme la correcte et continueront à travailler à son extension. Si deux nœuds diffusent des versions différentes du prochain bloc simultanément, certains nœuds peuvent recevoir l'un ou l'autre en premier. Dans ce cas, ils travaillent sur le premier qu'ils ont reçu, mais sauvegardent l'autre branche au cas où elle deviendrait plus longue. Le lien sera rompu lorsque la prochaine preuve de travail sera trouvée et qu'une branche deviendra plus longue ; les nœuds qui travaillaient sur l'autre branche passeront alors à la plus longue.
Les diffusions de nouvelles transactions n'ont pas nécessairement besoin d'atteindre tous les nœuds. Tant qu'elles atteignent de nombreux nœuds, elles entreront dans un bloc avant longtemps. Les diffusions de blocs tolèrent également les messages perdus. Si un nœud ne reçoit pas un bloc, il le demandera lorsqu'il recevra le prochain bloc et se rendra compte qu'il en a manqué un.
6. Incitation Par convention, la première transaction dans un bloc est une transaction spéciale qui démarre une nouvelle pièce détenue par le créateur du bloc. Cela ajoute une incitation pour les nœuds à soutenir le réseau et fournit un moyen de distribuer initialement les pièces en circulation, puisque il n'y a pas d'autorité centrale pour les émettre. L'ajout régulier d'un montant constant de nouvelles pièces est analogue à l'extraction d'or par les mineurs d'or pour ajouter de l'or à la circulation. Dans notre cas, c'est le temps CPU et l'électricité qui sont dépensés. L'incitation peut également être financée par des frais de transaction. Si la valeur de sortie d'une transaction est inférieure à sa valeur d'entrée, la différence est un frais de transaction qui est ajouté à la valeur d'incitation du bloc contenant la transaction. Une fois qu'un nombre prédéterminé de pièces est entré dans la circulation, l'incitation peut passer entièrement aux frais de transaction et être complètement exemptée d'inflation. L'incitation peut aider à encourager les nœuds à rester honnêtes. Si un attaquant avide est capable d'assembler plus de puissance CPU que tous les nœuds honnêtes, il devrait choisir entre l'utiliser pour frauder les gens en reprenant ses paiements, ou l'utiliser pour générer de nouvelles pièces. Il devrait trouver plus rentable de jouer selon les règles, des règles qui le favorisent avec plus de nouvelles pièces que tout le monde combiné, que de saper le système et la validité de sa propre richesse.
7. Récupération d'Espace Disque Une fois que la dernière transaction dans une pièce est enfouie sous suffisamment de blocs, les transactions dépensées avant cela peuvent être écartées pour économiser de l'espace disque. Pour faciliter cela sans briser le hash du bloc, les transactions sont hachées dans un arbre Merkle [7][2][5], avec seulement la racine incluse dans le hash du bloc. Les anciens blocs peuvent alors être compactés en supprimant des branches de l'arbre. Les hachages intérieurs n'ont pas besoin d'être stockés. Bloc En-tête de Bloc (Hash de Bloc) Hash Précédent Nonce Hash Racine Hash01 Hash0 Hash1 Hash23 Hash2 Tx0 Tx1 Tx2 Hash3 Tx3 Transactions Hachées dans un Arbre Merkle Bloc En-tête de Bloc (Hash de Bloc) Hash Précédent Nonce Hash Racine Hash01 Hash23 Hash2 Hash3 Tx3 Après Élagage Tx0-2 du Bloc Un en-tête de bloc sans transactions serait d'environ 80 octets. Si nous supposons que les blocs sont générés toutes les 10 minutes, 80 octets * 6 * 24 * 365 = 4.2Mo par an. Avec des systèmes informatiques se vendant généralement avec 2 Go de RAM en 2008, et la loi de Moore prédisant une croissance actuelle de 1.2 Go par an, le stockage ne devrait pas poser de problème même si les en-têtes de blocs doivent être conservés en mémoire.
8. Vérification Simplifiée des Paiements Il est possible de vérifier les paiements sans exécuter un nœud de réseau complet. Un utilisateur n'a besoin de conserver qu'une copie des en-têtes de bloc de la plus longue chaîne de preuve de travail, qu'il peut obtenir en interrogeant les nœuds du réseau jusqu'à ce qu'il soit convaincu d'avoir la plus longue chaîne, et obtenir la branche Merkle reliant la transaction au bloc dans lequel elle est timestampée. Il ne peut pas vérifier la transaction lui-même, mais en la liant à un endroit dans la chaîne, il peut voir qu'un nœud du réseau l'a acceptée, et les blocs ajoutés après confirment davantage que le réseau l'a acceptée. Chaîne de Preuve de Travail la Plus Longue En-tête de Bloc Hash Précédent Nonce Racine Merkle En-tête de Bloc Hash Précédent Racine Merkle Hash01 Hash2 En-tête de Bloc Nonce Hash Précédent Nonce Racine Merkle Hash23 Branche Merkle pour Tx3 Hash3 Tx3 En tant que tel, la vérification est fiable tant que des nœuds honnêtes contrôlent le réseau, mais elle est plus vulnérable si le réseau est dominé par un attaquant. Bien que les nœuds du réseau puissent vérifier les transactions pour eux-mêmes, la méthode simplifiée peut être trompée par des transactions fabriquées par un attaquant tant que l'attaquant peut continuer à dominer le réseau. Une stratégie pour se protéger contre cela serait d'accepter des alertes des nœuds du réseau lorsqu'ils détectent un bloc invalide, incitant le logiciel de l'utilisateur à télécharger le bloc complet et les transactions alertées pour confirmer l'incohérence. Les entreprises qui reçoivent des paiements fréquents voudront probablement toujours exécuter leurs propres nœuds pour plus de sécurité indépendante et une vérification plus rapide.
9. Combinaison et Division de Valeur Bien qu'il soit possible de gérer les pièces individuellement, il serait peu pratique de faire une transaction séparée pour chaque centime dans un transfert. Pour permettre à la valeur d'être divisée et combinée, les transactions contiennent plusieurs entrées et sorties. Normalement, il y aura soit une seule entrée d'une transaction précédente plus importante, soit plusieurs entrées combinant des montants plus petits, et au maximum deux sorties : une pour le paiement, et une retournant la monnaie, le cas échéant, à l'expéditeur. Transaction Entrée Entrée Sortie ... ... Il convient de noter que le fan-out, où une transaction dépend de plusieurs transactions, et ces transactions dépendent de beaucoup plus, n'est pas un problème ici. Il n'est jamais nécessaire d'extraire une copie autonome complète de l'historique d'une transaction.
10. Confidentialité Le modèle bancaire traditionnel atteint un certain niveau de confidentialité en limitant l'accès à l'information aux parties impliquées et au tiers de confiance. La nécessité d'annoncer toutes les transactions publiquement préclut cette méthode, mais la confidentialité peut toujours être maintenue en rompant le flux d'informations à un autre endroit : en gardant les clés publiques anonymes. Le public peut voir que quelqu'un envoie un montant à quelqu'un d'autre, mais sans information reliant la transaction à quiconque. Cela est similaire au niveau d'information publié par les bourses, où le temps et la taille des transactions individuelles, le "tape", sont rendus publics, mais sans indiquer qui étaient les parties. Modèle de Confidentialité Traditionnel Identités Nouveau Modèle de Confidentialité Identités Transactions Tiers de Confiance Transactions Contrepartie Publique Publique Comme pare-feu supplémentaire, une nouvelle paire de clés devrait être utilisée pour chaque transaction afin de les empêcher d'être liées à un propriétaire commun. Un certain lien est encore inévitable avec des transactions multi-entrées, qui révèlent nécessairement que leurs entrées étaient détenues par le même propriétaire. Le risque est que si le propriétaire d'une clé est révélé, le lien pourrait révéler d'autres transactions qui appartenaient au même propriétaire.
11. Calculs Nous considérons le scénario d'un attaquant essayant de générer une chaîne alternative plus rapidement que la chaîne honnête. Même si cela est réalisé, cela n'ouvre pas le système à des changements arbitraires, comme créer de la valeur à partir de rien ou prendre de l'argent qui n'a jamais appartenu à l'attaquant. Les nœuds ne vont pas accepter une transaction invalide comme paiement, et les nœuds honnêtes n'accepteront jamais un bloc les contenant. Un attaquant ne peut essayer de changer qu'une de ses propres transactions pour reprendre de l'argent qu'il a récemment dépensé. La course entre la chaîne honnête et la chaîne d'un attaquant peut être caractérisée comme une marche aléatoire binomiale. L'événement de succès est la chaîne honnête étant étendue d'un bloc, augmentant son avance de +1, et l'événement d'échec est la chaîne de l'attaquant étant étendue d'un bloc, réduisant l'écart de -1. La probabilité qu'un attaquant rattrape un déficit donné est analogue à un problème de ruine du joueur. Supposons qu'un joueur avec un crédit illimité commence à un déficit et joue un nombre potentiellement infini d'essais pour essayer d'atteindre l'équilibre. Nous pouvons calculer la probabilité qu'il atteigne un jour l'équilibre, ou qu'un attaquant rattrape un jour la chaîne honnête, comme suit [8]: p = probabilité qu'un nœud honnête trouve le prochain bloc q = probabilité que l'attaquant trouve le prochain bloc qz = probabilité que l'attaquant rattrape un jour depuis z blocs de retard qz = { 1 si p≤q q/ pz si pq }
Étant donné notre hypothèse que p > q, la probabilité chute exponentiellement à mesure que le nombre de blocs que l'attaquant doit rattraper augmente. Avec les chances contre lui, s'il ne fait pas une poussée chanceuse en avant tôt, ses chances deviennent extrêmement petites à mesure qu'il prend du retard. Nous considérons maintenant combien de temps le destinataire d'une nouvelle transaction doit attendre avant d'être suffisamment certain que l'expéditeur ne peut pas changer la transaction. Nous supposons que l'expéditeur est un attaquant qui veut faire croire au destinataire qu'il lui a payé pendant un certain temps, puis le changer pour se rembourser après qu'un certain temps se soit écoulé. Le récepteur sera alerté lorsque cela se produira, mais l'expéditeur espère que cela sera trop tard. Le récepteur génère une nouvelle paire de clés et donne la clé publique à l'expéditeur peu avant de signer. Cela empêche l'expéditeur de préparer une chaîne de blocs à l'avance en travaillant dessus en continu jusqu'à ce qu'il ait la chance d'être assez en avance, puis d'exécuter la transaction à ce moment-là. Une fois la transaction envoyée, l'expéditeur malhonnête commence à travailler secrètement sur une chaîne parallèle contenant une version alternative de sa transaction. Le destinataire attend jusqu'à ce que la transaction ait été ajoutée à un bloc et que z blocs aient été liés après. Il ne connaît pas le montant exact des progrès réalisés par l'attaquant, mais en supposant que les blocs honnêtes ont pris le temps moyen attendu par bloc, le potentiel de progrès de l'attaquant sera une distribution de Poisson avec une valeur attendue : =z q p Pour obtenir la probabilité que l'attaquant puisse toujours rattraper maintenant, nous multiplions la densité de Poisson pour chaque montant de progrès qu'il aurait pu réaliser par la probabilité qu'il puisse rattraper depuis ce point : ∞ ke− ∑ k=0 k! ⋅ { q/ pz−k si k≤z 1 si kz } Réarranger pour éviter de sommer la queue infinie de la distribution... 1−∑ k=0 z ke− k! 1−q/ pz−k Conversion en code C... #include <math.h> double AttackerSuccessProbability(double q, int z) { double p = 1.0 - q; double lambda = z * (q / p); double sum = 1.0; int i, k; for (k = 0; k <= z; k++) { double poisson = exp(-lambda); for (i = 1; i <= k; i++) poisson *= lambda / i; sum -= poisson * (1 - pow(q / p, z - k)); } return sum; }
En exécutant certains résultats, nous pouvons voir la probabilité diminuer exponentiellement avec z. q=0.1 z=0 P=1.0000000 z=1 P=0.2045873 z=2 P=0.0509779 z=3 P=0.0131722 z=4 P=0.0034552 z=5 P=0.0009137 z=6 P=0.0002428 z=7 P=0.0000647 z=8 P=0.0000173 z=9 P=0.0000046 z=10 P=0.0000012 q=0.3 z=0 P=1.0000000 z=5 P=0.1773523 z=10 P=0.0416605 z=15 P=0.0101008 z=20 P=0.0024804 z=25 P=0.0006132 z=30 P=0.0001522 z=35 P=0.0000379 z=40 P=0.0000095 z=45 P=0.0000024 z=50 P=0.0000006 Résolution pour P inférieur à 0.1%... P < 0.001 q=0.10 z=5 q=0.15 z=8 q=0.20 z=11 q=0.25 z=15 q=0.30 z=24 q=0.35 z=41 q=0.40 z=89 q=0.45 z=340
12. Conclusion Nous avons proposé un système pour des transactions électroniques sans dépendre de la confiance. Nous avons commencé avec le cadre habituel des pièces fabriquées à partir de signatures numériques, qui fournit un contrôle fort de la propriété, mais est incomplet sans un moyen de prévenir la double dépense. Pour résoudre cela, nous avons proposé un réseau pair-à-pair utilisant la preuve de travail pour enregistrer une histoire publique des transactions qui devient rapidement impratiquable sur le plan computationnel pour un attaquant de changer si des nœuds honnêtes contrôlent la majorité de la puissance CPU. Le réseau est robuste dans sa simplicité non structurée. Les nœuds travaillent tous en même temps avec peu de coordination. Ils n'ont pas besoin d'être identifiés, puisque les messages ne sont pas routés vers un endroit particulier et doivent simplement être livrés sur une base de meilleure effort. Les nœuds peuvent quitter et rejoindre le réseau à leur guise, acceptant la chaîne de preuve de travail comme preuve de ce qui s'est passé pendant leur absence. Ils votent avec leur puissance CPU, exprimant leur acceptation des blocs valides en travaillant à les étendre et rejetant les blocs invalides en refusant de travailler dessus. Toutes les règles et incitations nécessaires peuvent être appliquées avec ce mécanisme de consensus.