Bitcoin : Un système de monnaie électronique pair-à-pair
Abstract
Una version puramente peer-to-peer de dinero electronico permitiria enviar pagos en linea directamente de una parte a otra sin pasar por una institucion financiera. Las firmas digitales proporcionan parte de la solucion, pero los principales beneficios se pierden si todavia se requiere un tercero de confianza para prevenir el doble gasto. Proponemos una solucion al problema del doble gasto utilizando una red peer-to-peer. La red marca temporalmente las transacciones al incluirlas mediante hash en una cadena continua de proof-of-work basada en hash, formando un registro que no puede ser modificado sin rehacer el proof-of-work. La cadena mas larga no solo sirve como prueba de la secuencia de eventos presenciados, sino como prueba de que proviene del mayor conjunto de poder de CPU. Mientras la mayoria del poder de CPU este controlado por nodos que no cooperan para atacar la red, generaran la cadena mas larga y superaran a los atacantes. La red en si requiere una estructura minima. Los mensajes se transmiten con base en el mejor esfuerzo, y los nodos pueden abandonar y reincorporarse a la red a voluntad, aceptando la cadena de proof-of-work mas larga como prueba de lo que ocurrio mientras estuvieron ausentes.
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
El comercio en Internet ha llegado a depender casi exclusivamente de instituciones financieras que sirven como terceros de confianza para procesar pagos electronicos. Si bien el sistema funciona suficientemente bien para la mayoria de las transacciones, todavia adolece de las debilidades inherentes del modelo basado en la confianza. Las transacciones completamente irreversibles no son realmente posibles, ya que las instituciones financieras no pueden evitar mediar en disputas. El costo de la mediacion aumenta los costos de transaccion, limitando el tamano minimo practico de la transaccion y eliminando la posibilidad de pequenas transacciones casuales, y existe un costo mas amplio en la perdida de la capacidad de realizar pagos irreversibles por servicios irreversibles. Con la posibilidad de reversion, la necesidad de confianza se extiende. Los comerciantes deben desconfiar de sus clientes, solicitandoles mas informacion de la que de otro modo necesitarian. Un cierto porcentaje de fraude se acepta como inevitable. Estos costos e incertidumbres de pago pueden evitarse en persona utilizando moneda fisica, pero no existe ningun mecanismo para realizar pagos a traves de un canal de comunicacion sin un tercero de confianza.
Lo que se necesita es un sistema de pago electronico basado en prueba criptografica en lugar de confianza, que permita a dos partes dispuestas realizar transacciones directamente entre si sin la necesidad de un tercero de confianza. Las transacciones que son computacionalmente impracticas de revertir protegerian a los vendedores del fraude, y mecanismos rutinarios de deposito en garantia podrian implementarse facilmente para proteger a los compradores. En este documento, proponemos una solucion al problema del doble gasto utilizando un servidor de marcas de tiempo distribuido peer-to-peer para generar prueba computacional del orden cronologico de las transacciones. El sistema es seguro mientras los nodos honestos controlen colectivamente mas poder de CPU que cualquier grupo cooperante de nodos atacantes.
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
Definimos una moneda electronica como una cadena de firmas digitales. Cada propietario transfiere la moneda al siguiente firmando digitalmente un hash de la transaccion anterior y la clave publica del siguiente propietario, y anadiendo estos al final de la moneda. Un beneficiario puede verificar las firmas para verificar la cadena de propiedad.
El problema, por supuesto, es que el beneficiario no puede verificar que uno de los propietarios no haya gastado doblemente la moneda. Una solucion comun es introducir una autoridad central de confianza, o casa de moneda, que verifique cada transaccion en busca de doble gasto. Despues de cada transaccion, la moneda debe ser devuelta a la casa de moneda para emitir una nueva moneda, y solo las monedas emitidas directamente por la casa de moneda son confiables de no haber sido doblemente gastadas. El problema con esta solucion es que el destino de todo el sistema monetario depende de la empresa que administra la casa de moneda, y cada transaccion debe pasar por ella, igual que un banco.
Necesitamos una forma para que el beneficiario sepa que los propietarios anteriores no firmaron ninguna transaccion previa. Para nuestros propositos, la transaccion mas temprana es la que cuenta, por lo que no nos preocupan los intentos posteriores de doble gasto. La unica forma de confirmar la ausencia de una transaccion es estar al tanto de todas las transacciones. En el modelo basado en la casa de moneda, esta estaba al tanto de todas las transacciones y decidia cual llego primero. Para lograr esto sin un tercero de confianza, las transacciones deben ser anunciadas publicamente [^1], y necesitamos un sistema para que los participantes acuerden un unico historial del orden en que fueron recibidas. El beneficiario necesita prueba de que, en el momento de cada transaccion, la mayoria de los nodos acordo que fue la primera recibida.
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 solucion que proponemos comienza con un servidor de marcas de tiempo. Un servidor de marcas de tiempo funciona tomando un hash de un bloque de elementos a los que se les asignara una marca de tiempo y publicando ampliamente el hash, como en un periodico o una publicacion de Usenet [^2] [^3] [^4] [^5]. La marca de tiempo demuestra que los datos deben haber existido en ese momento, obviamente, para poder ser incluidos en el hash. Cada marca de tiempo incluye la marca de tiempo anterior en su hash, formando una cadena, donde cada marca de tiempo adicional refuerza las anteriores.
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
Para implementar un servidor de marcas de tiempo distribuido en una base peer-to-peer, necesitaremos utilizar un sistema de proof-of-work similar al Hashcash de Adam Back [^6], en lugar de publicaciones en periodicos o Usenet. El proof-of-work implica buscar un valor que, al ser hasheado, como con SHA-256, el hash comience con un numero de bits cero. El trabajo promedio requerido es exponencial en el numero de bits cero requeridos y puede verificarse ejecutando un unico hash.
Para nuestra red de marcas de tiempo, implementamos el proof-of-work incrementando un nonce en el bloque hasta que se encuentra un valor que le da al hash del bloque los bits cero requeridos. Una vez que el esfuerzo de CPU se ha gastado para satisfacer el proof-of-work, el bloque no puede ser cambiado sin rehacer el trabajo. A medida que se encadenan bloques posteriores, el trabajo para cambiar el bloque incluiria rehacer todos los bloques posteriores.
El proof-of-work tambien resuelve el problema de determinar la representacion en la toma de decisiones por mayoria. Si la mayoria se basara en una-direccion-IP-un-voto, podria ser subvertida por cualquiera capaz de asignar muchas IPs. El proof-of-work es esencialmente un-CPU-un-voto. La decision mayoritaria esta representada por la cadena mas larga, que tiene el mayor esfuerzo de proof-of-work invertido en ella. Si la mayoria del poder de CPU esta controlada por nodos honestos, la cadena honesta crecera mas rapido y superara a cualquier cadena competidora. Para modificar un bloque pasado, un atacante tendria que rehacer el proof-of-work del bloque y todos los bloques posteriores, y luego alcanzar y superar el trabajo de los nodos honestos. Mostraremos mas adelante que la probabilidad de que un atacante mas lento alcance a los demas disminuye exponencialmente a medida que se anaden bloques subsiguientes.
Para compensar el aumento de la velocidad del hardware y el interes variable en ejecutar nodos a lo largo del tiempo, la dificultad del proof-of-work se determina mediante un promedio movil que apunta a un numero promedio de bloques por hora. Si se generan demasiado rapido, la dificultad aumenta.
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
Los pasos para ejecutar la red son los siguientes:
- Las nuevas transacciones se transmiten a todos los nodos.
- Cada nodo recopila nuevas transacciones en un bloque.
- Cada nodo trabaja en encontrar un proof-of-work dificil para su bloque.
- Cuando un nodo encuentra un proof-of-work, transmite el bloque a todos los nodos.
- Los nodos aceptan el bloque solo si todas las transacciones en el son validas y no han sido gastadas previamente.
- Los nodos expresan su aceptacion del bloque trabajando en crear el siguiente bloque en la cadena, utilizando el hash del bloque aceptado como el hash anterior.
Los nodos siempre consideran la cadena mas larga como la correcta y continuaran trabajando para extenderla. Si dos nodos transmiten diferentes versiones del siguiente bloque simultaneamente, algunos nodos pueden recibir una u otra primero. En ese caso, trabajan en la primera que recibieron, pero guardan la otra rama en caso de que se vuelva mas larga. El empate se rompera cuando se encuentre el siguiente proof-of-work y una rama se vuelva mas larga; los nodos que estaban trabajando en la otra rama cambiaran entonces a la mas larga.
Las transmisiones de nuevas transacciones no necesariamente necesitan llegar a todos los nodos. Mientras lleguen a muchos nodos, entraran en un bloque en poco tiempo. Las transmisiones de bloques tambien son tolerantes a mensajes perdidos. Si un nodo no recibe un bloque, lo solicitara cuando reciba el siguiente bloque y se de cuenta de que le falta uno.
Network
Les etapes pour faire fonctionner le reseau sont les suivantes :
- Les nouvelles transactions sont diffusees a tous les noeuds.
- Chaque noeud collecte les nouvelles transactions dans un bloc.
- Chaque noeud travaille a trouver un proof-of-work difficile pour son bloc.
- Lorsqu'un noeud trouve un proof-of-work, il diffuse le bloc a tous les noeuds.
- Les noeuds acceptent le bloc uniquement si toutes les transactions qu'il contient sont valides et n'ont pas deja ete depensees.
- 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
Por convencion, la primera transaccion en un bloque es una transaccion especial que inicia una nueva moneda propiedad del creador del bloque. Esto anade un incentivo para que los nodos apoyen la red, y proporciona una forma de distribuir inicialmente monedas en circulacion, ya que no existe una autoridad central para emitirlas. La adicion constante de una cantidad fija de nuevas monedas es analoga a los mineros de oro que gastan recursos para anadir oro a la circulacion. En nuestro caso, es el tiempo de CPU y la electricidad lo que se gasta.
El incentivo tambien puede financiarse con tarifas de transaccion. Si el valor de salida de una transaccion es menor que su valor de entrada, la diferencia es una tarifa de transaccion que se anade al valor del incentivo del bloque que contiene la transaccion. Una vez que un numero predeterminado de monedas ha entrado en circulacion, el incentivo puede transicionar completamente a tarifas de transaccion y estar completamente libre de inflacion.
El incentivo puede ayudar a alentar a los nodos a mantenerse honestos. Si un atacante codicioso es capaz de reunir mas poder de CPU que todos los nodos honestos, tendria que elegir entre usarlo para defraudar a las personas robando sus pagos, o usarlo para generar nuevas monedas. Deberia encontrar mas rentable jugar segun las reglas, reglas que lo favorecen con mas monedas nuevas que todos los demas combinados, que socavar el sistema y la validez de su propia riqueza.
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
Una vez que la ultima transaccion en una moneda esta enterrada bajo suficientes bloques, las transacciones gastadas anteriores pueden descartarse para ahorrar espacio en disco. Para facilitar esto sin romper el hash del bloque, las transacciones se hashean en un Merkle Tree [^7] [^2] [^5], con solo la raiz incluida en el hash del bloque. Los bloques antiguos pueden entonces compactarse eliminando ramas del arbol. Los hashes interiores no necesitan ser almacenados.
Un encabezado de bloque sin transacciones seria de aproximadamente 80 bytes. Si suponemos que los bloques se generan cada 10 minutos, 80 bytes * 6 * 24 * 365 = 4.2MB por ano. Con los sistemas informaticos que tipicamente se vendian con 2GB de RAM en 2008, y la Ley de Moore prediciendo un crecimiento actual de 1.2GB por ano, el almacenamiento no deberia ser un problema incluso si los encabezados de bloque deben mantenerse en memoria.
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
Es posible verificar pagos sin ejecutar un nodo completo de la red. Un usuario solo necesita mantener una copia de los encabezados de bloque de la cadena de proof-of-work mas larga, que puede obtener consultando los nodos de la red hasta estar convencido de que tiene la cadena mas larga, y obtener la rama del Merkle Tree que vincula la transaccion al bloque en el que se le asigno la marca de tiempo. No puede verificar la transaccion por si mismo, pero al vincularla a un lugar en la cadena, puede ver que un nodo de la red la ha aceptado, y los bloques anadidos despues de ella confirman aun mas que la red la ha aceptado.
Como tal, la verificacion es confiable mientras los nodos honestos controlen la red, pero es mas vulnerable si la red es dominada por un atacante. Aunque los nodos de la red pueden verificar las transacciones por si mismos, el metodo simplificado puede ser enganado por transacciones fabricadas de un atacante mientras este pueda continuar dominando la red. Una estrategia para protegerse contra esto seria aceptar alertas de los nodos de la red cuando detecten un bloque invalido, solicitando al software del usuario descargar el bloque completo y las transacciones alertadas para confirmar la inconsistencia. Los negocios que reciben pagos frecuentes probablemente aun querran ejecutar sus propios nodos para una seguridad mas independiente y una verificacion mas rapida.
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
Aunque seria posible manejar monedas individualmente, seria poco practico hacer una transaccion separada por cada centavo en una transferencia. Para permitir que el valor se divida y combine, las transacciones contienen multiples entradas y salidas. Normalmente habra una unica entrada de una transaccion previa mayor o multiples entradas que combinan cantidades menores, y como maximo dos salidas: una para el pago, y una devolviendo el cambio, si lo hay, al remitente.
Cabe senalar que la ramificacion, donde una transaccion depende de varias transacciones, y esas transacciones dependen de muchas mas, no es un problema aqui. Nunca es necesario extraer una copia completa e independiente del historial de una transaccion.
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
El modelo bancario tradicional logra un nivel de privacidad limitando el acceso a la informacion a las partes involucradas y al tercero de confianza. La necesidad de anunciar todas las transacciones publicamente excluye este metodo, pero la privacidad aun puede mantenerse rompiendo el flujo de informacion en otro lugar: manteniendo las claves publicas anonimas. El publico puede ver que alguien esta enviando una cantidad a alguien mas, pero sin informacion que vincule la transaccion a nadie. Esto es similar al nivel de informacion publicado por las bolsas de valores, donde el tiempo y tamano de las operaciones individuales, la "cinta", se hace publica, pero sin revelar quienes fueron las partes.
Como cortafuegos adicional, se deberia usar un nuevo par de claves para cada transaccion para evitar que se vinculen a un propietario comun. Cierto grado de vinculacion es aun inevitable con transacciones de multiples entradas, que necesariamente revelan que sus entradas pertenecian al mismo propietario. El riesgo es que si se revela el propietario de una clave, la vinculacion podria revelar otras transacciones que pertenecieron al mismo propietario.
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
Consideramos el escenario de un atacante que intenta generar una cadena alternativa mas rapido que la cadena honesta. Incluso si esto se logra, no abre el sistema a cambios arbitrarios, como crear valor de la nada o tomar dinero que nunca pertenecio al atacante. Los nodos no van a aceptar una transaccion invalida como pago, y los nodos honestos nunca aceptaran un bloque que las contenga. Un atacante solo puede intentar cambiar una de sus propias transacciones para recuperar dinero que gasto recientemente.
La carrera entre la cadena honesta y la cadena de un atacante puede caracterizarse como un Paseo Aleatorio Binomial. El evento de exito es que la cadena honesta se extienda un bloque, aumentando su ventaja en +1, y el evento de fracaso es que la cadena del atacante se extienda un bloque, reduciendo la brecha en -1.
La probabilidad de que un atacante alcance desde un deficit dado es analoga al problema de la Ruina del Jugador. Supongamos que un jugador con credito ilimitado comienza con un deficit y juega potencialmente un numero infinito de intentos para tratar de alcanzar el punto de equilibrio. Podemos calcular la probabilidad de que alguna vez alcance el punto de equilibrio, o de que un atacante alguna vez alcance a la cadena honesta, de la siguiente manera [^8]:
p = probabilidad de que un nodo honesto encuentre el siguiente bloque
q = probabilidad de que el atacante encuentre el siguiente bloque
q = probabilidad de que el atacante alguna vez alcance desde z bloques detras
``````
\[
qz =
\begin{cases}
1 & \text{if } p \leq q \\
\left(\frac{q}{p}\right) z & \text{if } p > q
\end{cases}
\]
Dada nuestra suposicion de que p q, la probabilidad cae exponencialmente a medida que aumenta el numero de bloques que el atacante tiene que alcanzar. Con las probabilidades en su contra, si no logra un avance afortunado temprano, sus posibilidades se vuelven infinitesimalmente pequenas a medida que queda mas atras.
Ahora consideramos cuanto tiempo necesita esperar el destinatario de una nueva transaccion antes de estar suficientemente seguro de que el remitente no puede cambiar la transaccion. Asumimos que el remitente es un atacante que quiere hacer creer al destinatario que le pago durante un tiempo, y luego cambiarlo para pagarse a si mismo despues de que haya pasado algun tiempo. El receptor sera alertado cuando eso suceda, pero el remitente espera que sea demasiado tarde.
El receptor genera un nuevo par de claves y entrega la clave publica al remitente poco antes de firmar. Esto evita que el remitente prepare una cadena de bloques con anticipacion trabajando en ella continuamente hasta que tenga la suerte de adelantarse lo suficiente, y luego ejecutar la transaccion en ese momento. Una vez que la transaccion es enviada, el remitente deshonesto comienza a trabajar en secreto en una cadena paralela que contiene una version alternativa de su transaccion.
El destinatario espera hasta que la transaccion se haya anadido a un bloque y z bloques se hayan vinculado despues de el. No conoce la cantidad exacta de progreso que el atacante ha hecho, pero asumiendo que los bloques honestos tomaron el tiempo promedio esperado por bloque, el progreso potencial del atacante sera una distribucion de Poisson con valor esperado:
\[
\lambda = z\frac{q}{p}
\]
Para obtener la probabilidad de que el atacante aun pueda alcanzar, multiplicamos la densidad de Poisson para cada cantidad de progreso que podria haber hecho por la probabilidad de que pueda alcanzar desde ese punto:
\[
\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.
\]
Reorganizando para evitar sumar la cola infinita de la distribucion...
\[
1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right)
\]
Convirtiendo a codigo 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;
}
Ejecutando algunos resultados, podemos ver que la probabilidad cae exponencialmente con 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
Resolviendo para P menor que 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
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
Hemos propuesto un sistema para transacciones electronicas sin depender de la confianza. Comenzamos con el marco habitual de monedas hechas de firmas digitales, que proporciona un fuerte control de propiedad, pero es incompleto sin una forma de prevenir el doble gasto. Para resolver esto, propusimos una red peer-to-peer que utiliza proof-of-work para registrar un historial publico de transacciones que rapidamente se vuelve computacionalmente impractico de cambiar para un atacante si los nodos honestos controlan la mayoria del poder de CPU. La red es robusta en su simplicidad no estructurada. Los nodos trabajan todos a la vez con poca coordinacion. No necesitan ser identificados, ya que los mensajes no se enrutan a ningun lugar particular y solo necesitan ser entregados con base en el mejor esfuerzo. Los nodos pueden abandonar y reincorporarse a la red a voluntad, aceptando la cadena de proof-of-work como prueba de lo que ocurrio mientras estuvieron ausentes. Votan con su poder de CPU, expresando su aceptacion de bloques validos al trabajar en extenderlos y rechazando bloques invalidos al negarse a trabajar en ellos. Cualquier regla e incentivo necesario puede ser aplicado con este mecanismo de consenso.
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
-
H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
-
S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
References
-
H. Massias, X.S. Avila, and J.-J. Quisquater, "Design of a secure timestamping service with minimal trust requirements," In 20th Symposium on Information Theory in the Benelux, May 1999.
-
S. Haber, W.S. Stornetta, "How to time-stamp a digital document," In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991.
-
D. Bayer, S. Haber, W.S. Stornetta, "Improving the efficiency and reliability of digital time-stamping," In Sequences II: Methods in Communication, Security and Computer Science, pages 329-334, 1993.
-
S. Haber, W.S. Stornetta, "Secure names for bit-strings," In Proceedings of the 4th ACM Conference on Computer and Communications Security, pages 28-35, April 1997.
-
A. Back, "Hashcash - a denial of service counter-measure," http://www.hashcash.org/papers/hashcash.pdf, 2002.
-
R.C. Merkle, "Protocols for public key cryptosystems," In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980.
-
W. Feller, "An introduction to probability theory and its applications," 1957.
