Satoshi Nakamoto
satoshin@gmx.com
www.bitcoin.org
Resumo: Uma versão puramente peer-to-peer do dinheiro eletrônico permitiria que pagamentos on-line fossem enviados diretamente de uma parte para outra, sem passar por uma instituição financeira. As assinaturas digitais fornecem parte da solução, mas os principais benefícios são perdidos se um terceiro confiável ainda for necessário para evitar gastos duplos. Propomos uma solução para o problema do gasto duplo usando uma rede peer-to-peer. A rede registra a data e hora das transações fazendo hash em uma cadeia contínua de prova de trabalho baseada em hash, formando um registro que não pode ser alterado sem refazer a prova de trabalho. A cadeia mais longa não serve apenas como prova da sequência de eventos testemunhados, mas também como prova de que veio do maior conjunto de potência da CPU. Enquanto a maior parte da potência da CPU for controlada por nós que não cooperam para atacar a rede, eles gerarão a cadeia mais longa e ultrapassarão os invasores. A própria rede requer estrutura mínima. As mensagens são transmitidas com base no melhor esforço e os nós podem sair e voltar à rede à vontade, aceitando a cadeia de prova de trabalho mais longa como prova do que aconteceu enquanto eles estavam fora.
1. Introdução
O comércio na Internet passou a depender quase exclusivamente de instituições financeiras que servem como terceiros de confiança para processar pagamentos eletrónicos. Embora o sistema funcione suficientemente bem para a maioria das transações, ainda sofre das fraquezas inerentes ao modelo baseado na confiança. Transações totalmente irreversíveis não são realmente possíveis, uma vez que as instituições financeiras não podem evitar a mediação de disputas. O custo da mediação aumenta os custos de transação, limitando o tamanho mínimo prático da transação e eliminando a possibilidade de pequenas transações casuais, e há um custo mais amplo na perda da capacidade de efetuar pagamentos irreversíveis por serviços irreversíveis. Com a possibilidade de reversão, a necessidade de confiança se espalha. Os comerciantes devem ser cautelosos com seus clientes, incomodando-os para obter mais informações do que de outra forma precisariam. Uma certa percentagem de fraude é considerada inevitável. Estes custos e incertezas de pagamento podem ser evitados pessoalmente através da utilização de moeda física, mas não existe nenhum mecanismo para efetuar pagamentos através de um canal de comunicação sem uma parte confiável.
O que é necessário é um sistema de pagamento electrónico baseado em prova criptográfica em vez de confiança, permitindo que quaisquer duas partes dispostas transaccionem directamente entre si, sem a necessidade de um terceiro de confiança. As transações cuja reversão é impraticável do ponto de vista computacional protegeriam os vendedores contra fraudes, e mecanismos de garantia de rotina poderiam ser facilmente implementados para proteger os compradores. Neste artigo, propomos uma solução para o problema do gasto duplo usando um servidor de carimbo de data/hora distribuído ponto a ponto para gerar prova computacional da ordem cronológica das transações. O sistema é seguro desde que nós honestos controlem coletivamente mais poder de CPU do que qualquer grupo cooperativo de nós invasores.
2. Transações
Definimos uma moeda eletrônica como uma cadeia de assinaturas digitais. Cada proprietário transfere a moeda para o próximo assinando digitalmente um hash da transação anterior e a chave pública do próximo proprietário e adicionando-os ao final da moeda. Um beneficiário pode verificar as assinaturas para verificar a cadeia de propriedade.
O problema, claro, é que o beneficiário não pode verificar se um dos proprietários não gastou o dobro da moeda. Uma solução comum é introduzir uma autoridade central confiável, ou mint, que verifique cada transação quanto a gastos duplos. Após cada transação, a moeda deve ser devolvida à casa da moeda para a emissão de uma nova moeda, e apenas as moedas emitidas diretamente da casa da moeda são confiáveis para não serem gastas duas vezes. O problema com esta solução é que o destino de todo o sistema monetário depende da empresa que administra a casa da moeda, e cada transação deve passar por ela, assim como um banco. Precisamos de uma forma de o beneficiário saber que os proprietários anteriores não assinaram nenhuma transação anterior. Para os nossos propósitos, a transação mais antiga é a que conta, por isso não nos importamos com tentativas posteriores de duplicar os gastos. A única forma de confirmar a ausência de uma transação é estar ciente de todas as transações. No modelo baseado na casa da moeda, a casa da moeda estava ciente de todas as transações e decidia quais chegavam primeiro. Para conseguir isso sem uma parte confiável, as transações devem ser anunciadas publicamente [1], e precisamos de um sistema para que os participantes cheguem a um acordo sobre um único histórico da ordem em que foram recebidas. O beneficiário precisa de provas de que, no momento de cada transação, a maioria dos nós concordou que foi a primeira a ser recebida.
3. Servidor de carimbo de data/hora
A solução que propomos começa com um servidor de carimbo de data/hora. Um servidor de carimbo de data/hora funciona pegando um hash de um bloco de itens a ser carimbado e publicando amplamente o hash, como em um jornal ou em uma postagem da Usenet [2-5]. O carimbo de data/hora prova que os dados deveriam existir naquele momento, obviamente, para entrar no hash. Cada timestamp inclui o timestamp anterior em seu hash, formando uma cadeia, com cada timestamp adicional reforçando os anteriores.
4. Prova de Trabalho
Para implementar um servidor de carimbo de data e hora distribuído ponto a ponto, precisaremos usar um sistema de prova de trabalho semelhante ao Hashcash de Adam Back [6], em vez de publicações em jornais ou na Usenet. A prova de trabalho envolve a varredura de um valor que, quando hash, como no SHA-256, o hash começa com um número de zero bits. O trabalho médio necessário é exponencial no número de zero bits necessários e pode ser verificado executando um único hash.
Para nossa rede de carimbo de data/hora, implementamos a prova de trabalho incrementando um nonce no bloco até que seja encontrado um valor que forneça ao hash do bloco os zero bits necessários. Uma vez que o esforço da CPU tenha sido despendido para satisfazer a prova de trabalho, o bloco não pode ser alterado sem refazer o trabalho. À medida que os blocos posteriores são encadeados após ele, o trabalho para alterar o bloco incluiria refazer todos os blocos posteriores.
A prova de trabalho também resolve o problema de determinação da representação na tomada de decisão por maioria. Se a maioria fosse baseada em um endereço IP, um voto, ela poderia ser subvertida por qualquer pessoa capaz de alocar muitos IPs. A prova de trabalho é essencialmente uma CPU-um-voto. A decisão majoritária é representada pela cadeia mais longa, que possui o maior esforço de prova de trabalho investido nela. Se a maior parte do poder da CPU for controlada por nós honestos, a cadeia honesta crescerá mais rapidamente e ultrapassará quaisquer cadeias concorrentes. Para modificar um bloco anterior, um invasor teria que refazer a prova de trabalho do bloco e de todos os blocos posteriores e então alcançar e superar o trabalho dos nós honestos. Mostraremos mais tarde que a probabilidade de um invasor mais lento alcançá-lo diminui exponencialmente à medida que blocos subsequentes são adicionados.
Para compensar o aumento da velocidade do hardware e o interesse variável na execução de nós ao longo do tempo, a dificuldade da prova de trabalho é determinada por uma média móvel visando um número médio de blocos por hora. Se forem gerados muito rápido, a dificuldade aumenta.
5. Rede
As etapas para operar a rede são as seguintes:
1) Novas transações são transmitidas para todos os nós.
2) Cada nó coleta novas transações em um bloco.
3) Cada nó trabalha para encontrar uma prova de trabalho difícil para seu bloco.
4) Quando um nó encontra prova de trabalho, ele transmite o bloco para todos os nós.
5) Os nós aceitam o bloco somente se todas as transações nele contidas forem válidas e ainda não gastas.
6) Os nós expressam sua aceitação do bloco trabalhando na criação do próximo bloco da cadeia, usando o hash do bloco aceito como o hash anterior.
Os nós sempre consideram a cadeia mais longa como a correta e continuarão trabalhando para estendê-la. Se dois nós transmitirem versões diferentes do próximo bloco simultaneamente, alguns nós poderão receber um ou outro primeiro. Nesse caso, eles trabalham no primeiro que receberam, mas guardam o outro ramo caso fique mais longo. O empate será desfeito quando for encontrada a próxima prova de trabalho e um ramo ficar mais longo; os nós que estavam trabalhando na outra ramificação mudarão para a ramificação mais longa.
Novas transmissões de transações não precisam necessariamente atingir todos os nós. Contanto que alcancem muitos nós, eles entrarão em um bloco em pouco tempo. As transmissões em bloco também são tolerantes com mensagens perdidas. Se um nó não receber um bloco, ele irá solicitá-lo quando receber o próximo bloco e perceber que perdeu um.
6. Incentivo
Por convenção, a primeira transação em um bloco é uma transação especial que inicia uma nova moeda de propriedade do criador do bloco. Isto adiciona um incentivo para os nós apoiarem a rede e fornece uma forma de distribuir inicialmente moedas em circulação, uma vez que não existe uma autoridade central para emiti-las. A adição constante de uma quantidade constante de novas moedas é análoga aos mineradores de ouro que gastam recursos para adicionar ouro à circulação. No nosso caso, é o tempo de CPU e a eletricidade que são gastos.
O incentivo também pode ser financiado com taxas de transação. Se o valor de saída de uma transação for menor que seu valor de entrada, a diferença será uma taxa de transação que será adicionada ao valor de incentivo do bloco que contém a transação. Depois que um número predeterminado de moedas entrar em circulação, o incentivo pode passar inteiramente para taxas de transação e ser totalmente livre de inflação.
O incentivo pode ajudar a encorajar os nós a permanecerem honestos. Se um invasor ganancioso conseguir reunir mais poder de CPU do que todos os nós honestos, ele terá que escolher entre usá-lo para fraudar as pessoas, roubando seus pagamentos ou usá-lo para gerar novas moedas. Ele deveria achar mais lucrativo seguir as regras, regras que o favorecem com mais moedas novas do que todos os outros juntos, do que minar o sistema e a validade da sua própria riqueza.
7. Recuperando espaço em disco
Uma vez que a última transação em uma moeda esteja enterrada em blocos suficientes, as transações gastas antes dela podem ser descartadas para economizar espaço em disco. Para facilitar isso sem quebrar o hash do bloco, as transações são hashadas em uma Árvore Merkle [7][2][5], com apenas a raiz incluída no hash do bloco. Blocos antigos podem então ser compactados arrancando galhos da árvore. Os hashes internos não precisam ser armazenados.
Um cabeçalho de bloco sem transações teria cerca de 80 bytes. Se supormos que os blocos são gerados a cada 10 minutos, 80 bytes 6 24 * 365 = 4,2 MB por ano. Com sistemas de computador normalmente vendidos com 2 GB de RAM a partir de 2008, e a Lei de Moore prevendo um crescimento atual de 1,2 GB por ano, o armazenamento não deve ser um problema, mesmo que os cabeçalhos dos blocos devam ser mantidos na memória.
8. Verificação de pagamento simplificada
É possível verificar pagamentos sem executar um nó de rede completo. Um usuário só precisa manter uma cópia dos cabeçalhos de bloco da cadeia de prova de trabalho mais longa, que ele pode obter consultando os nós da rede até estar convencido de que possui a cadeia mais longa, e obter o ramo Merkle que liga a transação ao bloco seu carimbo de data / hora. Ele não pode verificar a transação por si mesmo, mas ao vinculá-la a um local na cadeia, ele pode ver que um nó da rede a aceitou e os blocos adicionados após confirmarem ainda mais que a rede a aceitou.
Como tal, a verificação é confiável desde que nós honestos controlem a rede, mas é mais vulnerável se a rede for dominada por um invasor. Embora os nós da rede possam verificar as transações por si próprios, o método simplificado pode ser enganado pelas transações fabricadas por um invasor, enquanto o invasor puder continuar a dominar a rede. Uma estratégia para se proteger contra isso seria aceitar alertas dos nós da rede quando eles detectam um bloco inválido, solicitando que o software do usuário baixe o bloco completo e alerte as transações para confirmar a inconsistência. As empresas que recebem pagamentos frequentes provavelmente ainda desejarão executar seus próprios nós para maior segurança independente e verificação mais rápida.
9. Combinando e dividindo valor
Embora fosse possível lidar com moedas individualmente, seria difícil fazer uma transação separada para cada centavo de uma transferência. Para permitir que o valor seja dividido e combinado, as transações contêm múltiplas entradas e saídas. Normalmente haverá uma única entrada de uma transação anterior maior ou múltiplas entradas combinando quantias menores e, no máximo, duas saídas: uma para o pagamento e outra para devolver o troco, se houver, ao remetente.
Deve-se notar que o fan-out, onde uma transação depende de diversas transações, e essas transações dependem de muitas mais, não é um problema aqui. Nunca há necessidade de extrair uma cópia completa e independente do histórico de uma transação.
10. Privacidade
O modelo bancário tradicional atinge um nível de privacidade ao limitar o acesso às informações às partes envolvidas e ao terceiro confiável. A necessidade de anunciar publicamente todas as transações impede este método, mas a privacidade ainda pode ser mantida interrompendo o fluxo de informações em outro local: mantendo as chaves públicas anônimas. O público pode perceber que alguém está enviando uma quantia para outra pessoa, mas sem informações que vinculem a transação a ninguém. Isto é semelhante ao nível de informação divulgado pelas bolsas de valores, onde o tempo e o tamanho das negociações individuais, a “fita”, são tornados públicos, mas sem dizer quem eram as partes.
Como firewall adicional, um novo par de chaves deve ser usado para cada transação, para evitar que sejam vinculadas a um proprietário comum. Algumas ligações ainda são inevitáveis no caso de transacções com múltiplos factores de produção, o que revela necessariamente que os seus factores de produção pertenciam ao mesmo proprietário. O risco é que, se o proprietário de uma chave for revelado, a vinculação poderá revelar outras transações que pertenciam ao mesmo proprietário.
11. Cálculos
Consideramos o cenário de um invasor tentando gerar uma cadeia alternativa mais rapidamente do que a cadeia honesta. Mesmo que isto seja conseguido, não deixa o sistema aberto a mudanças arbitrárias, como a criação de valor a partir do nada ou a retirada de dinheiro que nunca pertenceu ao atacante. Os nós não aceitarão uma transação inválida como pagamento, e os nós honestos nunca aceitarão um bloco que as contenha. Um invasor só pode tentar alterar uma de suas próprias transações para recuperar o dinheiro gasto recentemente. A corrida entre a cadeia honesta e uma cadeia atacante pode ser caracterizada como um passeio aleatório binomial. O evento de sucesso é a cadeia honesta sendo estendida em um bloco, aumentando sua vantagem em +1, e o evento de falha é a cadeia do atacante sendo estendida em um bloco, reduzindo a lacuna em -1.
A probabilidade de um invasor recuperar o atraso de um determinado déficit é análoga ao problema da Ruína do Jogador. Suponha que um jogador com crédito ilimitado comece com um défice e jogue potencialmente um número infinito de tentativas para tentar atingir o ponto de equilíbrio. Podemos calcular a probabilidade de ele atingir o ponto de equilíbrio ou de um invasor alcançar a cadeia honesta, como segue [8]:
p = probabilidade de um nó honesto encontrar o próximo bloco
q = probabilidade de o invasor encontrar o próximo bloco
qz = probabilidade de o invasor alcançar z blocos atrás
qz= { 1 se p≤q
(q/ p)^z se p>q}
Dada a nossa suposição de que p > q, a probabilidade cai exponencialmente à medida que aumenta o número de blocos que o invasor precisa alcançar. Com as probabilidades contra ele, se ele não der uma investida de sorte logo no início, suas chances se tornarão cada vez menores à medida que ele ficar para trás.
Consideraremos agora quanto tempo o destinatário de uma nova transação precisa esperar antes de ter certeza suficiente de que o remetente não pode alterar a transação. Presumimos que o remetente é um invasor que deseja fazer o destinatário acreditar que ele o pagou por um tempo e, em seguida, trocá-lo para pagar a si mesmo depois de algum tempo. O destinatário será alertado quando isso acontecer, mas o remetente espera que seja tarde demais.
O receptor gera um novo par de chaves e fornece a chave pública ao remetente pouco antes de assinar. Isso evita que o remetente prepare uma cadeia de blocos com antecedência, trabalhando nela continuamente até ter a sorte de avançar o suficiente e, em seguida, executar a transação naquele momento. Assim que a transação é enviada, o remetente desonesto começa a trabalhar em segredo numa cadeia paralela contendo uma versão alternativa da sua transação.
O destinatário espera até que a transação seja adicionada a um bloco e z blocos sejam vinculados depois dela. Ele não sabe a quantidade exata de progresso que o atacante fez, mas assumindo que os blocos honestos levaram o tempo médio esperado por bloco, o progresso potencial do atacante será uma distribuição de Poisson com valor esperado:
Convertendo para código C...
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
12. Conclusão
Propusemos um sistema para transações eletrônicas sem depender de confiança. Começamos com a estrutura usual de moedas feitas a partir de assinaturas digitais, que proporciona um forte controle de propriedade, mas é incompleta sem uma forma de evitar gastos duplos. Para resolver isso, propusemos uma rede peer-to-peer usando prova de trabalho para registrar um histórico público de transações que rapidamente se torna computacionalmente impraticável para um invasor alterar se nós honestos controlarem a maior parte do poder da CPU. A rede é robusta em sua simplicidade não estruturada. Os nós funcionam todos ao mesmo tempo com pouca coordenação. Eles não precisam ser identificados, uma vez que as mensagens não são roteadas para nenhum local específico e só precisam ser entregues com base no melhor esforço. Os nós podem sair e ingressar na rede à vontade, aceitando a cadeia de prova de trabalho como prova do que aconteceu enquanto eles estavam fora. Eles votam com o poder de sua CPU, expressando sua aceitação de blocos válidos trabalhando para estendê-los e rejeitando blocos inválidos recusando-se a trabalhar neles. Quaisquer regras e incentivos necessários podem ser aplicados com este mecanismo de consenso.
Referências
[1] W. Dai, "b-money", http://www.weidai.com/bmoney.txt, 1998.
[2] H. Massias, XS. Ávila, e J.‑J. Quisquater, "Projeto de um serviço de carimbo de data/hora seguro com mínimo
requisitos de confiança", no 20º Simpósio sobre Teoria da Informação no Benelux, maio de 1999.
[3] S. Haber, WS. Stornetta, "Como registrar a data e hora de um documento digital", In Journal of Cryptology, vol 3, não
2, páginas 99-111, 1991.
[4] D. Bayer, S. Haber, W.S. Stornetta, "Melhorando a eficiência e a confiabilidade do carimbo de data/hora digital",
Em Sequências II: Métodos em Comunicação, Segurança e Ciência da Computação, páginas 329-334, 1993.
[5] S. Haber, WS. Stornetta, "Nomes seguros para cadeias de bits", em Anais da 4ª Conferência ACM
sobre segurança de computadores e comunicações, páginas 28-35, abril de 1997.
[6] A. Back, "Hashcash - uma contramedida de negação de serviço",
http://www.hashcash.org/papers/hashcash.pdf, 2002.
[7] RC. Merkle, "Protocolos para criptosistemas de chave pública", In Proc. Simpósio de 1980 sobre Segurança e
Privacidade, IEEE Computer Society, páginas 122-133, abril de 1980.
[8] W. Feller, "Uma introdução à teoria da probabilidade e suas aplicações", 1957.
