Bitcoin: Un Sistema de Efectivo Electrónico Peer-to-Peer
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
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.
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
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.
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
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.
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 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.
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
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.
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
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.
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
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.
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
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.
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
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.
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
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.
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
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.
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
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
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
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.
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.
