बिटकॉइन: एक पीयर-टू-पीयर इलेक्ट्रॉनिक कैश सिस्टम

Abstract

Une version purement pair-a-pair de monnaie electronique permettrait d'envoyer des paiements en ligne directement d'une partie a une autre sans passer par une institution financiere. Les signatures numeriques fournissent une partie de la solution, mais les principaux avantages sont perdus si un tiers de confiance est toujours necessaire pour empecher la double depense. Nous proposons une solution au probleme de la double depense en utilisant un reseau pair-a-pair. Le reseau horodate les transactions en les hachant dans une chaine continue de proof-of-work basee sur le hachage, formant un enregistrement qui ne peut etre modifie sans refaire le proof-of-work. La chaine la plus longue sert non seulement de preuve de la sequence des evenements observes, mais aussi de preuve qu'elle provient du plus grand pool de puissance CPU. Tant qu'une majorite de la puissance CPU est controlee par des noeuds qui ne cooperent pas pour attaquer le reseau, ils genereront la chaine la plus longue et devanceront les attaquants. Le reseau lui-meme necessite une structure minimale. Les messages sont diffuses au mieux, et les noeuds peuvent quitter et rejoindre le reseau a volonte, acceptant la chaine de proof-of-work la plus longue comme preuve de ce qui s'est passe pendant leur absence.

Introduction

Le commerce sur Internet en est venu a reposer presque exclusivement sur des institutions financieres servant de tiers de confiance pour traiter les paiements electroniques. Bien que le systeme fonctionne assez bien pour la plupart des transactions, il souffre encore des faiblesses inherentes au modele base sur la confiance. Les transactions completement irreversibles ne sont pas vraiment possibles, puisque les institutions financieres ne peuvent eviter de medier les litiges. Le cout de la mediation augmente les couts de transaction, limitant la taille minimale pratique des transactions et eliminant la possibilite de petites transactions occasionnelles, et il y a un cout plus large dans la perte de la capacite a effectuer des paiements irreversibles pour des services irreversibles. Avec la possibilite d'inversion, le besoin de confiance se repand. Les commercants doivent se mefier de leurs clients, les harcelant pour obtenir plus d'informations qu'ils n'en auraient autrement besoin. Un certain pourcentage de fraude est accepte comme inevitable. Ces couts et incertitudes de paiement peuvent etre evites en personne en utilisant de la monnaie physique, mais aucun mecanisme n'existe pour effectuer des paiements sur un canal de communication sans un tiers de confiance.

Ce qui est necessaire est un systeme de paiement electronique base sur la preuve cryptographique plutot que sur la confiance, permettant a deux parties consentantes de transiger directement l'une avec l'autre sans besoin d'un tiers de confiance. Les transactions qu'il est informatiquement impraticable d'inverser protegeraient les vendeurs contre la fraude, et des mecanismes d'entiercement routiniers pourraient etre facilement mis en oeuvre pour proteger les acheteurs. Dans cet article, nous proposons une solution au probleme de la double depense en utilisant un serveur d'horodatage distribue pair-a-pair pour generer une preuve informatique de l'ordre chronologique des transactions. Le systeme est securise tant que les noeuds honnetes controlent collectivement plus de puissance CPU que tout groupe cooperant de noeuds attaquants.

Transactions

Nous definissons une piece electronique comme une chaine de signatures numeriques. Chaque proprietaire transfere la piece au suivant en signant numeriquement un hash de la transaction precedente et la cle publique du proprietaire suivant, et en ajoutant ceux-ci a la fin de la piece. Un beneficiaire peut verifier les signatures pour verifier la chaine de propriete.

Le probleme bien sur est que le beneficiaire ne peut pas verifier qu'un des proprietaires n'a pas double-depense la piece. Une solution courante est d'introduire une autorite centrale de confiance, ou un atelier monetaire, qui verifie chaque transaction pour la double depense. Apres chaque transaction, la piece doit etre retournee a l'atelier monetaire pour emettre une nouvelle piece, et seules les pieces emises directement par l'atelier monetaire sont considerees comme non double-depensees. Le probleme avec cette solution est que le destin de l'ensemble du systeme monetaire depend de l'entreprise qui gere l'atelier monetaire, chaque transaction devant passer par eux, tout comme une banque.

Nous avons besoin d'un moyen pour le beneficiaire de savoir que les proprietaires precedents n'ont pas signe de transactions anterieures. Pour nos besoins, la transaction la plus ancienne est celle qui compte, donc nous ne nous soucions pas des tentatives ulterieures de double depense. La seule facon de confirmer l'absence d'une transaction est d'etre au courant de toutes les transactions. Dans le modele base sur l'atelier monetaire, l'atelier monetaire etait au courant de toutes les transactions et decidait laquelle etait arrivee en premier. Pour accomplir cela sans un tiers de confiance, les transactions doivent etre publiquement annoncees [^1], et nous avons besoin d'un systeme pour que les participants s'accordent sur un historique unique de l'ordre dans lequel elles ont ete recues. Le beneficiaire a besoin de la preuve qu'au moment de chaque transaction, la majorite des noeuds a convenu qu'elle etait la premiere recue.

Timestamp Server

La solution que nous proposons commence par un serveur d'horodatage. Un serveur d'horodatage fonctionne en prenant un hash d'un bloc d'elements a horodater et en publiant largement le hash, comme dans un journal ou un message Usenet [^2] [^3] [^4] [^5]. L'horodatage prouve que les donnees devaient exister a ce moment-la, evidemment, pour etre incluses dans le hash. Chaque horodatage inclut l'horodatage precedent dans son hash, formant une chaine, chaque horodatage supplementaire renforcant les precedents.

Proof-of-Work

Pour implementer un serveur d'horodatage distribue sur une base pair-a-pair, nous devrons utiliser un systeme de proof-of-work similaire au Hashcash d'Adam Back [^6], plutot que des journaux ou des messages Usenet. Le proof-of-work consiste a rechercher une valeur qui, lorsqu'elle est hachee, par exemple avec SHA-256, le hash commence par un certain nombre de bits zero. Le travail moyen requis est exponentiel par rapport au nombre de bits zero requis et peut etre verifie en executant un seul hash.

Pour notre reseau d'horodatage, nous implementons le proof-of-work en incrementant un nonce dans le bloc jusqu'a ce qu'une valeur soit trouvee qui donne au hash du bloc les bits zero requis. Une fois que l'effort CPU a ete depense pour satisfaire le proof-of-work, le bloc ne peut pas etre modifie sans refaire le travail. Comme les blocs ulterieurs sont chaines apres lui, le travail pour modifier le bloc inclurait de refaire tous les blocs apres lui.

Le proof-of-work resout egalement le probleme de la determination de la representation dans la prise de decision majoritaire. Si la majorite etait basee sur une-adresse-IP-un-vote, elle pourrait etre corrompue par quiconque capable d'allouer de nombreuses adresses IP. Le proof-of-work est essentiellement un-CPU-un-vote. La decision majoritaire est representee par la chaine la plus longue, qui a le plus grand effort de proof-of-work investi. Si une majorite de la puissance CPU est controlee par des noeuds honnetes, la chaine honnete croitra le plus rapidement et devancera toutes les chaines concurrentes. Pour modifier un bloc passe, un attaquant devrait refaire le proof-of-work du bloc et de tous les blocs apres lui, puis rattraper et depasser le travail des noeuds honnetes. Nous montrerons plus tard que la probabilite qu'un attaquant plus lent rattrape diminue exponentiellement a mesure que des blocs subsequents sont ajoutes.

Pour compenser la vitesse croissante du materiel et l'interet variable pour l'exploitation des noeuds au fil du temps, la difficulte du proof-of-work est determinee par une moyenne mobile visant un nombre moyen de blocs par heure. S'ils sont generes trop rapidement, la difficulte augmente.

Network

Les etapes pour faire fonctionner le reseau sont les suivantes :

1. Les nouvelles transactions sont diffusees a tous les noeuds.
2. Chaque noeud collecte les nouvelles transactions dans un bloc.
3. Chaque noeud travaille a trouver un proof-of-work difficile pour son bloc.
4. Lorsqu'un noeud trouve un proof-of-work, il diffuse le bloc a tous les noeuds.
5. Les noeuds acceptent le bloc uniquement si toutes les transactions qu'il contient sont valides et n'ont pas deja ete depensees.
6. Les noeuds expriment leur acceptation du bloc en travaillant a la creation du bloc suivant dans la chaine, en utilisant le hash du bloc accepte comme hash precedent.

Les noeuds considerent toujours la chaine la plus longue comme etant la correcte et continueront a travailler a son extension. Si deux noeuds diffusent des versions differentes du bloc suivant simultanement, certains noeuds peuvent recevoir l'une ou l'autre en premier. Dans ce cas, ils travaillent sur la premiere qu'ils ont recue, mais conservent l'autre branche au cas ou elle deviendrait plus longue. L'egalite sera brisee lorsque le prochain proof-of-work sera trouve et qu'une branche deviendra plus longue ; les noeuds qui travaillaient sur l'autre branche basculeront alors sur la plus longue.

Les diffusions de nouvelles transactions n'ont pas necessairement besoin d'atteindre tous les noeuds. Tant qu'elles atteignent de nombreux noeuds, elles seront integrees dans un bloc sous peu. Les diffusions de blocs sont egalement tolerantes aux messages perdus. Si un noeud ne recoit pas un bloc, il le demandera lorsqu'il recevra le bloc suivant et realisera qu'il en a manque un.

Incentive

Par convention, la premiere transaction d'un bloc est une transaction speciale qui cree une nouvelle piece appartenant au createur du bloc. Cela ajoute une incitation pour les noeuds a soutenir le reseau et fournit un moyen de distribuer initialement les pieces en circulation, puisqu'il n'y a pas d'autorite centrale pour les emettre. L'ajout regulier d'une quantite constante de nouvelles pieces est analogue aux mineurs d'or qui depensent des ressources pour ajouter de l'or en circulation. Dans notre cas, ce sont le temps CPU et l'electricite qui sont depenses.

L'incitation peut aussi etre financee par les frais de transaction. Si la valeur de sortie d'une transaction est inferieure a sa valeur d'entree, la difference est un frais de transaction qui s'ajoute a la valeur d'incitation du bloc contenant la transaction. Une fois qu'un nombre predetermine de pieces est entre en circulation, l'incitation peut passer entierement aux frais de transaction et etre completement exempte d'inflation.

L'incitation peut aider a encourager les noeuds a rester honnetes. Si un attaquant cupide est capable de rassembler plus de puissance CPU que tous les noeuds honnetes, il devrait choisir entre l'utiliser pour escroquer les gens en volant ses paiements, ou l'utiliser pour generer de nouvelles pieces. Il devrait trouver plus profitable de jouer selon les regles, des regles qui le favorisent avec plus de nouvelles pieces que tous les autres combines, plutot que de saper le systeme et la validite de sa propre richesse.

Reclaiming Disk Space

Une fois que la derniere transaction d'une piece est enfouie sous suffisamment de blocs, les transactions depensees avant elle peuvent etre supprimees pour economiser de l'espace disque. Pour faciliter cela sans casser le hash du bloc, les transactions sont hachees dans un Merkle Tree [^7] [^2] [^5], avec seule la racine incluse dans le hash du bloc. Les anciens blocs peuvent alors etre compactes en elaguant les branches de l'arbre. Les hash interieurs n'ont pas besoin d'etre stockes.

Un en-tete de bloc sans transactions ferait environ 80 octets. Si nous supposons que les blocs sont generes toutes les 10 minutes, 80 octets * 6 * 24 * 365 = 4,2 Mo par an. Avec des systemes informatiques generalement vendus avec 2 Go de RAM en 2008, et la loi de Moore prevoyant une croissance actuelle de 1,2 Go par an, le stockage ne devrait pas etre un probleme meme si les en-tetes de blocs doivent etre conserves en memoire.

Simplified Payment Verification

Il est possible de verifier les paiements sans faire fonctionner un noeud reseau complet. Un utilisateur n'a besoin que de conserver une copie des en-tetes de blocs de la plus longue chaine de proof-of-work, qu'il peut obtenir en interrogeant les noeuds du reseau jusqu'a ce qu'il soit convaincu d'avoir la chaine la plus longue, et d'obtenir la branche Merkle reliant la transaction au bloc dans lequel elle est horodatee. Il ne peut pas verifier la transaction par lui-meme, mais en la reliant a un endroit dans la chaine, il peut voir qu'un noeud du reseau l'a acceptee, et les blocs ajoutes apres confirment davantage que le reseau l'a acceptee.

En tant que telle, la verification est fiable tant que les noeuds honnetes controlent le reseau, mais est plus vulnerable si le reseau est domine par un attaquant. Bien que les noeuds du reseau puissent verifier les transactions par eux-memes, la methode simplifiee peut etre trompee par les transactions fabriquees d'un attaquant tant que l'attaquant peut continuer a dominer le reseau. Une strategie pour se proteger contre cela serait d'accepter les alertes des noeuds du reseau lorsqu'ils detectent un bloc invalide, incitant le logiciel de l'utilisateur a telecharger le bloc complet et les transactions signalees pour confirmer l'incoherence. Les entreprises qui recoivent des paiements frequents voudront probablement toujours faire fonctionner leurs propres noeuds pour une securite plus independante et une verification plus rapide.

Combining and Splitting Value

Bien qu'il soit possible de gerer les pieces individuellement, il serait peu pratique de faire une transaction separee pour chaque centime dans un transfert. Pour permettre de diviser et combiner la valeur, les transactions contiennent des entrees et des sorties multiples. Normalement, il y aura soit une seule entree provenant d'une transaction precedente plus importante, soit plusieurs entrees combinant des montants plus petits, et au plus deux sorties : une pour le paiement, et une restituant la monnaie, le cas echeant, a l'expediteur.

Il convient de noter que l'eventail, ou une transaction depend de plusieurs transactions, et ces transactions dependent de beaucoup d'autres, n'est pas un probleme ici. Il n'y a jamais besoin d'extraire une copie autonome complete de l'historique d'une transaction.

Privacy

Le modele bancaire traditionnel atteint un niveau de confidentialite en limitant l'acces a l'information aux parties concernees et au tiers de confiance. La necessite d'annoncer toutes les transactions publiquement exclut cette methode, mais la confidentialite peut toujours etre maintenue en rompant le flux d'informations a un autre endroit : en gardant les cles publiques anonymes. Le public peut voir que quelqu'un envoie un montant a quelqu'un d'autre, mais sans information reliant la transaction a quiconque. Ceci est similaire au niveau d'information publie par les bourses, ou le moment et la taille des transactions individuelles, le "ruban", sont rendus publics, mais sans dire qui etaient les parties.

Comme pare-feu supplementaire, une nouvelle paire de cles devrait etre utilisee pour chaque transaction afin de les empecher d'etre liees a un proprietaire commun. Un certain lien est toujours inevitable avec les transactions a entrees multiples, qui revelent necessairement que leurs entrees appartenaient au meme proprietaire. Le risque est que si le proprietaire d'une cle est revele, le lien pourrait reveler d'autres transactions qui appartenaient au meme proprietaire.

Calculations

Nous considerons le scenario d'un attaquant essayant de generer une chaine alternative plus rapidement que la chaine honnete. Meme si cela est accompli, cela n'ouvre pas le systeme a des modifications arbitraires, comme creer de la valeur a partir de rien ou prendre de l'argent qui n'a jamais appartenu a l'attaquant. Les noeuds n'accepteront pas une transaction invalide comme paiement, et les noeuds honnetes n'accepteront jamais un bloc les contenant. Un attaquant ne peut qu'essayer de modifier une de ses propres transactions pour recuperer l'argent qu'il a recemment depense.

La course entre la chaine honnete et la chaine d'un attaquant peut etre caracterisee comme une marche aleatoire binomiale. L'evenement de succes est l'extension de la chaine honnete d'un bloc, augmentant son avance de +1, et l'evenement d'echec est l'extension de la chaine de l'attaquant d'un bloc, reduisant l'ecart de -1.

La probabilite qu'un attaquant rattrape a partir d'un deficit donne est analogue au probleme de la ruine du joueur. Supposons qu'un joueur avec un credit illimite commence avec un deficit et joue potentiellement un nombre infini d'essais pour tenter d'atteindre l'equilibre. Nous pouvons calculer la probabilite qu'il atteigne un jour l'equilibre, ou qu'un attaquant rattrape un jour la chaine honnete, comme suit [^8] :

p = probability an honest node finds the next block
q = probability the attacker finds the next block
q = probability the attacker will ever catch up from z blocks behind
``````

\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]

Etant donne notre hypothese que p  q, la probabilite diminue exponentiellement a mesure que le nombre de blocs que l'attaquant doit rattraper augmente. Avec les chances contre lui, s'il ne fait pas une poussee chanceuse en avant tot, ses chances deviennent infiniment petites a mesure qu'il prend du retard.

Nous considerons maintenant combien de temps le destinataire d'une nouvelle transaction doit attendre avant d'etre suffisamment certain que l'expediteur ne peut pas modifier la transaction. Nous supposons que l'expediteur est un attaquant qui veut faire croire au destinataire qu'il l'a paye pendant un certain temps, puis basculer pour se rembourser lui-meme apres un certain temps. Le destinataire sera alerte quand cela se produira, mais l'expediteur espere qu'il sera trop tard.

Le destinataire genere une nouvelle paire de cles et donne la cle publique a l'expediteur peu avant la signature. Cela empeche l'expediteur de preparer une chaine de blocs a l'avance en y travaillant continuellement jusqu'a ce qu'il ait la chance d'etre suffisamment en avance, puis d'executer la transaction a ce moment-la. Une fois la transaction envoyee, l'expediteur malhonnete commence a travailler en secret sur une chaine parallele contenant une version alternative de sa transaction.

Le destinataire attend que la transaction ait ete ajoutee a un bloc et que z blocs aient ete lies apres. Il ne connait pas la quantite exacte de progres que l'attaquant a fait, mais en supposant que les blocs honnetes ont pris le temps moyen attendu par bloc, le progres potentiel de l'attaquant sera une distribution de Poisson avec la valeur attendue :

\[
\lambda = z\frac{q}{p}
\]

Pour obtenir la probabilite que l'attaquant puisse encore rattraper maintenant, nous multiplions la densite de Poisson pour chaque quantite de progres qu'il aurait pu faire par la probabilite qu'il puisse rattraper a partir de ce point :

\[
\sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{
\begin{array}{cl}
\left(\frac{q}{p}\right)^{(z-k)} & \text{if } k \leq z \\
1 & \text{if } k > z
\end{array}
\right.
\]

Rearrangement pour eviter de sommer la queue infinie de la distribution...

\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]

Conversion en code C...

```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 executant quelques resultats, nous pouvons voir la probabilite 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

Resolution pour P inferieur a 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

Conclusion

Nous avons propose un systeme pour les transactions electroniques sans reposer sur la confiance. Nous avons commence avec le cadre habituel de pieces faites de signatures numeriques, qui fournit un controle fort de la propriete, mais est incomplet sans un moyen de prevenir la double depense. Pour resoudre cela, nous avons propose un reseau pair-a-pair utilisant le proof-of-work pour enregistrer un historique public des transactions qui devient rapidement informatiquement impraticable a modifier pour un attaquant si les noeuds honnetes controlent une majorite de la puissance CPU. Le reseau est robuste dans sa simplicite non structuree. Les noeuds travaillent tous en meme temps avec peu de coordination. Ils n'ont pas besoin d'etre identifies, puisque les messages ne sont pas achemines vers un endroit particulier et n'ont besoin d'etre delivres qu'au mieux. Les noeuds peuvent quitter et rejoindre le reseau a volonte, acceptant la chaine de proof-of-work comme preuve de ce qui s'est passe pendant leur absence. Ils votent avec leur puissance CPU, exprimant leur acceptation des blocs valides en travaillant a les etendre et rejetant les blocs invalides en refusant de travailler dessus. Toutes les regles et incitations necessaires peuvent etre appliquees avec ce mecanisme de consensus.

References