Bitcoin : Un système de monnaie électronique pair-à-pair
Abstract
Uma versao puramente peer-to-peer de dinheiro eletronico permitiria que pagamentos online fossem enviados diretamente de uma parte para outra sem passar por uma instituicao financeira. Assinaturas digitais fornecem parte da solucao, mas os principais beneficios sao perdidos se um terceiro confiavel ainda for necessario para prevenir o gasto duplo. Propomos uma solucao para o problema do gasto duplo usando uma rede peer-to-peer. A rede carimba as transacoes com timestamps fazendo hash delas em uma cadeia continua de proof-of-work baseada em hash, formando um registro que nao pode ser alterado sem refazer o proof-of-work. A cadeia mais longa nao serve apenas como prova da sequencia de eventos testemunhados, mas tambem como prova de que ela veio do maior conjunto de poder de CPU. Enquanto a maioria do poder de CPU for controlada por nos que nao estao cooperando para atacar a rede, eles gerarao a cadeia mais longa e superarao os atacantes. A rede em si requer estrutura minima. As mensagens sao transmitidas com base no melhor esforco, e os nos podem sair e reingressar na rede a qualquer momento, aceitando a cadeia de proof-of-work mais longa como prova do que aconteceu enquanto estavam 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
O comercio na Internet passou a depender quase exclusivamente de instituicoes financeiras servindo como terceiros confiaveis para processar pagamentos eletronicos. Embora o sistema funcione bem o suficiente para a maioria das transacoes, ele ainda sofre das fraquezas inerentes ao modelo baseado em confianca. Transacoes completamente irreversiveis nao sao realmente possiveis, uma vez que as instituicoes financeiras nao podem evitar a mediacao de disputas. O custo da mediacao aumenta os custos de transacao, limitando o tamanho minimo pratico da transacao e eliminando a possibilidade de pequenas transacoes casuais, e ha um custo mais amplo na perda da capacidade de fazer pagamentos irreversiveis para servicos irreversiveis. Com a possibilidade de reversao, a necessidade de confianca se espalha. Os comerciantes devem desconfiar de seus clientes, solicitando mais informacoes do que seria necessario. Uma certa porcentagem de fraude e aceita como inevitavel. Esses custos e incertezas de pagamento podem ser evitados pessoalmente usando moeda fisica, mas nenhum mecanismo existe para fazer pagamentos por um canal de comunicacao sem uma parte confiavel.
O que e necessario e um sistema de pagamento eletronico baseado em prova criptografica em vez de confianca, permitindo que quaisquer duas partes dispostas transacionem diretamente entre si sem a necessidade de um terceiro confiavel. Transacoes que sao computacionalmente impraticaveis de reverter protegeriam os vendedores contra fraudes, e mecanismos rotineiros de custodia poderiam ser facilmente implementados para proteger os compradores. Neste artigo, propomos uma solucao para o problema do gasto duplo usando um servidor de timestamp distribuido peer-to-peer para gerar prova computacional da ordem cronologica das transacoes. O sistema e seguro enquanto nos honestos controlarem coletivamente mais poder de CPU do que qualquer grupo cooperante de nos 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 uma moeda eletronica como uma cadeia de assinaturas digitais. Cada proprietario transfere a moeda para o proximo assinando digitalmente um hash da transacao anterior e a chave publica do proximo proprietario e adicionando estes ao final da moeda. Um beneficiario pode verificar as assinaturas para verificar a cadeia de propriedade.
O problema, claro, e que o beneficiario nao pode verificar se um dos proprietarios nao gastou a moeda duas vezes. Uma solucao comum e introduzir uma autoridade central confiavel, ou casa da moeda, que verifica cada transacao quanto ao gasto duplo. Apos cada transacao, a moeda deve ser devolvida a casa da moeda para emitir uma nova moeda, e apenas moedas emitidas diretamente pela casa da moeda sao confiaveis quanto a nao terem sido gastas duas vezes. O problema com esta solucao e que o destino de todo o sistema monetario depende da empresa que administra a casa da moeda, com cada transacao tendo que passar por eles, assim como um banco.
Precisamos de uma maneira para o beneficiario saber que os proprietarios anteriores nao assinaram nenhuma transacao anterior. Para nossos propositos, a transacao mais antiga e a que conta, entao nao nos preocupamos com tentativas posteriores de gasto duplo. A unica maneira de confirmar a ausencia de uma transacao e estar ciente de todas as transacoes. No modelo baseado na casa da moeda, a casa da moeda estava ciente de todas as transacoes e decidia qual chegou primeiro. Para conseguir isso sem uma parte confiavel, as transacoes devem ser anunciadas publicamente [^1], e precisamos de um sistema para que os participantes concordem com um unico historico da ordem em que foram recebidas. O beneficiario precisa de prova de que, no momento de cada transacao, a maioria dos nos concordou que ela foi a primeira recebida.
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
A solucao que propomos comeca com um servidor de timestamp. Um servidor de timestamp funciona pegando um hash de um bloco de itens a serem carimbados com timestamp e publicando amplamente o hash, como em um jornal ou postagem Usenet [^2] [^3] [^4] [^5]. O timestamp prova que os dados devem ter existido naquele momento, obviamente, para entrar no hash. Cada timestamp inclui o timestamp anterior em seu hash, formando uma cadeia, com cada timestamp adicional reforcando os 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 um servidor de timestamp distribuido em uma base peer-to-peer, precisaremos usar um sistema de proof-of-work semelhante ao Hashcash de Adam Back [^6], em vez de jornais ou postagens Usenet. O proof-of-work envolve a varredura de um valor que, quando submetido a hash, como com SHA-256, o hash comeca com um numero de bits zero. O trabalho medio necessario e exponencial no numero de bits zero requeridos e pode ser verificado executando um unico hash.
Para nossa rede de timestamp, implementamos o proof-of-work incrementando um nonce no bloco ate que um valor seja encontrado que de ao hash do bloco os bits zero necessarios. Uma vez que o esforco de CPU tenha sido gasto para satisfazer o proof-of-work, o bloco nao pode ser alterado sem refazer o trabalho. Como blocos posteriores sao encadeados apos ele, o trabalho para alterar o bloco incluiria refazer todos os blocos apos ele.
O proof-of-work tambem resolve o problema de determinar a representacao na tomada de decisao por maioria. Se a maioria fosse baseada em um-endereco-IP-um-voto, poderia ser subvertida por qualquer pessoa capaz de alocar muitos IPs. O proof-of-work e essencialmente um-CPU-um-voto. A decisao da maioria e representada pela cadeia mais longa, que tem o maior esforco de proof-of-work investido nela. Se a maioria do poder de CPU for controlada por nos honestos, a cadeia honesta crescera mais rapido e superara quaisquer cadeias concorrentes. Para modificar um bloco passado, um atacante teria que refazer o proof-of-work do bloco e de todos os blocos apos ele e entao alcancar e superar o trabalho dos nos honestos. Mostraremos mais adiante que a probabilidade de um atacante mais lento alcancar diminui exponencialmente a medida que blocos subsequentes sao adicionados.
Para compensar a velocidade crescente do hardware e o interesse variavel em operar nos ao longo do tempo, a dificuldade do proof-of-work e determinada por uma media movel visando um numero medio de blocos por hora. Se eles forem gerados muito rapidamente, a dificuldade 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
Os passos para operar a rede sao os seguintes:
- Novas transacoes sao transmitidas para todos os nos.
- Cada no coleta novas transacoes em um bloco.
- Cada no trabalha para encontrar um proof-of-work dificil para seu bloco.
- Quando um no encontra um proof-of-work, ele transmite o bloco para todos os nos.
- Os nos aceitam o bloco somente se todas as transacoes nele forem validas e nao tiverem sido gastas anteriormente.
- Os nos expressam sua aceitacao do bloco trabalhando na criacao do proximo bloco na cadeia, usando o hash do bloco aceito como o hash anterior.
Os nos sempre consideram a cadeia mais longa como a correta e continuarao trabalhando para estende-la. Se dois nos transmitirem versoes diferentes do proximo bloco simultaneamente, alguns nos podem receber uma ou outra primeiro. Nesse caso, eles trabalham na primeira que receberam, mas guardam o outro ramo caso ele se torne mais longo. O empate sera quebrado quando o proximo proof-of-work for encontrado e um ramo se tornar mais longo; os nos que estavam trabalhando no outro ramo entao mudarao para o mais longo.
Transmissoes de novas transacoes nao precisam necessariamente alcancar todos os nos. Desde que alcancem muitos nos, elas entrarao em um bloco em breve. Transmissoes de blocos tambem sao tolerantes a mensagens perdidas. Se um no nao receber um bloco, ele o solicitara quando receber o proximo bloco e perceber que perdeu um.
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 convencao, a primeira transacao em um bloco e uma transacao especial que inicia uma nova moeda pertencente ao criador do bloco. Isso adiciona um incentivo para que os nos apoiem a rede e fornece uma maneira de distribuir inicialmente moedas em circulacao, ja que nao ha uma autoridade central para emiti-las. A adicao constante de uma quantidade fixa de novas moedas e analoga a mineradores de ouro gastando recursos para adicionar ouro a circulacao. No nosso caso, e tempo de CPU e eletricidade que sao gastos.
O incentivo tambem pode ser financiado com taxas de transacao. Se o valor de saida de uma transacao for menor que seu valor de entrada, a diferenca e uma taxa de transacao que e adicionada ao valor de incentivo do bloco que contem a transacao. Uma vez que um numero predeterminado de moedas tenha entrado em circulacao, o incentivo pode transitar inteiramente para taxas de transacao e ser completamente livre de inflacao.
O incentivo pode ajudar a encorajar os nos a permanecerem honestos. Se um atacante ganancioso for capaz de reunir mais poder de CPU do que todos os nos honestos, ele teria que escolher entre usa-lo para fraudar pessoas roubando seus pagamentos de volta, ou usa-lo para gerar novas moedas. Ele deveria achar mais lucrativo jogar pelas regras, regras que o favorecem com mais moedas novas do que todos os outros combinados, do que minar o sistema e a validade de sua propria 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
Uma vez que a transacao mais recente em uma moeda esteja enterrada sob blocos suficientes, as transacoes gastas antes dela podem ser descartadas para economizar espaco em disco. Para facilitar isso sem quebrar o hash do bloco, as transacoes sao organizadas em hash em uma Merkle Tree [^7] [^2] [^5], com apenas a raiz incluida no hash do bloco. Blocos antigos podem entao ser compactados removendo ramos da arvore. Os hashes interiores nao precisam ser armazenados.
Um cabecalho de bloco sem transacoes teria cerca de 80 bytes. Se supusermos que blocos sao gerados a cada 10 minutos, 80 bytes * 6 * 24 * 365 = 4,2MB por ano. Com sistemas de computador tipicamente vendidos com 2GB de RAM em 2008, e a Lei de Moore prevendo um crescimento atual de 1,2GB por ano, o armazenamento nao deveria ser um problema mesmo que os cabecalhos dos blocos precisem ser mantidos na 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
E possivel verificar pagamentos sem operar um no completo da rede. Um usuario precisa apenas manter uma copia dos cabecalhos de bloco da cadeia de proof-of-work mais longa, que ele pode obter consultando nos da rede ate estar convencido de que tem a cadeia mais longa, e obter o ramo Merkle que liga a transacao ao bloco no qual ela foi carimbada com timestamp. Ele nao pode verificar a transacao por si mesmo, mas ao liga-la a um lugar na cadeia, ele pode ver que um no da rede a aceitou, e blocos adicionados apos ela confirmam ainda mais que a rede a aceitou.
Assim, a verificacao e confiavel enquanto nos honestos controlarem a rede, mas e mais vulneravel se a rede for dominada por um atacante. Enquanto os nos da rede podem verificar transacoes por si mesmos, o metodo simplificado pode ser enganado por transacoes fabricadas do atacante enquanto o atacante puder continuar dominando a rede. Uma estrategia para se proteger contra isso seria aceitar alertas dos nos da rede quando eles detectam um bloco invalido, solicitando que o software do usuario baixe o bloco completo e as transacoes alertadas para confirmar a inconsistencia. Empresas que recebem pagamentos frequentes provavelmente ainda vao querer operar seus proprios nos para seguranca mais independente e verificacao mais 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
Embora fosse possivel lidar com moedas individualmente, seria impraticavel fazer uma transacao separada para cada centavo em uma transferencia. Para permitir que o valor seja dividido e combinado, as transacoes contem multiplas entradas e saidas. Normalmente havera uma unica entrada de uma transacao anterior maior ou multiplas entradas combinando quantias menores, e no maximo duas saidas: uma para o pagamento e uma devolvendo o troco, se houver, ao remetente.
Deve-se notar que o fan-out, onde uma transacao depende de varias transacoes, e essas transacoes dependem de muitas mais, nao e um problema aqui. Nunca ha a necessidade de extrair uma copia completa e independente do historico de uma transacao.
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
O modelo bancario tradicional alcanca um nivel de privacidade limitando o acesso a informacao as partes envolvidas e ao terceiro confiavel. A necessidade de anunciar todas as transacoes publicamente impede este metodo, mas a privacidade ainda pode ser mantida quebrando o fluxo de informacao em outro lugar: mantendo as chaves publicas anonimas. O publico pode ver que alguem esta enviando uma quantia para outra pessoa, mas sem informacao ligando a transacao a qualquer individuo. Isso e semelhante ao nivel de informacao divulgado pelas bolsas de valores, onde o horario e o tamanho das negociacoes individuais, a "fita", sao tornados publicos, mas sem dizer quem foram as partes.
Como uma protecao adicional, um novo par de chaves deve ser usado para cada transacao para evitar que sejam ligadas a um proprietario comum. Alguma ligacao ainda e inevitavel com transacoes de multiplas entradas, que necessariamente revelam que suas entradas pertenciam ao mesmo proprietario. O risco e que, se o proprietario de uma chave for revelado, a ligacao poderia revelar outras transacoes que pertenciam ao mesmo proprietario.
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 o cenario de um atacante tentando gerar uma cadeia alternativa mais rapido que a cadeia honesta. Mesmo que isso seja alcancado, nao abre o sistema para mudancas arbitrarias, como criar valor do nada ou tomar dinheiro que nunca pertenceu ao atacante. Os nos nao vao aceitar uma transacao invalida como pagamento, e nos honestos nunca aceitarao um bloco que as contenha. Um atacante so pode tentar mudar uma de suas proprias transacoes para recuperar dinheiro que gastou recentemente.
A corrida entre a cadeia honesta e a cadeia do atacante pode ser caracterizada como um Passeio Aleatorio Binomial. O evento de sucesso e a cadeia honesta sendo estendida por um bloco, aumentando sua vantagem em +1, e o evento de falha e a cadeia do atacante sendo estendida por um bloco, reduzindo a diferenca em -1.
A probabilidade de um atacante alcancar a partir de um dado deficit e analoga ao problema da Ruina do Apostador. Suponha que um apostador com credito ilimitado comeca em deficit e joga potencialmente um numero infinito de tentativas para tentar alcancar o equilibrio. Podemos calcular a probabilidade de ele alguma vez alcancar o equilibrio, ou de um atacante alguma vez alcancar a cadeia honesta, da seguinte forma [^8]:
p = probabilidade de um no honesto encontrar o proximo bloco
q = probabilidade de o atacante encontrar o proximo bloco
q = probabilidade de o atacante alguma vez alcancar estando z blocos atras
\[ qz = \begin{cases} 1 & \text{se } p \leq q \\ \left(\frac{q}{p}\right) z & \text{se } p > q \end{cases} \]
Dada nossa suposicao de que p q, a probabilidade cai exponencialmente a medida que o numero de blocos que o atacante precisa alcancar aumenta. Com as chances contra ele, se ele nao fizer um avanco sortudo no inicio, suas chances se tornam infinitesimalmente pequenas a medida que fica mais para tras.
Agora consideramos quanto tempo o destinatario de uma nova transacao precisa esperar antes de estar suficientemente certo de que o remetente nao pode mudar a transacao. Assumimos que o remetente e um atacante que quer fazer o destinatario acreditar que o pagou por um tempo, e entao muda-lo para pagar a si mesmo apos algum tempo ter passado. O destinatario sera alertado quando isso acontecer, mas o remetente espera que seja tarde demais.
O destinatario gera um novo par de chaves e da a chave publica ao remetente pouco antes de assinar. Isso evita que o remetente prepare uma cadeia de blocos com antecedencia trabalhando nela continuamente ate ter sorte o suficiente para ficar suficientemente a frente, e entao executar a transacao naquele momento. Uma vez que a transacao e enviada, o remetente desonesto comeca a trabalhar em segredo em uma cadeia paralela contendo uma versao alternativa de sua transacao.
O destinatario espera ate que a transacao tenha sido adicionada a um bloco e z blocos tenham sido ligados apos ele. Ele nao sabe a quantidade exata de progresso que o atacante fez, mas assumindo que os blocos honestos levaram o tempo medio esperado por bloco, o progresso potencial do atacante sera uma distribuicao de Poisson com valor esperado:
\[ \lambda = z\frac{q}{p} \]
Para obter a probabilidade de o atacante ainda poder alcancar agora, multiplicamos a densidade de Poisson para cada quantidade de progresso que ele poderia ter feito pela probabilidade de ele poder alcancar a partir daquele ponto:
\[ \sum_{k=0}^{\infty} \frac{\lambda^k e^{-\lambda}}{k!} \cdot \left\{ \begin{array}{cl} \left(\frac{q}{p}\right)^{(z-k)} & \text{se } k \leq z \\ 1 & \text{se } k > z \end{array} \right. \]
Reorganizando para evitar somar a cauda infinita da distribuicao...
\[ 1 - \sum_{k=0}^{z} \frac{\lambda^k e^{-\lambda}}{k!} \left(1-\left(\frac{q}{p}\right)^{(z-k)}\right) \]
Convertendo para codigo 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;
}
Executando alguns resultados, podemos ver a probabilidade cair exponencialmente com 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
Resolvendo 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
Propusemos um sistema para transacoes eletronicas sem depender de confianca. Comecamos com o framework usual de moedas feitas de assinaturas digitais, que fornece forte controle de propriedade, mas e incompleto sem uma maneira de prevenir o gasto duplo. Para resolver isso, propusemos uma rede peer-to-peer usando proof-of-work para registrar um historico publico de transacoes que rapidamente se torna computacionalmente impraticavel para um atacante alterar se nos honestos controlarem a maioria do poder de CPU. A rede e robusta em sua simplicidade nao estruturada. Os nos trabalham todos de uma vez com pouca coordenacao. Eles nao precisam ser identificados, uma vez que as mensagens nao sao roteadas para nenhum lugar especifico e apenas precisam ser entregues com base no melhor esforco. Os nos podem sair e reingressar na rede a qualquer momento, aceitando a cadeia de proof-of-work como prova do que aconteceu enquanto estavam ausentes. Eles votam com seu poder de CPU, expressando sua aceitacao de blocos validos ao trabalhar para estende-los e rejeitando blocos invalidos ao se recusar a trabalhar neles. Quaisquer regras e incentivos necessarios podem ser aplicados com 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.
