Bitcoin: Um Sistema de Dinheiro Eletrônico Peer-to-Peer

Satoshi Nakamoto
[email protected]
www.bitcoin.org
31 de outubro de 2008

Resumo

Uma versão puramente peer-to-peer de dinheiro eletrônico permitiria que pagamentos online fossem enviados diretamente de uma parte para outra sem a necessidade de uma instituição financeira. Assinaturas digitais fornecem parte da solução, mas os principais benefícios são perdidos se uma terceira parte confiável ainda for necessária para evitar o gasto duplo. Propomos uma solução para o problema do gasto duplo usando uma rede peer-to-peer. A rede carimba as transações ao colocá-las em uma cadeia contínua de provas de trabalho com base em hash, formando um registro que não pode ser alterado sem refazer a prova de trabalho. A cadeia mais longa não apenas serve como prova da sequência dos eventos, mas também garante que ela prove que veio do maior pool de poder computacional. Enquanto a maior parte do poder computacional for controlada por nós que não cooperam para atacar a rede, eles gerarão a cadeia mais longa e superarão os atacantes. A própria rede requer estrutura mínima. As mensagens são transmitidas em uma base de melhor esforço, e os nós podem sair e se juntar à rede à vontade, aceitando a cadeia mais longa como prova do que aconteceu enquanto estavam fora.

1. Introdução

O comércio na internet tornou-se dependente quase exclusivamente de instituições financeiras que atuam como intermediários confiáveis para processar pagamentos eletrônicos. Embora o sistema funcione bem para a maioria das transações, ele ainda sofre das fraquezas inerentes ao modelo baseado em confiança. Transações irreversíveis não são realmente possíveis, pois as instituições financeiras não podem evitar disputas intermediárias. O custo da mediação aumenta o custo das transações, limitando o tamanho mínimo prático das transações e eliminando a possibilidade de pequenas transações casuais, e há um custo mais amplo na perda da capacidade de realizar pagamentos irreversíveis para serviços irreversíveis. Com a possibilidade de reversão, a necessidade de confiança se espalha. Comerciantes devem desconfiar dos seus clientes, pedindo mais informações do que realmente precisariam. Uma certa porcentagem de fraude é aceita como inevitável. Esses custos e incertezas de pagamento podem ser evitados em transações presenciais utilizando dinheiro físico, mas não existe um mecanismo equivalente para fazer pagamentos através de um canal de comunicação sem uma parte confiável.

O que é necessário é um sistema de pagamento eletrônico baseado em prova criptográfica em vez de confiança, permitindo que duas partes transacionem diretamente uma com a outra sem a necessidade de uma terceira parte confiável. Transações que são computacionalmente impraticáveis de reverter protegeriam os vendedores contra fraudes, e mecanismos rotineiros de escrow poderiam ser implementados para proteger os compradores. Neste artigo, propomos uma solução para o problema do gasto duplo utilizando um servidor de carimbo de tempo distribuído peer-to-peer para gerar provas computacionais da ordem cronológica das transações. O sistema é seguro enquanto os nós honestos coletivamente controlarem mais poder computacional do que qualquer grupo cooperante de nós atacantes.

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 esses à moeda. Um destinatário pode verificar as assinaturas para verificar a cadeia de propriedade.

O problema, claro, é que o destinatário não pode verificar se um dos proprietários não gastou duas vezes a mesma moeda. A solução comum é introduzir uma autoridade central confiável, ou casa da moeda, que verifica cada transação para garantir que ela não foi gasta duas vezes. Depois de cada transação, a moeda deve ser devolvida à casa da moeda para emitir uma nova, e somente moedas emitidas diretamente pela casa da moeda são confiáveis para não serem gastas duas vezes. O problema com essa solução é que o destino de todo o sistema de dinheiro reside na empresa que gerencia a casa da moeda, com cada transação precisando passar por eles, assim como em um banco.

Precisamos de uma maneira para o destinatário saber que os donos anteriores não assinaram nenhuma transação anterior. Para nossos propósitos, a transação mais antiga é a que conta, então não nos importamos em tentar separar um ataque de gasto duplo de uma tentativa honesta de gastar a mesma moeda duas vezes. A única maneira de confirmar a ausência de uma transação é estar ciente de todas as transações. No modelo baseado em casa da moeda, a casa da moeda estava ciente de todas as transações e decidia qual chegou primeiro. Para realizar isso sem uma parte confiável, as transações devem ser anunciadas publicamente [1], e precisamos de um sistema para os participantes concordarem em uma única história da ordem em que foram recebidas. O destinatário precisa de prova de que, no momento de cada transação, a maioria dos nós concordou que foi a primeira recebida.

3. Servidor de Carimbo de Tempo

A solução que propomos começa com um servidor de carimbo de tempo. Um servidor de carimbo de tempo funciona pegando um hash de um bloco de itens a serem carimbados e publicando amplamente o hash, como em um jornal ou post na Usenet [2-5]. O carimbo de tempo prova que os dados devem ter existido, obviamente, no momento em que o hash foi publicado, para entrar no hash. Cada carimbo de tempo inclui o anterior em seu hash, formando uma cadeia, com cada carimbo de tempo adicional reforçando os anteriores.

4. Prova de Trabalho

Para implementar um servidor de carimbo de tempo distribuído em uma base peer-to-peer, precisamos usar um sistema de prova de trabalho semelhante ao Hashcash de Adam Back [6], em vez de um sistema de jornal ou Usenet. A prova de trabalho envolve a busca por um valor que, quando hashado, como com o SHA-256, o hash começa com um número de bits zero. O trabalho médio necessário é exponencial em relação ao número de bits zero necessários e pode ser verificado executando um único hash.

Para nossa rede de carimbo de tempo, implementamos a prova de trabalho incrementando um nonce no bloco até que um valor seja encontrado que dá ao hash do bloco o número necessário de bits zero. Uma vez que o esforço computacional foi gasto para satisfazer a prova de trabalho, o bloco não pode ser alterado sem refazer o trabalho. Como blocos subsequentes são encadeados após o bloco, o trabalho para alterar o bloco incluiria refazer todos os blocos subsequentes.

A prova de trabalho também resolve o problema de determinar a representação na tomada de decisões por maioria. Se a maioria fosse baseada em um-voto-por-endereço-IP, poderia ser subvertida por qualquer pessoa capaz de alocar muitos IPs. A prova de trabalho é essencialmente um-voto-por-CPU. A decisão da maioria é representada pela cadeia mais longa, que possui o maior esforço de prova de trabalho investido. Se a maioria do poder de CPU for controlada por nós honestos, a cadeia honesta crescerá mais rápido e superará qualquer cadeia concorrente. Para modificar um bloco passado, um invasor teria que refazer a prova de trabalho daquele bloco e de todos os blocos subsequentes, e então alcançar e superar o trabalho dos nós honestos. Mostraremos mais adiante que a probabilidade de um invasor mais lento alcançar diminui exponencialmente à medida que novos blocos são adicionados.

Para compensar o aumento da velocidade do hardware e o interesse variável em rodar nós ao longo do tempo, a dificuldade da prova de trabalho é determinada por uma média móvel que visa a um número médio de blocos por hora. Se eles forem gerados muito rápido, a dificuldade aumenta.

5. Rede

As etapas para executar a rede são as seguintes:

1. Novas transações são transmitidas para todos os nós.
2. Cada nó coleta as 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 uma prova de trabalho, transmite o bloco para todos os nós.
5. Os nós aceitam o bloco apenas se todas as transações nele forem válidas e não gastas.
6. Os nós expressam sua aceitação do bloco trabalhando para criar o próximo bloco na 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 podem receber um ou outro primeiro. Nesse caso, eles trabalharão na primeira que receberam, mas salvarão a outra no caso de ela se tornar a mais longa. O empate será quebrado quando a próxima prova de trabalho for encontrada, e uma cadeia se tornar mais longa; os nós que estavam trabalhando na outra cadeia, então, mudarão para a mais longa.

Novas transações transmitidas não precisam necessariamente alcançar todos os nós. Contanto que elas alcancem muitos nós, serão incluídas em um bloco em breve. As transmissões de blocos também são tolerantes a mensagens perdidas. Se um nó não receber um bloco, ele o solicitará 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 pertencente ao criador do bloco. Isso adiciona um incentivo para os nós apoiarem a rede e fornece uma maneira de distribuir moedas para a circulação, pois não há autoridade central para emiti-las. 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 é uma taxa de transação que é adicionada ao valor do incentivo do bloco que contém a transação. Assim que um número predeterminado de moedas entrou em circulação, o incentivo pode ser completamente financiado pelas taxas de transação e ser completamente livre de inflação.

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 o valor de entrada, a diferença será uma taxa de transação que é adicionada ao valor do incentivo do bloco que contém a transação. Uma vez que um número predeterminado de moedas tenha entrado em circulação, o incentivo pode se tornar inteiramente baseado em taxas de transação e ser completamente livre de inflação.

O incentivo pode ajudar a incentivar os nós a permanecerem honestos. Se um atacante ganancioso puder reunir mais poder computacional do que todos os nós honestos, ele teria que escolher entre usar seu poder para fraudar as pessoas roubando seus pagamentos ou usar seu poder para gerar novas moedas. Ele deveria achar mais rentável jogar pelas regras, tais regras que favorecem mais moedas para si mesmo, do que subverter o sistema e a validade de sua própria riqueza.

7. Recuperando Espaço em Disco

Uma vez que a última transação em uma moeda foi enterrada sob 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 podando os ramos da árvore. Os interiores dos ramos não precisam ser armazenados.

Um cabeçalho de bloco sem transações teria cerca de 80 bytes. Supondo que os blocos sejam gerados a cada 10 minutos, 80 bytes * 6 * 24 * 365 = 4,2MB por ano. Com sistemas de computador normalmente sendo vendidos com 2GB de RAM em 2008, e a Lei de Moore prevendo um crescimento atual de 1,2GB por ano, o armazenamento não deve ser um problema, mesmo que os cabeçalhos de blocos precisem ser mantidos na memória.

8. Verificação Simples de Pagamento

É possível verificar pagamentos sem executar um nó de rede completo. Um usuário só precisa manter uma cópia dos cabeçalhos dos blocos da cadeia mais longa de provas de trabalho, que ele pode obter perguntando a nós de rede até que esteja convencido de que possui a cadeia mais longa e coletar as transações de seus merkle branch que ligam a transação ao bloco onde ela foi incluída. Ele não pode verificar a transação por si mesmo, mas ao linkar a transação a um lugar na cadeia, ele pode ver que um nó da rede a aceitou, e blocos adicionados depois a confirmarão.

Assim, a verificação é confiável enquanto os nós honestos controlarem a rede, mas torna-se mais vulnerável se a rede for sobrecarregada por um atacante. Embora os nós da rede possam verificar transações por si mesmos, o método simplificado pode ser enganado por transações forjadas por um atacante, enquanto ele conseguir sobrepujar a rede. Uma estratégia para se proteger contra isso seria aceitar alertas de nós da rede quando detectarem um bloco inválido, levando o software do usuário a baixar o bloco completo e as transações alertadas para confirmar a inconsistência. Empresas que recebem pagamentos frequentes provavelmente ainda desejarão operar seus próprios nós para maior segurança independente e verificação mais rápida.

9. Combinação e Divisão de Valor

Embora seja possível manipular transações para realizar a combinação e divisão de moedas, um formato mais simples, eficiente e seguro é criar transações apenas onde todo o valor de entrada é dividido entre uma ou mais saídas. Normalmente, uma das saídas é o novo proprietário, e a outra, caso tenha algum valor, retorna o troco ao remetente. Para proteger contra a reutilização de transações, todas as saídas de uma transação são usadas como entradas de outra, criando novas transações ao dividir ou combinar valores.

Vale ressaltar que a propagação em árvore, onde uma transação depende de várias outras transações, e essas transações dependem de muitas mais, não é um problema aqui. Nunca há a necessidade de extrair uma cópia completa e autônoma do histórico de uma transação.

10. Privacidade

O modelo bancário tradicional atinge um nível de privacidade limitando o acesso à informação às partes envolvidas e ao terceiro intermediário de confiança. A necessidade de anunciar publicamente todas as transações impede esse método, mas a privacidade ainda pode ser mantida quebrando o fluxo de informações em outro lugar: mantendo as chaves públicas anônimas. O público pode ver que alguém está enviando uma quantia para outra pessoa, mas sem informações que vinculem a transação ao remetente e ao destinatário. Isso é similar ao nível de informação liberado pelas bolsas de valores, onde o tempo e o tamanho das transações individuais são disponibilizados, mas sem contar quem eram as partes envolvidas.

Como uma firewall adicional, um novo par de chaves deve ser usado para cada transação para impedir que elas sejam vinculadas a um proprietário comum. Alguns sistemas existentes como o B-money [8] propõem ter todos os valores saldos disponíveis publicamente para que qualquer parte possa verificar que o sistema não está fraudando. No entanto, usar essa solução para segurança pública é uma abordagem de menor privacidade, pois, por ser uma prática a ser implementada com a certeza de que todos os fundos pertencem ao público, nada impede que um pequeno grupo de pessoas trabalhe em conjunto para usar isso em benefício próprio, comprometendo a segurança e a privacidade dos usuários.

11. Cálculos

Consideramos o cenário de um atacante tentando gerar uma cadeia alternativa mais rápida do que a cadeia honesta. Mesmo que isso seja alcançado, o sistema não fica vulnerável a mudanças arbitrárias, como criar valor do nada ou tomar dinheiro que nunca pertenceu ao atacante. Os nodes não vão aceitar uma transação inválida como pagamento, e os nodes honestos nunca aceitarão um bloco que a contenha. Um atacante só pode tentar alterar uma de suas próprias transações para recuperar o dinheiro que ele gastou recentemente.

A corrida entre a cadeia honesta e a cadeia de um atacante pode ser caracterizada como um Caminho Aleatório Binomial. O evento de sucesso é a cadeia honesta ser estendida por um bloco, aumentando sua vantagem em +1, e o evento de falha é a cadeia do atacante ser estendida por um bloco, reduzindo a diferença em -1.

A probabilidade de um atacante alcançar a cadeia honesta a partir de um déficit é análoga ao problema da Ruína do Jogador. Suponha um jogador com crédito ilimitado que começa em déficit e joga um número potencialmente infinito de rodadas para tentar atingir o equilíbrio. Podemos calcular a probabilidade de ele eventualmente alcançar o equilíbrio, ou de um atacante alcançar a cadeia honesta, da seguinte maneira:[8]

$$\begin{array}{rl}p& =\text{probabilidade de um nó honesto encontrar o próximo bloco}\\ q& =\text{probabilidade de o atacante encontrar o próximo bloco}\\ q_z& =\text{probabilidade de o atacante alcançar }z\text{ blocos de desvantagem}\end{array}$$
$$q_z=\left\{\begin{array}{cc}1& \text{if}p\le q\\ (q/p{)}^z& \text{if}p>q\end{array}\right\}$$
Dada a nossa suposição de que $p>q$, a probabilidade diminui exponencialmente à medida que o número de blocos que o atacante precisa alcançar aumenta. Com as probabilidades contra ele, se não conseguir avançar com sorte no início, suas chances se tornam extremamente pequenas à medida que ele fica cada vez mais para trás.

Agora consideramos quanto tempo o destinatário de uma nova transação precisa esperar antes de estar suficientemente certo de que o remetente não pode alterar a transação. Assumimos que o remetente é um atacante que quer fazer o destinatário acreditar que o pagou por um tempo, e então mudar para pagar de volta para si mesmo depois que algum tempo tenha passado. O destinatário será alertado quando isso acontecer, mas o remetente espera que seja tarde demais.

O destinatário gera um novo par de chaves e dá a chave pública ao remetente pouco antes de assinar. Isso impede que o remetente prepare uma cadeia de blocos com antecedência, trabalhando nela continuamente até que ele tenha sorte o suficiente para avançar o suficiente, e então execute a transação naquele momento. Assim que a transação é enviada, o remetente desonesto começa a trabalhar secretamente em uma cadeia paralela contendo uma versão alternativa de sua transação.

O destinatário espera até que a transação tenha sido adicionada a um bloco e blocos tenham sido ligados após ele. 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:

$$\lambda =z\frac{q}{p}$$

Para obter a probabilidade de que o atacante ainda possa alcançar o progresso agora, multiplicamos a densidade de Poisson para cada quantidade de progresso que ele pode ter feito pela probabilidade de ele conseguir alcançar a partir desse ponto:

$$\sum _{k=0}^{\mathrm{\infty }}\frac{{\lambda }^k{e}^{-\lambda }}{k!}\cdot \left\{\begin{array}{cc}(q/p{)}^{(z-k)}& \text{if}k\le z\\ 1& \text{if}k>z\end{array}\right\}$$

Reorganizando para evitar a soma da cauda infinita da distribuição…

$$1-\sum _{k=0}^z\frac{{\lambda }^k{e}^{-\lambda }}{k!}(1-(q/p{)}^{(z-k)})$$

Convertendo para liguagem 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;
}

Ao rodar alguns resultados, podemos ver que a probabilidade diminui 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

Solving for P less than 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 o framework comum de moedas baseadas em assinaturas digitais, que proporciona forte controle de propriedade, mas é incompleto sem uma maneira de evitar o gasto duplo. Para resolver isso, propusemos uma rede peer-to-peer que utiliza prova de trabalho para registrar uma história pública das transações que rapidamente se torna computacionalmente impraticável para um atacante alterar se nós honestos controlarem a maioria do poder computacional. A rede é robusta em sua simplicidade não estruturada. Os nós trabalham todos de uma vez com pouca coordenação. Eles não precisam ser identificados, pois as mensagens não são direcionadas a um local específico e precisam ser entregues apenas com base no melhor esforço. Os nós podem sair e se juntar à rede à vontade, aceitando a cadeia de prova de trabalho como prova do que aconteceu enquanto estavam fora. Eles votam com seu poder de CPU, expressando sua aceitação de blocos válidos ao trabalhar para estendê-los e rejeitar blocos inválidos ao se recusarem 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, 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. 
3. S. Haber, W.S. Stornetta, “How to time-stamp a digital document,” In Journal of Cryptology, vol 3, no 2, pages 99-111, 1991. 
4. 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. 
5. 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. 
6. A. Back, “Hashcash – a denial of service counter-measure,” http://www.hashcash.org/papers/hashcash.pdf, 2002. 
7. R.C. Merkle, “Protocols for public key cryptosystems,” In Proc. 1980 Symposium on Security and Privacy, IEEE Computer Society, pages 122-133, April 1980. 
8. W. Feller, “An introduction to probability theory and its applications,” 1957.